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 =)
Bubuka keur Scheduler
Intina masalah: Kumaha carana ngamekarkeun kawijakan scheduler
Kumaha dasarna kerangka kawijakan scheduler kedah dirancang? Naon anu kedah janten asumsi konci? Métrik naon anu penting? Naon téhnik dasar anu dipaké dina sistem komputasi mimiti?
Asumsi Beban Gawé
Sateuacan ngabahas kawijakan anu mungkin, hayu urang ngadamel sababaraha digressions nyederhanakeun ngeunaan prosés anu ngajalankeun dina sistem, anu sacara koléktif disebut beban gawé. Nangtukeun beban kerja mangrupikeun bagian anu penting dina kawijakan ngawangun, sareng langkung seueur anjeun terang ngeunaan beban kerja, langkung saé kawijakan anjeun tiasa nyerat.
Hayu urang nyieun asumsi di handap ngeunaan prosés ngajalankeun dina sistem, sok disebut oge jobs (tugas). Ampir sakabéh asumsi ieu teu realistis, tapi diperlukeun pikeun ngembangkeun pamikiran.
- Unggal tugas dijalankeun pikeun jumlah waktos anu sami,
- Sadaya tugas diatur sakaligus,
- Tugas anu ditugaskeun dugi ka réngsé,
- Sadaya tugas ngan ukur nganggo CPU,
- Waktu ngajalankeun unggal tugas dipikanyaho.
Métrik scheduler
Salian sababaraha asumsi ngeunaan beban, alat sejen pikeun ngabandingkeun kawijakan scheduling béda diperlukeun: metrics scheduler. A métrik ngan ukur sababaraha ukuran. Aya sababaraha métrik anu tiasa dianggo pikeun ngabandingkeun jadwal.
Contona, urang bakal ngagunakeun métrik disebut waktos turnaround (waktu balik). Waktu turnaround tugas diartikeun salaku bédana antara waktu parantosan tugas jeung waktu datangna tugas dina sistem.
Tturnaround=Tcompletion-Tarrival
Kusabab urang nganggap yén sadaya tugas sumping dina waktos anu sami, maka Ta = 0 sahingga Tt = Tc. Nilai ieu sacara alami bakal robih nalika urang ngarobih asumsi di luhur.
Métrik séjén - fairness (adil, jujur). Produktivitas sareng kaadilan sering janten ciri anu nentang dina perencanaan. Contona, scheduler nu bisa ngaoptimalkeun kinerja, tapi dina biaya ngantosan tugas séjén pikeun ngajalankeun, sahingga ngurangan fairness.
Kaluar heula (FIFO)
Algoritma paling dasar anu tiasa urang laksanakeun disebut FIFO atanapi mimiti datang (asup), mimiti dilayanan (kaluar). Algoritma ieu ngagaduhan sababaraha kaunggulan: éta gampang pisan pikeun diimplementasikeun sareng cocog sareng sadaya asumsi urang sareng ngalaksanakeun padamelan anu saé.
Hayu urang nempo conto basajan. Sebutkeun 3 tugas disetél sakaligus. Tapi hayu urang nganggap yén tugas A anjog saeutik saméméhna ti sakabeh batur, ku kituna bakal muncul dina daptar palaksanaan saméméhna ti batur, kawas B relatif ka C. Hayu urang nganggap yén unggal sahijina bakal dieksekusi pikeun 10 detik. Naon waktos rata-rata pikeun ngarengsekeun tugas-tugas ieu dina hal ieu?
Ku cacah nilai - 10+20+30 sarta ngabagi 3, urang meunang rata-rata waktu palaksanaan program sarua jeung 20 detik.
Ayeuna hayu urang coba ngarobah asumsi urang. Khususna, asumsi 1 sahingga urang moal deui nganggap yén unggal tugas nyandak waktos anu sami pikeun dieksekusi. Kumaha FIFO bakal ngalakukeun waktos ieu?
Tétéla, waktu palaksanaan tugas béda boga dampak pisan négatip on produktivitas algoritma FIFO. Anggap tugas A butuh 100 detik pikeun ngarengsekeun, sedengkeun B jeung C masih butuh 10 detik unggal.
Salaku bisa ditempo ti gambar, waktu rata pikeun sistem bakal jadi (100 + 110 + 120) / 3 = 110. Pangaruh ieu disebut pangaruh konvoi, Nalika sababaraha pamakéna jangka pondok sumberdaya a bakal antrian sanggeus konsumen beurat. Ieu kawas antrian di toko grocery lamun aya customer di hareup anjeun kalayan karanjang pinuh. Solusi anu pangsaéna pikeun masalah éta nyaéta nyobian ngarobih kasir atanapi bersantai sareng ngambekan jero.
Proyék pondok munggaran
Naha mungkin pikeun kumaha waé ngabéréskeun kaayaan anu sami sareng prosés beurat? Tangtu. tipe séjén tata disebutProyék pondok munggaran (SJF). Algoritma na ogé rada primitif - sakumaha nami nunjukkeun, tugas anu paling pondok bakal diluncurkeun heula, hiji-hiji.
Dina conto ieu, hasil tina ngajalankeun prosés anu sami bakal janten paningkatan dina rata-rata waktos turnaround program sareng bakal sami sareng 50 tibatan 110, anu ampir 2 kali langkung saé.
Ku kituna, pikeun asumsi dibikeun yén sakabéh tugas datangna dina waktos anu sareng, algoritma SJF sigana algoritma paling optimal. Sanajan kitu, asumsi urang masih teu sigana realistis. Waktos ieu urang ngarobih asumsi 2 sareng waktos ieu ngabayangkeun yén tugas tiasa hadir iraha waé, sareng henteu sadayana dina waktos anu sami. Masalah naon anu tiasa nyababkeun ieu?
Hayu urang ngabayangkeun yén tugas A (100c) datang munggaran tur mimitian dieksekusi. Dina t=10, tugas B jeung C datang, nu masing-masing butuh 10 detik. Janten waktos palaksanaan rata-rata nyaéta (100+(110-10)+(120-10))3 = 103. Naon anu tiasa dilakukeun ku scheduler pikeun ningkatkeun ieu?
Waktos-to-Rengse Kahiji (STCF)
Pikeun ningkatkeun kaayaan, urang ngaleungitkeun asumsi 3 yén program diluncurkeun sareng jalan dugi ka réngsé. Salaku tambahan, urang peryogi dukungan hardware sareng, sakumaha anu anjeun panginten, kami bakal nganggo timer ngaganggu tugas ngajalankeun na konteks switching. Ku kituna, scheduler nu bisa ngalakukeun hiji hal di momen tugas B, C anjog - eureun executing tugas A sarta nempatkeun tugas B jeung C kana processing jeung, sanggeus parantosan maranéhna, nuluykeun executing prosés A. scheduler sapertos disebut. STCFatawa Proyék Preemptive Kahiji.
Hasil tina planner ieu bakal hasil kieu: ((120-0)+(20-10)+(30-10))/3=50. Janten, penjadwal sapertos kitu janten langkung optimal pikeun tugas urang.
Métrik Tanggapan Time
Ku kituna, lamun urang nyaho waktu ngajalankeun tugas jeung tugas ieu ngan ngagunakeun CPU, STCF bakal jadi solusi pangalusna. Sareng sakali dina jaman awal, algoritma ieu damel saé. Nanging, pangguna ayeuna nyéépkeun waktosna di terminal sareng ngarepkeun pangalaman interaktif anu produktif. Janten métrik anyar lahir - waktos respon (réspon).
Waktu respon diitung saperti kieu:
Tresponse=Tfirstrun−Tarrival
Ku kituna, pikeun conto saméméhna, waktu respon bakal: A=0, B=0, C=10 (abg=3,33).
Sareng tétéla yén algoritma STCF henteu saé dina kaayaan dimana 3 tugas sumping dina waktos anu sami - éta kedah ngantosan dugi ka tugas-tugas alit parantos réngsé. Janten algoritmana saé pikeun métrik waktos turnaround, tapi goréng pikeun métrik interaktivitas. Bayangkeun upami anjeun linggih di terminal nyobian ngetik karakter kana redaktur sareng kedah ngantosan langkung ti 10 detik kusabab sababaraha tugas sanés nyandak CPU. Teu pikaresepeun pisan.
Janten urang nyanghareupan masalah anu sanés - kumaha urang tiasa ngawangun jadwal anu sénsitip kana waktos réspon?
Robin buleud
Algoritma dikembangkeun pikeun ngajawab masalah ieu Robin buleud (RR). Gagasan dasar anu cukup basajan: tinimbang ngajalankeun tugas dugi aranjeunna réngsé, urang bakal ngajalankeun tugas pikeun kurun waktu nu tangtu (disebut nyiksikan waktu) lajeng pindah ka tugas sejen tina antrian. Algoritma ngulang padamelan na dugi ka sadaya tugas réngsé. Dina hal ieu, waktos ngajalankeun program kedah sababaraha kali tina waktos saatos éta timer bakal ngaganggu prosés. Contona, upami hiji timer interrupts hiji prosés unggal x = 10ms, mangka ukuran jandela palaksanaan prosés kudu kelipatan 10 sarta jadi 10,20 atawa x * 10.
Hayu urang nempo conto: tugas ABC datangna sakaligus dina sistem jeung unggal sahijina hayang ngajalankeun pikeun 5 detik. Algoritma SJF bakal ngalengkepan unggal tugas sateuacan ngamimitian anu sanés. Sabalikna, algoritma RR kalayan jandela peluncuran = 1s bakal ngaliwat tugas sapertos kieu (Gbr. 4.3):
(SJF Deui (Bad for Response Time)
(Round Robin (Alus Pikeun Waktu Tanggapan)
Waktu respon rata pikeun algoritma RR nyaéta (0+1+2)/3=1, sedengkeun pikeun SJF (0+5+10)/3=5.
Logis pikeun nganggap yén jandela waktos mangrupikeun parameter anu penting pisan pikeun RR; anu langkung alit, langkung luhur waktos réspon. Nanging, anjeun henteu kedah alit teuing, sabab waktos gentos kontéks ogé bakal maénkeun peran dina pagelaran umum. Janten, pilihan waktos palaksanaan jandela diatur ku arsiték OS sareng gumantung kana tugas anu direncanakeun pikeun dilaksanakeun di jerona. Ngalihkeun kontéks sanés ngan ukur operasi jasa anu nyéépkeun waktos - program anu dijalankeun ngoperasikeun seueur hal anu sanés, contona, rupa-rupa caches, sareng unggal saklar kedah ngahemat sareng malikkeun lingkungan ieu, anu ogé tiasa nyandak seueur waktos. waktos.
RR mangrupikeun jadwal anu saé upami urang ngan ukur nyarios ngeunaan métrik waktos réspon. Tapi kumaha métrik waktos turnaround tugas bakal kalakuanana sareng algoritma ieu? Mertimbangkeun conto di luhur, nalika waktu operasi A, B, C = 5s sarta anjog dina waktos anu sareng. Tugas A bakal réngsé dina 13, B dina 14, C dina 15s sarta rata-rata waktos turnaround bakal 14s. Ku kituna, RR teh algoritma awon pikeun métrik elehan.
Dina istilah anu leuwih umum, sagala algoritma RR-tipe adil; éta ngabagi waktu CPU sarua antara sakabéh prosés. Ku kituna, métrik ieu terus-terusan konflik saling.
Ku kituna, urang gaduh sababaraha algoritma kontras jeung dina waktos anu sareng masih aya sababaraha asumsi ditinggalkeun - yén waktu tugas geus dipikawanoh tur tugas ngan ngagunakeun CPU.
Pergaulan jeung I/O
Anu mimiti, hayu urang hapus asumsi 4 yén prosésna ngan ukur nganggo CPU; sacara alami, ieu sanés masalahna sareng prosés tiasa ngaksés alat-alat sanés.
Momen sagala prosés requests hiji I / O operasi, prosés asup ka kaayaan diblokir, ngantosan I / O réngsé. Upami I / O dikirim ka hard drive, operasi sapertos kitu tiasa nyandak sababaraha mdet atanapi langkung lami, sareng prosésor bakal dianggurkeun dina waktos ayeuna. Salila ieu, scheduler tiasa ngeusian prosésor sareng prosés anu sanés. Kaputusan salajengna anu kedah dilakukeun ku penjadwal nyaéta nalika prosésna bakal ngalengkepan I / O na. Nalika ieu kajadian, hiji interupsi bakal lumangsung sarta OS bakal nempatkeun prosés nu disebut I / O kana kaayaan siap.
Hayu urang nempo conto sababaraha masalah. Tiap di antarana merlukeun 50ms waktu CPU. Tapi, anu kahiji bakal ngaksés I/O unggal 10ms (anu ogé bakal dieksekusi unggal 10ms). Jeung prosés B saukur ngagunakeun processor 50ms tanpa I / O.
Dina conto ieu urang bakal nganggo scheduler STCF. Kumaha scheduler bakal kalakuanana lamun prosés kawas A diluncurkeun dina eta? Anjeunna bakal ngalakukeun di handap ieu: mimitina anjeunna bakal lengkep ngerjakeun prosés A, teras prosés B.
Pendekatan tradisional pikeun ngabéréskeun masalah ieu nyaéta pikeun ngubaran unggal 10 ms subtugas prosés A salaku tugas anu misah. Ku kituna, nalika dimimitian ku algoritma STJF, pilihan antara tugas 50 ms jeung tugas 10 ms atra. Teras, nalika subtugas A parantos réngsé, prosés B sareng I/O bakal diluncurkeun. Saatos I / O réngsé, éta bakal jadi adat pikeun ngamimitian prosés 10ms A deui tinimbang prosés B. Ku cara kieu, kasebut nyaéta dimungkinkeun pikeun nerapkeun tumpang tindihna, dimana CPU dipaké ku prosés sejen bari hiji munggaran ngantosan Abdi / O. Hasilna, sistem langkung saé dianggo - dina waktos prosés interaktif ngantosan I / O, prosés sanésna tiasa dilaksanakeun dina prosésor.
Oracle geus euweuh
Ayeuna hayu urang cobaan pikeun nyingkirkeun anggapan yén waktu ngajalankeun tugasna dipikanyaho. Ieu umumna asumsi awon na paling unrealistic dina sakabéh daptar. Nyatana, dina rata-rata OS biasa, OS sorangan biasana terang sakedik ngeunaan waktos palaksanaan tugas, janten kumaha anjeun tiasa ngawangun scheduler tanpa terang sabaraha lila tugas bakal dieksekusi? Panginten urang tiasa nganggo sababaraha prinsip RR pikeun ngabéréskeun masalah ieu?
hasil
Urang nempo gagasan dasar scheduling tugas jeung nempo 2 kulawarga schedulers. Anu kahiji ngamimitian tugas anu paling pondok heula sahingga ningkatkeun waktos turnaround, sedengkeun anu kadua torn antara sadaya tugas anu sami, ningkatkeun waktos réspon. Duanana algoritma anu goréng dimana algoritma kulawarga séjén anu alus. Urang ogé nempo kumaha pamakéan paralel CPU jeung I / O bisa ningkatkeun kinerja, tapi teu ngajawab masalah jeung OS clairvoyance. Sareng dina palajaran salajengna urang bakal ningali hiji planner anu ningali kana masa lalu anu langsung sareng nyobian ngaduga masa depan. Sarta eta disebut antrian eupan balik multi-tingkat.
sumber: www.habr.com