آپریٹنگ سسٹمز کا تعارف
ارے حبر! میں آپ کی توجہ میں مضامین کی ایک سیریز - میری رائے میں ایک دلچسپ ادب کے تراجم کی طرف لانا چاہتا ہوں - OSTEP۔ یہ مواد یونکس جیسے آپریٹنگ سسٹم کے کام کے بارے میں کافی گہرائی سے بحث کرتا ہے، یعنی پروسیس، مختلف شیڈولرز، میموری، اور اسی طرح کے دوسرے اجزاء کے ساتھ کام جو جدید OS بناتے ہیں۔ آپ یہاں تمام مواد کی اصل دیکھ سکتے ہیں۔ . براہ کرم نوٹ کریں کہ ترجمہ غیر پیشہ ورانہ طور پر کیا گیا تھا (کافی آزادانہ)، لیکن مجھے امید ہے کہ میں نے عام معنی کو برقرار رکھا ہے۔
اس موضوع پر لیبارٹری کا کام یہاں پایا جا سکتا ہے:
دوسرے حصے:
آپ میرا چینل بھی دیکھ سکتے ہیں۔ =)
شیڈولر کا تعارف
مسئلہ کا جوہر: شیڈولر پالیسی کیسے تیار کی جائے۔
بنیادی شیڈولر پالیسی فریم ورک کو کس طرح ڈیزائن کیا جانا چاہئے؟ کلیدی مفروضے کیا ہونے چاہئیں؟ کیا میٹرکس اہم ہیں؟ ابتدائی کمپیوٹنگ سسٹم میں کون سی بنیادی تکنیکیں استعمال کی جاتی تھیں؟
کام کے بوجھ کے مفروضے۔
ممکنہ پالیسیوں پر بحث کرنے سے پہلے، آئیے پہلے نظام میں چلنے والے عمل کے بارے میں کچھ آسان بنانے والے اختلا فات کو بناتے ہیں، جنہیں اجتماعی طور پر کہا جاتا ہے۔ کام کا بوجھ. کام کے بوجھ کی وضاحت کرنا پالیسیوں کی تعمیر کا ایک اہم حصہ ہے، اور آپ جتنا زیادہ کام کے بوجھ کے بارے میں جانتے ہیں، اتنی ہی بہتر پالیسی آپ لکھ سکتے ہیں۔
آئیے سسٹم میں چلنے والے عمل کے بارے میں درج ذیل مفروضے بناتے ہیں، جسے کبھی کبھی کہا جاتا ہے۔ روزگار کے مواقع (کام) ان میں سے تقریباً تمام مفروضات حقیقت پسندانہ نہیں ہیں بلکہ فکر کی نشوونما کے لیے ضروری ہیں۔
- ہر کام ایک ہی وقت تک چلتا ہے،
- تمام کام ایک ساتھ طے کیے جاتے ہیں،
- تفویض کردہ کام اس کے مکمل ہونے تک کام کرتا ہے،
- تمام کام صرف CPU استعمال کرتے ہیں،
- ہر کام کے چلنے کا وقت معلوم ہوتا ہے۔
شیڈولر میٹرکس
بوجھ کے بارے میں کچھ مفروضوں کے علاوہ، مختلف شیڈولنگ پالیسیوں کا موازنہ کرنے کے لیے ایک اور ٹول کی ضرورت ہے: شیڈولر میٹرکس۔ میٹرک کسی چیز کا صرف ایک پیمانہ ہے۔ متعدد میٹرکس ہیں جن کا استعمال شیڈولرز کا موازنہ کرنے کے لیے کیا جا سکتا ہے۔
مثال کے طور پر، ہم ایک میٹرک استعمال کریں گے جسے کہتے ہیں۔ تبدیلی کا وقت (ٹرنراؤنڈ ٹائم)۔ ٹاسک ٹرنراؤنڈ ٹائم کی تعریف ٹاسک کی تکمیل کے وقت اور سسٹم میں ٹاسک کی آمد کے وقت کے درمیان فرق کے طور پر کی جاتی ہے۔
Tturnaround=Tcompletion−Tarrival
چونکہ ہم نے فرض کیا کہ تمام کام ایک ہی وقت میں پہنچ گئے، پھر Ta=0 اور اس طرح Tt=Tc۔ جب ہم مندرجہ بالا مفروضوں کو تبدیل کریں گے تو یہ قدر قدرتی طور پر بدل جائے گی۔
ایک اور میٹرک - انصاف (انصاف، ایمانداری)۔ پیداواریت اور انصاف پسندی اکثر منصوبہ بندی میں مخالف خصوصیات ہیں۔ مثال کے طور پر، شیڈولر کارکردگی کو بہتر بنا سکتا ہے، لیکن دوسرے کاموں کے چلنے کا انتظار کرنے کی قیمت پر، اس طرح انصاف پسندی کو کم کر دیتا ہے۔
فرسٹ ان فرسٹ آؤٹ (FIFO)
سب سے بنیادی الگورتھم جسے ہم نافذ کر سکتے ہیں اسے FIFO یا کہا جاتا ہے۔ پہلے آو (اندر)، پہلے پیش کیا (باہر). اس الگورتھم کے کئی فائدے ہیں: اس پر عمل درآمد کرنا بہت آسان ہے اور یہ ہمارے تمام مفروضوں پر فٹ بیٹھتا ہے اور کام اچھی طرح کرتا ہے۔
آئیے ایک سادہ سی مثال دیکھتے ہیں۔ ہم کہتے ہیں کہ 3 کام ایک ساتھ سیٹ کیے گئے تھے۔ لیکن آئیے فرض کریں کہ ٹاسک A باقی تمام کاموں سے تھوڑا پہلے پہنچا ہے، اس لیے یہ عمل درآمد کی فہرست میں دوسروں سے پہلے ظاہر ہو گا، بالکل اسی طرح جیسے B کا تعلق C سے ہے۔ فرض کریں کہ ان میں سے ہر ایک کو 10 سیکنڈز کے لیے انجام دیا جائے گا۔ اس صورت میں ان کاموں کو مکمل کرنے کا اوسط وقت کیا ہوگا؟
قدروں کو شمار کرنے سے - 10+20+30 اور 3 سے تقسیم کرنے سے، ہمیں پروگرام پر عمل درآمد کا اوسط وقت 20 سیکنڈ کے برابر ملتا ہے۔
اب آئیے اپنے مفروضوں کو بدلنے کی کوشش کرتے ہیں۔ خاص طور پر، مفروضہ 1 اور اس طرح ہم اب یہ فرض نہیں کریں گے کہ ہر کام کو انجام دینے میں اتنا ہی وقت لگتا ہے۔ فیفو اس بار کیسی کارکردگی دکھائے گا؟
جیسا کہ یہ پتہ چلتا ہے، مختلف کاموں کو انجام دینے کے اوقات FIFO الگورتھم کی پیداواری صلاحیت پر انتہائی منفی اثر ڈالتے ہیں۔ آئیے فرض کریں کہ ٹاسک A کو مکمل ہونے میں 100 سیکنڈ لگیں گے، جبکہ B اور C کو اب بھی 10 سیکنڈ لگیں گے۔
جیسا کہ اعداد و شمار سے دیکھا جا سکتا ہے، نظام کا اوسط وقت (100+110+120)/3=110 ہوگا۔ اس اثر کو کہتے ہیں۔ قافلہ اثر، جب وسائل کے کچھ قلیل مدتی صارفین بھاری صارف کے بعد قطار میں کھڑے ہوں گے۔ یہ گروسری اسٹور پر لائن کی طرح ہے جب آپ کے سامنے ایک پوری ٹوکری کے ساتھ ایک گاہک ہوتا ہے۔ مسئلے کا بہترین حل یہ ہے کہ کیش رجسٹر کو تبدیل کرنے کی کوشش کریں یا آرام کریں اور گہرے سانس لیں۔
سب سے مختصر کام پہلے
کیا کسی طرح ہیوی ویٹ عمل کے ساتھ اسی طرح کی صورتحال کو حل کرنا ممکن ہے؟ یقیناً۔ دوسری قسم کی منصوبہ بندی کہلاتی ہے۔سب سے مختصر کام پہلے (SJF)۔ اس کا الگورتھم بھی کافی قدیم ہے - جیسا کہ نام سے ظاہر ہے، مختصر ترین کام پہلے، ایک کے بعد ایک شروع کیے جائیں گے۔
اس مثال میں، ایک جیسے عمل کو چلانے کا نتیجہ پروگرام کے اوسط ٹرناراؤنڈ ٹائم میں بہتری آئے گا اور یہ اس کے برابر ہوگا۔ 50 کے بجائے 110۔، جو تقریبا 2 گنا بہتر ہے۔
اس طرح، دیے گئے مفروضے کے لیے کہ تمام کام ایک ہی وقت میں پہنچتے ہیں، SJF الگورتھم سب سے بہترین الگورتھم لگتا ہے۔ تاہم، ہمارے مفروضے اب بھی حقیقت پسندانہ نظر نہیں آتے۔ اس بار ہم مفروضہ 2 کو تبدیل کرتے ہیں اور اس بار تصور کریں کہ کام کسی بھی وقت موجود ہو سکتے ہیں، اور تمام ایک ہی وقت میں نہیں۔ اس سے کیا مسائل پیدا ہو سکتے ہیں؟
آئیے تصور کریں کہ ٹاسک A (100c) پہلے آتا ہے اور اس پر عمل درآمد شروع ہوتا ہے۔ t=10 پر، کام B اور C آتے ہیں، جن میں سے ہر ایک میں 10 سیکنڈ لگیں گے۔ تو عمل درآمد کا اوسط وقت ہے (100+(110-10)+(120-10))3 = 103۔ شیڈولر اس کو بہتر بنانے کے لیے کیا کر سکتا ہے؟
تکمیل کے لیے مختصر ترین وقت پہلے (STCF)
صورتحال کو بہتر بنانے کے لیے، ہم مفروضہ 3 کو چھوڑ دیتے ہیں کہ پروگرام شروع ہوا ہے اور مکمل ہونے تک چلتا ہے۔ اس کے علاوہ، ہمیں ہارڈویئر سپورٹ کی ضرورت ہوگی اور جیسا کہ آپ اندازہ لگا سکتے ہیں، ہم استعمال کریں گے۔ ٹائمر چلتے ہوئے کام میں خلل ڈالنا اور سیاق و سباق سوئچنگ. اس طرح، شیڈیولر اس وقت کچھ کر سکتا ہے جب ٹاسک B، C پہنچتے ہیں - ٹاسک A کو انجام دینا بند کر دیں اور B اور C کو پروسیسنگ میں ڈالیں اور ان کی تکمیل کے بعد A پر عمل درآمد جاری رکھیں۔ ایسے شیڈولر کو کہا جاتا ہے۔ ایس ٹی سی ایفیا قبل از وقت ملازمت پہلے.
اس منصوبہ ساز کا نتیجہ درج ذیل ہوگا: ((120-0)+(20-10)+(30-10))/3=50۔ اس طرح، ایسا شیڈولر ہمارے کاموں کے لیے اور بھی زیادہ موزوں ہو جاتا ہے۔
میٹرک رسپانس ٹائم
اس طرح، اگر ہم کاموں کے چلنے کا وقت جانتے ہیں اور یہ کہ یہ کام صرف CPU استعمال کرتے ہیں، STCF بہترین حل ہوگا۔ اور ابتدائی اوقات میں ایک بار، یہ الگورتھم کافی اچھا کام کرتے تھے۔ تاہم، صارف اب اپنا زیادہ تر وقت ٹرمینل پر گزارتا ہے اور ایک نتیجہ خیز انٹرایکٹو تجربے کی توقع رکھتا ہے۔ اس طرح ایک نیا میٹرک پیدا ہوا - جواب وقت (جواب).
جوابی وقت کا حساب اس طرح کیا جاتا ہے:
Tresponse=Tfirstrun−Tarrival
اس طرح، پچھلی مثال کے لیے، جواب کا وقت ہوگا: A=0، B=0، C=10 (abg=3,33)۔
اور یہ پتہ چلتا ہے کہ STCF الگورتھم ایسی صورتحال میں اتنا اچھا نہیں ہے جہاں ایک ہی وقت میں 3 کام آتے ہیں - اسے چھوٹے کاموں کے مکمل ہونے تک انتظار کرنا پڑے گا۔ لہذا الگورتھم ٹرناراؤنڈ ٹائم میٹرک کے لیے اچھا ہے، لیکن انٹرایکٹیویٹی میٹرک کے لیے برا ہے۔ تصور کریں کہ کیا آپ کسی ٹرمینل پر بیٹھے ہوئے ہیں کہ ایک ایڈیٹر میں کریکٹر ٹائپ کرنے کی کوشش کر رہے ہوں اور 10 سیکنڈ سے زیادہ انتظار کرنا پڑے کیونکہ کوئی اور کام CPU کو لے رہا تھا۔ یہ بہت خوشگوار نہیں ہے۔
تو ہمیں ایک اور مسئلہ کا سامنا ہے - ہم ایک ایسا شیڈولر کیسے بنا سکتے ہیں جو ردعمل کے وقت کے لیے حساس ہو؟
راؤنڈ رابن
اس مسئلے کو حل کرنے کے لیے الگورتھم تیار کیا گیا۔ راؤنڈ رابن (آر آر)۔ بنیادی خیال بہت آسان ہے: کاموں کو مکمل ہونے تک چلانے کے بجائے، ہم کام کو ایک خاص مدت تک چلائیں گے (جسے ٹائم سلائس کہا جاتا ہے) اور پھر قطار سے دوسرے کام پر جائیں گے۔ الگورتھم اپنے کام کو دہراتا ہے جب تک کہ تمام کام مکمل نہ ہو جائیں۔ اس صورت میں، پروگرام کا چلنے کا وقت اس وقت کا ایک کثیر ہونا چاہیے جس کے بعد ٹائمر عمل میں خلل ڈالے گا۔ مثال کے طور پر، اگر ٹائمر کسی عمل میں ہر x=10ms میں خلل ڈالتا ہے، تو پروسیس ایگزیکیوشن ونڈو کا سائز 10 کا کثیر ہونا چاہیے اور 10,20 یا x*10 ہونا چاہیے۔
آئیے ایک مثال دیکھیں: ABC کام بیک وقت سسٹم میں آتے ہیں اور ان میں سے ہر ایک 5 سیکنڈ تک چلنا چاہتا ہے۔ SJF الگورتھم ہر کام کو دوسرا شروع کرنے سے پہلے مکمل کرے گا۔ اس کے برعکس، لانچ ونڈو = 1s کے ساتھ RR الگورتھم مندرجہ ذیل کاموں سے گزرے گا (تصویر 4.3):
(ایس جے ایف دوبارہ (ریسپانس ٹائم کے لیے برا)
(راؤنڈ رابن (رسپانس ٹائم کے لیے اچھا)
RR الگورتھم کے لیے اوسط جوابی وقت (0+1+2)/3=1 ہے، جبکہ SJF (0+5+10)/3=5 ہے۔
یہ سمجھنا منطقی ہے کہ ٹائم ونڈو RR کے لیے ایک بہت اہم پیرامیٹر ہے؛ یہ جتنا چھوٹا ہوگا، رسپانس ٹائم اتنا ہی زیادہ ہوگا۔ تاہم، آپ کو اسے بہت چھوٹا نہیں بنانا چاہیے، کیونکہ سیاق و سباق کو تبدیل کرنے کا وقت بھی مجموعی کارکردگی میں ایک کردار ادا کرے گا۔ اس طرح، ایگزیکیوشن ونڈو ٹائم کا انتخاب OS آرکیٹیکٹ کے ذریعہ طے کیا جاتا ہے اور اس کا انحصار ان کاموں پر ہوتا ہے جن کو اس میں انجام دینے کا منصوبہ ہے۔ سیاق و سباق کو تبدیل کرنا واحد سروس آپریشن نہیں ہے جو وقت ضائع کرتا ہے - چلانے والا پروگرام بہت سی دوسری چیزوں پر کام کرتا ہے، مثال کے طور پر، مختلف کیشز، اور ہر سوئچ کے ساتھ اس ماحول کو بچانے اور بحال کرنے کے لیے ضروری ہے، جس میں بہت زیادہ وقت لگ سکتا ہے۔ وقت
اگر ہم صرف رسپانس ٹائم میٹرک کے بارے میں بات کر رہے ہوں تو RR ایک بہترین شیڈولر ہے۔ لیکن اس الگورتھم کے ساتھ ٹاسک ٹرناراؤنڈ ٹائم میٹرک کیسے برتاؤ کرے گا؟ اوپر دی گئی مثال پر غور کریں، جب A, B, C = 5s کا آپریٹنگ ٹائم اور ایک ہی وقت پر پہنچتا ہے۔ ٹاسک A 13 پر، B کو 14 پر، C کو 15 پر ختم ہو گا اور اوسط ٹرناراؤنڈ ٹائم 14 سیکنڈ ہوگا۔ اس طرح، RR ٹرن اوور میٹرک کے لیے بدترین الگورتھم ہے۔
مزید عام اصطلاحات میں، کوئی بھی RR-قسم کا الگورتھم منصفانہ ہے؛ یہ CPU وقت کو تمام عملوں کے درمیان یکساں طور پر تقسیم کرتا ہے۔ اور اس طرح، یہ میٹرکس مسلسل ایک دوسرے سے متصادم رہتے ہیں۔
اس طرح، ہمارے پاس متعدد متضاد الگورتھم ہیں اور ایک ہی وقت میں ابھی بھی کئی مفروضے باقی ہیں - کہ کام کا وقت معلوم ہے اور یہ کہ کام صرف CPU استعمال کرتا ہے۔
I/O کے ساتھ اختلاط
سب سے پہلے، آئیے مفروضہ 4 کو ہٹا دیں کہ عمل صرف CPU استعمال کرتا ہے؛ قدرتی طور پر، ایسا نہیں ہے اور عمل دوسرے آلات تک رسائی حاصل کر سکتے ہیں۔
جس لمحے کوئی بھی عمل I/O آپریشن کی درخواست کرتا ہے، عمل بلاک شدہ حالت میں داخل ہوتا ہے، I/O مکمل ہونے کا انتظار کرتا ہے۔ اگر I/O ہارڈ ڈرائیو پر بھیجا جاتا ہے، تو اس طرح کے آپریشن میں کئی ms یا اس سے زیادہ وقت لگ سکتا ہے، اور پروسیسر اس وقت بیکار رہے گا۔ اس وقت کے دوران، شیڈیولر کسی دوسرے عمل کے ساتھ پروسیسر پر قبضہ کر سکتا ہے۔ اگلا فیصلہ شیڈیولر کو کرنا ہوگا جب یہ عمل اپنا I/O مکمل کرے گا۔ جب ایسا ہوتا ہے تو، ایک رکاوٹ آئے گی اور OS اس عمل کو تیار کر دے گا جسے I/O کہتے ہیں۔
آئیے کئی مسائل کی ایک مثال دیکھیں۔ ان میں سے ہر ایک کو 50ms CPU وقت درکار ہے۔ تاہم، پہلا I/O ہر 10ms تک رسائی حاصل کرے گا (جسے ہر 10ms پر عمل درآمد بھی کیا جائے گا)۔ اور پروسیس بی صرف I/O کے بغیر 50ms پروسیسر استعمال کرتا ہے۔
اس مثال میں ہم STCF شیڈولر استعمال کریں گے۔ شیڈولر کیسا برتاؤ کرے گا اگر اس پر A جیسا عمل شروع کیا جائے؟ وہ مندرجہ ذیل کام کرے گا: پہلے وہ عمل A کو مکمل طور پر کام کرے گا، اور پھر B پر کارروائی کرے گا۔
اس مسئلے کو حل کرنے کا روایتی طریقہ یہ ہے کہ عمل A کے ہر 10 ms ذیلی ٹاسک کو ایک الگ کام کے طور پر سمجھا جائے۔ اس طرح، STJF الگورتھم کے ساتھ شروع کرتے وقت، 50 ms ٹاسک اور 10 ms ٹاسک کے درمیان انتخاب واضح ہے۔ پھر، سب ٹاسک A مکمل ہونے پر، B اور I/O کا عمل شروع کیا جائے گا۔ I/O مکمل ہونے کے بعد، B پروسیسنگ کے بجائے 10ms پراسیس A کو دوبارہ شروع کرنے کا رواج ہوگا۔ اس طرح، اوورلیپ کو لاگو کرنا ممکن ہے، جہاں CPU کسی اور عمل کے ذریعے استعمال ہوتا ہے جبکہ پہلا کا انتظار ہوتا ہے۔ I/O اور اس کے نتیجے میں، سسٹم کا بہتر استعمال کیا جاتا ہے - اس وقت جب انٹرایکٹو عمل I/O کا انتظار کر رہے ہوتے ہیں، پروسیسر پر دیگر عمل کو انجام دیا جا سکتا ہے۔
اوریکل اب نہیں ہے۔
اب آئیے اس مفروضے سے جان چھڑانے کی کوشش کرتے ہیں کہ کام کے چلنے کا وقت معلوم ہے۔ یہ عام طور پر پوری فہرست میں بدترین اور غیر حقیقی مفروضہ ہے۔ درحقیقت، اوسط عام OS میں، OS خود عام طور پر کاموں کے عمل درآمد کے وقت کے بارے میں بہت کم جانتا ہے، تو پھر آپ یہ جانے بغیر ایک شیڈیولر کیسے بنا سکتے ہیں کہ کام کو انجام دینے میں کتنا وقت لگے گا؟ شاید ہم اس مسئلے کو حل کرنے کے لیے کچھ RR اصول استعمال کر سکتے ہیں؟
کل
ہم نے ٹاسک شیڈولنگ کے بنیادی خیالات کو دیکھا اور شیڈولرز کے 2 خاندانوں کو دیکھا۔ پہلا پہلا مختصر ترین کام شروع کرتا ہے اور اس طرح ٹرناراؤنڈ ٹائم میں اضافہ ہوتا ہے، جبکہ دوسرا تمام کاموں کے درمیان یکساں طور پر پھٹا جاتا ہے، جس سے رسپانس ٹائم بڑھتا ہے۔ دونوں الگورتھم خراب ہیں جہاں دوسرے خاندان کے الگورتھم اچھے ہیں۔ ہم نے یہ بھی دیکھا کہ کس طرح CPU اور I/O کا متوازی استعمال کارکردگی کو بہتر بنا سکتا ہے، لیکن OS کی دعویداری کے ساتھ مسئلہ حل نہیں ہوا۔ اور اگلے سبق میں ہم ایک منصوبہ ساز کو دیکھیں گے جو ماضی قریب میں دیکھتا ہے اور مستقبل کی پیشین گوئی کرنے کی کوشش کرتا ہے۔ اور اسے ملٹی لیول فیڈ بیک قطار کہا جاتا ہے۔
ماخذ: www.habr.com