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 =)
Planning: Multi-Level Umpan Balik Antrian
Ing kuliah iki kita bakal ngomong babagan masalah ngembangake salah sawijining pendekatan sing paling misuwur
tata, kang diarani Antrian Umpan Balik Multi-Level (MLFQ). Penjadwal MLFQ pisanan diterangake ing taun 1962 dening Fernando J. Corbató ing sistem sing diarani
Kompatibel Time-Sharing System (CTSS). Karya-karya iki (kalebu karya mengko
Multics) banjur dinominasikake kanggo Penghargaan Turing. Planner punika
salajengipun apik lan angsal tampilan sing bisa ditemokaké wis ing
sawetara sistem modern.
Algoritma MLFQ nyoba ngrampungake 2 masalah tumpang tindih dhasar.
Sepisanan, nyoba kanggo ngoptimalake wektu turnaround, sing, kaya sing kita rembugan ing kuliah sadurunge, dioptimalake kanthi metode wiwitan ing wiwitan antrian paling akeh.
tugas singkat. Nanging, OS ora ngerti suwene proses tartamtu bakal mlaku, lan iki
kawruh perlu kanggo operasi saka SJF, algoritma STCF. Kaping kalih, MLFQ nyoba
nggawe sistem responsif kanggo pangguna (contone, kanggo sing lungguh lan
mentheleng ing layar ngenteni tugas rampung) lan kanthi mangkono nyilikake wektu
wangsulan. Sayange, algoritma kaya RR nambah wektu respon, nanging arang banget
duwe pengaruh ala ing metrik wektu turnaround. Mulane masalah kita: Cara ngrancang
panjadwal sing bakal nyukupi syarat kita tanpa ngerti apa-apa
sifat proses ing umum? Kepiye panjadwal sinau karakteristik tugas,
kang diluncurake lan kanthi mangkono nggawe keputusan perencanaan sing luwih apik?
Inti masalah: Kepiye ngrancang setelan tugas tanpa kawruh sing sampurna?
Carane ngrancang panjadwal sing bebarengan nyilikake wektu respon
kanggo tugas interaktif lan ing wektu sing padha nyilikake wektu turnaround tanpa ngerti
kawruh babagan wektu eksekusi tugas?
Cathetan: kita sinau saka acara sadurunge
Antrian MLFQ minangka conto banget saka sistem sing sinau saka
acara kepungkur kanggo prédhiksi mangsa. Pendekatan sing padha asring
ditemokake ing OS (Lan akeh cabang ilmu komputer liyane, kalebu cabang
prediksi hardware lan algoritma caching). Lelungan sing padha
dipicu nalika tugas duwe fase prilaku lan bisa diprediksi.
Nanging, sampeyan kudu ati-ati karo teknik iki amarga prediksi gampang banget
bisa dadi salah lan mimpin sistem kanggo nggawe keputusan sing luwih elek tinimbang
bakal tanpa kawruh babar pisan.
MLFQ: Aturan dhasar
Ayo goleki aturan dhasar algoritma MLFQ. Lan sanajan implementasine saka algoritma iki
Ana sawetara, pendekatan dhasar padha.
Ing implementasine sing bakal kita deleng, MLFQ bakal duwe sawetara
antrian kapisah, saben kang bakal duwe prioritas beda. Kapan wae,
tugas siap kanggo eksekusi ing siji antrian. MLFQ nggunakake prioritas,
kanggo mutusaké kang tugas kanggo mbukak kanggo eksekusi, i.e. tugas karo sing luwih dhuwur
prioritas (tugas saka antrian kanthi prioritas paling dhuwur) bakal diluncurake dhisik
antrian.
Mesthi, ana uga luwih saka siji tugas ing antrian tartamtu, supaya
supaya padha duwe prioritas padha. Ing kasus iki, mekanisme bakal digunakake
RR kanggo jadwal roto antarane tugas iki.
Mangkono, kita teka ing rong aturan dhasar kanggo MLFQ:
- Aturan1: Yen prioritas(A) > Prioritas(B), tugas A bakal diluncurake (B ora bakal)
- Aturan2: Yen prioritas(A) = Prioritas(B), A&B diwiwiti nganggo RR
Adhedhasar ing ndhuwur, unsur kunci kanggo ngrancang MLFQ
minangka prioritas. Tinimbang menehi prioritas tetep kanggo saben
tugas, MLFQ ngganti prioritas gumantung prilaku diamati.
Contone, yen tugas terus-terusan mbuwang karya ing CPU nalika ngenteni input keyboard,
MLFQ bakal tetep dadi prioritas proses amarga kaya ngono
proses interaktif kudu bisa. Yen, ing nalisir, tugas terus-terusan lan
nggunakake CPU akeh banget liwat dangu, MLFQ bakal murah
prioritas. Dadi, MLFQ bakal nyinaoni prilaku proses nalika lagi mlaku
lan nggunakake prilaku.
Ayo digambar conto kaya apa antrian ing sawetara titik
wektu banjur sampeyan entuk kaya iki:
Ing skema iki, 2 proses A lan B ana ing antrian prioritas paling dhuwur. Proses
C nang endi wae ing tengah, lan proses D ing mburi banget saka antrian. Miturut ing ndhuwur
Miturut katrangan saka algoritma MLFQ, panjadwal bakal nglakokake tugas mung kanthi paling dhuwur
prioritas miturut RR, lan tugas C, D bakal metu saka karya.
Mesthine, gambar statis ora bakal menehi gambaran lengkap babagan cara kerja MLFQ.
Iku penting kanggo ngerti persis carane gambar diganti liwat wektu.
Usaha 1: Cara ngganti prioritas
Ing jalur iki sampeyan kudu mutusake carane MLFQ bakal ngganti tingkat prioritas
tugas (lan kanthi mangkono posisi tugas ing antrian) minangka progresses liwat siklus urip. Kanggo
iki perlu kanggo mbudidaya alur kerja: jumlah tartamtu
tugas interaktif kanthi runtime cendhak (lan kanthi mangkono kerep diluncurake
CPU) lan sawetara tugas long-mlaku sing nggunakake CPU kabeh wektu kerja, nalika
Wektu nanggepi ora penting kanggo tugas kasebut. Lan kanthi cara iki sampeyan bisa nyoba pisanan
ngleksanakake algoritma MLFQ kanthi aturan ing ngisor iki:
- Aturan 3: Nalika tugas mlebu sistem, diselehake ing antrian kanthi paling dhuwur
- prioritas.
- Aturan4a: Yen tugas nggunakake kabeh jendhela wektu sing diwenehake, banjur
- prioritas wis suda.
- Aturan4b: Yen Tugas ngeculake CPU sadurunge jendhela wektu kadaluwarsa, banjur
- tetep karo prioritas padha.
Conto 1: Tugas sing dawa
Kaya sing bisa dideleng ing conto iki, tugas diakoni disetel kanthi paling dhuwur
prioritas. Sawise jendhela wektu 10ms, proses diturunake ing prioritas
planner. Sawise jendhela sabanjure, tugas kasebut pungkasane diturunake
prioritas paling ing sistem, ngendi iku tetep.
Conto 2: Ngirim tugas singkat
Saiki ayo deleng conto carane MLFQ bakal nyoba nyedhaki SJF. Ing iku
contone, loro tugas: A, kang tugas long-mlaku terus
manggoni CPU lan B, kang tugas interaktif singkat. Kudune
yen A wis sawetara wektu nalika tugas B teka.
Grafik iki nuduhake asil saka skenario. Tugas A, kaya tugas apa wae,
Panggunaan CPU ana ing paling ngisor. Tugas B bakal teka ing wektu T = 100 lan bakal
diselehake ing antrian prioritas paling dhuwur. Wiwit wektu operasi cendhak, banjur
bakal rampung sadurunge tekan antrian pungkasan.
Saka conto iki, tujuan utama algoritma kudu dimangerteni: amarga algoritma kasebut ora
ngerti apa tugas dawa utawa cendhak, banjur luwih dhisik dheweke nganggep tugas kasebut
cendhak lan menehi prioritas paling dhuwur. Yen iki tugas sing cendhak banget, mula
iku bakal rampung cepet, digunakake yen tugas dawa, iku bakal pindhah alon
prioritas mudhun lan bakal rauh mbuktekaken yen dheweke pancen tugas dawa sing ora
mbutuhake respon.
Tuladha 3: Kepiye babagan I/O?
Saiki ayo goleki conto I/O. Kaya sing kasebut ing aturan 4b,
yen proses ngeculake prosesor tanpa nggunakake kabeh wektu prosesor,
banjur tetep ing tingkat prioritas padha. Tujuan saka aturan iki cukup prasaja
- yen proyek interaktif nindakake akeh I / O operasi, Contone, nunggu
saka tombol pangguna utawa mouse meksa, tugas kuwi bakal mbebasake prosesor
sadurunge jendhela sing diwenehake. Kita ora pengin nyuda prioritas tugas kasebut,
lan kanthi mangkono bakal tetep ing tingkat sing padha.
Conto iki nuduhake carane algoritma bakal bisa karo proses kasebut - proyek interaktif B, sing mung mbutuhake CPU kanggo 1ms sadurunge eksekusi
I / O proses lan long-mlaku Proyek A, kang nglampahi kabeh wektu nggunakake CPU.
MLFQ njaga proses B dadi prioritas paling dhuwur amarga terus
ngeculake CPU. Yen B minangka tugas interaktif, mula algoritma wis entuk
Tujuan sampeyan kanggo mbukak tugas interaktif kanthi cepet.
Masalah karo algoritma MLFQ saiki
Ing conto sadurunge kita mbangun versi dhasar saka MLFQ. Lan misale jek dheweke
nindakake proyek kanthi apik lan jujur, nyebarake wektu CPU kanthi adil ing antarane
tugas dawa lan ngidini tugas cendhak utawa dhuwur-volume
nggarap I / O kanthi cepet. Sayange, pendekatan iki ngemot sawetara
masalah serius.
Sepisanan, masalah keluwen: yen sistem wis akeh interaktif
tugas, banjur padha bakal nganggo kabeh wektu prosesor lan kanthi mangkono ora siji kanggo dangu
tugas ora bakal bisa kaleksanan (padha kaliren).
Kaping kalih, pangguna pinter bisa nulis program supaya
ngapusi scheduler. Deception dumunung ing nindakake soko kanggo meksa
Penjadwal menehi proses luwih akeh wektu CPU. Algoritma sing
diterangake ing ndhuwur cukup ngrugekke kanggo serangan padha: sadurunge jendhela wektu praktis
rampung, sampeyan kudu nindakake operasi I/O (kanggo sawetara, ora ketompo file apa)
lan kanthi mangkono mbebasake CPU. Prilaku kasebut bakal ngidini sampeyan tetep padha
antrian dhewe lan maneh persentasi luwih gedhe saka wektu CPU. Yen sampeyan nindakake
iki bener (contone, nglakokake 99% wektu jendhela sadurunge ngeculake CPU),
tugas kuwi mung bisa monopolize prosesor.
Pungkasan, program bisa ngganti prilaku saka wektu. Tugas-tugas kuwi
kang digunakake CPU bisa dadi interaktif. Ing conto kita, padha
tugas ora bakal nampa perawatan padha pantes saka panjadwal minangka liyane bakal
(wiwit) tugas interaktif.
Pitakonan kanggo pamirsa: serangan apa ing panjadwal sing bisa ditindakake ing jagad modern?
Upaya 2: Nambah prioritas
Ayo dadi nyoba kanggo ngganti aturan lan ndeleng apa kita bisa supaya masalah karo
pasa. Apa kita bisa nindakake kanggo mesthekake yen gegandhengan
Tugas CPU bakal entuk wektu (sanajan ora suwe).
Minangka solusi prasaja kanggo masalah, sampeyan bisa suggest periodik
mundhakaken prioritas kabeh tugas kuwi ing sistem. Ana akeh cara
Kanggo entuk iki, ayo nyoba ngleksanakake prasaja minangka conto: nerjemahake
kabeh tugas langsung diwenehi prioritas paling dhuwur, mula aturan anyar:
- Aturan5: Sawise wektu tartamtu S, mindhah kabeh tugas ing sistem kanggo antrian paling dhuwur.
Aturan anyar kita ngrampungake rong masalah bebarengan. Kaping pisanan, proses
dijamin ora keluwen: tugas sing ana ing prioritas paling dhuwur bakal dibagi
wektu CPU miturut algoritma RR lan kanthi mangkono kabeh pangolahan bakal nampa
wektu CPU. Kapindho, yen sawetara proses sing sadurunge digunakake
mung prosesor dadi interaktif, iku bakal tetep ing antrian karo paling dhuwur
prioritas sawise nampa nambah siji-wektu ing prioritas kanggo paling dhuwur.
Ayo padha ndeleng conto. Ing skenario iki, nimbang siji proses nggunakake
CPU lan loro interaktif, pangolahan singkat. Ing sisih kiwa ing tokoh, tokoh nuduhake prilaku tanpa promosi prioritas, lan kanthi mangkono tugas long-mlaku wiwit keluwen sawise loro tugas interaktif teka ing sistem. Ing gambar ing sisih tengen, paningkatan prioritas ditindakake saben 50ms lan kabeh proses dijamin nampa wektu CPU lan bakal diluncurake sacara periodik. 50ms ing kasus iki dijupuk minangka conto, ing kasunyatan nomer iki rada luwih.
Temenan, nambah wektu nambah periodik S ndadékaké kanggo
pitakonan logis: Nilai apa kudu disetel? Salah sijine sing diajeni
insinyur sistem John Ousterhout nyebutake jumlah kasebut ing sistem minangka voo-doo
pancet, wiwit padha ing sawetara cara dibutuhake tenung ireng kanggo bener
pameran. Lan, sayangé, S wis gondho kuwi. Yen sampeyan nyetel nilai banget
gedhe - tugas dawa bakal miwiti keluwen. Lan yen sampeyan nyetel regane sithik banget,
Tugas interaktif ora bakal nampa wektu CPU sing tepat.
Upaya 3: Akuntansi sing luwih apik
Saiki kita duwe masalah liyane kanggo ngatasi: carane ora
ngidini scheduler kita diapusi? Wong sing kudu disalahake kanggo kemungkinan iki yaiku
aturan 4a, 4b, sing ngidini proyek tetep prioritas, mbebasake prosesor
sadurunge wektu sing wis ditemtokake. Carane menehi hasil karo iki?
Solusi ing kasus iki bisa dianggep accounting luwih saka wektu CPU ing saben
tingkat MLFQ. Tinimbang lali wektu program digunakake
prosesor kanggo periode diparengake, iku kudu dijupuk menyang akun lan disimpen. Sawise
proses wis nggunakake wektu sing wis ditemtokake, kudu diturunake menyang sabanjure
tingkat prioritas. Saiki ora ketompo carane proses bakal nggunakake wektu - carane
terus-terusan ngitung ing prosesor utawa minangka sawetara telpon. Mangkono,
aturan 4 kudu ditulis maneh menyang wangun ing ngisor iki:
- Aturan4: Sawise tugas wis digunakake munggah wektu diparengake ing antrian saiki (ora ketompo carane kakehan mbebasake CPU), prioritas tugas sudo (ngobahake mudhun antrian).
Ayo ndeleng conto:
»
Tokoh nuduhake apa mengkono yen sampeyan nyoba kanggo ngapusi panjadwal, kaya
yen karo aturan sadurunge 4a, 4b asil ing sisih kiwa bakal dijupuk. Sugeng anyar
aturan iku asil ing sisih tengen. Sadurunge proteksi, proses apa wae bisa nelpon I/O sadurunge rampung lan
mangkono dominasi CPU, sawise mbisakake pangayoman, preduli saka prilaku
I / O, kang isih bakal pindhah mudhun ing antrian lan kanthi mangkono ora bakal bisa kanggo dishonestly
njupuk liwat sumber daya CPU.
Ngapikake MLFQ lan masalah liyane
Kanthi dandan ing ndhuwur teka masalah anyar: salah siji sing utama
Pitakonan - kepiye paramèter panjadwal kasebut? Sing. Sepira kudune
antrian? Apa ukuran jendhela program ing antrian? Carane
Prioritas program kudu asring tambah supaya ora keluwen lan
njupuk menyang akun owah-owahan ing prilaku program? Ora ana jawaban sing prasaja kanggo pitakonan kasebut
jawaban lan mung nyobi karo kathah lan konfigurasi sakteruse
planner bisa mimpin kanggo sawetara imbangan puas.
Contone, paling implementasine MLFQ ngidini sampeyan nemtokake beda
interval wektu kanggo antrian beda. Antrian prioritas dhuwur biasane
interval cendhak diwènèhaké. Antrian kasebut kalebu tugas interaktif,
ngoper antarane kang cukup sensitif lan kudu njupuk 10 utawa kurang
ms. Ing kontras, antrian kurang prioritas kalebu tugas long-mlaku sing digunakake
CPU. Lan ing kasus iki, interval wektu dawa pas banget (100ms).
Ing conto iki ana 2 tugas sing makarya ing antrian prioritas dhuwur 20
ms, dipérang dadi 10ms windows. 40ms ing antrian tengah (20ms jendhela) lan ing prioritas kurang
Jendhela wektu antrian dadi 40ms ing ngendi tugas rampung.
Implementasi MLFQ Solaris OS minangka kelas panjadwal wektu bareng.
Planner bakal nyedhiyani pesawat saka tabel sing nemtokake persis minangka ngirim
prioritas proses owah-owahan liwat Course saka urip, apa kudu ukuran
jendhela sing diparengake lan sepira kerepe sampeyan kudu ngunggahake prioritas tugas. Administrator
sistem bisa sesambungan karo tabel iki lan nimbulaké jadwal tumindak
beda. Kanthi gawan, Tabel iki wis 60 antrian karo Tambah bertahap
ukuran jendhela saka 20ms (prioritas dhuwur) kanggo sawetara atus ms (prioritas kurang), lan
uga karo ngedongkrak kabeh tugas sapisan saben detik.
Planners MLFQ liyane ora nggunakake meja utawa tartamtu
aturan sing diterangake ing kuliah iki, ing nalisir, padha ngetung prioritas nggunakake
rumus matematika. Contone, panjadwal FreeBSD nggunakake rumus kanggo
ngetung prioritas saiki tugas adhedhasar suwene proses
digunakake CPU. Kajaba iku, panggunaan CPU saya suwe saya suwe, lan liya-liyane
Mangkono, nambah prioritas kedadeyan rada beda tinimbang sing kasebut ing ndhuwur. Iki bener
disebut algoritma bosok. Wiwit versi 7.1, FreeBSD wis nggunakake panjadwal ULE.
Pungkasan, akeh panjadwal duwe fitur liyane. Contone, sawetara
schedulers cadangan tingkat paling dhuwur kanggo operasi sistem operasi lan kanthi mangkono
Mangkono, ora ana proses pangguna sing bisa nampa prioritas paling dhuwur ing
sistem. Sawetara sistem ngidini sampeyan menehi saran kanggo mbantu
planner bisa nyetel prioritas bener. Contone, nggunakake printah becik
sampeyan bisa nambah utawa nyuda prioritas tugas lan kanthi mangkono nambah utawa
nyuda kemungkinan program nggunakake wektu CPU.
MLFQ: Ringkesan
Kita wis diterangake pendekatan planning disebut MLFQ. Asmane
terlampir ing prinsip operasi - wis sawetara antrian lan nggunakake saran
kanggo nemtokake prioritas tugas.
Wangun pungkasan saka aturan bakal kaya ing ngisor iki:
- Aturan1: Yen prioritas(A) > Prioritas(B), tugas A bakal diluncurake (B ora bakal)
- Aturan2: Yen prioritas(A) = Prioritas(B), A&B diwiwiti nganggo RR
- Aturan3: Nalika tugas lumebu sistem, diselehake ing antrian prioritas paling dhuwur.
- Aturan4: Sawise tugas wis digunakake munggah wektu diparengake ing antrian saiki (ora ketompo carane kakehan mbebasake CPU), prioritas tugas sudo (ngobahake mudhun antrian).
- Aturan5: Sawise wektu tartamtu S, mindhah kabeh tugas ing sistem kanggo antrian paling dhuwur.
MLFQ menarik amarga alasan ing ngisor iki - tinimbang mbutuhake kawruh babagan
sifat tugas ing advance, algoritma nyinaoni prilaku kepungkur saka tugas lan mranata
prioritas miturut. Mangkono, dheweke nyoba njagong ing rong kursi bebarengan - kanggo entuk produktivitas kanggo tugas-tugas cilik (SJF, STCF) lan kanthi jujur mbukak dawa,
jobs CPU-loading. Mula, akeh sistem, kalebu BSD lan turunane,
Solaris, Windows, Mac nggunakake sawetara wangun algoritma minangka panjadwal
MLFQ minangka dhasar.
Bahan tambahan:
- (komputerisasi)
Source: www.habr.com