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 =)
Pengantar Penjadwal
Inti masalahnya: Bagaimana mengembangkan kebijakan penjadwal
Bagaimana kerangka kebijakan penjadwal yang mendasarinya dirancang? Apa yang harus menjadi asumsi utama? Metrik apa yang penting? Teknik dasar apa yang digunakan dalam sistem komputasi awal?
Asumsi Beban Kerja
Sebelum membahas kemungkinan kebijakan, pertama-tama mari kita buat beberapa penyimpangan sederhana mengenai proses yang berjalan dalam sistem, yang secara kolektif disebut beban kerja. Mendefinisikan beban kerja adalah bagian penting dalam membuat kebijakan, dan semakin banyak Anda mengetahui tentang beban kerja, semakin baik kebijakan yang dapat Anda tulis.
Mari kita buat asumsi berikut tentang proses yang berjalan di sistem, kadang disebut juga pekerjaan (tugas). Hampir semua asumsi tersebut tidak realistis, namun diperlukan untuk perkembangan pemikiran.
- Setiap tugas berjalan untuk jumlah waktu yang sama,
- Semua tugas ditetapkan secara bersamaan,
- Tugas yang diberikan bekerja sampai selesai,
- Semua tugas hanya menggunakan CPU,
- Waktu berjalan setiap tugas diketahui.
Metrik Penjadwal
Selain beberapa asumsi tentang beban, diperlukan alat lain untuk membandingkan kebijakan penjadwalan yang berbeda: metrik penjadwal. Metrik hanyalah ukuran dari sesuatu. Ada sejumlah metrik yang dapat digunakan untuk membandingkan penjadwal.
Misalnya, kita akan menggunakan metrik yang disebut waktu penyelesaian (waktu penyelesaian). Waktu penyelesaian tugas didefinisikan sebagai perbedaan antara waktu penyelesaian tugas dan waktu kedatangan tugas dalam sistem.
Tturnaround=Tcompletion−Tarrival
Karena kita berasumsi bahwa semua tugas tiba pada waktu yang sama, maka Ta=0 dan Tt=Tc. Nilai ini tentu saja akan berubah ketika kita mengubah asumsi di atas.
Metrik lainnya - keadilan (keadilan, kejujuran). Produktivitas dan keadilan sering kali merupakan karakteristik yang berlawanan dalam perencanaan. Misalnya, penjadwal mungkin mengoptimalkan kinerja, namun harus menunggu tugas lain dijalankan, sehingga mengurangi keadilan.
PERTAMA DALAM PERTAMA KELUAR (FIFO)
Algoritma paling dasar yang dapat kita terapkan disebut FIFO atau pertama datang (masuk), pertama dilayani (keluar). Algoritme ini memiliki beberapa keunggulan: sangat mudah diimplementasikan dan memenuhi semua asumsi kami serta melakukan tugasnya dengan cukup baik.
Mari kita lihat contoh sederhana. Katakanlah 3 tugas ditetapkan secara bersamaan. Tapi mari kita asumsikan bahwa tugas A tiba sedikit lebih awal dari yang lain, sehingga akan muncul dalam daftar eksekusi lebih awal dari yang lain, sama seperti B relatif terhadap C. Mari kita asumsikan bahwa masing-masing tugas akan dieksekusi selama 10 detik. Berapa waktu rata-rata untuk menyelesaikan tugas-tugas ini dalam kasus ini?
Dengan menghitung nilai - 10+20+30 dan membaginya dengan 3, kita mendapatkan waktu rata-rata eksekusi program sebesar 20 detik.
Sekarang mari kita coba mengubah asumsi kita. Secara khusus, asumsi 1 dan dengan demikian kita tidak akan lagi berasumsi bahwa setiap tugas memerlukan jumlah waktu yang sama untuk dijalankan. Bagaimana kinerja FIFO kali ini?
Ternyata, waktu pelaksanaan tugas yang berbeda mempunyai dampak yang sangat negatif terhadap produktivitas algoritma FIFO. Anggaplah tugas A membutuhkan waktu 100 detik untuk diselesaikan, sedangkan tugas B dan C masing-masing masih membutuhkan waktu 10 detik.
Seperti terlihat pada gambar, waktu rata-rata untuk sistem adalah (100+110+120)/3=110. Efek ini disebut efek konvoi, ketika beberapa konsumen jangka pendek suatu sumber daya akan mengantri setelah konsumen berat. Ini seperti antrean di toko kelontong ketika ada pelanggan di depan Anda dengan troli penuh. Solusi terbaik untuk masalah ini adalah mencoba mengganti mesin kasir atau bersantai dan bernapas dalam-dalam.
Pekerjaan Terpendek Terlebih Dahulu
Apakah mungkin untuk memecahkan situasi serupa dengan proses kelas berat? Tentu. Jenis perencanaan lain disebutPekerjaan Terpendek Terlebih Dahulu (SJF). Algoritmenya juga cukup primitif - sesuai dengan namanya, tugas terpendek akan diluncurkan terlebih dahulu, satu demi satu.
Dalam contoh ini, hasil dari menjalankan proses yang sama adalah peningkatan rata-rata waktu penyelesaian program dan akan sama dengan 50 bukannya 110, yang hampir 2 kali lebih baik.
Jadi, dengan asumsi bahwa semua tugas tiba pada waktu yang sama, algoritma SJF tampaknya merupakan algoritma yang paling optimal. Namun asumsi kami tampaknya masih belum realistis. Kali ini kita ubah asumsi 2 dan kali ini bayangkan tugas bisa muncul kapan saja, dan tidak semuanya sekaligus. Masalah apa yang dapat ditimbulkan oleh hal ini?
Bayangkan tugas A (100c) datang lebih dulu dan mulai dijalankan. Pada t=10, tugas B dan C tiba, yang masing-masing membutuhkan waktu 10 detik. Jadi waktu eksekusi rata-rata adalah (100+(110-10)+(120-10))3 = 103. Apa yang dapat dilakukan penjadwal untuk memperbaikinya?
Waktu-untuk-Penyelesaian Terpendek Pertama (STCF)
Untuk memperbaiki keadaan, kami menghilangkan asumsi 3 bahwa program diluncurkan dan berjalan hingga selesai. Selain itu, kami memerlukan dukungan perangkat keras dan, seperti yang Anda duga, kami akan menggunakannya timer untuk menghentikan tugas yang sedang berjalan dan peralihan konteks. Jadi, penjadwal dapat melakukan sesuatu pada saat tugas B, C tiba - berhenti menjalankan tugas A dan memasukkan tugas B dan C ke dalam pemrosesan dan, setelah selesai, melanjutkan menjalankan proses A. Penjadwal seperti itu disebut STCFили Pekerjaan Preemptive Pertama.
Hasil dari perencana ini adalah sebagai berikut: ((120-0)+(20-10)+(30-10))/3=50. Dengan demikian, penjadwal seperti itu menjadi lebih optimal untuk tugas kita.
Waktu Respons Metrik
Jadi, jika kita mengetahui waktu berjalannya tugas dan tugas tersebut hanya menggunakan CPU, STCF akan menjadi solusi terbaik. Dan pada masa-masa awal, algoritma ini bekerja dengan cukup baik. Namun, pengguna kini menghabiskan sebagian besar waktunya di terminal dan mengharapkan pengalaman interaktif yang produktif. Maka lahirlah metrik baru - waktu merespon (tanggapan).
Waktu respons dihitung sebagai berikut:
Tresponse=Tfirstrun−Tarrival
Jadi, untuk contoh sebelumnya, waktu responsnya adalah: A=0, B=0, C=10 (abg=3,33).
Dan ternyata algoritma STCF tidak begitu baik dalam situasi di mana 3 tugas tiba pada waktu yang sama - ia harus menunggu sampai tugas-tugas kecil selesai sepenuhnya. Jadi algoritme ini bagus untuk metrik waktu penyelesaian, namun buruk untuk metrik interaktivitas. Bayangkan jika Anda sedang duduk di depan terminal mencoba mengetikkan karakter ke dalam editor dan harus menunggu lebih dari 10 detik karena ada tugas lain yang menyita CPU. Ini sangat tidak menyenangkan.
Jadi kita dihadapkan pada masalah lain - bagaimana kita bisa membuat penjadwal yang peka terhadap waktu respons?
Round Robin
Sebuah algoritma dikembangkan untuk memecahkan masalah ini Round Robin (RR). Ide dasarnya cukup sederhana: alih-alih menjalankan tugas sampai selesai, kita akan menjalankan tugas selama jangka waktu tertentu (disebut irisan waktu) dan kemudian beralih ke tugas lain dari antrian. Algoritme mengulangi pekerjaannya hingga semua tugas selesai. Dalam hal ini, waktu berjalannya program harus merupakan kelipatan waktu setelah pengatur waktu akan menghentikan proses. Misalnya, jika pengatur waktu menginterupsi suatu proses setiap x=10 md, maka ukuran jendela eksekusi proses harus kelipatan 10 dan menjadi 10,20 atau x*10.
Mari kita lihat contohnya: Tugas ABC tiba secara bersamaan di sistem dan masing-masing tugas ingin dijalankan selama 5 detik. Algoritma SJF akan menyelesaikan setiap tugas sebelum memulai tugas lainnya. Sebaliknya, algoritma RR dengan jendela peluncuran = 1s akan menjalankan tugas sebagai berikut (Gbr. 4.3):
(SJF Lagi (Buruk untuk Waktu Respons)
(Round Robin (Bagus Untuk Waktu Respons)
Rata-rata waktu respon untuk algoritma RR adalah (0+1+2)/3=1, sedangkan untuk SJF (0+5+10)/3=5.
Adalah logis untuk berasumsi bahwa time window adalah parameter yang sangat penting untuk RR; semakin kecil time window, semakin tinggi waktu responnya. Namun, Anda tidak boleh membuatnya terlalu kecil, karena waktu peralihan konteks juga akan berperan dalam kinerja secara keseluruhan. Dengan demikian, pilihan waktu jendela eksekusi ditentukan oleh arsitek OS dan bergantung pada tugas yang direncanakan untuk dijalankan di dalamnya. Peralihan konteks bukan satu-satunya operasi layanan yang membuang-buang waktu - program yang sedang berjalan beroperasi pada banyak hal lain, misalnya, berbagai cache, dan dengan setiap peralihan, lingkungan ini perlu disimpan dan dipulihkan, yang juga dapat memakan banyak waktu. waktu.
RR adalah penjadwal yang bagus jika kita hanya berbicara tentang metrik waktu respons. Namun bagaimana perilaku metrik waktu penyelesaian tugas dengan algoritme ini? Perhatikan contoh di atas, bila waktu pengoperasian A, B, C = 5s dan tiba pada waktu yang bersamaan. Tugas A akan berakhir pada 13, B pada 14, C pada 15 detik dan waktu penyelesaian rata-rata adalah 14 detik. Jadi, RR adalah algoritma terburuk untuk metrik turnover.
Dalam istilah yang lebih umum, algoritma tipe RR apa pun adalah adil; algoritma ini membagi waktu CPU secara merata di antara semua proses. Oleh karena itu, metrik ini terus-menerus bertentangan satu sama lain.
Jadi, kami memiliki beberapa algoritma yang kontras dan pada saat yang sama masih ada beberapa asumsi yang tersisa - bahwa waktu tugas diketahui dan tugas tersebut hanya menggunakan CPU.
Mencampur dengan I/O
Pertama-tama, mari kita hilangkan asumsi 4 bahwa proses hanya menggunakan CPU; tentu saja, hal ini tidak terjadi dan proses dapat mengakses peralatan lain.
Saat suatu proses meminta operasi I/O, proses memasuki keadaan diblokir, menunggu I/O selesai. Jika I/O dikirim ke hard drive, maka operasi tersebut dapat memakan waktu hingga beberapa ms atau lebih lama, dan prosesor akan menganggur saat ini. Selama waktu ini, penjadwal dapat menyibukkan prosesor dengan proses lainnya. Keputusan selanjutnya yang harus diambil oleh penjadwal adalah kapan proses akan menyelesaikan I/O-nya. Jika hal ini terjadi, interupsi akan terjadi dan OS akan menempatkan proses yang disebut I/O ke dalam status siap.
Mari kita lihat contoh beberapa masalah. Masing-masing membutuhkan waktu CPU 50ms. Namun, yang pertama akan mengakses I/O setiap 10 md (yang juga akan dieksekusi setiap 10 md). Dan proses B hanya menggunakan prosesor 50ms tanpa I/O.
Dalam contoh ini kita akan menggunakan penjadwal STCF. Bagaimana perilaku penjadwal jika proses seperti A diluncurkan di dalamnya? Dia akan melakukan hal berikut: pertama dia akan menyelesaikan proses A sepenuhnya, dan kemudian proses B.
Pendekatan tradisional untuk memecahkan masalah ini adalah dengan memperlakukan setiap subtugas 10 ms dari proses A sebagai tugas terpisah. Jadi, ketika memulai dengan algoritma STJF, pilihan antara tugas 50 ms dan tugas 10 ms sudah jelas. Kemudian, ketika subtugas A selesai, proses B dan I/O akan diluncurkan. Setelah I/O selesai, biasanya proses A yang berdurasi 10 md akan dimulai lagi, bukan proses B. Dengan cara ini, dimungkinkan untuk menerapkan tumpang tindih, di mana CPU digunakan oleh proses lain sementara proses pertama sedang menunggu proses I/O selesai. masukan/keluaran. Dan sebagai hasilnya, sistem dimanfaatkan dengan lebih baik - pada saat proses interaktif menunggu I/O, proses lain dapat dijalankan pada prosesor.
Oracle sudah tidak ada lagi
Sekarang mari kita coba menghilangkan asumsi bahwa waktu berjalannya tugas diketahui. Ini umumnya merupakan asumsi terburuk dan paling tidak realistis dalam daftar keseluruhan. Faktanya, pada rata-rata OS biasa, OS itu sendiri biasanya hanya mengetahui sedikit tentang waktu pelaksanaan tugas, jadi bagaimana Anda dapat membuat penjadwal tanpa mengetahui berapa lama waktu yang dibutuhkan untuk menjalankan tugas tersebut? Mungkin kita bisa menggunakan beberapa prinsip RR untuk mengatasi masalah ini?
Total
Kami melihat ide dasar penjadwalan tugas dan melihat 2 kelompok penjadwal. Yang pertama memulai tugas terpendek terlebih dahulu dan dengan demikian meningkatkan waktu penyelesaiannya, sedangkan yang kedua membagi semua tugas secara merata, sehingga meningkatkan waktu respons. Kedua algoritme tersebut buruk sedangkan algoritme dari keluarga lainnya baik. Kami juga melihat bagaimana penggunaan CPU dan I/O secara paralel dapat meningkatkan kinerja, namun tidak menyelesaikan masalah dengan kewaskitaan OS. Dan dalam pelajaran berikutnya kita akan melihat sebuah perencana yang melihat ke masa lalu dan mencoba memprediksi masa depan. Dan ini disebut antrian umpan balik multi-level.
Sumber: www.habr.com