Pengantar Sistem Operasi
Hey Habr! Aku pengin menehi perhatian marang sawetara artikel-terjemahan saka siji literatur sing menarik miturut pendapatku - OSTEP. Materi iki mbahas kanthi jero babagan sistem operasi kaya unix, yaiku, nggarap proses, macem-macem jadwal, memori, lan komponen liyane sing padha sing nggawe OS modern. Sampeyan bisa ndeleng asli kabeh bahan kene . Wigati dimangerteni manawa terjemahan kasebut digawe kanthi ora profesional (cukup bebas), nanging muga-muga bisa tetep makna umum.
Pakaryan laboratorium babagan subyek iki bisa ditemokake ing kene:
bagean liyane:
Sampeyan uga bisa mriksa saluranku ing =)
Pambuka kanggo Scheduler
Inti masalah: Cara ngembangake kabijakan panjadwal
Kepiye kerangka kabijakan panjadwal sing ndasari kudu dirancang? Apa sing kudu dadi asumsi utama? Apa metrik sing penting? Apa teknik dhasar sing digunakake ing sistem komputasi awal?
Asumsi Beban Kerja
Sadurunge ngrembug kabijakan sing bisa ditindakake, ayo nggawe sawetara digression sing nyederhanakake babagan proses sing mlaku ing sistem, sing diarani bebarengan. beban kerja. Nemtokake beban kerja minangka bagean kritis saka kabijakan bangunan, lan luwih akeh sampeyan ngerti babagan beban kerja, luwih apik kabijakan sing bisa ditulis.
Ayo nggawe asumsi ing ngisor iki babagan proses sing mlaku ing sistem, kadhangkala uga disebut jobs (tugas). Meh kabeh asumsi kasebut ora nyata, nanging perlu kanggo pangembangan pamikiran.
- Saben tugas mlaku kanggo wektu sing padha,
- Kabeh tugas disetel bebarengan,
- Tugas sing ditugasake ditindakake nganti rampung,
- Kabeh tugas mung nggunakake CPU,
- Wektu mlaku saben tugas dikenal.
Metrik Penjadwal
Saliyane sawetara asumsi babagan beban, alat liyane kanggo mbandhingake kabijakan jadwal sing beda dibutuhake: metrik penjadwal. Metrik mung sawetara ukuran. Ana sawetara metrik sing bisa digunakake kanggo mbandhingake jadwal.
Contone, kita bakal nggunakake metrik disebut wektu turnaround (waktu giliran). Wektu turnaround tugas ditetepake minangka prabédan antarane wektu rampung tugas lan wektu rawuh tugas ing sistem.
Tturnaround=Tcompletion-Tarrival
Amarga kita nganggep yen kabeh tugas teka bebarengan, banjur Ta = 0 lan kanthi mangkono Tt = Tc. Nilai iki bakal owah kanthi alami nalika kita ngganti asumsi ing ndhuwur.
Metrik liyane - keadilan (adil, jujur). Produktivitas lan keadilan asring nglawan karakteristik ing perencanaan. Contone, panjadwal bisa ngoptimalake kinerja, nanging ing biaya nunggu tugas liyane kanggo mbukak, saéngga ngurangi keadilan.
FIRST IN FIRST OUT (FIFO)
Algoritma paling dhasar sing bisa ditindakake yaiku FIFO utawa pisanan teka (mlebu), pisanan dilayani (metu). Algoritma iki nduweni sawetara kaluwihan: gampang banget kanggo dileksanakake lan cocog karo kabeh asumsi kita lan nindakake tugas kanthi apik.
Ayo goleki conto sing prasaja. Ayo ngomong 3 tugas disetel bebarengan. Nanging ayo kang nganggep sing tugas A teka sethitik sadurungé saka kabeh liyane, supaya bakal katon ing dhaftar eksekusi sadurungé saka liyane, kaya B relatif kanggo C. Ayo nganggep sing saben wong bakal kaleksanan kanggo 10 detik. Apa wektu rata-rata kanggo ngrampungake tugas kasebut ing kasus iki?
Kanthi ngetung nilai - 10+20+30 lan dibagi 3, kita entuk wektu eksekusi program rata-rata padha karo 20 detik.
Saiki ayo nyoba ngganti asumsi kita. Utamane, asumsi 1 lan kanthi mangkono kita ora bakal nganggep yen saben tugas mbutuhake wektu sing padha kanggo dieksekusi. Kepiye FIFO bakal nindakake wektu iki?
Ternyata, wektu eksekusi tugas sing beda-beda duwe pengaruh negatif banget marang produktivitas algoritma FIFO. Ayo nganggep yen tugas A butuh 100 detik kanggo ngrampungake, dene B lan C isih butuh 10 detik.
Minangka bisa dideleng saka tokoh, wektu rata-rata kanggo sistem bakal dadi (100 + 110 + 120) / 3 = 110. Efek iki diarani efek konvoi, nalika sawetara konsumen jangka pendek saka sumber daya bakal antri sawise konsumen abot. Kaya antrian ing toko nalika ana pelanggan ing ngarep sampeyan kanthi grobag lengkap. Solusi sing paling apik kanggo masalah kasebut yaiku nyoba ngganti mesin kasir utawa santai lan ambegan kanthi jero.
Pekerjaan Singkat Pertama
Apa bisa ngatasi kahanan sing padha karo proses abot? temtunipun. Jinis perencanaan liyane diaraniPekerjaan Singkat Pertama (SJF). Algoritma kasebut uga cukup primitif - kaya jeneng kasebut, tugas paling cendhak bakal diluncurake dhisik, siji-sijine.
Ing conto iki, asil nglakokake proses sing padha bakal dadi dandan ing rata-rata wektu turnaround program lan bakal padha karo 50 tinimbang 110, sing meh 2 kaping luwih apik.
Mangkono, kanggo anggepan yen kabeh tugas teka ing wektu sing padha, algoritma SJF katon minangka algoritma sing paling optimal. Nanging, asumsi kita isih ora katon nyata. Wektu iki kita ngganti asumsi 2 lan wektu iki mbayangno tugas bisa ana kapan wae, lan ora kabeh bebarengan. Masalah apa sing bisa nyebabake?
Coba bayangake yen tugas A (100c) teka dhisik lan wiwit dieksekusi. Ing t = 10, tugas B lan C teka, saben-saben butuh 10 detik. Dadi wektu eksekusi rata-rata yaiku (100+(110-10)+(120-10))3 = 103. Apa sing bisa ditindakake panjadwal kanggo nambah iki?
Wektu paling cendhak kanggo Completion First (STCF)
Kanggo nambah kahanan, kita ngilangi asumsi 3 yen program kasebut diluncurake lan mlaku nganti rampung. Kajaba iku, kita butuh dhukungan hardware lan, kaya sing sampeyan duga, bakal digunakake wektu kanggo ngganggu tugas mlaku lan alih konteks. Mangkono, panjadwal bisa nindakake apa wae nalika tugas B, C teka - mungkasi nglakokake tugas A lan sijine tugas B lan C menyang proses lan, sawise rampung, terus nglakokake proses A. Penjadwal kasebut diarani. STCFutawa Preemptive Job First.
Asil saka planner iki bakal dadi asil ing ngisor iki: ((120-0)+(20-10)+(30-10))/3=50. Dadi, panjadwal kasebut dadi luwih optimal kanggo tugas kita.
Wektu Respon Metrik
Mangkono, yen kita ngerti wektu mlaku tugas lan tugas kasebut mung nggunakake CPU, STCF bakal dadi solusi sing paling apik. Lan sapisan ing jaman wiwitan, algoritma kasebut bisa digunakake kanthi apik. Nanging, pangguna saiki akeh wektune ing terminal lan ngarepake pengalaman interaktif sing produktif. Dadi metrik anyar lair - wektu nanggepi (wangsulan).
Wektu respon diitung kaya ing ngisor iki:
Tresponse=Tfirstrun−Tarrival
Dadi, kanggo conto sadurunge, wektu nanggepi bakal dadi: A=0, B=0, C=10 (abg=3,33).
Lan ternyata algoritma STCF ora apik banget ing kahanan sing 3 tugas teka ing wektu sing padha - kudu ngenteni nganti tugas cilik rampung. Dadi algoritma apik kanggo metrik wektu turnaround, nanging ala kanggo metrik interaktivitas. Bayangake yen sampeyan lagi lungguh ing terminal nyoba ngetik karakter menyang editor lan kudu ngenteni luwih saka 10 detik amarga sawetara tugas liyane njupuk CPU. Ora kepenak banget.
Dadi kita ngadhepi masalah liyane - kepiye carane nggawe jadwal sing sensitif marang wektu nanggepi?
Robin Babak
Algoritma dikembangake kanggo ngatasi masalah iki Robin Babak (RR). Ing idea dhasar cukup prasaja: tinimbang mbukak tugas nganti padha rampung, kita bakal mbukak tugas kanggo wektu tartamtu (disebut irisan wektu) lan banjur ngalih menyang tugas liyane saka antrian. Algoritma mbaleni karyane nganti kabeh tugas rampung. Ing kasus iki, wektu mlaku program kudu kaping pirang-pirang wektu sawise wektu bakal ngganggu proses kasebut. Contone, yen wektu ngganggu proses saben x = 10ms, ukuran jendhela eksekusi proses kudu kelipatan 10 lan 10,20 utawa x * 10.
Ayo katon ing conto: tugas ABC teka bebarengan ing sistem lan saben wong pengin mbukak kanggo 5 detik. Algoritma SJF bakal ngrampungake saben tugas sadurunge miwiti liyane. Ing kontras, algoritma RR kanthi jendhela peluncuran = 1s bakal ngliwati tugas kaya ing ngisor iki (Gambar 4.3):
(SJF Again (Bad for Response Time)
(Round Robin (Apik Kanggo Response Time)
Wektu respon rata-rata kanggo algoritma RR yaiku (0+1+2)/3=1, dene kanggo SJF (0+5+10)/3=5.
Iku logis kanggo nganggep yen jendhela wektu minangka parameter sing penting banget kanggo RR; sing luwih cilik, sing luwih dhuwur wektu respon. Nanging, sampeyan ora kudu nggawe cilik banget, amarga wektu ngoper konteks uga bakal duwe peran ing kinerja sakabèhé. Mangkono, pilihan wektu jendhela eksekusi disetel dening arsitek OS lan gumantung marang tugas sing direncanakake bakal ditindakake. Konteks ngoper ora mung operasi layanan sing mbuwang wektu - program sing mlaku ngoperasikake akeh perkara liyane, contone, macem-macem cache, lan saben switch perlu kanggo nyimpen lan mulihake lingkungan iki, sing uga bisa njupuk akeh. wektu.
RR minangka panjadwal sing apik yen kita mung ngomong babagan metrik wektu respon. Nanging kepiye metrik wektu turnaround tugas bakal tumindak karo algoritma iki? Coba conto ing ndhuwur, nalika wektu operasi A, B, C = 5s lan teka ing wektu sing padha. Tugas A bakal rampung ing 13, B ing 14, C ing 15s lan wektu turnaround rata-rata bakal 14s. Mangkono, RR minangka algoritma paling awon kanggo metrik turnover.
Ing istilah sing luwih umum, algoritma jinis RR apa wae sing adil; iki mbagi wektu CPU kanthi rata ing antarane kabeh proses. Lan kanthi mangkono, metrik kasebut terus-terusan saling bertentangan.
Mangkono, kita duwe sawetara algoritma sing kontras lan ing wektu sing padha isih ana sawetara asumsi - yen wektu tugas wis dingerteni lan tugas kasebut mung nggunakake CPU.
Nyampur karo I / O
Kaping pisanan, ayo mbusak asumsi 4 yen proses kasebut mung nggunakake CPU; mesthi, iki ora kedadeyan lan proses bisa ngakses peralatan liyane.
Nalika proses apa wae njaluk operasi I / O, proses kasebut mlebu ing negara sing diblokir, ngenteni I / O rampung. Yen I / O dikirim menyang hard drive, operasi kuwi bisa njupuk nganti sawetara ms utawa maneh, lan prosesor bakal nganggur ing wayahe. Sajrone wektu iki, panjadwal bisa ngenggoni prosesor karo proses liyane. Kaputusan sabanjure sing kudu ditindakake panjadwal yaiku nalika proses bakal ngrampungake I / O. Yen kedadeyan kasebut, interupsi bakal kedadeyan lan OS bakal nggawe proses sing diarani I / O dadi status siap.
Ayo goleki conto sawetara masalah. Saben wong mbutuhake 50ms wektu CPU. Nanging, sing pisanan bakal ngakses I/O saben 10ms (sing uga bakal dieksekusi saben 10ms). Lan proses B mung nggunakake prosesor 50ms tanpa I / O.
Ing conto iki kita bakal nggunakake panjadwal STCF. Kepiye panjadwal bakal tumindak yen proses kaya A diluncurake? Dheweke bakal nindakake ing ngisor iki: pisanan dheweke bakal ngrampungake proses A, banjur proses B.
Pendekatan tradisional kanggo ngatasi masalah iki kanggo nambani saben 10 ms subtask saka proses A minangka tugas kapisah. Mangkono, nalika miwiti karo algoritma STJF, pilihan antarane tugas 50 ms lan tugas 10 ms ketok. Banjur, nalika subtugas A rampung, proses B lan I/O bakal diluncurake. Sawise I / O rampung, iku bakal dadi adat kanggo miwiti proses 10ms A maneh tinimbang proses B. Kanthi cara iki, iku bisa kanggo ngleksanakake tumpang tindih, ngendi CPU digunakake dening proses liyane nalika pisanan nunggu Aku/O. Lan minangka asil, sistem luwih digunakke - ing wayahe nalika proses interaktif nunggu I / O, pangolahan liyane bisa kaleksanan ing prosesor.
Oracle ora ana maneh
Saiki ayo nyoba nyingkirake asumsi yen wektu kerja tugas kasebut dikenal. Iki umume minangka asumsi sing paling awon lan paling ora nyata ing kabeh dhaptar. Nyatane, ing rata-rata OS biasa, OS dhewe biasane ngerti sethithik babagan wektu eksekusi tugas, mula kepiye carane sampeyan bisa nggawe jadwal tanpa ngerti suwene tugas bakal ditindakake? Mungkin kita bisa nggunakake sawetara prinsip RR kanggo ngatasi masalah iki?
Asile
Kita nyawang gagasan dhasar saka jadwal tugas lan ndeleng 2 kulawarga penjadwal. Sing kapisan miwiti tugas sing paling cendhak dhisik lan kanthi mangkono nambah wektu turnaround, dene sing kapindho ambruk ing antarane kabeh tugas kanthi merata, nambah wektu nanggepi. Kaloro algoritma kasebut ala ing ngendi algoritma kulawarga liyane apik. Kita uga ndeleng carane paralel nggunakake CPU lan I / O bisa nambah kinerja, nanging ora ngatasi masalah karo OS clairvoyance. Lan ing pawulangan sabanjure, kita bakal ndeleng perencana sing ndeleng masa lalu langsung lan nyoba prédhiksi masa depan. Lan diarani antrian umpan balik multi-tingkat.
Source: www.habr.com