Pengantar Sistem Operasi
Hai Habr! Saya ingin menyampaikan kepada Anda serangkaian artikel-terjemahan dari salah satu literatur yang menarik menurut saya - OSTEP. Materi ini membahas cukup mendalam tentang cara kerja sistem operasi mirip unix, yaitu bekerja dengan proses, berbagai penjadwal, memori, dan komponen serupa lainnya yang membentuk sebuah OS modern. Anda dapat melihat semua materi asli di sini . Harap dicatat bahwa terjemahannya dibuat tidak profesional (cukup bebas), tapi saya harap saya tetap mempertahankan arti umum.
Pekerjaan laboratorium mengenai hal ini dapat ditemukan di sini:
Bagian lain:
Anda juga dapat memeriksa saluran saya di =)
Perencanaan: Antrean Umpan Balik Bertingkat
Dalam kuliah ini, kita akan membahas masalah pengembangan salah satu pendekatan paling terkenal
perencanaan, yang disebut Antrian Umpan Balik Multi-Level (MLFQ). Penjadwal MLFQ pertama kali dijelaskan pada tahun 1962 oleh Fernando J. CorbatΓ³ dalam sebuah sistem yang disebut
Sistem Pembagian Waktu yang Kompatibel (CTSS). Karya-karya ini (termasuk karya-karya selanjutnya
Multics) kemudian dinominasikan untuk Turing Award. Penjadwalnya adalah
kemudian ditingkatkan dan memperoleh tampilan yang sudah dapat ditemukan
beberapa sistem modern.
Algoritma MLFQ mencoba memecahkan 2 masalah mendasar yang tumpang tindih.
Pertama, ia mencoba untuk mengoptimalkan waktu penyelesaian, yang seperti telah kita bahas pada kuliah sebelumnya, dioptimalkan dengan metode berjalan di bagian paling depan antrian
tugas singkat. Namun, OS tidak mengetahui berapa lama proses ini atau itu akan berjalan, dan ini
pengetahuan yang diperlukan untuk pengoperasian algoritma SJF, STCF. Kedua, MLFQ mencoba
membuat sistem responsif bagi pengguna (misalnya, bagi mereka yang duduk dan
menatap layar menunggu tugas selesai) dan dengan demikian meminimalkan waktu
tanggapan. Sayangnya, algoritma seperti RR mengurangi waktu respons, namun
berdampak buruk pada metrik waktu penyelesaian. Oleh karena itu masalah kita: Bagaimana mendesain
penjadwal yang akan memenuhi persyaratan kami dan pada saat yang sama tidak tahu apa-apa tentangnya
sifat proses secara umum? Bagaimana penjadwal mempelajari karakteristik tugas,
yang diluncurkannya dan dengan demikian membuat keputusan perencanaan yang lebih baik?
Inti permasalahan: Bagaimana merencanakan penetapan tugas tanpa pengetahuan yang sempurna?
Bagaimana merancang penjadwal yang secara bersamaan meminimalkan waktu respons
untuk tugas-tugas interaktif dan pada saat yang sama meminimalkan waktu penyelesaian tanpa menyadarinya
pengetahuan tentang waktu pelaksanaan tugas?
Catatan: belajar dari kejadian sebelumnya
Antrean MLFQ adalah contoh bagus dari sistem yang dilatih
peristiwa masa lalu untuk memprediksi masa depan. Pendekatan serupa sering kali dilakukan
ditemukan di OS (Dan banyak cabang ilmu komputer lainnya, termasuk cabang
prediksi perangkat keras dan algoritma caching). Pendakian serupa
dipicu ketika tugas memiliki fase perilaku dan dengan demikian dapat diprediksi.
Namun teknik ini harus hati-hati karena prediksinya sangat mudah.
mungkin ternyata salah dan menyebabkan sistem mengambil keputusan yang lebih buruk
akan tanpa pengetahuan sama sekali.
MLFQ: Aturan Dasar
Pertimbangkan aturan dasar algoritma MLFQ. Dan meskipun implementasi algoritma ini
ada beberapa, pendekatan dasarnya serupa.
Dalam implementasinya yang akan kita lihat, MLFQ akan memiliki beberapa
antrian terpisah, yang masing-masing akan memiliki prioritas berbeda. Kapan pun,
tugas yang siap dijalankan berada dalam antrian yang sama. MLFQ menggunakan prioritas,
untuk memutuskan tugas mana yang akan dijalankan untuk dieksekusi, mis. tugas dengan lebih tinggi
prioritas (tugas dari antrian dengan prioritas tertinggi) akan diluncurkan terlebih dahulu
antre.
Tentu saja, mungkin terdapat lebih dari satu tugas dalam antrean tertentu, jadi
jadi mereka akan mendapat prioritas yang sama. Dalam hal ini, mekanisme tersebut akan digunakan
RR untuk perencanaan peluncuran di antara tugas-tugas ini.
Jadi kita sampai pada dua aturan dasar untuk MLFQ:
- Aturan 1: Jika prioritas(A) > Prioritas(B), tugas A akan diluncurkan (B tidak akan)
- Aturan2: Jika prioritas(A) = Prioritas(B), A&B dimulai menggunakan RR
Berdasarkan hal di atas, elemen kunci perencanaan MLFQ
adalah prioritas. Daripada memberikan prioritas tetap pada masing-masingnya
tugas, MLFQ mengubah prioritasnya tergantung pada perilaku yang diamati.
Misalnya, jika suatu tugas terus-menerus berhenti di CPU sambil menunggu input keyboard,
MLFQ akan menjaga prioritas proses tetap tinggi karena itulah caranya
proses interaktif seharusnya berhasil. Jika, sebaliknya, tugasnya terus-menerus dan
menggunakan CPU secara berlebihan dalam jangka waktu lama, MLFQ akan menurunkannya
Sebuah prioritas. Dengan demikian, MLFQ akan mempelajari perilaku proses saat sedang berjalan
dan menggunakan perilaku.
Mari kita ambil contoh seperti apa antrian pada suatu saat
waktu dan kemudian Anda mendapatkan sesuatu seperti ini:
Pada skema ini, 2 proses A dan B berada pada antrian dengan prioritas tertinggi. Proses
C berada di tengah-tengah, dan proses D berada di ujung antrian. Menurut hal di atas
Seperti yang dijelaskan pada algoritma MLFQ, penjadwal hanya akan mengeksekusi tugas dengan nilai tertinggi
prioritas menurut RR, dan tugas C, D akan keluar dari pekerjaan.
Tentu saja, snapshot statis tidak akan memberikan gambaran lengkap tentang cara kerja MLFQ.
Penting untuk memahami dengan tepat bagaimana gambaran tersebut berubah seiring waktu.
Percobaan 1: Bagaimana 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
dari ini, Anda perlu mengingat alur kerjanya: jumlah tertentu
tugas interaktif dengan waktu berjalan yang singkat (dan karenanya sering dirilis
CPU) dan beberapa tugas yang berjalan lama yang menggunakan CPU sepanjang waktu kerjanya, sementara
waktu respons untuk tugas-tugas seperti itu tidak penting. Jadi Anda bisa melakukan upaya pertama
mengimplementasikan algoritma MLFQ dengan aturan sebagai berikut:
- Aturan3: Ketika suatu tugas masuk ke sistem, tugas itu ditempatkan di antrian dengan yang tertinggi
- prioritas.
- Aturan4a: Jika suatu tugas menggunakan seluruh jangka waktu yang diberikan padanya, maka tugas tersebut
- prioritasnya diturunkan.
- Aturan4b: Jika suatu Tugas melepaskan CPU sebelum jangka waktunya berakhir, maka Tugas tersebut
- tetap dengan prioritas yang sama.
Contoh 1: Tugas tunggal yang sudah berjalan lama
Seperti dapat dilihat pada contoh ini, tugas penerimaan ditetapkan paling tinggi
prioritas. Setelah jangka waktu 10 ms, prioritas proses diturunkan.
penjadwal. Setelah jangka waktu berikutnya, tugas akhirnya diturunkan versinya menjadi
prioritas terendah dalam sistem, jika tetap ada.
Contoh 2: Mengambil tugas singkat
Sekarang mari kita lihat contoh bagaimana MLFQ mencoba mendekati SJF. Karena
Misalnya, dua tugas: A, yang merupakan tugas jangka panjang yang terus-menerus
menempati CPU dan B, yang merupakan tugas interaktif singkat. Memperkirakan
bahwa A sudah berjalan selama beberapa waktu pada saat tugas B tiba.
Grafik ini menunjukkan hasil skenario. Tugas A, seperti tugas lainnya,
menggunakan CPU berada di bagian paling bawah. Tugas B akan tiba pada waktu T=100 dan akan tiba
ditempatkan pada antrian dengan prioritas tertinggi. Karena waktu pengoperasiannya singkat,
itu akan selesai sebelum mencapai antrian terakhir.
Dari contoh ini, Anda harus memahami tujuan utama dari algoritma: karena algoritma tidak
mengetahui apakah suatu tugas itu panjang atau pendek, maka pertama-tama dia mengasumsikan tugas itu
singkat dan memberikannya prioritas tertinggi. Jika itu benar-benar tugas yang singkat, maka
itu akan selesai dengan cepat, sebaliknya jika tugasnya panjang, itu akan berjalan lambat
dalam prioritasnya turun dan akan segera membuktikan bahwa dia memang merupakan tugas panjang yang tidak
membutuhkan respons.
Contoh 3: Bagaimana dengan I/O?
Sekarang mari kita lihat contoh I/O. Sebagaimana dinyatakan dalam aturan 4b,
jika suatu proses melepaskan prosesor tanpa menggunakan waktu prosesornya sepenuhnya,
maka hal tersebut tetap pada tingkat prioritas yang sama. Maksud dari aturan ini cukup sederhana.
- jika pekerjaan interaktif melakukan banyak I/O, misalnya menunggu
dari penekanan tombol atau mouse pengguna, tugas seperti itu akan membebaskan prosesor
sebelum jendela yang ditentukan. Kami tidak ingin menurunkan prioritas tugas seperti itu,
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 selama 1 ms sebelum dieksekusi
Proses I/O dan pekerjaan A yang panjang, yang menggunakan CPU sepanjang waktu.
MLFQ menjaga proses B pada prioritas tertinggi seiring berjalannya waktu
lepaskan CPUnya. Jika B adalah tugas interaktif, maka algoritma dalam hal ini telah tercapai
tujuannya adalah untuk meluncurkan tugas interaktif dengan cepat.
Masalah dengan algoritma MLFQ saat ini
Pada contoh sebelumnya kami membuat versi dasar MLFQ. Dan sepertinya dia
melakukan tugasnya dengan baik dan adil, mendistribusikan waktu CPU secara adil
tugas panjang dan memungkinkan tugas pendek atau tugas yang banyak diakses
ke I/O untuk diproses dengan cepat. Sayangnya, pendekatan ini mengandung beberapa hal
masalah serius.
Pertama, masalah kelaparan: jika sistem memiliki banyak interaktif
tugas, mereka akan menghabiskan seluruh waktu CPU dan karenanya tidak memakan waktu lama
tugas tidak akan mendapat kesempatan untuk dilaksanakan (mereka kelaparan).
Kedua, pengguna yang cerdas dapat menulis program mereka sedemikian rupa
menipu penjadwal. Kebohongannya terletak pada melakukan sesuatu untuk memaksa
Penjadwal memberi proses lebih banyak waktu CPU. Algoritma itu
dijelaskan di atas cukup rentan terhadap serangan seperti itu: sebelum jangka waktu praktis
selesai, Anda perlu melakukan operasi I / O (untuk beberapa, tidak peduli file mana)
dan dengan demikian membebaskan CPU. Perilaku seperti itu akan memungkinkan Anda untuk tetap sama
antrian itu sendiri dan sekali lagi mendapatkan persentase waktu CPU yang lebih besar. Jika selesai
ini benar (misalnya menjalankan 99% waktu jendela sebelum melepaskan CPU),
tugas seperti itu hanya dapat memonopoli prosesor.
Terakhir, suatu program dapat mengubah perilakunya seiring berjalannya waktu. Tugas-tugas itu
yang digunakan CPU dapat menjadi interaktif. Dalam contoh kita, serupa
tugas tidak akan menerima perlakuan yang tepat dari penjadwal, seperti yang lainnya
(awal) tugas interaktif.
Pertanyaan kepada hadirin: serangan apa terhadap penjadwal yang dapat dilakukan di dunia modern?
Upaya 2: Meningkatkan prioritas
Mari kita coba mengubah aturan dan melihat apakah kita dapat menghindari masalah
puasa. Apa yang dapat kami lakukan untuk memastikan hal tersebut terkait
Tugas-tugas CPU akan mendapatkan waktunya (walaupun tidak lama).
Sebagai solusi sederhana untuk masalah tersebut, Anda dapat menyarankannya secara berkala
meningkatkan prioritas semua tugas tersebut dalam sistem. Ada banyak cara
untuk mencapai hal ini, mari kita coba menerapkan sesuatu yang sederhana sebagai contoh: menerjemahkan
semua tugas sekaligus ke prioritas tertinggi, maka aturan barunya:
- Rule5: Setelah beberapa periode S, pindahkan semua tugas dalam sistem ke antrian tertinggi.
Aturan baru kami menyelesaikan dua masalah sekaligus. Pertama, prosesnya
dijamin tidak kelaparan: tugas di antrian tertinggi akan dibagikan
waktu prosesor sesuai dengan algoritma RR dan dengan demikian semua proses akan menerima
waktu prosesor. Kedua, jika beberapa proses yang sebelumnya digunakan
hanya prosesor yang menjadi interaktif, ia akan tetap berada di antrian dengan yang tertinggi
prioritas setelah menerima peningkatan ke prioritas tertinggi satu kali.
Perhatikan sebuah contoh. Dalam skenario ini, pertimbangkan penggunaan satu proses
CPU dan dua proses singkat dan interaktif. Di sebelah kiri gambar, gambar menunjukkan perilaku tanpa peningkatan prioritas, dan dengan demikian tugas yang berjalan lama mulai terhenti setelah dua tugas interaktif tiba di sistem. Pada gambar di sebelah kanan, setiap 50 ms peningkatan prioritas dilakukan dan dengan demikian semua proses dijamin menerima waktu prosesor dan akan dimulai secara berkala. 50ms dalam hal ini diambil sebagai contoh, kenyataannya angka ini agak lebih tinggi.
Jelasnya, penambahan waktu kenaikan periodik S akan menghasilkan
pertanyaan logis: nilai apa yang harus ditetapkan? Salah satu yang memang layak
insinyur sistem John Ousterhout menyebut kuantitas serupa dalam sistem sebagai voo-doo
konstan, karena mereka dalam beberapa hal memerlukan ilmu hitam untuk memperbaikinya
paparan. Dan sayangnya, S memiliki rasa seperti itu. Jika Anda menetapkan nilainya juga
besar - tugas yang panjang akan mulai membuat kelaparan. Dan jika Anda menetapkan nilainya terlalu rendah,
tugas interaktif tidak akan menerima waktu CPU yang tepat.
Percobaan 3: Akuntansi yang Lebih Baik
Sekarang kita punya masalah lain yang harus dipecahkan: bagaimana tidak melakukannya
biarkan penjadwal kita tertipu? Orang-orang yang patut disalahkan atas kemungkinan ini adalah
aturan 4a, 4b, yang memungkinkan pekerjaan mempertahankan prioritas, sehingga membebaskan prosesor
sebelum waktu yang ditentukan habis. Bagaimana cara mengatasinya?
Solusi dalam hal ini dapat dianggap sebagai penghitungan waktu CPU yang lebih baik pada masing-masingnya
tingkat MLFQ. Daripada lupa waktu program tersebut digunakan
prosesor untuk jangka waktu yang ditentukan, itu harus diperhitungkan dan disimpan. Setelah
proses telah menghabiskan waktu yang ditentukan, maka harus diturunkan ke proses berikutnya
tingkat prioritas. Sekarang tidak masalah bagaimana prosesnya akan menggunakan waktunya - bagaimana caranya
terus-menerus menghitung pada prosesor atau sebagai sejumlah panggilan. Dengan demikian,
aturan 4 harus ditulis ulang ke bentuk berikut:
- Rule4: Setelah tugas menghabiskan waktu yang dialokasikan dalam antrean saat ini (berapa pun kali tugas tersebut membebaskan CPU), prioritas tugas tersebut dikurangi (tugas tersebut berpindah ke antrean).
Mari kita lihat sebuah contoh:
Β»
Gambar tersebut menunjukkan apa yang terjadi jika Anda mencoba mengelabui penjadwal seperti
jika dengan aturan sebelumnya 4a, 4b akan didapat hasil di sebelah kiri. Selamat baru
aturannya hasilnya ada di sebelah kanan. Sebelum proteksi, proses apa pun dapat memanggil I/O sebelum selesai dan
sehingga mendominasi CPU, setelah mengaktifkan perlindungan, apa pun perilakunya
I/O, dia akan tetap turun dalam antrian dan dengan demikian tidak akan bisa berbuat tidak jujur
mengambil alih sumber daya CPU.
Meningkatkan MLFQ dan masalah lainnya
Dengan perbaikan di atas, muncul masalah baru: salah satu masalah utama
pertanyaan - bagaimana cara membuat parameter penjadwal seperti itu? Itu. Berapa yang seharusnya
antrian? Berapa ukuran jendela program dalam antrian? Bagaimana
Prioritas program harus sering ditingkatkan untuk menghindari kelaparan dan kelaparan
memperhitungkan perubahan perilaku program? Untuk pertanyaan-pertanyaan ini, tidak ada yang sederhana
jawaban dan hanya eksperimen dengan beban dan konfigurasi selanjutnya
perencana dapat menghasilkan keseimbangan yang memuaskan.
Misalnya, sebagian besar implementasi MLFQ memungkinkan Anda menetapkan yang berbeda
slot waktu untuk antrian yang berbeda. Antrian dengan prioritas tinggi biasanya
interval pendek ditentukan. Antrian ini terdiri dari tugas interaktif,
peralihan di antaranya cukup sensitif dan memerlukan waktu 10 atau kurang
MS. Sebaliknya, antrian berprioritas rendah terdiri dari tugas-tugas yang berjalan lama dan menggunakan
CPU. Dan dalam hal ini, interval waktu yang lama (100 ms) sangat cocok.
Pada contoh ini, ada 2 tugas yang dikerjakan pada antrian prioritas tinggi 20
ms, dibagi menjadi jendela 10 ms. 40 md di antrian tengah (jendela 20 md) dan dalam prioritas rendah
jendela waktu antrian menjadi 40 ms saat tugas menyelesaikan pekerjaannya.
Implementasi MLFQ di Solaris OS adalah kelas penjadwal pembagian waktu.
Perencana akan menyediakan satu set tabel yang mendefinisikan sebagaimana mestinya
mengubah prioritas proses selama masa pakainya, berapa ukurannya
jendela yang akan dialokasikan dan seberapa sering meningkatkan prioritas tugas. Administrator
sistem dapat berinteraksi dengan tabel ini dan membuat penjadwal berperilaku
berbeda. Secara default, tabel ini memiliki 60 antrian dengan peningkatan bertahap
ukuran jendela dari 20 md (prioritas tinggi) hingga beberapa ratus md (prioritas terendah), dan
juga dengan peningkatan semua tugas satu kali per detik.
Perencana MLFQ lainnya tidak menggunakan tabel atau spesifik apa pun
aturan yang dijelaskan dalam bab ini, sebaliknya, mereka menghitung prioritas menggunakan
rumus matematika. Misalnya, penjadwal di FreeBSD menggunakan rumus untuk
menghitung prioritas tugas saat ini berdasarkan seberapa banyak prosesnya
menggunakan CPU. Selain itu, penggunaan CPU menurun seiring waktu, dan karenanya
Oleh karena itu, peningkatan prioritas terjadi dengan cara yang sedikit berbeda dari yang dijelaskan di atas. ini benar
disebut algoritma peluruhan. Sejak versi 7.1, FreeBSD telah menggunakan penjadwal ULE.
Terakhir, banyak perencana yang memiliki fitur lain. Misalnya saja beberapa
penjadwal mencadangkan tingkat yang lebih tinggi untuk pengoperasian sistem operasi dan karenanya
Dengan demikian, tidak ada proses pengguna yang dapat memperoleh prioritas tertinggi
sistem. Beberapa sistem memungkinkan Anda memberikan saran untuk membantu
perencana dapat menetapkan prioritas dengan benar. Misalnya saja dengan menggunakan perintah bagus
Anda dapat menambah atau mengurangi prioritas tugas dan dengan demikian menambah atau mengurangi
mengurangi kemungkinan program menggunakan waktu CPU.
MLFQ: Ringkasan
Kami telah menjelaskan pendekatan perencanaan yang disebut MLFQ. Namanya
tertutup dalam prinsip operasi - memiliki beberapa antrian dan menggunakan umpan balik
untuk memprioritaskan suatu tugas.
Bentuk akhir dari peraturan tersebut adalah sebagai berikut:
- Rule1: Jika prioritas(A) > Prioritas(B), tugas A akan diluncurkan (B tidak)
- Rule2: Jika prioritas(A) = Prioritas(B), A&B dimulai menggunakan RR
- Rule3: Ketika suatu tugas memasuki sistem, tugas tersebut ditempatkan dalam antrian prioritas tertinggi.
- Rule4: Setelah tugas menghabiskan waktu yang dialokasikan dalam antrean saat ini (berapa pun kali tugas tersebut membebaskan CPU), prioritas tugas tersebut dikurangi (tugas tersebut berpindah ke antrean).
- Rule5: Setelah beberapa periode S, pindahkan semua tugas dalam sistem ke antrian tertinggi.
MLFQ menarik karena alasan berikut - alih-alih membutuhkan pengetahuan tentangnya
sifat tugas sebelumnya, algoritma mempelajari perilaku tugas dan set di masa lalu
prioritas yang sesuai. Oleh karena itu, ia mencoba untuk duduk di dua kursi sekaligus - untuk mencapai kinerja untuk tugas-tugas kecil (SJF, STCF) dan menjalankan tugas-tugas panjang dengan jujur,
Pekerjaan memuat CPU. Oleh karena itu, banyak sistem, termasuk BSD dan turunannya,
Solaris, Windows, Mac menggunakan beberapa bentuk algoritma sebagai penjadwal
MLFQ sebagai garis dasar.
Bahan tambahan:
- (komputasi)
Sumber: www.habr.com