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 =)
Pengenalan kepada Penjadual
Intipati masalah: Bagaimana untuk membangunkan dasar penjadual
Bagaimanakah rangka kerja dasar penjadual yang mendasari direka bentuk? Apakah andaian utama yang sepatutnya? Apakah metrik yang penting? Apakah teknik asas yang digunakan dalam sistem pengkomputeran awal?
Andaian Beban Kerja
Sebelum membincangkan dasar yang mungkin, mari kita buat beberapa penyimpangan yang memudahkan tentang proses yang berjalan dalam sistem, yang secara kolektif dipanggil beban kerja. Menentukan beban kerja adalah bahagian penting dalam dasar pembinaan, dan lebih banyak anda mengetahui tentang beban kerja, lebih baik dasar yang boleh anda tulis.
Mari kita buat andaian berikut tentang proses yang berjalan dalam sistem, kadangkala juga dipanggil pekerjaan (tugasan). Hampir semua andaian ini tidak realistik, tetapi perlu untuk perkembangan pemikiran.
- Setiap tugas dijalankan untuk jumlah masa yang sama,
- Semua tugas ditetapkan serentak,
- Tugasan yang diberikan berfungsi sehingga selesai,
- Semua tugas hanya menggunakan CPU,
- Masa berjalan setiap tugas diketahui.
Metrik Penjadual
Selain beberapa andaian tentang beban, alat lain untuk membandingkan dasar penjadualan yang berbeza diperlukan: metrik penjadual. Metrik hanyalah beberapa ukuran sesuatu. Terdapat beberapa metrik yang boleh digunakan untuk membandingkan penjadual.
Sebagai contoh, kita akan menggunakan metrik yang dipanggil masa pusing ganti (masa pusing ganti). Masa penyelesaian tugasan ditakrifkan sebagai perbezaan antara masa siap tugas dan masa ketibaan tugas dalam sistem.
Tturnaround=Tcompletion−Tarrival
Oleh kerana kita mengandaikan bahawa semua tugas tiba pada masa yang sama, maka Ta=0 dan dengan itu Tt=Tc. Nilai ini secara semula jadi akan berubah apabila kita mengubah andaian di atas.
Satu lagi metrik - keadilan (keadilan, kejujuran). Produktiviti dan keadilan sering menjadi ciri yang bertentangan dalam perancangan. Sebagai contoh, penjadual mungkin mengoptimumkan prestasi, tetapi dengan kos menunggu tugas lain dijalankan, sekali gus mengurangkan keadilan.
DULU DULU KELUAR (FIFO)
Algoritma paling asas yang boleh kita laksanakan dipanggil FIFO atau mula-mula masuk (masuk), mula-mula berkhidmat (keluar). Algoritma ini mempunyai beberapa kelebihan: ia sangat mudah untuk dilaksanakan dan ia sesuai dengan semua andaian kami dan melakukan tugas dengan baik.
Mari kita lihat contoh mudah. Katakan 3 tugasan telah ditetapkan serentak. Tetapi mari kita anggap bahawa tugas A tiba sedikit lebih awal daripada semua yang lain, jadi ia akan muncul dalam senarai pelaksanaan lebih awal daripada yang lain, sama seperti B berbanding C. Mari kita anggap bahawa setiap satu daripada mereka akan dilaksanakan selama 10 saat. Apakah purata masa untuk menyelesaikan tugasan ini dalam kes ini?
Dengan mengira nilai - 10+20+30 dan membahagikan dengan 3, kami mendapat purata masa pelaksanaan program bersamaan dengan 20 saat.
Sekarang mari cuba ubah andaian kita. Khususnya, andaian 1 dan dengan itu kami tidak akan lagi menganggap bahawa setiap tugas mengambil masa yang sama untuk dilaksanakan. Bagaimanakah prestasi FIFO kali ini?
Ternyata, masa pelaksanaan tugas yang berbeza mempunyai kesan yang sangat negatif terhadap produktiviti algoritma FIFO. Mari kita andaikan bahawa tugasan A akan mengambil masa 100 saat untuk diselesaikan, manakala B dan C masih akan mengambil masa 10 saat setiap satu.
Seperti yang dapat dilihat daripada rajah, purata masa untuk sistem ialah (100+110+120)/3=110. Kesan ini dipanggil kesan konvoi, apabila sesetengah pengguna jangka pendek sumber akan beratur selepas pengguna berat. Ia seperti barisan di kedai runcit apabila ada pelanggan di hadapan anda dengan troli penuh. Penyelesaian terbaik untuk masalah ini ialah cuba menukar daftar tunai atau berehat dan bernafas dalam-dalam.
Kerja Terpendek Didahulukan
Adakah mungkin untuk menyelesaikan situasi yang sama dengan proses wajaran berat? Sudah tentu. Satu lagi jenis perancangan dipanggilKerja Terpendek Didahulukan (SJF). Algoritmanya juga agak primitif - seperti namanya, tugas terpendek akan dilancarkan terlebih dahulu, satu demi satu.
Dalam contoh ini, hasil daripada menjalankan proses yang sama akan menjadi peningkatan dalam purata masa pemulihan program dan ia akan sama dengan 50 bukannya 110, yang hampir 2 kali lebih baik.
Oleh itu, untuk andaian yang diberikan bahawa semua tugas tiba pada masa yang sama, algoritma SJF nampaknya merupakan algoritma yang paling optimum. Walau bagaimanapun, andaian kami masih kelihatan tidak realistik. Kali ini kita ubah andaian 2 dan kali ini bayangkan bahawa tugasan boleh hadir pada bila-bila masa, dan bukan semua pada masa yang sama. Apakah masalah yang boleh menyebabkan ini?
Mari kita bayangkan bahawa tugas A (100c) tiba dahulu dan mula dilaksanakan. Pada t=10, tugasan B dan C tiba, setiap satu akan mengambil masa 10 saat. Jadi purata masa pelaksanaan ialah (100+(110-10)+(120-10))3 = 103. Apakah yang boleh dilakukan oleh penjadual untuk memperbaikinya?
Masa Terpendek untuk Siap Pertama (STCF)
Untuk memperbaiki keadaan, kami meninggalkan andaian 3 bahawa program ini dilancarkan dan berjalan sehingga selesai. Di samping itu, kami memerlukan sokongan perkakasan dan, seperti yang anda rasa, kami akan gunakan pemasa untuk mengganggu tugas yang sedang berjalan dan penukaran konteks. Oleh itu, penjadual boleh melakukan sesuatu pada saat tugas B, C tiba - berhenti melaksanakan tugas A dan meletakkan tugas B dan C ke dalam pemprosesan dan, selepas selesai, teruskan melaksanakan proses A. Penjadual sedemikian dipanggil STCFatau Kerja Preemptive First.
Keputusan perancang ini ialah keputusan berikut: ((120-0)+(20-10)+(30-10))/3=50. Oleh itu, penjadual sedemikian menjadi lebih optimum untuk tugas kita.
Masa Respons Metrik
Oleh itu, jika kita mengetahui masa berjalan tugasan dan bahawa tugasan ini hanya menggunakan CPU, STCF akan menjadi penyelesaian terbaik. Dan sekali pada masa awal, algoritma ini berfungsi dengan baik. Walau bagaimanapun, pengguna kini menghabiskan sebahagian besar masanya di terminal dan mengharapkan pengalaman interaktif yang produktif. Maka lahirlah metrik baharu - masa tindak balas (tindak balas).
Masa tindak balas dikira seperti berikut:
Tresponse=Tfirstrun−Tarrival
Oleh itu, untuk contoh sebelumnya, masa tindak balas ialah: A=0, B=0, C=10 (abg=3,33).
Dan ternyata algoritma STCF tidak begitu baik dalam keadaan di mana 3 tugas tiba pada masa yang sama - ia perlu menunggu sehingga tugas kecil selesai sepenuhnya. Jadi algoritma adalah baik untuk metrik masa pemulihan, tetapi tidak baik untuk metrik interaktiviti. Bayangkan jika anda sedang duduk di terminal cuba menaip aksara ke dalam editor dan perlu menunggu lebih daripada 10 saat kerana beberapa tugas lain sedang mengambil CPU. Ia tidak begitu menyenangkan.
Jadi kita berhadapan dengan masalah lain - bagaimana kita boleh membina penjadual yang sensitif kepada masa tindak balas?
Round Robin
Algoritma telah dibangunkan untuk menyelesaikan masalah ini Round Robin (RR). Idea asasnya agak mudah: daripada menjalankan tugasan sehingga ia selesai, kami akan menjalankan tugasan untuk tempoh masa tertentu (dipanggil kepingan masa) dan kemudian beralih kepada tugasan lain daripada baris gilir. Algoritma mengulangi kerjanya sehingga semua tugasan selesai. Dalam kes ini, masa berjalan program mestilah berbilang masa selepas itu pemasa akan mengganggu proses. Contohnya, jika pemasa mengganggu proses setiap x=10ms, maka saiz tetingkap pelaksanaan proses hendaklah gandaan 10 dan 10,20 atau x*10.
Mari lihat contoh: Tugasan ABC tiba serentak dalam sistem dan setiap satu daripadanya mahu berjalan selama 5 saat. Algoritma SJF akan menyelesaikan setiap tugasan sebelum memulakan tugasan yang lain. Sebaliknya, algoritma RR dengan tetingkap pelancaran = 1s akan melalui tugasan seperti berikut (Rajah 4.3):
(SJF Lagi (Bad for Response Time)
(Robin Bulat (Baik Untuk Masa Tindak Balas)
Purata masa tindak balas untuk algoritma RR ialah (0+1+2)/3=1, manakala bagi SJF (0+5+10)/3=5.
Adalah logik untuk menganggap bahawa tetingkap masa adalah parameter yang sangat penting untuk RR; semakin kecil ia, semakin tinggi masa tindak balas. Walau bagaimanapun, anda tidak seharusnya menjadikannya terlalu kecil, kerana masa penukaran konteks juga akan memainkan peranan dalam prestasi keseluruhan. Oleh itu, pilihan masa tetingkap pelaksanaan ditetapkan oleh arkitek OS dan bergantung kepada tugas-tugas yang dirancang untuk dilaksanakan di dalamnya. Konteks penukaran bukanlah satu-satunya operasi perkhidmatan yang membuang masa - program berjalan beroperasi pada banyak perkara lain, contohnya, pelbagai cache, dan dengan setiap suis adalah perlu untuk menyimpan dan memulihkan persekitaran ini, yang juga boleh mengambil banyak masa.
RR ialah penjadual yang hebat jika kita hanya bercakap tentang metrik masa tindak balas. Tetapi bagaimanakah metrik masa pemulihan tugas akan bertindak dengan algoritma ini? Pertimbangkan contoh di atas, apabila masa operasi A, B, C = 5s dan tiba pada masa yang sama. Tugasan A akan tamat pada 13, B pada 14, C pada 15s dan purata masa pusingan ialah 14s. Oleh itu, RR ialah algoritma terburuk untuk metrik pusing ganti.
Dalam istilah yang lebih umum, mana-mana algoritma jenis RR adalah adil; ia membahagikan masa CPU sama rata antara semua proses. Oleh itu, metrik ini sentiasa bercanggah antara satu sama lain.
Oleh itu, kami mempunyai beberapa algoritma yang berbeza dan pada masa yang sama masih terdapat beberapa andaian - bahawa masa tugas diketahui dan tugas itu hanya menggunakan CPU.
Mencampurkan dengan I/O
Pertama sekali, mari kita buang andaian 4 bahawa proses itu hanya menggunakan CPU; secara semulajadi, ini tidak berlaku dan proses boleh mengakses peralatan lain.
Apabila mana-mana proses meminta operasi I/O, proses memasuki keadaan disekat, menunggu I/O selesai. Jika I/O dihantar ke cakera keras, maka operasi sedemikian boleh mengambil masa sehingga beberapa ms atau lebih lama, dan pemproses akan melahu pada masa ini. Pada masa ini, penjadual boleh mengisi pemproses dengan sebarang proses lain. Keputusan seterusnya yang perlu dibuat oleh penjadual ialah apabila proses itu akan menyelesaikan I/Onya. Apabila ini berlaku, gangguan akan berlaku dan OS akan meletakkan proses yang memanggil I/O ke dalam keadaan sedia.
Mari kita lihat contoh beberapa tugasan. Setiap daripada mereka memerlukan 50ms masa CPU. Walau bagaimanapun, yang pertama akan mengakses I/O setiap 10ms (yang juga akan dilaksanakan setiap 10ms). Dan proses B hanya menggunakan pemproses 50ms tanpa I/O.
Dalam contoh ini kita akan menggunakan penjadual STCF. Bagaimanakah penjadual akan bertindak jika proses seperti A dilancarkan padanya? Dia akan melakukan perkara berikut: pertama dia akan menyelesaikan proses A sepenuhnya, dan kemudian memproses B.
Pendekatan tradisional untuk menyelesaikan masalah ini adalah dengan menganggap setiap subtugas 10 ms proses A sebagai tugas yang berasingan. Oleh itu, apabila bermula dengan algoritma STJF, pilihan antara tugasan 50 ms dan tugasan 10 ms adalah jelas. Kemudian, apabila subtugas A selesai, proses B dan I/O akan dilancarkan. Selepas I/O selesai, ia akan menjadi kebiasaan untuk memulakan proses 10ms A semula dan bukannya proses B. Dengan cara ini, adalah mungkin untuk melaksanakan pertindihan, di mana CPU digunakan oleh proses lain sementara yang pertama sedang menunggu untuk I/O. Dan akibatnya, sistem digunakan dengan lebih baik - pada masa proses interaktif sedang menunggu I/O, proses lain boleh dilaksanakan pada pemproses.
Oracle sudah tiada lagi
Sekarang mari kita cuba untuk menyingkirkan andaian bahawa masa berjalan tugas itu diketahui. Ini biasanya andaian yang paling teruk dan paling tidak realistik pada keseluruhan senarai. Malah, dalam purata OS biasa, OS itu sendiri biasanya tahu sedikit tentang masa pelaksanaan tugas, jadi bagaimanakah anda boleh membina penjadual tanpa mengetahui berapa lama tugas itu akan diambil untuk dilaksanakan? Mungkin kita boleh menggunakan beberapa prinsip RR untuk menyelesaikan masalah ini?
Jumlah
Kami melihat idea asas penjadualan tugas dan melihat 2 keluarga penjadual. Yang pertama memulakan tugas terpendek dahulu dan dengan itu meningkatkan masa pusing ganti, manakala yang kedua terbelah antara semua tugas secara sama rata, meningkatkan masa tindak balas. Kedua-dua algoritma adalah buruk di mana algoritma keluarga lain adalah baik. Kami juga melihat bagaimana penggunaan CPU dan I/O selari boleh meningkatkan prestasi, tetapi tidak menyelesaikan masalah dengan kewaskitaan OS. Dan dalam pelajaran seterusnya kita akan melihat perancang yang melihat masa lalu serta-merta dan cuba meramalkan masa depan. Dan ia dipanggil baris gilir maklum balas pelbagai peringkat.
Sumber: www.habr.com