Pengenalan kepada Sistem Operasi
Hai Habr! Saya ingin membawa perhatian anda satu siri artikel-terjemahan satu kesusasteraan yang menarik pada pendapat saya - OSTEP. Bahan ini membincangkan secara mendalam tentang kerja sistem pengendalian seperti unix, iaitu, bekerja dengan proses, pelbagai penjadual, memori, dan komponen lain yang serupa yang membentuk OS moden. Anda boleh melihat asal semua bahan di sini . Sila ambil perhatian bahawa terjemahan itu dibuat secara tidak profesional (agak bebas), tetapi saya harap saya mengekalkan maksud umum.
Kerja makmal mengenai subjek ini boleh didapati di sini:
Bahagian lain:
Anda juga boleh menyemak saluran saya di =)
Perancangan: Barisan Maklum Balas Pelbagai Peringkat
Dalam kuliah ini, kita akan bercakap tentang masalah membangunkan salah satu pendekatan yang paling terkenal
perancangan, yang dipanggil Barisan Maklum Balas Pelbagai Peringkat (MLFQ). Penjadual MLFQ pertama kali diterangkan pada tahun 1962 oleh Fernando J. CorbatΓ³ dalam sistem yang dipanggil
Sistem Perkongsian Masa yang Serasi (CTSS). Kerja-kerja ini (termasuk kerja-kerja kemudian
Multics) kemudiannya dicalonkan untuk Anugerah Turing. Penjadual adalah
kemudiannya dipertingkatkan dan memperoleh rupa yang boleh didapati di dalamnya
beberapa sistem moden.
Algoritma MLFQ cuba menyelesaikan 2 masalah bertindih asas.
Pertama, ia cuba mengoptimumkan masa pusing ganti, yang, seperti yang kita bincangkan dalam kuliah sebelumnya, dioptimumkan dengan kaedah bermula di kepala barisan paling banyak.
tugasan pendek. Walau bagaimanapun, OS tidak tahu berapa lama proses ini atau itu akan berjalan, dan ini
pengetahuan yang diperlukan untuk operasi SJF, algoritma STCF. Kedua, MLFQ sedang mencuba
menjadikan sistem responsif untuk pengguna (contohnya, bagi mereka yang duduk dan
merenung skrin sementara menunggu tugasan selesai) dan dengan itu meminimumkan masa
tindak balas. Malangnya, algoritma seperti RR mengurangkan masa tindak balas, tetapi
mempunyai kesan buruk pada metrik masa pemulihan. Oleh itu masalah kami: Bagaimana untuk mereka bentuk
penjadual yang akan memenuhi keperluan kami tanpa mengetahui apa-apa
sifat proses, secara umum? Bagaimanakah penjadual dapat mempelajari ciri-ciri tugas,
yang mana ia dilancarkan dan dengan itu membuat keputusan penjadualan yang lebih baik?
Intipati masalah: Bagaimana untuk merancang penetapan tugas tanpa pengetahuan yang sempurna?
Cara mereka bentuk penjadual yang meminimumkan masa tindak balas secara serentak
untuk tugasan interaktif dan pada masa yang sama meminimumkan masa pemulihan tanpa mengetahui
pengetahuan tentang masa pelaksanaan tugas?
Nota: belajar dari peristiwa sebelumnya
Barisan gilir MLFQ ialah contoh terbaik sistem yang dilatih
peristiwa masa lalu untuk meramalkan masa depan. Pendekatan sedemikian selalunya
terdapat dalam OS (Dan banyak cabang lain dalam sains komputer, termasuk cawangan
ramalan perkakasan dan algoritma caching). Perjalanan yang serupa
dicetuskan apabila tugasan mempunyai fasa tingkah laku dan dengan itu boleh diramal.
Walau bagaimanapun, anda harus berhati-hati dengan teknik ini kerana ramalan adalah sangat mudah
mungkin ternyata salah dan menyebabkan sistem membuat keputusan yang lebih buruk daripada
akan menjadi tanpa pengetahuan sama sekali.
MLFQ: Peraturan Asas
Pertimbangkan peraturan asas algoritma MLFQ. Dan walaupun pelaksanaan algoritma ini
terdapat beberapa, pendekatan asas adalah serupa.
Dalam pelaksanaan yang akan kami pertimbangkan, MLFQ akan mempunyai beberapa
baris gilir berasingan, setiap satunya akan mempunyai keutamaan yang berbeza. bila-bila masa,
tugas yang sedia untuk dilaksanakan adalah dalam baris gilir yang sama. MLFQ menggunakan keutamaan,
untuk memutuskan tugas mana yang hendak dijalankan untuk pelaksanaan, i.e. tugas dengan lebih tinggi
keutamaan (tugas daripada baris gilir dengan keutamaan tertinggi) akan dilancarkan pada mulanya
beratur.
Sudah tentu, terdapat lebih daripada satu tugasan dalam baris gilir tertentu, jadi
jadi mereka akan mempunyai keutamaan yang sama. Dalam kes ini, mekanisme akan digunakan
RR untuk perancangan pelancaran antara tugas-tugas ini.
Oleh itu, kami sampai pada dua peraturan asas untuk MLFQ:
- Peraturan1: Jika keutamaan(A) > Keutamaan(B), tugasan A akan dijalankan (B tidak akan)
- Peraturan2: Jika keutamaan(A) = Keutamaan(B), A&B dimulakan menggunakan RR
Berdasarkan perkara di atas, elemen utama untuk merancang MLFQ ialah
adalah keutamaan. Daripada memberi keutamaan tetap kepada masing-masing
tugas, MLFQ mengubah keutamaannya bergantung pada tingkah laku yang diperhatikan.
Sebagai contoh, jika tugas sentiasa berhenti pada CPU semasa menunggu input papan kekunci,
MLFQ akan mengekalkan keutamaan proses yang tinggi kerana begitulah caranya
proses interaktif harus berfungsi. Jika, sebaliknya, tugas itu sentiasa dan
adalah intensif CPU untuk tempoh yang lama, MLFQ akan menurunkan tarafnya
keutamaan. Oleh itu, MLFQ akan mengkaji tingkah laku proses pada masa ia dijalankan.
dan menggunakan tingkah laku.
Mari kita lukiskan contoh tentang rupa baris gilir pada satu ketika
masa dan kemudian anda mendapat sesuatu seperti ini:
Dalam skim ini, 2 proses A dan B berada dalam baris gilir dengan keutamaan tertinggi. Proses
C berada di suatu tempat di tengah, dan proses D berada di hujung baris gilir. Mengikut perkara di atas
penerangan tentang algoritma MLFQ, penjadual hanya akan melaksanakan tugas dengan yang tertinggi
keutamaan mengikut RR, dan tugas C, D akan tiada kerja.
Sememangnya, syot kilat statik tidak akan memberikan gambaran lengkap tentang cara MLFQ berfungsi.
Adalah penting untuk memahami dengan tepat bagaimana gambar berubah dari semasa ke semasa.
Percubaan 1: Bagaimana untuk menukar keutamaan
Pada ketika ini, anda perlu memutuskan bagaimana MLFQ akan mengubah tahap keutamaan
tugasan (dan dengan itu kedudukan tugasan dalam baris gilir) semasa kitaran hayatnya. Untuk
ini adalah perlu untuk mengingati aliran kerja: jumlah tertentu
tugas interaktif dengan masa berjalan yang singkat (dan dengan itu pelepasan kerap
CPU) dan beberapa tugas panjang yang menggunakan CPU sepanjang masa kerja mereka, manakala
masa tindak balas untuk tugasan sedemikian tidak penting. Dan supaya anda boleh membuat percubaan pertama
melaksanakan algoritma MLFQ dengan peraturan berikut:
- Peraturan3: Apabila tugasan memasuki sistem, ia diletakkan dalam baris gilir dengan yang tertinggi
- keutamaan.
- Rule4a: Jika tugasan menggunakan seluruh tetingkap masanya, maka tugas itu
- keutamaan diturunkan.
- Peraturan4b: Jika Tugasan mengeluarkan CPU sebelum tetingkap masanya tamat, maka ia
- tetap dengan keutamaan yang sama.
Contoh 1: Tugasan jangka panjang tunggal
Seperti yang anda lihat dalam contoh ini, tugas semasa kemasukan ditetapkan dengan yang tertinggi
keutamaan. Selepas tetingkap masa 10ms, proses diturunkan dalam keutamaan.
penjadual. Selepas tetingkap kali seterusnya, tugas akhirnya diturunkan taraf kepada
keutamaan terendah dalam sistem, di mana ia kekal.
Contoh 2: Mengambil tugasan pendek
Sekarang mari kita lihat contoh bagaimana MLFQ akan cuba mendekati SJF. Dalam itu
contoh, dua tugasan: A, iaitu tugasan yang berpanjangan secara berterusan
menduduki CPU dan B, yang merupakan tugas interaktif yang singkat. Kiranya
bahawa A telah pun berjalan untuk beberapa lama pada masa tugas B tiba.
Graf ini menunjukkan keputusan senario. Tugasan A, seperti mana-mana tugasan,
menggunakan CPU berada di bahagian paling bawah. Tugasan B akan tiba pada masa T=100 dan akan
diletakkan dalam barisan keutamaan tertinggi. Memandangkan masa berjalan adalah singkat,
ia akan selesai sebelum ia mencapai baris gilir terakhir.
Daripada contoh ini, anda harus memahami matlamat utama algoritma: kerana algoritma tidak
mengetahui tugas yang panjang atau yang pendek, maka pertama sekali dia menganggap bahawa tugas itu
pendek dan memberikan keutamaan tertinggi. Jika ia benar-benar tugas yang singkat, maka
ia akan dilaksanakan dengan cepat, sebaliknya jika ia adalah tugas yang panjang ia akan bergerak perlahan
dalam keutamaan ke bawah dan tidak lama lagi akan membuktikan bahawa dia sememangnya satu tugas yang panjang yang tidak
memerlukan tindak balas.
Contoh 3: Bagaimana dengan I/O?
Sekarang mari kita lihat contoh I/O. Seperti yang dinyatakan dalam peraturan 4b,
jika proses melepaskan pemproses tanpa menggunakan sepenuhnya masa pemprosesnya,
maka ia kekal pada tahap keutamaan yang sama. Tujuan peraturan ini agak mudah.
- jika kerja interaktif melakukan banyak I/O, contohnya, menunggu
daripada ketukan kekunci atau tetikus pengguna, tugas sedemikian akan membebaskan pemproses
sebelum tetingkap yang diperuntukkan. Kami tidak ingin meninggalkan tugas keutamaan sedemikian,
dan dengan itu ia akan kekal pada tahap yang sama.
Contoh ini menunjukkan cara algoritma akan berfungsi dengan proses sedemikian - tugas interaktif B, yang hanya memerlukan CPU selama 1ms sebelum melaksanakan
Proses I/O dan kerja A yang panjang, yang menggunakan CPU sepanjang masa.
MLFQ mengekalkan proses B pada keutamaan tertinggi kerana ia berterusan
lepaskan CPU. Jika B ialah tugasan interaktif, maka algoritma dalam kes ini telah sampai
tujuannya adalah untuk melancarkan tugas interaktif dengan cepat.
Masalah dengan algoritma MLFQ semasa
Dalam contoh sebelumnya, kami telah membina versi asas MLFQ. Dan nampaknya dia
melakukan tugasnya dengan baik dan adil, mengagihkan masa CPU secara adil antara
tugasan yang panjang dan membenarkan tugasan pendek atau tugasan yang banyak diakses
kepada I/O untuk memproses dengan cepat. Malangnya, pendekatan ini mengandungi beberapa
masalah yang serius.
Pertama, masalah kelaparan: jika sistem akan mempunyai banyak interaktif
tugasan, maka mereka akan menggunakan semua masa pemproses dan dengan itu tidak satu pun untuk masa yang lama
tugas tidak akan mendapat peluang untuk dilaksanakan (mereka kelaparan).
Kedua, pengguna pintar boleh menulis program mereka supaya
menipu penjadual. Penipuan terletak pada melakukan sesuatu untuk memaksa
penjadual untuk memberi proses lebih masa CPU. Algoritma yang
yang diterangkan di atas agak terdedah kepada serangan sedemikian: sebelum tetingkap masa boleh dikatakan
selesai, anda perlu melakukan operasi I / O (kepada sesetengah orang, tidak kira fail mana)
dan dengan itu membebaskan CPU. Tingkah laku sedemikian akan membolehkan anda kekal dalam keadaan yang sama
baris gilir itu sendiri dan sekali lagi mendapat peratusan masa CPU yang lebih besar. Jika selesai
ini betul (mis. jalankan 99% masa tetingkap sebelum melepaskan CPU),
tugas sedemikian hanya boleh memonopoli pemproses.
Akhirnya, program boleh mengubah tingkah lakunya dari semasa ke semasa. Tugas-tugas itu
yang menggunakan CPU boleh menjadi interaktif. Dalam contoh kami, serupa
tugas tidak akan menerima rawatan yang sewajarnya daripada penjadual, seperti yang dilakukan oleh orang lain
tugasan interaktif (asal).
Soalan untuk penonton: apakah serangan ke atas penjadual yang boleh dilakukan di dunia moden?
Percubaan 2: Tingkatkan keutamaan
Mari cuba ubah peraturan dan lihat sama ada kita boleh mengelakkan masalah dengannya
kelaparan. Apa yang boleh kita lakukan untuk memastikan yang berkaitan
Tugas CPU akan mendapat masanya (walaupun tidak lama).
Sebagai penyelesaian mudah kepada masalah tersebut, anda boleh mencadangkan secara berkala
meningkatkan keutamaan semua tugas tersebut dalam sistem. Terdapat banyak cara
Untuk mencapai matlamat ini, mari cuba laksanakan sesuatu yang mudah sebagai contoh: terjemah
semua tugas segera diberi keutamaan tertinggi, oleh itu peraturan baharu:
- Peraturan5: Selepas beberapa tempoh S, pindahkan semua tugasan dalam sistem ke baris gilir tertinggi.
Peraturan baharu kami menyelesaikan dua masalah sekaligus. Pertama, proses
dijamin tidak kebuluran: tugas dalam baris gilir tertinggi akan dikongsi
Masa CPU mengikut algoritma RR dan dengan itu semua proses akan menerima
masa pemproses. Kedua, jika beberapa proses yang digunakan sebelum ini
hanya pemproses menjadi interaktif, ia akan kekal dalam baris gilir dengan yang tertinggi
keutamaan selepas menerima rangsangan kepada keutamaan tertinggi sekali.
Pertimbangkan satu contoh. Dalam senario ini, pertimbangkan satu proses menggunakan
CPU dan dua proses pendek interaktif. Di sebelah kiri dalam rajah, rajah menunjukkan tingkah laku tanpa rangsangan keutamaan, dan dengan itu tugasan yang berjalan lama mula kebuluran selepas dua tugasan interaktif tiba pada sistem. Dalam rajah di sebelah kanan, setiap 50ms peningkatan keutamaan dilakukan dan dengan itu semua proses dijamin menerima masa pemproses dan akan dimulakan secara berkala. 50ms dalam kes ini diambil sebagai contoh, sebenarnya angka ini agak tinggi.
Adalah jelas bahawa penambahan masa kenaikan berkala S membawa kepada
soalan logik: apakah nilai yang perlu ditetapkan? Salah seorang yang layak
jurutera sistem John Ousterhout merujuk kepada kuantiti yang sama dalam sistem sebagai voo-doo
tetap, kerana mereka dalam beberapa cara memerlukan ilmu hitam untuk yang betul
dedahan. Dan, malangnya, S mempunyai rasa sedemikian. Jika anda menetapkan nilai juga
besar - tugas yang panjang akan kelaparan. Dan jika anda menetapkannya terlalu rendah,
tugas interaktif tidak akan menerima masa CPU yang betul.
Percubaan 3: Perakaunan yang Lebih Baik
Sekarang kita mempunyai satu lagi masalah untuk diselesaikan: bagaimana tidak
membenarkan untuk menipu penjadual kami? Penyebab kemungkinan ini adalah
peraturan 4a, 4b yang membenarkan kerja mengekalkan keutamaannya dengan membebaskan pemproses
sebelum tamat masa yang diperuntukkan. Bagaimana untuk menanganinya?
Penyelesaian dalam kes ini boleh dianggap sebagai perakaunan masa CPU yang lebih baik pada setiap satu
tahap MLFQ. Daripada melupakan masa program yang digunakan
pemproses untuk tempoh yang diperuntukkan, ia perlu diambil kira dan disimpan. Selepas
proses itu telah menghabiskan masa yang diperuntukkan, ia harus diturunkan ke peringkat seterusnya
tahap keutamaan. Sekarang tidak kira bagaimana proses itu akan menggunakan masanya - bagaimana
sentiasa mengira pada pemproses atau sebagai satu set panggilan. Oleh itu,
peraturan 4 hendaklah ditulis semula seperti berikut:
- Peraturan4: Selepas tugas telah menggunakan masa yang diperuntukkan dalam baris gilir semasa (tidak kira berapa kali ia membebaskan CPU), keutamaan tugas tersebut dikurangkan (ia bergerak ke bawah baris gilir).
Mari lihat contoh:
Β»
Rajah menunjukkan perkara yang berlaku jika anda cuba menipu penjadual seperti itu
jika dengan peraturan 4a sebelumnya, 4b akan menjadi keputusan di sebelah kiri. Selamat baru
peraturannya adalah hasilnya di sebelah kanan. Sebelum perlindungan, sebarang proses boleh memanggil I/O sebelum selesai dan
dengan itu menguasai CPU, selepas membolehkan perlindungan, tanpa mengira tingkah laku
I/O, dia masih akan bergerak ke bawah dalam baris gilir dan dengan itu tidak akan dapat melakukan secara tidak jujur
mengambil alih sumber CPU.
Menambah baik MLFQ dan isu-isu lain
Dengan penambahbaikan di atas, masalah baru timbul: salah satu yang utama
soalan - bagaimana untuk parameterkan penjadual sedemikian? Itu. Berapa yang sepatutnya
beratur? Apakah saiz tetingkap program dalam baris gilir? Bagaimana
program harus selalu diutamakan untuk mengelakkan kebuluran dan
untuk mengambil kira perubahan tingkah laku program? Tiada jawapan mudah untuk soalan-soalan ini
tindak balas dan hanya eksperimen dengan beban dan konfigurasi seterusnya
penjadual boleh membawa kepada beberapa baki yang memuaskan.
Sebagai contoh, kebanyakan pelaksanaan MLFQ membolehkan anda menetapkan yang berbeza
slot masa untuk baris gilir yang berbeza. Barisan beratur keutamaan tinggi biasanya
selang pendek. Barisan ini terdiri daripada tugasan interaktif,
menukar antara yang agak sensitif dan perlu mengambil masa 10 atau kurang
Cik. Sebaliknya, baris gilir keutamaan rendah terdiri daripada tugasan jangka panjang yang menggunakan
CPU. Dan dalam kes ini, selang masa yang panjang sangat sesuai (100ms).
Dalam contoh ini, terdapat 2 tugasan yang telah berfungsi dalam baris gilir keutamaan tinggi 20
ms dibahagikan kepada 10ms windows. 40ms dalam baris gilir tengah (20ms tetingkap) dan dalam baris gilir keutamaan rendah
Tetingkap masa giliran menjadi 40ms di mana tugasan menyelesaikan kerja mereka.
Pelaksanaan MLFQ dalam OS Solaris ialah kelas penjadual perkongsian masa.
Penjadual akan menyediakan satu set jadual yang menentukan dengan tepat bagaimana ia sepatutnya
ubah keutamaan proses sepanjang hayatnya, saiz yang sepatutnya
tetingkap untuk diperuntukkan dan kekerapan untuk meningkatkan keutamaan tugas. Pentadbir
sistem boleh berinteraksi dengan jadual ini dan membuat penjadual berkelakuan
berbeza. Secara lalai, jadual ini mempunyai 60 baris gilir dengan peningkatan beransur-ansur
saiz tetingkap daripada 20ms (keutamaan tinggi) kepada beberapa ratus ms (keutamaan terendah), dan
juga dengan rangsangan semua tugasan sekali sesaat.
Penjadual MLFQ lain tidak menggunakan jadual atau mana-mana yang khusus
peraturan yang diterangkan dalam bab ini, sebaliknya, mereka mengira keutamaan menggunakan
formula matematik. Contohnya, penjadual dalam FreeBSD menggunakan formula untuk
mengira keutamaan tugas semasa berdasarkan berapa banyak proses
menggunakan CPU. Di samping itu, penggunaan CPU mereput dari semasa ke semasa, dan dengan itu
Oleh itu, peningkatan keutamaan agak berbeza daripada yang diterangkan di atas. Ini adalah benar
dipanggil algoritma pereputan. Mulai versi 7.1, FreeBSD menggunakan penjadual ULE.
Akhirnya, banyak perancang mempunyai ciri lain. Sebagai contoh, beberapa
penjadual menyimpan tahap yang lebih tinggi untuk operasi sistem pengendalian dan dengan itu
Oleh itu, tiada proses pengguna boleh mendapat keutamaan tertinggi
sistem. Sesetengah sistem membenarkan anda memberi nasihat untuk membantu
penjadual untuk memberi keutamaan dengan betul. Sebagai contoh, menggunakan arahan baik
anda boleh menambah atau mengurangkan keutamaan tugas dan dengan itu menambah atau mengurangkan
mengurangkan peluang program menggunakan masa CPU.
MLFQ: Ringkasan
Kami telah menerangkan pendekatan perancangan yang dipanggil MLFQ. Nama dia
disertakan dalam prinsip operasi - ia mempunyai beberapa baris gilir dan menggunakan maklum balas
untuk mengutamakan sesuatu tugas.
Bentuk akhir peraturan adalah seperti berikut:
- Peraturan1: Jika keutamaan(A) > Keutamaan(B), tugas A akan dijalankan (B tidak akan)
- Peraturan2: Jika keutamaan(A) = Keutamaan(B), A&B dimulakan menggunakan RR
- Peraturan3: Apabila tugasan memasuki sistem, ia diletakkan dalam baris gilir keutamaan tertinggi.
- Peraturan4: Selepas tugas telah menggunakan masa yang diperuntukkan dalam baris gilir semasa (tidak kira berapa kali ia membebaskan CPU), keutamaan tugas tersebut dikurangkan (ia bergerak ke bawah baris gilir).
- Peraturan5: Selepas beberapa tempoh S, pindahkan semua tugasan dalam sistem ke baris gilir tertinggi.
MLFQ menarik kerana sebab berikut - bukannya memerlukan pengetahuan tentang
sifat tugas terlebih dahulu, algoritma mempelajari tingkah laku masa lalu tugas dan set
keutamaan sewajarnya. Oleh itu, dia cuba duduk di atas dua kerusi sekaligus - untuk mencapai prestasi untuk tugas-tugas kecil (SJF, STCF) dan dengan jujur ββmenjalankan yang panjang,
Kerja memuatkan CPU. Oleh itu, banyak sistem, termasuk BSD dan derivatifnya,
Solaris, Windows, Mac menggunakan beberapa bentuk algoritma sebagai penjadual
MLFQ sebagai garis dasar.
Bahan tambahan:
- (pengkomputeran)
Sumber: www.habr.com