Үйлдлийн системийн танилцуулга
Хөөе Хабр! Миний бодлоор OSTEP хэмээх нэгэн сонирхолтой уран зохиолын цуврал нийтлэл-орчуулгыг та бүхэнд хүргэхийг хүсч байна. Энэхүү материал нь орчин үеийн үйлдлийн системийг бүрдүүлдэг процесс, төрөл бүрийн хуваарь, санах ой болон бусад ижил төстэй бүрэлдэхүүн хэсгүүдтэй ажиллах unix-тэй төстэй үйлдлийн системүүдийн ажлыг нэлээд гүнзгий авч үздэг. Та бүх материалын эх хувийг эндээс харж болно . Орчуулга нь мэргэжлийн бус (нэлээн чөлөөтэй) хийгдсэн гэдгийг анхаарна уу, гэхдээ би ерөнхий утгыг хадгалсан гэдэгт найдаж байна.
Энэ сэдвээр хийсэн лабораторийн ажлыг эндээс харж болно.
Бусад хэсгүүд:
Та мөн миний сувгийг эндээс үзэж болно =)
Хуваарьлагчийн танилцуулга
Асуудлын мөн чанар: Төлөвлөгчийн бодлогыг хэрхэн боловсруулах вэ
Төлөвлөгчийн үндсэн бодлогын хүрээг хэрхэн төлөвлөх ёстой вэ? Гол таамаглал нь юу байх ёстой вэ? Ямар хэмжүүр чухал вэ? Тооцооллын эхэн үеийн системд ямар үндсэн техникийг ашигласан бэ?
Ажлын ачааллын таамаглал
Боломжит бодлогуудын талаар ярихаасаа өмнө эхлээд системд ажиллаж байгаа процессуудын талаар хэд хэдэн хялбаршуулсан тайлбар хийцгээе. ажлын ачаалал. Ажлын ачааллыг тодорхойлох нь бодлого барих чухал хэсэг бөгөөд ажлын ачааллын талаар хэдий чинээ ихийг мэдэх тусам бодлого бичих боломжтой болно.
Системд ажиллаж байгаа процессуудын талаар дараах таамаглалыг хийцгээе, заримдаа бас нэрлэдэг ажлын байр (даалгаварууд). Эдгээр бараг бүх таамаглал нь бодитой биш боловч сэтгэлгээг хөгжүүлэхэд зайлшгүй шаардлагатай.
- Даалгавар бүр ижил хугацаанд ажиллана,
- Бүх даалгавруудыг нэгэн зэрэг тавьдаг,
- Томилогдсон ажил дуусах хүртэл ажиллана,
- Бүх ажил зөвхөн CPU ашигладаг,
- Даалгавар бүрийн ажиллах хугацаа тодорхой байна.
Хуваарьлагч хэмжигдэхүүн
Ачааллын талаарх зарим таамаглалаас гадна өөр өөр хуваарийн бодлогуудыг харьцуулах өөр хэрэгсэл хэрэгтэй: хуваарьлагч хэмжигдэхүүн. Хэмжилт гэдэг нь ямар нэг зүйлийн хэмжүүр юм. Хуваарилагчдыг харьцуулах хэд хэдэн хэмжүүр байдаг.
Жишээлбэл, бид хэмжигдэхүүнийг ашиглах болно өөрчлөгдөх цаг (өөрчлөгдөх цаг). Даалгаврын гүйцэтгэлийн хугацаа нь даалгаврын гүйцэтгэлийн хугацаа болон системд ирэх цагийн зөрүүгээр тодорхойлогддог.
Tturnaround=Tcompletion−Tarival
Бид бүх даалгавар нэгэн зэрэг ирсэн гэж үзсэн тул Ta=0, улмаар Tt=Tc. Дээрх таамаглалыг өөрчлөх үед энэ утга аяндаа өөрчлөгдөх болно.
Өөр нэг хэмжүүр - шударга байдал (шударга байдал, үнэнч шударга байдал). Бүтээмж ба шударга байдал нь төлөвлөлтийн эсрэг шинж чанарууд юм. Жишээлбэл, хуваарь гаргагч нь гүйцэтгэлийг оновчтой болгох боловч бусад ажлуудыг гүйцэтгэхийг хүлээх зардлаар шударга байдлыг бууруулдаг.
ЭХЛЭЭД ЭХЛЭЭД (FIFO)
Бидний хэрэгжүүлж болох хамгийн энгийн алгоритмыг FIFO эсвэл гэж нэрлэдэг түрүүлж ирсэн (орох), түрүүлж үйлчилсэн (гадагшаа). Энэ алгоритм нь хэд хэдэн давуу талтай: хэрэгжүүлэхэд маш хялбар бөгөөд бидний бүх таамаглалд нийцэж, ажлыг маш сайн гүйцэтгэдэг.
Энгийн жишээг харцгаая. 3 даалгавар нэгэн зэрэг тавигдсан гэж бодъё. Гэхдээ А даалгаврыг бусдаас арай эрт ирсэн гэж бодъё, тиймээс энэ нь гүйцэтгэлийн жагсаалтад С-тэй харьцуулахад Б-тэй адил бусдаас эрт гарч ирнэ. Тэдгээрийг тус бүр 10 секундын турш гүйцэтгэнэ гэж бодъё. Энэ тохиолдолд эдгээр ажлыг гүйцэтгэх дундаж хугацаа хэд байх вэ?
10+20+30 утгыг тоолж, 3-т хуваахад бид програмын гүйцэтгэлийн дундаж хугацаа 20 секунд болно.
Одоо бид таамаглалаа өөрчлөхийг хичээцгээе. Ялангуяа, 1-р таамаглал тул бид ажил бүрийг гүйцэтгэхэд ижил хэмжээний цаг зарцуулдаг гэж үзэхээ болино. FIFO энэ удаад хэрхэн ажиллах бол?
Даалгаврын гүйцэтгэлийн өөр өөр хугацаа нь FIFO алгоритмын бүтээмжид маш сөрөг нөлөө үзүүлдэг. А даалгаврыг гүйцэтгэхэд 100 секунд зарцуулагдах бол B, C-д тус бүр 10 секунд зарцуулагдана гэж бодъё.
Зургаас харахад системийн дундаж хугацаа (100+110+120)/3=110 байна. Энэ эффект гэж нэрлэгддэг цуваа нөлөө, нөөцийн зарим богино хугацааны хэрэглэгчид хүнд хэрэглэгчийн дараа дараалал үүсгэх үед. Яг л тэргэнцэр дүүрэн худалдан авагч урд чинь зогсож байхад хүнсний дэлгүүрийн дараалал шиг. Асуудлыг шийдэх хамгийн сайн шийдэл бол кассын машиныг солих эсвэл тайвширч, гүнзгий амьсгалах явдал юм.
Хамгийн богино ажлын байр Эхлээд
Хүнд жинтэй процессуудтай ижил төстэй нөхцөл байдлыг ямар нэгэн байдлаар шийдвэрлэх боломжтой юу? Мэдээж. Өөр нэг төрлийн төлөвлөлт гэж нэрлэдэгХамгийн богино ажлын байр Эхлээд (SJF). Түүний алгоритм нь бас нэлээд энгийн бөгөөд нэрнээс нь харахад хамгийн богино даалгавруудыг эхлээд дараалан эхлүүлэх болно.
Энэ жишээнд ижил процессуудыг ажиллуулсны үр дүн нь програмын ажиллах дундаж хугацааг сайжруулах бөгөөд энэ нь тэнцүү байх болно. 50 биш 110, энэ нь бараг 2 дахин илүү юм.
Тиймээс, бүх даалгавар нэгэн зэрэг ирдэг гэсэн таамаглалын хувьд SJF алгоритм нь хамгийн оновчтой алгоритм юм. Гэсэн хэдий ч бидний таамаглал бодитой биш хэвээр байна. Энэ удаад бид 2-р таамаглалыг өөрчилсөн бөгөөд энэ удаад даалгаврууд нэгэн зэрэг биш хэдийд ч байж болно гэж төсөөлж байна. Энэ нь ямар асуудалд хүргэж болох вэ?
А (100в) даалгавар эхлээд ирж, биелэгдэж эхэлнэ гэж төсөөлье. t=10 үед B, C даалгавар ирэх бөгөөд тус бүрд 10 секунд зарцуулагдана. Тэгэхээр гүйцэтгэлийн дундаж хугацаа (100+(110-10)+(120-10))3 = 103. Үүнийг сайжруулахын тулд төлөвлөгч юу хийж чадах вэ?
Эхлээд дуусгах хамгийн богино хугацаа (STCF)
Нөхцөл байдлыг сайжруулахын тулд бид хөтөлбөрийг эхлүүлж, дуусах хүртэл ажиллана гэсэн 3-р таамаглалыг орхигдуулсан. Нэмж дурдахад бидэнд техник хангамжийн дэмжлэг хэрэгтэй бөгөөд таны таамаглаж байгаагаар бид ашиглах болно таймер ажиллаж байгаа ажлыг тасалдуулах ба контекст шилжих. Тиймээс төлөвлөгч нь B, C даалгаврууд ирэх агшинд ямар нэг зүйлийг хийх боломжтой - А даалгаврыг гүйцэтгэхээ зогсоож, B, C даалгавруудыг боловсруулалтанд оруулж, дууссаны дараа А процессыг үргэлжлүүлэн гүйцэтгэх боломжтой. Ийм хуваарьлагчийг гэнэ. STCFбуюу Эхлээд урьдчилан сэргийлэх ажил.
Энэхүү төлөвлөгчийн үр дүн нь дараах үр дүн байх болно: ((120-0)+(20-10)+(30-10))/3=50. Тиймээс ийм хуваарь гаргагч нь бидний даалгаварт илүү оновчтой болно.
Метрийн хариу өгөх хугацаа
Тиймээс, хэрэв бид даалгавруудын ажиллах цагийг мэддэг бөгөөд эдгээр ажлууд нь зөвхөн CPU ашигладаг гэдгийг мэддэг бол STCF нь хамгийн сайн шийдэл байх болно. Эрт дээр үед эдгээр алгоритмууд маш сайн ажилладаг байсан. Гэсэн хэдий ч хэрэглэгч одоо ихэнх цагаа терминал дээр өнгөрөөж, үр дүнтэй интерактив туршлагыг хүлээж байна. Ийнхүү шинэ хэмжүүр гарч ирэв - хариу цаг (хариулт).
Хариу өгөх хугацааг дараах байдлаар тооцоолно.
Tresponse=Tfirstrun−Tarival
Тиймээс өмнөх жишээний хувьд хариу өгөх хугацаа нь: A=0, B=0, C=10 (abg=3,33) байх болно.
3 даалгавар нэгэн зэрэг ирдэг нөхцөлд STCF алгоритм нь тийм ч сайн биш болох нь харагдаж байна - жижиг ажлууд бүрэн дуусах хүртэл хүлээх хэрэгтэй болно. Тиймээс алгоритм нь эргэлтийн хугацааны хэмжигдэхүүнд сайн, харин интерактив хэмжигдэхүүнд муу юм. Хэрэв та терминал дээр суугаад засварлагч руу тэмдэгт оруулах гэж оролдоод CPU-ийг өөр ажил эзэлдэг тул 10 секундээс илүү хүлээх хэрэгтэй гэж төсөөлөөд үз дээ. Энэ нь тийм ч таатай биш байна.
Тиймээс бид өөр нэг асуудалтай тулгараад байна - хариу өгөх цагийг мэдэрдэг хуваарьлагчийг хэрхэн бүтээх вэ?
Тойрон Эргэх
Энэ асуудлыг шийдэхийн тулд алгоритм боловсруулсан Тойрон Эргэх (RR). Үндсэн санаа нь маш энгийн: даалгавруудыг дуусгах хүртэл нь гүйцэтгэхийн оронд бид даалгаврыг тодорхой хугацаанд (цаг хугацааны зүсэлт гэж нэрлэдэг) ажиллуулж дарааллаас өөр ажил руу шилжих болно. Алгоритм нь бүх ажлыг дуусгах хүртэл ажлаа давтана. Энэ тохиолдолд програмын ажиллах хугацаа нь таймер үйл явцыг тасалдуулах хугацаанаас хэд дахин их байх ёстой. Жишээлбэл, хэрэв таймер процессыг x=10ms тутамд тасалдуулж байвал процессыг гүйцэтгэх цонхны хэмжээ 10-ын үржвэр байх ба 10,20 эсвэл x*10 байх ёстой.
Нэг жишээг харцгаая: ABC даалгаврууд системд нэгэн зэрэг ирдэг бөгөөд тус бүр нь 5 секундын турш ажиллахыг хүсдэг. SJF алгоритм нь өөр ажил эхлэхээс өмнө ажил бүрийг дуусгах болно. Үүний эсрэгээр, эхлүүлэх цонх = 1s бүхий RR алгоритм нь даалгавруудыг дараах байдлаар гүйцэтгэнэ (Зураг 4.3).
(Дахин SJF (Хариу өгөх хугацаандаа муу)
(Дугуй Робин (Хариулахын тулд сайн)
RR алгоритмын хариу өгөх дундаж хугацаа (0+1+2)/3=1, харин SJF (0+5+10)/3=5 байна.
Цагийн цонх нь RR-ийн хувьд маш чухал параметр гэж үзэх нь логик бөгөөд бага байх тусам хариу өгөх хугацаа өндөр болно. Гэсэн хэдий ч контекст шилжих хугацаа нь ерөнхий гүйцэтгэлд чухал үүрэг гүйцэтгэдэг тул та үүнийг хэтэрхий жижиг болгож болохгүй. Тиймээс, гүйцэтгэх цонхны хугацааг OS-ийн архитектор тогтоодог бөгөөд үүн дээр гүйцэтгэхээр төлөвлөж буй ажлуудаас хамаарна. Контекстыг сэлгэх нь цагийг дэмий үрдэг цорын ганц үйлчилгээний үйлдэл биш юм - ажиллаж байгаа програм нь бусад олон зүйл, жишээлбэл, янз бүрийн кэш дээр ажилладаг бөгөөд шилжүүлэгч болгонд энэ орчныг хэмнэж, сэргээх шаардлагатай байдаг бөгөөд энэ нь маш их хүчин чармайлт шаарддаг. цаг.
Хэрэв бид зөвхөн хариу өгөх хугацааны хэмжүүрийн тухай ярьж байсан бол RR бол маш сайн төлөвлөгч юм. Гэхдээ даалгаврыг гүйцэтгэх хугацааны хэмжүүр энэ алгоритмтай хэрхэн ажиллах вэ? Дээрх жишээг авч үзье, А, В, С = 5 секундын ажиллах хугацаа, нэгэн зэрэг ирэх үед. А даалгавар 13 секунд, Б 14 секунд, С 15 секунд дуусах ба гүйцэтгэлийн дундаж хугацаа 14 секунд байна. Тиймээс RR нь эргэлтийн хэмжүүрийн хамгийн муу алгоритм юм.
Илүү ерөнхий утгаараа аливаа RR төрлийн алгоритм нь шударга бөгөөд CPU-ийн цагийг бүх процессын хооронд тэнцүү хуваадаг. Тиймээс эдгээр хэмжүүрүүд хоорондоо байнга зөрчилддөг.
Тиймээс бид хэд хэдэн ялгаатай алгоритмуудтай бөгөөд үүнтэй зэрэгцэн хэд хэдэн таамаглалууд хэвээр байна - ажлын цаг нь мэдэгдэж байгаа бөгөөд даалгавар нь зөвхөн CPU ашигладаг.
I/O-той холих
Юуны өмнө процесс нь зөвхөн CPU ашигладаг гэсэн 4-р таамаглалыг хасъя; Мэдээжийн хэрэг, тийм биш бөгөөд процессууд бусад төхөөрөмжид хандах боломжтой.
Аливаа процесс оролт/гаралтын үйлдлийг хүсэх агшинд процесс блоклогдсон төлөвт орж, оролт/гаралтыг дуусгахыг хүлээнэ. Хэрэв I/O нь хатуу диск рүү илгээгдсэн бол ийм үйлдэл нь хэдэн мс ба түүнээс дээш хугацаа шаардагдах бөгөөд процессор яг одоо ажиллахгүй байх болно. Энэ хугацаанд хуваарь гаргагч нь процессорыг өөр ямар ч процессоор ажиллуулж болно. Төлөвлөгчийн хийх дараагийн шийдвэр бол процесс хэзээ I/O-оо дуусгах явдал юм. Энэ тохиолдолд тасалдал үүсч, үйлдлийн систем нь I/O-г дуудсан процессыг бэлэн байдалд оруулна.
Хэд хэдэн асуудлын жишээг авч үзье. Тэд тус бүр нь 50ms CPU цаг шаарддаг. Гэхдээ эхнийх нь 10 мс тутамд I/O-д хандах болно (энэ нь мөн 10 мс тутамд хийгдэх болно). Мөн В процесс нь I/O-гүй 50ms процессор ашигладаг.
Энэ жишээнд бид STCF төлөвлөгчийг ашиглах болно. Хэрэв үүн дээр А шиг процессыг эхлүүлбэл төлөвлөгч хэрхэн ажиллах вэ? Тэрээр дараахь зүйлийг хийх болно: эхлээд тэр А процессыг бүрэн боловсруулж, дараа нь В процессыг гүйцэтгэнэ.
Энэ асуудлыг шийдэх уламжлалт арга бол А процессын 10 мс-ийн дэд ажил бүрийг тусдаа даалгавар болгон авч үзэх явдал юм. Тиймээс, STJF алгоритмаас эхлэхэд 50 ms даалгавар болон 10 ms даалгавар хоёрын хоорондох сонголт тодорхой болно. Дараа нь А дэд даалгавар дуусахад B процесс болон I/O-г эхлүүлнэ. Оролт гаралтын ажил дууссаны дараа В процессын оронд 10ms-ийн А процессыг дахин эхлүүлэх нь заншилтай байх болно. Ийм байдлаар давхцлыг хэрэгжүүлэх боломжтой бөгөөд эхнийх нь процесс хүлээж байх хооронд CPU-г өөр процесс ашигладаг. I/O. Үүний үр дүнд системийг илүү сайн ашигладаг - интерактив процессууд оролт гаралтыг хүлээж байгаа энэ үед процессор дээр бусад процессуудыг гүйцэтгэх боломжтой.
Oracle байхгүй болсон
Одоо даалгаврын үргэлжлэх хугацаа нь мэдэгддэг гэсэн таамаглалаас салахыг хичээцгээе. Энэ нь ерөнхийдөө бүх жагсаалтын хамгийн муу, хамгийн бодит бус таамаглал юм. Үнэн хэрэгтээ, энгийн энгийн үйлдлийн системд үйлдлийн систем өөрөө даалгаврын гүйцэтгэлийн цаг хугацааны талаар маш бага мэддэг тул даалгаврыг гүйцэтгэхэд хэр хугацаа шаардагдахыг мэдэхгүй байж яаж төлөвлөгчийг бүтээх вэ? Магадгүй бид энэ асуудлыг шийдэхийн тулд RR зарчмуудыг ашиглаж болох уу?
Үр дүн
Бид даалгаврын хуваарийн үндсэн санааг авч үзээд 2 гэр бүл төлөвлөгчийг харлаа. Эхнийх нь хамгийн богино даалгаврыг эхлээд эхлүүлж, хариуцах хугацааг ихэсгэдэг бол хоёр дахь нь бүх даалгаврын хооронд тэнцүү хуваагдаж, хариу өгөх хугацааг нэмэгдүүлдэг. Нөгөө гэр бүлийн алгоритмууд сайн байвал хоёр алгоритм хоёулаа муу байна. Мөн бид CPU болон I/O-г зэрэгцүүлэн ашиглах нь гүйцэтгэлийг хэрхэн сайжруулж болохыг судалж үзсэн боловч үйлдлийн системийн нууцлаг байдлын асуудлыг шийдэж чадаагүй. Дараагийн хичээлээр бид өнгөрсөн үеийг харж, ирээдүйг урьдчилан таамаглахыг оролддог төлөвлөгчийг харах болно. Үүнийг олон түвшний санал хүсэлтийн дараалал гэж нэрлэдэг.
Эх сурвалж: www.habr.com