Bubuka pikeun Sistem Operasi
Héy Habr! Abdi hoyong nengetan runtuyan artikel-tarjamahan tina hiji literatur metot dina pamanggih kuring - OSTEP. Bahan ieu ngabahas sacara jero ngeunaan sistem operasi sapertos unix, nyaéta, damel sareng prosés, rupa-rupa jadwal, mémori, sareng komponén anu sami anu ngawangun OS modern. Anjeun tiasa ningali asli sadaya bahan di dieu . Punten perhatikeun yén tarjamahan éta dilakukeun sacara teu profésional (rada bébas), tapi kuring ngarep-arep nahan harti umum.
Karya laboratorium dina subjek ieu tiasa dipendakan di dieu:
bagian séjén:
Anjeun oge bisa pariksa kaluar channel abdi di =)
tata: antrian Eupan Balik Multi-Level
Dina kuliah ieu, urang bakal ngobrol ngeunaan masalah ngembangkeun salah sahiji pendekatan kawentar
tata, nu disebut Antrian Eupan Balik Multi-Level (MLFQ). Jadwal MLFQ munggaran dijelaskeun dina 1962 ku Fernando J. Corbató dina sistem anu disebut
Cocog Time-Bagi System (CTSS). Karya-karya ieu (kalebet karya salajengna
Multics) salajengna dicalonkeun pikeun Penghargaan Turing. scheduler éta
salajengna ningkat jeung kaala penampilan nu bisa kapanggih geus di
sababaraha sistem modern.
Algoritma MLFQ nyobian ngarengsekeun 2 masalah tumpang tindih dasar.
firstly, éta nyobian ngaoptimalkeun waktos turnaround, anu, sakumaha anu urang bahas dina ceramah sateuacana, dioptimalkeun ku metodeu dimimitian dina sirah antrian paling.
tugas pondok. Nanging, OS henteu terang sabaraha lami prosés ieu atanapi éta bakal dijalankeun, sareng ieu
pangaweruh diperlukeun pikeun operasi SJF, algoritma STCF. Bréh, MLFQ nyobian
ngajadikeun sistem responsif pikeun pamaké (contona, pikeun maranéhanana anu diuk na
neuteup dina layar bari ngantosan tugas rengse) sahingga ngaleutikan waktu
respon. Hanjakal, algoritma kawas RR ngurangan waktu respon, tapi
gaduh pangaruh goréng dina métrik waktos turnaround. Ku kituna masalah urang: Kumaha ngarancang
a scheduler anu bakal minuhan sarat urang tanpa nyaho nanaon tentang
alam prosés, sacara umum? Kumaha scheduler tiasa diajar karakteristik tugas,
nu eta ngajalankeun sahingga nyieun kaputusan scheduling hadé?
Intina masalah: Kumaha ngarencanakeun setting tugas tanpa pangaweruh anu sampurna?
Kumaha mendesain penjadwal anu sakaligus ngaminimalkeun waktos réspon
pikeun tugas interaktif tur dina waktos anu sareng ngaminimalkeun waktos turnaround tanpa nyaho
pangaweruh ngeunaan waktu palaksanaan tugas?
Catetan: diajar tina kajadian saméméhna
antrian MLFQ mangrupa conto alus teuing tina sistem anu dilatih dina
kajadian kaliwat pikeun prediksi mangsa nu bakal datang. Pendekatan sapertos kitu sering
kapanggih dina OS (Sareng seueur cabang séjén dina élmu komputer, kalebet cabang
prediksi hardware sareng algoritma cache). lalampahan sarupa
micu nalika tugas boga fase behavioral sahingga bisa diprediksi.
Sanajan kitu, hiji kudu ati kalawan téhnik ieu, sabab prediksi pisan gampang.
bisa tétéla salah jeung ngakibatkeun sistem pikeun nyieun kaputusan leuwih goreng ti
bakal tanpa pangaweruh pisan.
MLFQ: Aturan Dasar
Mertimbangkeun aturan dasar tina algoritma MLFQ. Jeung sanajan palaksanaan algoritma ieu
aya sababaraha, pendekatan dasar anu sarupa.
Dina palaksanaan nu urang bakal mertimbangkeun, MLFQ bakal mibanda sababaraha
antrian misah, nu masing-masing bakal boga prioritas béda. iraha waé,
tugas siap pikeun palaksanaan aya dina antrian sarua. MLFQ ngagunakeun prioritas,
mutuskeun nu tugas ngajalankeun pikeun palaksanaan, i.e. tugas kalawan luhur
prioritas (tugas ti antrian jeung prioritas pangluhurna) bakal dibuka dina munggaran
antrian.
Tangtosna, tiasa aya langkung ti hiji tugas dina antrian khusus, janten
jadi maranéhna bakal boga prioritas sarua. Dina hal ieu, mékanisme bakal dianggo
RR pikeun perencanaan peluncuran diantara tugas ieu.
Ku kituna urang sumping ka dua aturan dasar pikeun MLFQ:
- Aturan1: Lamun prioritas(A) > Prioritas(B), tugas A bakal ngajalankeun (B moal)
- Aturan2: Upami prioritas(A) = Prioritas(B), A&B dimimitian nganggo RR
Dumasar kana hal di luhur, unsur konci pikeun ngarencanakeun MLFQ nyaéta
mangrupakeun prioritas. Gantina méré prioritas tetep unggal
tugas, MLFQ robah prioritas na gumantung kana kabiasaan observasi.
Contona, upami hiji tugas terus-terusan kaluar dina CPU bari ngantosan input keyboard,
MLFQ bakal tetep prioritas prosés luhur sabab éta kumaha
prosés interaktif kedah jalan. Lamun, sabalikna, tugas téh terus jeung
nyaéta CPU intensif pikeun période lila, MLFQ bakal downgrade eta
hiji prioritas. Ku kituna, MLFQ bakal nalungtik paripolah prosés nalika aranjeunna ngajalankeun
jeung paripolah ngagunakeun.
Hayu urang ngagambar conto kumaha antrian bisa kasampak kawas di sawatara titik
waktos lajeng anjeun meunang hal kawas kieu:
Dina skéma ieu, 2 prosés A jeung B aya dina antrian jeung prioritas pangluhurna. Prosés
C nyaéta tempat di tengah, jeung prosés D aya dina tungtung antrian. Nurutkeun di luhur
déskripsi tina algoritma MLFQ, scheduler ngan bakal ngaéksekusi tugas kalawan pangluhurna
prioritas nurutkeun RR, jeung tugas C, D bakal kaluar gawé.
Alami, snapshot statik moal masihan gambaran lengkep kumaha MLFQ jalan.
Kadé ngartos persis kumaha gambar robah kana waktu.
usaha 1: Kumaha carana ngarobah prioritas
Dina titik ieu, anjeun kedah mutuskeun kumaha MLFQ bakal ngarobih tingkat prioritas
tugas (sahingga posisi tugas dina antrian) salila siklus hirup na. Pikeun
ieu, Anjeun kudu tetep dina pikiran workflow: jumlah nu tangtu
tugas interaktif sareng waktos jalan anu pondok (sahingga sering dileupaskeun
CPU) jeung sababaraha pancén lila-ngajalankeun nu ngagunakeun CPU sadaya waktu gawé maranéhanana, bari
waktos respon pikeun tugas sapertos teu penting. Tur jadi Anjeun bisa nyieun usaha munggaran
nerapkeun algoritma MLFQ kalayan aturan ieu:
- Aturan3: Nalika tugas asup kana sistem, éta disimpen dina antrian anu paling luhur
- prioritas.
- Rule4a: Upami hiji tugas nganggo sadayana jandela waktos, teras éta
- prioritas diréduksi.
- Aturan4b: Upami Tugas ngaleupaskeun CPU sateuacan jandela waktosna kadaluwarsa, teras éta
- tetep mibanda prioritas sarua.
Conto 1: Tugas tunggal anu panjang
Sapertos anu tiasa ditingali dina conto ieu, tugas pangakuan diatur kalayan pangluhurna
prioritas. Saatos jandela waktos 10ms, prosésna diturunkeun dina prioritas.
panjadwal. Saatos jandela waktos salajengna, tugas tungtungna diturunkeun ka
prioritas panghandapna dina sistem, dimana eta tetep.
Conto 2: Ngirimkeun tugas pondok
Ayeuna hayu urang tingali conto kumaha MLFQ bakal nyobian ngadeukeutan SJF. Dina éta
conto, dua tugas: A, nu mangrupakeun tugas lila-ngajalankeun terus
occupying CPU jeung B, nu mangrupakeun tugas interaktif pondok. Upamana
yén si A parantos ngajalankeun sababaraha waktos nalika tugas B dugi.
Grafik ieu nunjukkeun hasil tina skenario. Tugas A, sapertos tugas naon waé,
ngagunakeun CPU éta di handap pisan. Tugas B bakal sumping dina waktos T = 100 sareng bakal
ditempatkeun dina antrian prioritas pangluhurna. Kusabab waktu ngajalankeun pondok,
eta bakal réngsé saméméh éta ngahontal antrian panungtungan.
Tina conto ieu, anjeun kedah ngartos tujuan utama algoritma: sabab algoritma henteu
terang tugas panjang atanapi pondok, teras mimitina anjeunna nganggap tugas éta
pondok tur mere eta prioritas pangluhurna. Upami éta leres-leres tugas anu pondok, maka
eta bakal ngaéksekusi gancang, disebutkeun lamun éta tugas panjang eta bakal gerak lalaunan
dina prioritas handap sarta baris geura-giru ngabuktikeun yén Aisyah memang tugas panjang anu henteu
merlukeun respon.
Conto 3: Kumaha upami I/O?
Ayeuna hayu urang tingali conto I / O. Sakumaha didadarkeun dina aturan 4b,
lamun hiji prosés ngaleupaskeun prosésor tanpa ngagunakeun sapinuhna waktu prosésor,
mangka tetep dina tingkat prioritas sarua. Maksud aturan ieu cukup basajan.
- lamun pakasaban interaktif ngalakukeun loba I / operasi O, Contona, ngantosan
ti keystrokes pamaké atawa beurit, tugas saperti bakal ngosongkeun processor
saméméh jandela allotted. Kami henteu hoyong ngaleungitkeun tugas prioritas sapertos kitu,
sahingga bakal tetep dina tingkat anu sarua.
Conto ieu nunjukkeun kumaha algoritma bakal tiasa dianggo sareng prosés sapertos kitu - tugas interaktif B, anu ngan ukur peryogi CPU pikeun 1ms sateuacan dieksekusi.
I / O prosés jeung pakasaban lila A, nu ngagunakeun CPU sepanjang waktos.
MLFQ ngajaga prosés B dina prioritas pangluhurna sabab terus
ngaleupaskeun CPU. Upami B mangrupikeun tugas interaktif, maka algoritma dina hal ieu parantos ngahontal
tujuanana pikeun ngajalankeun tugas interaktif gancang.
Masalah sareng algoritma MLFQ ayeuna
Dina conto saméméhna, kami geus diwangun versi dasar MLFQ. Sareng sigana anjeunna
ngalakukeun pakasaban na ogé sarta adil, ngadistribusikaeun waktu CPU cukup antara
tugas panjang sarta ngidinan tugas pondok atawa tugas anu beurat diakses
ka I / O pikeun ngolah gancang. Hanjakal, pendekatan ieu ngandung sababaraha
masalah serius.
firstly, masalah lapar: lamun sistem bakal loba interaktif
tugas, aranjeunna bakal meakeun sadaya waktu CPU sahingga moal panjang tunggal
tugas moal meunang kasempetan pikeun dieksekusi (aranjeunna kalaparan).
Bréh, pamaké pinter bisa nulis program maranéhanana ku kituna
fool scheduler nu. tipu daya perenahna dina ngalakukeun hiji hal guna maksa
scheduler méré prosés leuwih waktos CPU. Algoritma éta
ditétélakeun di luhur cukup rentan ka serangan saperti: saméméh jandela waktu praktis
leuwih, Anjeun kudu ngalakukeun hiji I / O operasi (pikeun sababaraha, euweuh urusan nu file)
sahingga ngosongkeun CPU. Paripolah sapertos kitu bakal ngantep anjeun tetep sami
antrian sorangan jeung deui meunang perséntase gedé tina waktu CPU. Lamun geus rengse
Ieu leres (misalna ngajalankeun 99% tina waktos jandela sateuacan ngaleupaskeun CPU),
tugas saperti saukur bisa monopoliize processor.
Tungtungna, program bisa ngarobah kabiasaan na kana waktu. Éta tugas
nu dipaké CPU bisa jadi interaktif. Dina conto urang, sarupa
tugas moal nampi perlakuan ditangtoskeun ti scheduler nu, sakumaha batur ngalakukeunana
(asli) tugas interaktif.
Patarosan pikeun panongton: serangan naon on scheduler bisa dilaksanakeun di dunya modern?
Usaha 2: Ningkatkeun prioritas
Hayu urang cobian ngarobih aturan sareng tingali naha urang tiasa ngahindarkeun masalah
kalaparan. Naon anu bisa urang pigawé pikeun mastikeun nu patali
Tugas CPU bakal nyandak waktosna (sanaos henteu lami).
Salaku solusi basajan pikeun masalah, anjeun tiasa nyarankeun périodik
ningkatkeun prioritas sadaya tugas sapertos dina sistem. Aya loba cara
Pikeun ngahontal ieu, hayu urang coba nerapkeun hal basajan saperti conto: narjamahkeun
sadaya tugas sakaligus ka prioritas pangluhurna, ku kituna aturan anyar:
- Aturan5: Saatos sababaraha jaman S, mindahkeun sadaya tugas dina sistem ka antrian pangluhurna.
Aturan anyar urang ngajawab dua masalah sakaligus. Kahiji, prosés
dijamin moal kalaparan: tugas dina antrian pangluhurna bakal babagi
waktos processor nurutkeun algoritma RR sahingga sakabéh prosés bakal nampa
waktos processor. Kadua, lamun sababaraha prosés nu saméméhna dipaké
ngan processor jadi interaktif, eta bakal tetep dina antrian jeung pangluhurna
prioritas sanggeus narima dorongan ka prioritas pangluhurna sakali.
Pertimbangkeun conto. Dina skenario ieu, mertimbangkeun hiji prosés tunggal ngagunakeun
CPU jeung dua interaktif, prosés pondok. Di kénca dina inohong, inohong nembongkeun kabiasaan tanpa dorongan prioritas, sahingga tugas ngajalankeun lila dimimitian kalaparan sanggeus dua tugas interaktif anjog kana sistem. Dina gambar di beulah katuhu, unggal 50ms paningkatan prioritas dilaksanakeun sahingga sadaya prosés dijamin nampi waktos prosésor sareng bakal dimimitian périodik. 50ms dina hal ieu dicokot sabagé conto, dina kanyataanana jumlah ieu rada luhur.
Ieu écés yén tambahan waktu naékna periodik S ngabalukarkeun
patarosan logis: nilai naon kudu diatur? Salah sahiji anu pantes
insinyur sistem John Ousterhout ngarujuk kana jumlah anu sami dina sistem sapertos voo-doo
konstan, saprak aranjeunna dina sababaraha cara diperlukeun black magic pikeun bener
kakeunaan. Sareng, hanjakalna, S gaduh rasa sapertos kitu. Upami anjeun nyetél nilai ogé
badag - tugas panjang bakal kalaparan. Sareng upami anjeun nyetél éta handap teuing,
tugas interaktif moal nampi waktos CPU ditangtoskeun.
usaha 3: Akunting Leuwih alus
Ayeuna urang gaduh hiji deui masalah pikeun direngsekeun: kumaha henteu
ngidinan pikeun curang scheduler urang? The culprits pikeun kamungkinan ieu téh
aturan 4a, 4b nu ngidinan pakasaban tetep prioritas na ku ngabebaskeun processor
samemeh béak waktu nu geus ditangtukeun. Kumaha cara nungkulanana?
Solusi dina hal ieu bisa dianggap hiji akuntansi hadé waktu CPU on unggal
tingkat MLFQ. Gantina forgetting waktos program dipaké
processor pikeun interval allotted, Anjeun kudu tumut kana akun tur nyimpen eta. Sanggeus
prosés geus dipaké nepi waktu allotted na, eta kudu demoted ka salajengna
tingkat prioritas. Ayeuna henteu masalah kumaha prosésna bakal ngagunakeun waktosna - kumaha
komputasi terus-terusan dina prosésor atanapi sakumpulan telepon. Ku kituna,
aturan 4 kudu ditulis ulang saperti kieu:
- Aturan4: Saatos tugas geus dipaké nepi waktos na disadiakeun dina antrian ayeuna (paduli sabaraha kali eta dibébaskeun CPU), prioritas tugas misalna hiji ngurangan (eta ngalir ka handap antrian).
Hayu urang nempo conto:
»
Angka nunjukkeun naon anu bakal kajadian upami anjeun nyobian trik penjadwal sapertos
lamun éta kalayan aturan saméméhna 4a, 4b bakal hasil dina kénca. Kalawan anyar
aturan nyaéta hasilna aya di katuhu. Sateuacan panyalindungan, prosés naon waé tiasa nelepon I/O sateuacan réngsé sareng
sahingga ngadominasi CPU, sanggeus ngaktipkeun panyalindungan, paduli kabiasaan
abdi / O, anjeunna masih bakal mindahkeun handap dina antrian sahingga moal bisa dishonestly
nyokot alih sumberdaya CPU.
Ningkatkeun MLFQ sareng masalah anu sanés
Kalayan perbaikan di luhur, masalah anyar timbul: salah sahiji anu utama
patarosan - kumaha carana parameterize scheduler a? Jelema. Sabaraha kedah
antrian? Naon kedah ukuran jandela program dina antrian? Kumaha
program kudu mindeng jadi prioritized ulah kalaparan jeung
pikeun tumut kana akun parobahan paripolah program? Pikeun patarosan ieu, teu aya anu basajan
respon na ukur percobaan kalawan beban sarta konfigurasi saterusna
planner bisa ngakibatkeun sababaraha kasaimbangan nyugemakeun.
Contona, paling palaksanaan MLFQ ngidinan Anjeun pikeun napelkeun béda
time slot pikeun antrian béda. Antrian prioritas tinggi biasana
interval pondok. Antrian ieu diwangun ku tugas interaktif,
switching antara nu rada sénsitip sarta kedah nyandak 10 atanapi kirang
Ibu. Kontras, antrian-prioritas low diwangun ku tugas lila-ngajalankeun nu make
CPU. Sareng dina hal ieu, interval waktos anu lami pas pisan (100ms).
Dina conto ieu, aya 2 tugas anu parantos digarap dina antrian prioritas 20
ms dibagi kana 10ms windows. 40ms dina antrian tengah (jandela 20ms) jeung dina antrian prioritas low
Jandéla waktos antrian janten 40ms dimana tugas parantos réngsé.
Palaksanaan MLFQ dina Solaris OS mangrupikeun kelas jadwal ngabagi waktos.
scheduler bakal nyadiakeun susunan tabel nu nangtukeun persis kumaha sakuduna
ngarobah prioritas prosés ngaliwatan kursus hirupna, naon kudu ukuranana
Jandéla anu bakal dialokasikeun sareng sabaraha sering naékeun prioritas tugas. Pangurus
Sistim tiasa berinteraksi sareng tabel ieu sareng ngadamel scheduler kalakuanana
béda. Sacara standar, tabel ieu ngagaduhan 60 antrian kalayan paningkatan bertahap
ukuran jandela ti 20ms (prioritas luhur) nepi ka sababaraha ratus mdet (prioritas panghandapna), jeung
ogé kalayan dorongan sadaya tugas sakali per detik.
schedulers MLFQ séjén teu make tabel atawa husus
aturan anu dijelaskeun dina bab ieu, sabalikna, maranéhna ngitung prioritas ngagunakeun
rumus matematik. Contona, scheduler di FreeBSD ngagunakeun rumus pikeun
ngitung prioritas tugas ayeuna dumasar kana sabaraha prosés
dipaké CPU. Sajaba ti éta, pamakéan CPU rots kana waktu, sahingga
Ku kituna, paningkatan prioritas rada béda ti ditétélakeun di luhur. Ieu leres
disebutna algoritma buruk. Dina versi 7.1, FreeBSD nganggo jadwal ULE.
Tungtungna, loba planners gaduh fitur sejenna. Contona, sababaraha
schedulers cagar tingkat luhur pikeun operasi sistem operasi sahingga
Ku kituna, euweuh prosés pamaké bisa meunang prioritas pangluhurna di
sistem. Sababaraha sistem ngidinan Anjeun pikeun masihan nasihat pikeun mantuan
scheduler pikeun bener prioritas. Contona, ngagunakeun paréntah alus
anjeun tiasa ningkatkeun atanapi ngirangan prioritas tugas sahingga ningkatkeun atanapi ngirangan
ngurangan Chances program pikeun waktos CPU.
MLFQ: Ringkesan
Kami parantos ngajelaskeun pendekatan perencanaan anu disebut MLFQ. Namina
menyimpulkan dina prinsip operasi - eta boga sababaraha antrian sarta ngagunakeun eupan balik
pikeun prioritas hiji tugas.
Bentuk ahir aturan bakal kieu:
- Aturan1: Lamun prioritas(A) > Prioritas(B), tugas A bakal dibuka (B moal)
- Aturan2: Lamun prioritas (A) = Prioritas (B), A & B dimimitian maké RR
- Aturan3: Nalika tugas asup kana sistem, ieu disimpen dina antrian prioritas pangluhurna.
- Aturan4: Saatos tugas geus dipaké nepi waktos na disadiakeun dina antrian ayeuna (paduli sabaraha kali eta dibébaskeun CPU), prioritas tugas misalna hiji ngurangan (eta ngalir ka handap antrian).
- Aturan5: Saatos sababaraha jaman S, mindahkeun sadaya tugas dina sistem ka antrian pangluhurna.
MLFQ metot pikeun alesan di handap ieu - tinimbang merlukeun pangaweruh ngeunaan
alam tugas sateuacanna, algoritma learns kabiasaan kaliwat tina tugas jeung susunan
prioritas sasuai. Ku kituna, manéhna nyoba diuk dina dua korsi sakaligus - pikeun ngahontal kinerja tugas leutik (SJF, STCF) jeung jujur ngajalankeun panjang,
Proyék CPU-loading. Ku alatan éta, seueur sistem, kalebet BSD sareng turunanna,
Solaris, Windows, Mac nganggo sababaraha bentuk algoritma salaku penjadwal
MLFQ salaku garis dasar.
Bahan tambahan:
- (komputasi)
sumber: www.habr.com