هماهنگ سازی task و thread ها و Ada

اجرای یک برنامه تحت Ada دربرگیرنده اجرای یک یا چند task می باشد.هر task ، یک یا چند thread جداگانه برای کنترل مستقل یا همزمان در نقاطی که با سایر task ها تداخل دارد ایجاد می کند. شکل های مختلف این هماهنگ سازی و اثر متقابل بین task ها در این چند برگ توضیح داده می شود. این شکل ها به دسته بندی کلی زیر تقسیم می شوند :
1- فعال سازی و نابود سازی یک task
2- صدا زدن یک برنامه خاص که هماهنگ سازی را بر عهده بگیرد وداده ها و بخش های اشتراکی را مدیریت کند.
3- یک برنامه وقفه ای که شامل یک سری delay ها باشد. یا شامل یک سری برنامه های زمان بندی که به هر کدام از task زمان خاصی را بدهد.
4- یک سیستم خاتمه دهنده که به یک task اجهزه خاصی برای از بین بردن و از کار انداختن task دیگر می دهد.


زمان دهی پویا و زمان دهی ایستا static semantic , dynamic semantic :
در طول یک دوره یک task غیر فعال می تا زمانی که به فعالیت بازگردد. زمانی که یک task آماده شروع فعالیت گردید باید بخش ها و داده های مورد نیاز کامپیوتر به آن اختصاص داده شود. هر چند که این اجرا ممکن است روی یک سیستمmulti proccessorاجرا شود اما باز هم در چنین سیستم هایی اوقاتی پیش می آید که از دید task سیستم single proccess است و یا حتی روی هر یک از proccessor ها چندین task شروع به فعالیت می کنند. در این حالت به طور کلی دو نوع الگوریتم شروع به تقسیم بندی منابع سخت افزاری می نمایند که به نام های زمان دهی پویا و زمان دهی ایستا معروف هستند. هر چند هرکدام از این دو الگوریتم خود به الگوریتم های فراوان هماهنگ سازی دیگر تقسیم می شوند.
سیستم زمان دهی ایستا به این شکل عمل می کند که قبل از شروع به فعالیت task مشخصات آن را خوانده و به آن زمان می دهد. در صورتی که task ای از قبل نداند که چه مقدار زمان برای اجرا نیاز دارد این سیستم جوابگو نخواهد بود.
اما سیستم زمان دهی پویا که بسیار سنگین تر و پیچیده تر می باشد در هر لحظه اجرای task ها از آن ها توسط massage گزارش تهیه می کند و از این که یک task خاص چه مقدار زمان برای ادامه کار خود لازم دارد مطلع می شود و توسط زیر الگوریتم های مربوط به خود shairing را انجام می دهد. اما هر task چه قسمت هایی دارد؟ ما برای دانستن عمل هماهنگ سازی باید با قسمت های مختلف یک task آشنا شویم


همزمانی و مناطق بحرانی
موثر واقع شدن یک هسته مرکزی بازدخولی نیاز به استفاده از همزمانی دارد: اگر یک مسیرکنترل هسته مرکزی در حالیکه روی یک ساختمان داده هسته مرکزی فعالیت می کند، متوقف شود، هیچ مسیرکنترل هسته مرکزی دیگری اجازه نخواهد داشت تا بر روی همان ساختمان داده فعالیت کند مگر آنکه به یک وضعیت ثابت و پایدار بازگردد. بعلاوه برخورد دومسیرکنترل می تواند منجر به تخریب اطلاعات ذخیره شده بشود. بعنوان مثال، چنین تصور کنیم که یک V متغیرجهانی شامل تعدادی از موارد (items) قابل استفاده بعضی اجزا سیستم است. اولین مسیرکنترل هسته مرکزی (A) متغیر را میخواند و تعیین می کند که فقط یک مورد ( آیتم) قابل استفاده وجود دارد. در این نقطه، مسیرکنترل هسته مرکزی دیگر (B) فعال شده و همان متغیر را می خواند که هنوز دارای ارزش 1 می باشد. بنابراین V , B را کاهش داده و شرع به استفاده از آیتم می کند. سپس A فعالیت رادوباره آغاز می کند زیرا تقریبا ارزش V محتوی 1ـ می شود و دو راه کنترل هسته مرکزی از یک آیتم با اثرات تخریبی پتانسیلی استفاده می کنند؛ می گوئیم که "شرایط مسابقه" موجود است.
بطورکلی، دسترسی امن به متغیر سراسری با استفاده از "عملیات اتمیک" فراهم میشود. در مثال قبل، اگر دومسیرکنترل متغیر را بخوانند و V را با یک عمل بدون تداخل و تنها کاهش دهند، تخریب داده، امکان پذیر نخواهد بود. با اینحال هسته های مرکزی شامل ساختمان داده های بسیاری هستند که نمی توانند با یک عمل تنها قابل دسترسی باشند. برای مثال، معمولا جابجائی عنصر کلید از یک لیست پیوندی تنها با یک عمل ممکن نیست، زیرا هسته مرکزی حداقل به دو نقطه دسترسی در آن واحد نیاز دارد. هربخشی از کد که باید توسط پردازش به پایان برسد، قبل از اینکه یک پردازش دیگر بتواند وارد شود ناحیه بحرانی است. این مشکلات نه تنها در میان مسیرهای کنترل هسته مرکزی بلکه در میان پردازشهائی که از داده های مشترکی استفاده می کنند نیز رخ میدهد. تکنیکهای هم زمانی متعددی شکل گرفته اند. بخش بعدی به بررسی چگونگی هم زمان کردن و راههای کنترل هسته مرکزی می پردازد.

هسته های مرکزی انحصاری
در جستجوی راه حل ساده ای برای حل مشکلات هم زمانی، اکثر هسته های مرکزی یونیکس های ابتدائی انحصاری هستند : وقتی پردازشی در وضعیت هسته مرکزی اجرا می شود، نمی تواند بطور اختیاری متوقف شده و یا با پردازش دیگری جایگزین شود . بنابراین در یک سیستم تک پردازشی تمام ساختمان داده های هسته مرکزی که توسط پاسخگوی وقفه (interrupts) و استثناءها(exception update) به روز نشده اند برای دسترسی به هسته مرکزی امن و مطمئن هستند. در واقع، یک پردازش در وضعیت هسته مرکزی می تواند بصورت اختیاری از CPU صرف نظر کند، اما در این مورد باید اطمنیان حاصل کند که تمامی ساختمان داده های قابل دسترسی قبلی را که می توانسته اند تغییر کنند را باید دوباره چک کند. انحصاری بودن در سیستمهای چند پردازنده ای بی تاثیر است زیرا دو مسیرکنترل هسته مرکزی که در CPU های متفاوت در حال اجرا هستند می توانند با هم به ساختمان داده یکسانی دسترسی پیدا کنند.

غیر فعال کردن وقفه ها
مکانیسم دیگر همزمانی در سیستمهای تک پردازشی عبارتست از غیرفعال کردن تمامی وقفه های سخت افزاری قبل از ورود به منطقه بحرانی و فعال کردن مجدد انها دقیقا بعد از ترک منطقه بحرانی . این مکانیسم با وجود سادگی از نقطه اپتیمال بسیار دور است. اگر منطقه بحران وسیع باشد، وقفه ها برای زمان نسبتا طولانی غیرفعال باقی می مانند و تمامی فعالیتهای سخت افزار را منجر به فریز می کنند. علاوه براین، در یک سیستم چند پردازنده ای این مکانیسم کارگر نیست . هیچ راهی برای اطیمنان از عدم دسترسی CPU دیگری، به ساختمان داده های مشابهی که در منطقه حفاظت شده بحرانی update شده اند، وجود ندارد.

فشرده سازی اطلاعات (DATA COMPRESSION )

در این روش ذخیره اطلاعات به شکلی است که فضای کمتری را اشغال کند. این عملکرد در ارتباطات بسیار مهم است ، چرا که این امکان را به تجهیزات می دهد تا همان مقدار اطلاعات را با bit کمتری ذخیره یا منتقل کنند. تکنیک های مختلفی برای انجام اینکار وجود دارد اما تنها چند مورد از آنها استاندارد هستند. CCITT یک تکنیک فشرده سازی اطلاعات برای انتقال فاکس ها استاندارد( Group 3 ) و یک استاندارد فشرده سازی برای تبادل اطلاعات از طریق مودم ها ( CCITT V.42 bis) تعریف نموده است. علاوه براین ، انواع فشرده سازی فایل از قبیل ARC و ZIP نیز وجود دارد. فشرده سازی اطلاعات بطور گسترده ای در برنامه های ایجاد نسخة پشتیبان ، برنامه های صفحه گسترده و سیستم های مدیریت بانک اطلاعاتی نیز استفاده می شود. انواع مختلفی از اطلاعات نظیر تصاویر bit-map را می توان به سایزهای کوچکتر فشرده کرد

Protocol
شکل پذیرفته شده ای برای تبادل ارتباطات میان دو دستگاه است. پروتکل موارد زیر را تعریف می کند :
• روش مورد استفاده برای کنترل خطا
• شیوه فشرده سازی اطلاعات ، درصورت وجود
• شیوة اعلام و نمایش ارسال پیام توسط دستگاه فرستنده
• شیوة اعلام و نمایش دریافت پیام توسط دستگاه گیرنده
برنامه نویسان می توانند انواع مختلفی از پروتکل های استاندارد را انتخاب کنند. هریک از آنها دارای مزایا و معایب مخصوص به خود است ؛ مثلاً برخی از آنها ساده تر ، برخی قابل اطمینان تر و برخی سریعتر هستند. از نقطه نظر کاربر ، تنها جنبه جالب پروتکل ها ، قابلیت برقراری ارتباط کامپیوترشان با سایر کامپیوترها است. پروتکل را می توان در سخت افزار یا نرم افزار بکار برد.
CCITT
خلاصه نام موسسه Comite Consultatif International Telephonique et Telegraphique می باشد که استانداردهای ارتباطی بین المللی را تنظیم می کند. CCITT اکنون بعنوان ITU شناخته شده و استانداردهای مهمی را برای تبادل اطلاعات تعریف کرده است :
• Group 3 : پروتکل جهانی برای ارسال اسناد فاکس از طریق خطوط تلفن است. پروتـــــــکل Group 3 CCITT T.4 را برای فشرده سازی اطلاعات و حداکثر میزان انتقال ( baud9600 ) را مشخص کرده است. دو درجه وضوح تصویر وجود دارد: 203 x 98 و 203 x 196
• Group 4: پروتکلی برای ارسال اسناد فاکس از طریق شبکه های ISDN است. این گروه 400 پروتکل را پشتیبانی می کند که شامل تصاویر با وضوح بیش از dpi 400 می شوند
STAND-ALONE
به دستگاههایی اطلاق می شود که به تنهایی کارکرده و نیاز به تجهیزات دیگر ندارند. مثلاً دستگاه فاکس از این دسته است ؛ چرا که برای کارکردن نیاز ، به کامپیوتر ، چاپگر ، مودم یا سایر تجهیزات ندارد. به همین دلیل نیز چاپگرها STAND-ALONE محسوب نمی شوند چراکه برای فعالیت و تغذیه اطلاعات نیاز به کامپیوتر دارند.
تا آخر سال 2000، یعنی درست 4 سال پس از عرضه دی.وی.دی، مصرف‌کنندگان، 14 میلیون دستگاه پخش خریده و آن را به پرفروش‌ترین دستگاه الکترونیکی خانگی تبدیل کرده بودند.
امروزه با پیشرفت روزافزون فناوری در دستگاه‌های الکترونیکی خانگی بخصوص دی.وی.دی، این دستگاه مجهزتر می‌شود و روزبه‌روز کاربرد آن رو به افزایش است. مدیر مرکز تحقیقات و توسعه شرکت صنایع نماالکترونیک پیام با اشاره به مطلب فوق افزود: هم‌اکنون دی.وی.دی‌های موجود در بازار دارای امکانات متداول هستند.
در حال حاضر این شرکت سعی نموده است. دی.وی.دی‌ را بامشخصات بهتر و امکانات بیشتر در اختیار مصرف‌کنندگان قرار دهد. این دی.وی‌.دی در دو مدل DV-3500 و DV-3131 می‌باشد که فقط از لحاظ ظاهر متفاوت و از لحاظ عملکرد شبیه به هم هستند. این دستگاه مجهز به خروجی VGA برای اتصال به مانیتور برای دریافت تصاویر بهتر است و مجهز به مدار Progresive Scan که روش مدرنی است برای بدست آوردن تصویر مطلوب و با کیفیت، بدین معنا که برخلاف Interlace Scan که اسکن معمولی تصویر است این مدار بصورت اسکن متوالی تصویر برای وضوح بیشتر بکار می‌رود.
همچنین این دستگاه مجهز به قفل ایمنی دیسک‌های درجه‌بندی شده‌است. همچنین قابلیت کارائوکه(حذف صدای خواننده از روی موسیقی) و ورودی میکروفن و قابلیت پخش دیسک‌های عکس و اسلاید با فرمت‌های CD/JPEG,Kodak Picture را دارد.
از ویژگی‌های دیگر این دستگاه می‌توان به حافظه روی دیسک Marking یا علامت‌گذاری دی.وی.دی و تبدیل سیستم NTSC به پال برای تلویزیون‌هایی که قابلیت پخش سیستم NTSC را ندارد، اشاره نمود.
همچنین این دی.وی.دی دارای استانداردهای ایمنی و کیفیت از قبیل Class 1 (‌اشعه لیزر مورد استفاده در این دستگاه نوع ضعیف شده است و در نتیجه خطر تشعشع به بیرون دستگاه وجود ندارد) و دارای نشان CEاست،که نشان‌دهنده انطباق این دستگاه با استانداردهای کشورهای اروپایی می‌باشد.
با تنظیم اکولایزر این دستگاه صدای موسیقی Rock-pop-live-Dance-Techno-Classic-Soft را می‌توان انتخاب کرد و هنگام اجرای دیسک‌ها حالت مربوط به پخش صدای محیطی را انتخاب نمود.
درپایان برای آشنایی بیشتر خوانندگان با دستگاه دی.وی.دی توضیحی مختصر آمده است:
DVDکه نام کوتاه و متداول دیسک ویدئویی دیجیتال Digital Video Disc و یا دیسک چندمنظوره دیجیتال Digital Versatile Disc می‌باشد نسل جدید تکنولوژی ذخیره اطلاعات بر روی دیسک نوری بوده و این تکنولوژی قابلیت ذخیره یک فیلم سینمایی بر روی دیسک با کیفیت بالا و صدای عالی و یا ذخیره حجم اطلاعات کامپیوتری بیشتر از CD معمولی را دارد.

ایده آل های خطی به ترتیب کوهن-مکوالی

چکیده- G را یک نمودار غیرمستقیم ساده n راسی در نظر بگیرید و بگذارید برایده آل خطی مرتبطش دلالت کند. مانشان می دهیم که تمام نمودارهای و تری G ، به ترتیب کوهن- مکوالی هستند ، دلیل ما بر پایه نشان دادن این است که دوگانه الکساندر I(G) ،خطی و ازمولفه است.
نتیجه ما فرضیه فریدی را که می گوید ایده آل درخت ساده شده به ترتیب کوهن- مکوالی، هرزوگ، هیبی، می باشد، وفرضیه ژنگ که می گوید یک نمودار وتری کوهن-مکوالی است اگر و تنها اگر ایده آل خطی اش در هم ریخته نباشد، را تکمیل می کند. ما همچنین ویژگی های دایره های مرتب کوهن- مکوالی را بیان می کنیم و نمونه‌هایی از گراف های مرتب غیروتری کوهن- مکوالی را هم ارائه می کنیم.

1-مقدمه
G را یک گراف ساده n راسی در نظر بگیرید پس G هیچ حلقه یا خطوط چندگانه ای پهن دو راس ندارد.) رئوس ومجموعه های خطی G توسط EG,VG را به ترتیب نشان دهید. ما ایده آل تک جمله ای غیر مربع چهارگانه با K که یک میزان است و جایی که را به G ارتباط می دهیم.ایده ال ایده آل خطی Gنامیده می شود.
توجه اولیه این مقاله ایده آل های خطی گراف های وتری است. یک گراف G وتری است اگر هر دایره طول یک وتر داشته باشد. اینجا اگر ،خطوط یک دایره طول n باشند، ما می گوییم که دایره وری یک وتر دارد اگر دو راس xj,xi در دایره به نحوی وجود داشته باشند که یک خط برای G باشند اما خطی در دایره نباشد.
ما می گوییم که یگ گراف G کوهن –مکوالی است اگر کوهن-مکوالی باشد. چنانکه هرزوگ، هیبی و ژنگ اشاره می کنند، طبقه بندی تمام گراف های کوهن-مکوالی شاید اکنون قابل کشیدن نباشند، این مسئله به سختی طبقه بندی کردن تمام مجموعه های ساده شده کوهن-مکوالی است.]9[.البته هرزوگ، هیبی و ژنگ در ]9[ ثابت کردند که وقتی G یک گراف وتری باشد،پس G در هر میدانی کوهن-مکوالی است اگر وفقط اگر به هم نریخته باشد.
ویژگی کوهن –مکوالی به ترتیب بودن، که شرایطی است ضعیف تر از کوهن-مکوالی بودن، توسط استنلی ]14[ در ارتباط با تئوری قابلیت جدا شدن غیرخالص معرفی شد.
تعریف 1-1- را در نظر بگیرید. یک M معیار B درجه دار کوهن –مکوالی به ترتیب نامیده می شود اگر یک تصفیه معین از معیارهای R درجه بندی وجود داشته باشد.


به نحوی که کوهن –مکوالی باشد، و ابعاد کرول خارج قسمت در حال افزایش باشند:


ما میگوییم یک گراف G کوهن-مکوالی به ترتیب است و در K اگر کوهن-مکوالی به ترتیب باشد. ما می توانیم به نتیجه هرزوگ، هیبی و ژنگ بر سیم البته با استفاده از این تضعیف شرایط کوهن-مکوالی. نتیجه اصلی ما فرضیه زیر است (که مستقل از خاصیت (K) است.
فرضیه 2-1 فرضیه 2-3.تمام گراف های وتری کوهن-مکوالی به ترتیب هستند.
بنابراین حتی گراف های وتری که ایده آل های خطی نشان در هم نریخته نیستند نیز هنوز یک ویژگی جبری را دارا هستند.فرضیه 2-3 همچنین حالت یک بعدی کار فردی در توده های ساده شده ]3[ را نیز عمومیت می بخشد.
مقاله ما به صورت زیر سازمان می یابد. در قسمت بعدی ، ما نتایجی از این ادبیات درباره دوگانگی الکساندر ودرباره گراف های وتری جمع می کنیم. در بخش 3،فرضیه 2.3 را ثابت می کنیم.
ما برخی از گراف های غیروتری در قسمت 4 را که دایره های کوهن-مکوالی را به ترتیب طبقه بندی می کنند بررسی می کنیم و در مورد برخی ازویژگی های گراف‌های شامل دایره های –n برای n>3 تحقیق می کنیم.
همچنین شرایط کافی را برای گرافی که نمی تواند کوهن-مکوالی به ترتیب باشد ،ارائه می کنیم.
2-اجزا مورد نیاز
درطول این مقاله، G بر یک گراف ساده روی رئوس n با مجموعه نقطه ای VG ومجموعه خطی EG دلالت می کند. ایده آل خطی ،جایی که را به G مربوط می سازیم.
گراف کامل در رئوس n که بر Kn دلالت شده است،گرافی است با مجموعه خطی ، یعنی گراف این ویژگی را دارد که خطی بین هر جفت رئوس وجود دارد. اگر x نقطه ای در G باشد باید بنویسیم N(x) که بر همسایه‌های x دلالت کند،یعنی آن رئوسی که خطی را با x شریکند. ما ابتدا باید به حالتی توجه کنیم که G یک گرافی وتری است.گراف های وتری ویژگی زیر را دارند:
لم 21- G,[6,7,12,15] را یک گراف وتری در نظر بگیرید، x را یک زیر نمودار کامل از G در نظر بگیرید.اگر ،پس نقطه ای به نام وجود داردکه زیرگراف به وجود آمده توسط مجموعه همسایه مربوط به x، یک گراف کامل باشد. این امر همچنین زیر نمودار به وجود آمده در را وادار می کند که یک زیر گراف کامل باشد.
یک پوشش راس گراف G یک زیر مجموعه از VG است به نحوی که هر خط G حداقل به یک راس A برخوردار داشته باشد. توجه کنیدکه ما هیچ وقت به داشتن یک راس مجزا در پوشش راس نیاز نداریم.
مثلا ، اگر ما گرافی در سه راس داشته باشیم و تنها خط موجود باشد، پس هر دو پوشش های راس هستند. پوشش های راس یک گراف G به دو گانه الکساندر مربوطند.
تعریف 2-2- I را یک ایده آل تک جمله ای غیرمربع در نظر بگیرید. دوگانه الکساندر غیرمربع ایده آل
است.

پس نتیجه ساده ای گرفته می شود:
لم 3-2- G را یک گراف ساده با ایده آل خطی در نظر بگیرید.پس

یک پوشش راس برای G است.

یک تجزیه درجه بندی شده آزاد حداقل به هر ایده آل همگون I از R مرتبط است.

که در آن R(j) بر معیار R به دست آمده از تغییر درجات R توسط j دلالت می کند.