Pengantar Sistem Operasi

Halo, Habr! Saya ingin menarik perhatian Anda serangkaian artikel-terjemahan dari satu literatur yang menarik menurut saya - OSTEP. Artikel ini membahas lebih dalam karya sistem operasi mirip-unix, yaitu, bekerja dengan proses, berbagai penjadwal, memori, dan komponen serupa lainnya yang membentuk OS modern. Asli semua bahan bisa Anda lihat di sini . Harap dicatat bahwa terjemahannya dilakukan secara tidak profesional (cukup bebas), tetapi saya harap saya tetap memiliki makna umum.

Pekerjaan laboratorium tentang hal ini dapat ditemukan di sini:

Bagian lain:

Dan Anda dapat melihat saluran saya di telegram =)

Perencanaan: Antrian Umpan Balik Multi-Tingkat

Dalam kuliah ini kita akan berbicara tentang masalah mengembangkan salah satu pendekatan yang paling terkenal
Perencanaan yang disebut Multi-Level Feedback Queue (MLFQ). Penjadwal MLFQ pertama kali dijelaskan pada tahun 1962 oleh Fernando J. Corbató dalam suatu sistem yang disebut Sistem Berbagi-Waktu Kompatibel (CTSS). Karya-karya ini (termasuk karya Multics nanti) kemudian diserahkan ke Turing Award. Penjadwal kemudian diperbaiki dan memperoleh tampilan yang sudah dapat ditemukan di beberapa sistem modern.

Algoritma MLFQ berupaya memecahkan 2 masalah lintas sektoral yang mendasar.
Pertama , dia mencoba untuk mengoptimalkan waktu penyelesaian, yang, seperti yang kita bahas dalam kuliah sebelumnya, dioptimalkan dengan mulai dari awal antrian tugas terpendek. Namun, OS tidak tahu berapa lama proses ini atau itu akan bekerja, dan ini adalah pengetahuan yang diperlukan untuk pengoperasian algoritma SJF, STCF. Kedua , MLFQ mencoba membuat sistem responsif terhadap pengguna (misalnya, mereka yang duduk dan menatap layar sambil menunggu tugas selesai) dan dengan demikian meminimalkan waktu respons. Sayangnya, algoritma seperti RR mengurangi waktu respons, tetapi mereka memiliki efek yang sangat buruk pada metrik waktu penyelesaian. Oleh karena itu masalah kita: Bagaimana merancang penjadwal yang akan memenuhi persyaratan kita dan pada saat yang sama tidak tahu apa-apa tentang sifat proses, secara umum? Bagaimana cara penjadwal mempelajari karakteristik tugas yang ia luncurkan dan dengan demikian membuat keputusan perencanaan yang lebih baik?

Inti dari masalah: Bagaimana merencanakan perumusan tugas tanpa pengetahuan yang sempurna? Bagaimana mengembangkan penjadwal yang secara simultan meminimalkan waktu respons untuk tugas-tugas interaktif dan pada saat yang sama meminimalkan waktu penyelesaian tanpa mengetahui waktu untuk menyelesaikan tugas?

Catatan: belajar dari acara sebelumnya

Lineup MLFQ adalah contoh yang bagus dari sistem yang belajar dari peristiwa masa lalu untuk memprediksi masa depan. Pendekatan serupa sering ditemukan di OS (dan banyak cabang lain dalam ilmu komputer, termasuk cabang prediksi perangkat keras dan algoritma caching). Perjalanan serupa bekerja ketika tugas memiliki fase perilaku dan karenanya dapat diprediksi.

Namun, orang harus berhati-hati dengan teknik seperti itu, karena prediksi dapat dengan mudah berubah menjadi salah dan memimpin sistem untuk membuat keputusan yang lebih buruk daripada tanpa pengetahuan sama sekali.

MLFQ: Aturan Dasar

Pertimbangkan aturan dasar algoritma MLFQ. Meskipun ada beberapa implementasi dari algoritma ini, pendekatan dasarnya serupa.

Dalam implementasi yang akan kami pertimbangkan, dalam MLFQ akan ada beberapa antrian terpisah, yang masing-masing akan memiliki prioritas yang berbeda. Kapan saja, tugas yang siap dieksekusi dalam satu antrian. MLFQ menggunakan prioritas untuk memutuskan tugas mana yang akan dijalankan, mis. tugas dengan prioritas lebih tinggi (tugas dari antrian dengan prioritas lebih tinggi) akan diluncurkan terlebih dahulu.

Tidak diragukan lagi, lebih dari satu tugas dapat berada dalam antrian tertentu, sehingga mereka akan memiliki prioritas yang sama. Dalam hal ini, mesin RR akan digunakan untuk menjadwalkan peluncuran di antara tugas-tugas ini.

Jadi kita sampai pada dua aturan dasar untuk MLFQ:

Aturan1: Jika prioritas (A)> Prioritas (B), tugas A akan mulai (B tidak akan)
Aturan2: Jika prioritas (A) = Prioritas (B), A&B mulai menggunakan RR

Berdasarkan hal di atas, elemen kunci perencanaan MLFQ adalah prioritas. Alih-alih menetapkan prioritas tetap untuk setiap tugas, MLFQ mengubah prioritasnya tergantung pada perilaku yang diamati.

Sebagai contoh, jika suatu tugas secara konstan berhenti bekerja pada CPU sambil menunggu input keyboard, MLFQ akan mempertahankan prioritas proses pada level tinggi, karena ini adalah bagaimana proses interaktif seharusnya bekerja. Jika, sebaliknya, tugas tersebut secara konstan dan intensif menggunakan CPU untuk waktu yang lama, MLFQ akan menurunkan prioritasnya. Dengan demikian, MLFQ akan mempelajari perilaku proses pada saat operasi mereka dan menggunakan perilaku tersebut.

Mari kita ambil contoh bagaimana antrian terlihat pada suatu titik waktu dan kemudian kita mendapatkan sesuatu seperti ini:

gambar

Dalam skema ini, 2 proses A dan B berada dalam antrian dengan prioritas tertinggi. Proses C ada di suatu tempat di tengah, dan proses D di akhir antrian. Menurut uraian algoritma MLFQ di atas, penjadwal akan menjalankan tugas hanya dengan prioritas tertinggi menurut RR, dan tugas C, D akan keluar dari pekerjaan.

Secara alami, snapshot statis tidak akan memberikan gambaran lengkap tentang bagaimana MLFQ bekerja.
Penting untuk memahami dengan tepat bagaimana gambar berubah seiring waktu.

Percobaan 1: Cara mengubah prioritas

Pada titik ini, Anda perlu memutuskan bagaimana MLFQ akan mengubah tingkat prioritas tugas (dan dengan demikian posisi tugas dalam antrian) selama siklus hidupnya. Untuk melakukan ini, Anda perlu mengingat alur kerja: sejumlah tugas interaktif dengan waktu kerja yang singkat (dan dengan demikian sering melepaskan CPU) dan beberapa tugas panjang yang menggunakan CPU sepanjang waktu kerjanya, sedangkan waktu respons untuk tugas-tugas tersebut tidak penting. Dan dengan demikian, Anda dapat melakukan upaya pertama untuk mengimplementasikan algoritma MLFQ dengan aturan berikut:

Aturan3: Ketika sebuah tugas memasuki sistem, ia diurutkan dengan yang tertinggi
prioritas.
Rule4a: Jika tugas menggunakan seluruh jendela waktu yang diberikan untuknya, maka tugasnya
prioritas turun.
Rule4b: Jika Task membebaskan CPU sebelum berakhirnya window waktunya, maka itu
tetap dengan prioritas yang sama.

Contoh 1: Satu tugas jangka panjang

Seperti yang dapat Anda lihat dalam contoh ini, tugas penerimaan diajukan dengan prioritas tertinggi. Setelah jendela waktu 10 ms, proses diturunkan dalam prioritas oleh penjadwal. Setelah jendela waktu berikutnya, tugas akhirnya turun ke prioritas terendah dalam sistem, di mana ia tetap.

Contoh 2: Mereka membawa tugas pendek

Sekarang mari kita lihat contoh bagaimana MLFQ akan mencoba untuk lebih dekat dengan SJF. Ada dua tugas dalam contoh ini: A, yang merupakan tugas lama yang terus-menerus memakan CPU, dan B, yang merupakan tugas interaktif singkat. Misalkan A sudah bekerja beberapa saat pada saat tugas B tiba.

Dalam grafik ini, hasil skrip terlihat. Tugas A, seperti tugas apa pun yang menggunakan CPU, ada di bagian paling bawah. Tugas B akan tiba di T = 100 dan akan ditempatkan dalam antrian dengan prioritas tertinggi. Karena waktu kerjanya pendek, itu akan berakhir sebelum mencapai tahap terakhir.

Dari contoh ini, kita harus memahami tujuan utama dari algoritma: karena algoritma tidak mengetahui tugas yang panjang atau pendek, pertama-tama diasumsikan bahwa tugas itu singkat dan memberikan prioritas tertinggi. Jika ini adalah tugas yang sangat singkat, maka itu akan diselesaikan dengan cepat, jika tidak, jika itu adalah tugas yang panjang, maka perlahan akan bergerak ke bawah dalam prioritas dan akan segera membuktikan bahwa itu adalah tugas yang sangat panjang yang tidak memerlukan respons.

Contoh 3: Bagaimana dengan I / O?

Sekarang lihat contoh I / O. Sebagaimana dinyatakan dalam aturan 4b, jika suatu proses membebaskan prosesor tanpa sepenuhnya memanfaatkan waktu prosesornya, maka ia tetap pada tingkat prioritas yang sama. Maksud aturan ini cukup sederhana - jika tugas interaktif melakukan banyak operasi I / O, misalnya, menunggu pengguna menekan tombol atau mouse, tugas seperti itu akan membebaskan prosesor sebelum jendela yang diberikan. Kami tidak ingin mengabaikan tugas seperti itu dengan prioritas, dan dengan demikian akan tetap pada tingkat yang sama.

Contoh ini menunjukkan bagaimana algoritma akan bekerja dengan proses tersebut - tugas interaktif B, yang membutuhkan CPU hanya 1 ms sebelum melakukan proses I / O, dan tugas panjang A, yang menggunakan CPU sepanjang waktu.

MLFQ memegang proses B dengan prioritas tertinggi karena terus berlanjut sepanjang waktu.
bebaskan CPU. Jika B adalah tugas interaktif, maka algoritma kemudian mencapai tujuannya meluncurkan tugas-tugas interaktif dengan cepat.

Masalah dengan algoritma MLFQ saat ini

Dalam contoh sebelumnya, kami membangun versi dasar MLFQ. Dan sepertinya dia melakukan pekerjaannya dengan baik dan jujur, mendistribusikan waktu prosesor secara jujur antara tugas yang panjang dan memungkinkan tugas pendek atau tugas secara intensif mengakses I / O untuk bekerja dengan cepat. Sayangnya, pendekatan ini mengandung beberapa masalah serius.

Pertama , masalah kelaparan: jika sistem memiliki banyak tugas interaktif, mereka akan menghabiskan semua waktu prosesor dan dengan demikian tidak satu pun tugas panjang akan mendapatkan kesempatan untuk dieksekusi (mereka kelaparan).

Kedua , pengguna pintar bisa menulis program mereka sehingga
menipu perencana. Triknya adalah melakukan sesuatu untuk membuatnya
scheduler memberi proses lebih banyak waktu prosesor. Algoritma itu
dijelaskan di atas cukup rentan terhadap serangan seperti itu: sebelum jendela waktu praktis
berakhir Anda harus melakukan operasi I / O (untuk beberapa orang, tidak peduli file mana)
dan dengan demikian membebaskan CPU. Perilaku ini akan memungkinkan Anda untuk tetap sama
antrian itu sendiri dan sekali lagi mendapatkan persentase waktu CPU yang lebih besar. Jika dilakukan
ini benar (misalnya, 99% dari waktu jendela sebelum membebaskan CPU)
tugas seperti itu dapat memonopoli prosesor.

Akhirnya, suatu program dapat mengubah perilakunya dari waktu ke waktu. Tugas-tugas itu
yang menggunakan CPU bisa menjadi interaktif. Dalam contoh kita, mirip
tugas tidak akan menerima perlakuan yang tepat dari penjadwal, seperti yang akan diterima orang lain
(awal) tugas interaktif.

Pertanyaan kepada hadirin: serangan apa yang bisa dilakukan perencana di dunia modern?

Percobaan 2: Mengangkat Prioritas

Mari kita coba mengubah aturan dan melihat apakah kita dapat menghindari masalah dengan
puasa. Apa yang bisa kami lakukan untuk memastikan hal itu terkait
Tugas CPU akan mendapatkan waktu mereka (bahkan jika tidak lama).
Sebagai solusi sederhana untuk masalah ini, Anda dapat menawarkannya secara berkala
tingkatkan prioritas semua tugas tersebut dalam sistem. Ada banyak cara.
untuk mencapai ini, mari kita coba menerapkan sebagai contoh sesuatu yang sederhana: terjemahkan
semua tugas sekaligus dalam prioritas tertinggi, maka aturan baru:

Aturan5 : Setelah periode S tertentu, transfer semua tugas dalam sistem ke prioritas tertinggi.

Aturan baru kami menyelesaikan dua masalah sekaligus. Pertama, prosesnya
dijamin tidak kelaparan: tugas dalam prioritas tertinggi akan dibagikan
waktu prosesor sesuai dengan algoritma RR dan dengan demikian semua proses akan menerima
waktu prosesor. Kedua, jika ada beberapa proses yang sebelumnya digunakan
hanya prosesor yang menjadi interaktif, maka akan tetap sejalan dengan yang lebih tinggi
prioritas setelah satu kali akan menerima peningkatan prioritas ke tertinggi.
Pertimbangkan sebuah contoh. Dalam skenario ini, pertimbangkan satu proses menggunakan

CPU dan dua proses pendek interaktif. Di sebelah kiri dalam gambar, gambar menunjukkan perilaku tanpa meningkatkan prioritas, dan dengan demikian tugas panjang mulai kelaparan setelah dua tugas interaktif tiba di sistem. Pada gambar di sebelah kanan, setiap 50 ms prioritas ditingkatkan dan dengan demikian semua proses dijamin untuk menerima waktu prosesor dan akan dimulai secara berkala. 50ms dalam hal ini diambil sebagai contoh, dalam kenyataannya jumlah ini agak lebih besar.
Jelas, penambahan waktu untuk peningkatan S secara berkala mengarah ke
pertanyaan logis: nilai apa yang harus ditetapkan? Salah satu yang terhormat
insinyur sistem John Ousterhout menyebut jumlah yang serupa dalam sistem seperti voo-doo
konstan, karena mereka dalam beberapa cara menuntut ilmu hitam untuk benar
pameran. Dan, sayangnya, S memiliki aroma seperti itu. Jika Anda mengatur nilainya juga
tugas besar-panjang akan mulai kelaparan. Dan jika Anda menetapkan nilainya terlalu rendah,
Tugas interaktif tidak akan menerima waktu prosesor yang tepat.

Percobaan 3: Akuntansi Terbaik

Sekarang kita memiliki satu masalah lagi yang perlu dipecahkan: bagaimana tidak
biarkan menipu perencana kami? Bersalah atas kesempatan ini
aturan 4a, 4b, yang memungkinkan tugas mempertahankan prioritas, membebaskan prosesor
sebelum berakhirnya waktu yang diberikan. Bagaimana cara mengatasinya?
Solusi dalam hal ini dapat dianggap sebagai penghitungan waktu CPU terbaik untuk masing-masing
Tingkat MLFQ. Alih-alih lupa waktu program digunakan
prosesor untuk periode yang ditentukan, Anda harus mempertimbangkan dan menyimpannya. Setelah
proses telah menghabiskan waktu yang dialokasikan untuk itu harus dikurangi ke yang berikutnya
tingkat prioritas. Sekarang tidak peduli bagaimana prosesnya menggunakan waktu - caranya
terus-menerus menghitung pada prosesor atau banyak panggilan. Dengan cara ini
Aturan 4 harus ditulis ulang sebagai berikut:

Aturan4 : Setelah tugas menghabiskan waktu yang dialokasikan untuknya dalam antrian saat ini (terlepas dari berapa kali itu membebaskan CPU), prioritas tugas tersebut berkurang (bergerak ke bawah antrian).

Mari kita lihat sebuah contoh:

"

Angka tersebut menunjukkan apa yang terjadi jika Anda mencoba mengelabui penjadwal, caranya
jika dengan aturan sebelumnya 4a, 4b, kita mendapatkan hasil di sebelah kiri. Selamat baru
aturannya adalah hasil di sebelah kanan. Sebelum perlindungan, proses apa pun dapat meminta I / O sampai selesai dan
dengan demikian mendominasi CPU, setelah mengaktifkan perlindungan, terlepas dari perilaku
I / O, itu masih akan drop down line dan dengan demikian tidak akan tidak jujur
menguasai sumber daya CPU.

Meningkatkan MLFQ dan masalah lainnya

Dengan peningkatan di atas, muncul masalah baru: salah satu yang utama
pertanyaan - bagaimana membuat parameter penjadwal seperti itu? Yaitu Berapa banyak seharusnya
semburan? Berapa ukuran jendela program dalam antrian? Bagaimana
prioritas program harus sering ditingkatkan untuk menghindari kelaparan dan
memperhitungkan perubahan akun dalam perilaku program? Untuk pertanyaan-pertanyaan ini, tidak ada yang mudah
respon dan hanya eksperimen dengan banyak dan konfigurasi selanjutnya
perencana dapat menyebabkan keseimbangan yang memuaskan.

Sebagai contoh, sebagian besar implementasi MLFQ memungkinkan Anda untuk menetapkan yang berbeda
interval waktu untuk antrian yang berbeda. Antrian prioritas tinggi biasanya
interval pendek ditugaskan. Antrian ini terdiri dari tugas interaktif,
beralih di antara yang cukup sensitif dan harus memakan waktu 10 atau kurang
ms Sebaliknya, antrian prioritas rendah terdiri dari tugas-tugas panjang yang digunakan
CPU Dan dalam hal ini, interval waktu yang lama sangat cocok (100 ms).

Dalam contoh ini, ada 2 tugas yang berfungsi dalam antrian prioritas tinggi 20
ms, rusak oleh windows selama 10 ms. 40ms dalam antrian sedang (jendela pada 20ms) dan dalam prioritas rendah
Jendela waktu antrian menjadi 40ms, di mana tugas menyelesaikan pekerjaan mereka.

Implementasi Solaris OS MLFQ adalah kelas penjadwal berbagi waktu.
Penjadwal menyediakan satu set tabel yang menentukan dengan tepat bagaimana seharusnya
mengubah prioritas proses selama hidupnya, berapa ukurannya
jendela yang dipilih dan seberapa sering Anda perlu meningkatkan prioritas tugas. Admin
sistem dapat berinteraksi dengan tabel ini dan membuat penjadwal berperilaku
dengan cara yang berbeda. Secara default, ada 60 antrian tambahan dalam tabel ini.
ukuran jendela dari 20 ms (prioritas tinggi) hingga beberapa ratus ms (prioritas terendah), dan
juga dengan dorongan semua tugas sekali per detik.

Perencana MLFQ lainnya tidak menggunakan tabel atau spesifik apa pun
aturan yang dijelaskan dalam kuliah ini, sebaliknya mereka menghitung prioritas menggunakan
rumus matematika. Jadi, misalnya, scheduler di FreeBSD menggunakan rumus untuk
menghitung prioritas tugas saat ini berdasarkan pada seberapa banyak prosesnya
CPU yang digunakan. Selain itu, penggunaan CPU meluruh dari waktu ke waktu, dan sebagainya
Dengan demikian, peningkatan prioritas terjadi agak berbeda dari yang dijelaskan di atas. Begitu ya
disebut algoritma peluruhan. Sejak versi 7.1, FreeBSD menggunakan penjadwal ULE.

Akhirnya, banyak perencana memiliki fitur lain. Sebagai contoh, beberapa
perencana memiliki level tertinggi untuk sistem operasi dan sebagainya
dengan cara ini, tidak ada proses pengguna yang bisa mendapatkan prioritas tertinggi di
sistem. Beberapa sistem memungkinkan Anda memberikan tip untuk membantu.
scheduler untuk mengatur prioritas dengan benar. Misalnya, menggunakan perintah yang bagus
Anda dapat menambah atau mengurangi prioritas tugas dan karenanya menambah atau
mengurangi peluang program untuk waktu prosesor.

MLFQ: Ringkasan

Kami menggambarkan pendekatan perencanaan yang disebut MLFQ. Namanya
Disimpulkan dalam prinsip kerja - ia memiliki beberapa antrian dan menggunakan umpan balik
untuk menentukan prioritas tugas.
Bentuk akhir aturan adalah sebagai berikut:

Aturan1 : Jika prioritas (A)> Prioritas (B), tugas A akan dimulai (B tidak akan)
Aturan2 : Jika prioritas (A) = Prioritas (B), A&B mulai menggunakan RR
Aturan3 : Ketika sebuah tugas memasuki sistem, itu diurutkan dengan prioritas tertinggi.
Aturan4 : Setelah tugas tersebut menghabiskan waktu yang dialokasikan untuknya dalam antrian saat ini (terlepas dari berapa kali itu membebaskan CPU), prioritas tugas tersebut menurun (bergerak ke bawah antrian).
Aturan5 : Setelah periode S tertentu, transfer semua tugas dalam sistem ke prioritas tertinggi.

MLFQ menarik karena alasan berikut - alih-alih menuntut pengetahuan tentang
sifat tugas terlebih dahulu, algoritma memeriksa perilaku masa lalu dari tugas dan
memprioritaskannya. Karena itu, ia mencoba duduk di dua kursi sekaligus - untuk mencapai produktivitas untuk tugas-tugas kecil (SJF, STCF) dan jujur menjalankan
tugas yang panjang, memuat CPU. Oleh karena itu, banyak sistem, termasuk BSD dan turunannya,
Solaris, Windows, Mac, menggunakan beberapa bentuk algoritma
MLFQ sebagai penjadwal sebagai basis.

Sistem Operasi: Tiga Potongan Mudah. Bagian 5: Perencanaan: Antrian Umpan Balik Multi-Tingkat (terjemahan)