Ini adalah artikel asli ke-67 oleh pembuat Java
Di artikel sebelumnya, kami membedah esensi proses dan utas, dan bagaimana penerapannya. Dalam artikel ini, kita akan membahas cara berkomunikasi. Prosesnya memberi tahu saya bahwa utas tidak ingin hidup lagi. Saya tidak peduli tentang itu. Saya hanya ingin tahu. siapa saya? Bagaimana prosesnya memberi tahu saya? Apakah kemunculan proses dan matinya utas terkait dengan saya? Artikel ini memaparkan Anda. Di artikel sebelumnya, kami membedah esensi proses dan utas, dan bagaimana penerapannya. Dalam artikel ini, kami akan membahas cara berkomunikasi. Prosesnya memberi tahu saya bahwa utas tidak ingin hidup lagi. Saya tidak peduli tentang itu. ,siapa saya? Bagaimana prosesnya memberi tahu saya? Apakah kemunculan proses dan matinya utas terkait dengan saya? Artikel ini mengungkapkan untuk Anda ...
Komunikasi antarproses
Proses tersebut membutuhkan komunikasi yang sering dengan proses lain. Misalnya, dalam shell pipeline, output dari proses pertama harus diteruskan ke proses kedua agar dapat dilanjutkan di sepanjang pipeline. Oleh karena itu, jika diperlukan komunikasi antar proses, maka struktur data yang baik harus digunakan agar tidak terputus. Di bawah ini kami akan membahas masalah yang terkait dengan Inter Process Communication (IPC).
Mengenai komunikasi antar proses, ada tiga pertanyaan di sini
- Masalah pertama yang disebutkan di atas adalah bagaimana suatu proses meneruskan pesan ke proses lain.
- Pertanyaan kedua adalah bagaimana memastikan bahwa dua atau lebih utas tidak akan saling mengganggu. Misalnya, dua maskapai penerbangan mencoba mengambil kursi terakhir di pesawat untuk pelanggan yang berbeda.
- Masalah ketiga adalah urutan data, jika proses A menghasilkan data dan proses B mencetak data. Kemudian proses B harus menunggu A menghasilkan data sebelum mencetak data.
Perlu dicatat bahwa dua dari tiga pertanyaan terakhir ini juga berlaku untuk utas
Masalah pertama lebih mudah diselesaikan antar utas, karena mereka berbagi ruang alamat dan mereka memiliki lingkungan runtime yang sama. Dapat dibayangkan bahwa ketika Anda menulis kode multi-utas dalam bahasa tingkat tinggi, apakah masalah komunikasi utas lebih mudah diselesaikan?
Dua masalah lainnya juga berlaku untuk utas, dan masalah yang sama dapat diselesaikan dengan cara yang sama. Kami akan membahas ketiga masalah ini perlahan-lahan nanti, dan Anda dapat memiliki kesan di benak Anda sekarang.
Kondisi balapan
Dalam beberapa sistem operasi, proses yang bekerja sama dapat berbagi sumber daya yang sama yang dapat dibaca dan ditulis oleh satu sama lain. Sumber daya umum mungkin ada di memori atau di file bersama. Untuk memperjelas bagaimana proses berkomunikasi, di sini kami memberikan contoh: spooler. Ketika suatu proses perlu mencetak file, itu menempatkan nama file di direktori spooler khusus. Proses lain Daemon printer secara berkala akan memeriksa apakah file perlu dicetak, jika ada, akan mencetak dan menghapus nama file dari direktori.
Misalkan direktori back-end kita memiliki banyak slot (slot), angkanya 0, 1, 2, ..., dan setiap slot menyimpan nama file. Pada saat yang sama, misalkan ada dua variabel bersama: keluar, menunjuk ke file berikutnya yang akan dicetak; masuk, menunjuk ke slot kosong berikutnya dalam direktori. Anda dapat menyimpan kedua file ini dalam sebuah file yang dapat diakses oleh semua proses. Panjang file tersebut adalah dua kata. Pada saat tertentu, slot 0 hingga 3 kosong, dan slot 4 hingga 6 terisi. Pada saat yang sama, proses A dan proses B memutuskan untuk mengantrekan file untuk dicetak, situasinya adalah sebagai berikut
Hukum Murphy (Murphy) mengatakan bahwa segala sesuatu yang mungkin salah pada akhirnya akan beres. Saat kalimat ini berlaku, hal berikut mungkin terjadi.
Proses A membaca bahwa nilai dalam adalah 7, dan menyimpan 7 dalam variabel lokal next_free_slot. Pada saat ini, terjadi gangguan jam, dan CPU berpikir bahwa proses A telah berjalan cukup lama dan memutuskan untuk beralih ke proses B. Proses B juga membaca nilai in dan menemukan bahwa itu adalah 7. Kemudian proses B menulis 7 ke dalam variabel lokalnya next_free_slot Pada saat ini, kedua proses berpikir bahwa slot yang tersedia berikutnya adalah 7.
Proses B terus berjalan sekarang, ini akan menulis nama file cetak ke dalam slot 7, dan kemudian mengubah penunjuk masuk ke 8, dan kemudian memproses daun B untuk melakukan hal lain
Sekarang proses A mulai melanjutkan berjalan, karena proses A juga menemukan bahwa slot 7 kosong dengan memeriksa next_free_slot, jadi ini menyimpan nama file cetak di slot 7, dan kemudian memperbarui nilai masuk ke 8, karena slot 7 Sudah ada nilai yang ditulis oleh proses B dalam proses tersebut, sehingga nama file cetak proses A akan menimpa file proses B. Karena printer tidak dapat menemukan proses mana yang sedang diperbarui, fungsinya relatif terbatas, sehingga proses B tidak akan pernah dapat Hasil cetak, mirip dengan situasi ini, Artinya, ketika dua atau lebih utas mengubah data bersama pada saat yang sama, sehingga mempengaruhi kebenaran operasi program, ini disebut kondisi balapan (kondisi balapan) . Debugging kondisi balapan adalah tugas yang sangat sulit, karena dalam banyak kasus program berjalan dengan baik, tetapi dalam kasus yang jarang terjadi beberapa fenomena aneh yang tidak dapat dijelaskan akan terjadi. Sayangnya, masalah yang disebabkan oleh pertumbuhan multi-core ini membuat kondisi balapan semakin umum.
Bagian penting
Tidak hanya sumber daya yang dibagikan akan menyebabkan kondisi balapan, pada kenyataannya file bersama dan memori bersama juga akan menyebabkan kondisi balapan, jadi bagaimana cara menghindarinya? Mungkin satu kalimat bisa meringkas: Larang satu atau lebih proses dari membaca dan menulis sumber daya bersama (termasuk memori bersama, file bersama, dll.) Pada saat yang bersamaan . Dengan kata lain, diperlukan kondisi yang saling eksklusif (mutual exclusion), artinya jika suatu proses menggunakan shared variabel dan file dengan cara tertentu, proses lain selain proses tersebut dilarang melakukan hal tersebut. (Akses ke sumber daya terpadu). Titik kusut dari masalah di atas adalah bahwa proses B menggunakannya sebelum proses A penggunaan variabel bersama berakhir. Dalam sistem operasi apa pun, memilih primitif yang sesuai untuk saling pengecualian adalah masalah desain utama, dan kami akan fokus padanya selanjutnya.
Kondisi untuk menghindari masalah persaingan dapat dijelaskan secara abstrak. Seringkali, proses akan disibukkan dengan kalkulasi internal dan kalkulasi lain yang tidak akan menyebabkan kondisi balapan. Namun, terkadang proses akan mengakses memori atau file bersama, atau melakukan beberapa operasi yang dapat menyebabkan kondisi balapan. Kami menyebut fragmen program yang mengakses memori bersama sebagai wilayah kritis atau bagian kritis. Jika kita dapat beroperasi dengan benar sehingga tidak memungkinkan untuk dua proses yang berbeda berada di bagian kritis pada waktu yang sama, maka kondisi balapan dapat dihindari, hal ini juga dilakukan dari perspektif desain sistem operasi.
Meskipun desain di atas menghindari kondisi balapan, namun tidak dapat memastikan kebenaran dan efisiensi thread bersamaan yang mengakses data bersama secara bersamaan. Solusi yang baik harus mencakup empat kondisi berikut
Dari sudut pandang abstrak biasanya kita berharap bahwa perilaku proses seperti yang ditunjukkan pada gambar di atas, Pada t1 proses A memasuki bagian kritis, dan pada t2 proses B mencoba masuk ke bagian kritis karena proses A berada pada bagian kritis saat ini. Jadi proses B akan memblok hingga proses A meninggalkan bagian kritis pada t3, di mana saat itu proses B dapat diizinkan masuk ke bagian kritis. Akhirnya, pada t4, proses B meninggalkan bagian kritis, dan sistem kembali ke keadaan semula tanpa proses.
Sibuk menunggu saling pengecualian
Di bawah ini kami akan terus membahas berbagai desain untuk saling pengecualian. Dalam skenario ini, ketika suatu proses sibuk memperbarui memori bersama dari area kuncinya, tidak ada proses lain yang akan memasuki area utamanya dan tidak akan menimbulkan dampak apa pun.
Sela topengPada sistem prosesor tunggal, solusi paling sederhana adalah setiap proses menutupi semua interupsi segera setelah memasuki bagian kritis dan mengaktifkannya kembali sebelum meninggalkan bagian kritis. Setelah menutupi interupsi, interupsi jam juga akan ditutup. CPU hanya melakukan proses switching ketika terjadi interupsi jam atau interupsi lainnya. Dengan cara ini, CPU tidak akan beralih ke proses lain setelah melindungi interupsi. Oleh karena itu, setelah proses melindungi interupsi, ia dapat memeriksa dan memodifikasi memori bersama tanpa mengkhawatirkan proses lain yang mengintervensi untuk mengakses data bersama.
Apakah rencana ini layak? Siapa yang memutuskan bahwa proses tersebut memasuki area kritis? Bukankah ini proses pengguna? Ketika proses memasuki area kritis, proses pengguna menutup interupsi. Jika proses tidak pergi setelah jangka waktu yang lama, interupsi tidak akan diaktifkan. Apa hasilnya? Dapat menyebabkan penghentian seluruh sistem. Dan jika itu adalah multi-prosesor, interupsi pelindung hanya berlaku untuk CPU yang menjalankan instruksi penonaktifan. CPU lain akan terus berjalan dan dapat mengakses memori bersama.
Di sisi lain, akan lebih mudah bagi kernel untuk melindungi interupsi selama eksekusi beberapa instruksi yang memperbarui variabel atau daftar. Misalnya, jika beberapa proses terhenti saat memproses daftar siap, kondisi balapan dapat terjadi. Oleh karena itu, pelindung interupsi adalah teknologi yang sangat berguna untuk sistem operasi itu sendiri, tetapi untuk utas pengguna, interupsi pelindung bukanlah mekanisme pengecualian bersama yang umum.
Variabel kunciSebagai upaya kedua, Anda dapat menemukan solusi tingkat perangkat lunak. Pertimbangkan satu variabel bersama (kunci), awalnya dengan nilai 0. Ketika sebuah thread ingin memasuki area kritis, ia akan memeriksa terlebih dahulu apakah nilai kunci adalah 0. Jika nilai kunci adalah 0, proses akan menyetelnya ke 1 dan membiarkan proses memasuki area kritis. Jika status kunci adalah 1, proses akan menunggu hingga nilai variabel kunci menjadi 0. Oleh karena itu, nilai variabel kunci adalah 0 yang berarti tidak ada thread yang memasuki area kritis. Jika 1 berarti ada proses di area kritis. Setelah kita memodifikasi gambar diatas, maka menjadi sebagai berikut
Apakah metode desain ini benar? Apakah ada kekurangan? Misalkan suatu proses membaca nilai variabel kunci dan menemukan bahwa nilainya 0, dan sebelum menetapkannya ke 1, proses lain dijadwalkan untuk dijalankan, membaca variabel kunci ke 0, dan menetapkan variabel kunci ke 1. Kemudian utas pertama berjalan dan menetapkan nilai variabel kunci ke 1. Pada saat ini, dua proses di area kritis sedang berjalan pada waktu yang bersamaan.
Mungkin beberapa pembaca dapat berpikir bahwa jika Anda memeriksa sekali sebelum masuk dan memeriksa lagi di area utama yang ingin Anda tinggalkan, apakah tidak akan terselesaikan? Faktanya, situasi ini tidak membantu, karena utas lain mungkin masih mengubah nilai variabel kunci selama pemeriksaan kedua. Dengan kata lain, set-before-check ini bukan operasi atom, jadi itu juga akan Kondisi balapan terjadi.
Polling yang ketatMetode ketiga dari mutual exclusion pertama kali membuang potongan kode. Program di sini ditulis dalam bahasa C. Alasan menggunakan C adalah karena sistem operasi umumnya ditulis dalam C (terkadang dalam C ++), dan pada dasarnya tidak menggunakan Java Dalam bahasa seperti, Modula3, atau Pascal, kata kunci native di Java juga merupakan kode sumber yang ditulis dalam C atau C ++. Untuk menulis sistem operasi, perlu menggunakan bahasa C, bahasa yang kuat, efisien, dapat diprediksi dan berkarakteristik.Untuk Java, tidak dapat diprediksi karena akan kehabisan memori pada saat-saat kritis, dan ketika tidak sesuai Mekanisme pengumpulan sampah akan dipanggil untuk mendapatkan kembali memori. Dalam bahasa C, situasi ini tidak terjadi, dan bahasa C tidak secara aktif memanggil pengumpulan sampah untuk mendapatkan kembali memori. Untuk perbandingan C, C ++, Java dan empat bahasa lainnya, silakan merujuk ke
Kode untuk proses 0
while (TRUE) {while (turn! = 0) {/ * Masukkan region kritis * / critical_region (); turn = 1; / * Tinggalkan region kritis * / noncritical_region ();})Kode untuk proses 1
while (TRUE) {while (turn! = 1) {critical_region (); turn = 0; noncritical_region ();}}Dalam kode di atas, putaran variabel, dengan nilai awal 0, digunakan untuk merekam proses mana yang mendapat giliran untuk masuk ke bagian kritis, dan untuk memeriksa atau memperbarui memori bersama. Pada awalnya, proses 0 memeriksa belokan dan menemukan bahwa nilainya 0, sehingga memasuki bagian kritis. Proses 1 juga menemukan bahwa nilainya adalah 0, jadi ia terus menguji giliran dalam loop tunggu untuk melihat kapan nilainya menjadi 1. Memeriksa variabel secara terus menerus hingga muncul nilai tertentu, metode ini disebut busy waiting (busywaiting). Karena metode ini membuang-buang waktu CPU, ini umumnya harus dihindari. Kesibukan menunggu hanya dapat digunakan jika ada alasan untuk percaya bahwa waktu tunggu sangat singkat. Kunci yang digunakan untuk menunggu sibuk disebut spinlock.
Ketika proses 0 meninggalkan bagian kritis, ini menetapkan nilai belokan ke 1 untuk memungkinkan proses 1 memasuki bagian kritisnya. Dengan asumsi bahwa proses 1 segera meninggalkan zona kritis, kedua proses berada di luar zona kritis saat ini, dan nilai belokan disetel ke 0 lagi. Sekarang proses 0 menyelesaikan seluruh loop dengan sangat cepat, keluar dari bagian kritis, dan menyetel nilai turn ke 1. Pada saat ini, nilai belokannya adalah 1, dan kedua proses tersebut dijalankan di luar bagian kritisnya.
Tiba-tiba, proses 0 mengakhiri operasi di bagian non-kritis dan kembali ke awal pengulangan. Namun, saat ini tidak dapat masuk ke bagian kritis, karena nilai belokan saat ini adalah 1, dan proses 1 masih sibuk dalam operasi bagian non-kritis.Proses 0 hanya dapat melanjutkan perulangan while sampai proses 1 mengubah nilai belokan menjadi 0. Ini menunjukkan bahwa ketika satu proses dijalankan jauh lebih lambat daripada proses lainnya, bergiliran untuk memasuki bagian kritis bukanlah cara yang baik.
Keadaan ini melanggar 3 pernyataan sebelumnya yaitu Proses yang terletak di luar bagian kritis tidak boleh menghalangi proses lain , Proses 0 diblokir oleh proses di luar bagian kritis. Karena melanggar Pasal 3, itu juga bukan rencana yang baik.
Solusi PetersonMatematikawan Belanda T. Dekker pertama kali mengusulkan algoritma pengecualian timbal balik perangkat lunak yang tidak memerlukan rotasi ketat dengan menggabungkan variabel kunci dengan variabel peringatan
Kemudian, G.L.Peterson menemukan algoritma mutual exclusion yang lebih sederhana, algoritmanya adalah sebagai berikut
#define FALSE 0 # define TRUE 1 # definisikan N 2 / * Jumlah proses * / int giliran; / * Yang giliran sekarang * / int tertarik; / * Semua nilai diinisialisasi ke 0 (FALSE) * / void enter_region (proses int) {/ * Prosesnya adalah 0 atau 1 * / int lainnya; / * Nomor proses lain * / other = 1-proses; / * Proses lain * / tertarik = TRUE; / * Menunjukkan kesediaan untuk memasuki area kritis * / turn = proses ; sementara (turn == proses tertarik == true) {} / * loop kosong * /} void leave_region (int proses) {tertarik == FALSE; / * berarti meninggalkan wilayah kritis * /}Saat menggunakan variabel bersama (yaitu, sebelum memasuki wilayah kritisnya), setiap proses menggunakan nomor prosesnya sendiri 0 atau 1 sebagai parameter untuk memanggil enter_region. Pemanggilan fungsi ini akan menyebabkan proses menunggu hingga wilayah kritis aman. Setelah menyelesaikan operasi pada variabel bersama, proses akan memanggil leave_region untuk menunjukkan bahwa operasi telah selesai dan memungkinkan proses lain untuk masuk.
Sekarang mari kita lihat cara kerja metode ini. Pada awalnya, tidak ada proses di wilayah kritis, sekarang proses 0 panggilan enter_region. Ini menyatakan bahwa ia ingin memasuki bagian kritis dengan mengatur elemen array dan mengatur putar ke 0. Karena proses 1 tidak ingin memasuki wilayah kritis, enter_region segera kembali. Jika proses sekarang memanggil enter_region, proses 1 akan berhenti di sini sampai tertarik menjadi FALSE, yang hanya akan terjadi ketika proses 0 memanggil leave_region untuk keluar dari wilayah kritis.
Jadi yang telah dibahas di atas adalah kasus entri berurutan, sekarang mari kita pertimbangkan kasus di mana dua proses memanggil enter_region pada saat yang sama. Mereka semua menyimpan proses mereka sendiri ke dalam giliran, tetapi hanya ID proses terakhir yang disimpan yang valid, dan ID proses sebelumnya hilang karena penulisan ulang. Jika proses 1 adalah yang terakhir disimpan, maka giliran 1. Ketika kedua proses berjalan ke while, proses 0 tidak akan mengulang dan masuk ke bagian kritis, sedangkan proses 1 akan berulang tanpa batas dan tidak akan masuk ke bagian kritis sampai proses 0 keluar.
Instruksi TSLSekarang mari kita lihat solusi yang membutuhkan bantuan perangkat keras. Beberapa komputer, terutama yang dirancang untuk multiprosesor, akan memiliki instruksi berikut
TSL RX, KUNCIDisebut tes dan set kunci, itu membaca kunci kata memori ke dalam register RX, dan kemudian menyimpan nilai bukan nol di alamat memori. Instruksi baca dan tulis dapat dijamin terintegrasi, tidak terpisahkan, dan dijalankan bersama. Tidak ada prosesor lain yang diizinkan mengakses memori sampai akhir instruksi ini. CPU yang menjalankan instruksi TSL akan mengunci bus memori untuk mencegah CPU lain mengakses memori sebelum instruksi ini berakhir.
Poin pentingnya adalah bahwa mengunci bus memori tidak sama dengan menonaktifkan interupsi. Menonaktifkan interupsi tidak menjamin bahwa satu prosesor membaca dan menulis ke memori oleh prosesor lain antara operasi baca dan tulis. Dengan kata lain, melindungi interupsi pada prosesor 1 tidak berpengaruh pada prosesor 2. Cara terbaik untuk menjauhkan prosesor 2 dari memori hingga prosesor 1 selesai membaca dan menulis adalah dengan mengunci bus. Ini membutuhkan perangkat keras khusus (pada dasarnya, bus dapat memastikan bahwa bus digunakan oleh prosesor yang menguncinya, dan prosesor lain tidak dapat digunakan)
Untuk menggunakan instruksi TSL, kunci variabel bersama digunakan untuk mengoordinasikan akses ke memori bersama. Ketika kunci adalah 0, proses apapun dapat menggunakan instruksi TSL untuk mengaturnya ke 1, dan membaca dan menulis memori bersama. Saat operasi berakhir, proses menggunakan instruksi pindah untuk mengatur ulang nilai kunci ke 0.
Bagaimana instruksi ini mencegah dua proses memasuki bagian kritis pada saat yang bersamaan? Inilah solusinya
enter_region: TSL REGISTER, LOCK | Salin kunci ke register dan setel kunci ke 1 CMP REGISTER, # 0 | Apakah kuncinya 0? JNE enter_region | Jika bukan nol, kuncinya telah disetel, jadi loop RET | Kembali ke pemanggil dan masukkan wilayah kritis leave_region: MOVE LOCK, # 0 | Simpan 0 di kunci RET | Kembali ke pemanggilKita dapat melihat bahwa ide solusi ini sangat mirip dengan Peterson. Misalkan ada program bahasa assembly dengan total 4 instruksi sebagai berikut. Instruksi pertama menyalin nilai asli dari kunci ke register dan menyetel kunci ke 1. Kemudian nilai asli ini dibandingkan dengan 0. Jika bukan nol, itu berarti telah dikunci sebelumnya, dan program kembali ke awal dan menguji lagi. Setelah jangka waktu tertentu (baik panjang atau pendek), nilainya menjadi 0 (saat proses yang saat ini di bagian kritis keluar dari bagian kritis), proses kembali, dan kunci sekarang terkunci. Mengosongkan kunci ini juga relatif mudah. Program hanya perlu menyimpan 0 ke dalam kunci, dan tidak diperlukan instruksi sinkronisasi khusus.
Sekarang ada pendekatan yang sangat jelas, yaitu, proses akan memanggil enter_region sebelum memasuki wilayah kritis untuk menentukan apakah akan mengulang. Jika nilai kunci adalah 1, ia akan mengulang tanpa batas. Jika kunci 0, ia tidak akan memasuki loop dan memasuki wilayah kritis. Daerah. Saat proses kembali dari wilayah kritis, ia memanggil leave_region, yang menyetel kunci ke 0. Seperti semua solusi yang didasarkan pada masalah wilayah kritis, proses tersebut harus memanggil enter_region dan leave_region pada waktu yang tepat agar solusi berfungsi.
Instruksi lain yang dapat menggantikan TSL adalah XCHG, yang secara atomik menukar isi dari dua lokasi, misalnya register dan memory word, kodenya adalah sebagai berikut
enter_region: MOVE REGISTER, # 1 | Taruh 1 di memori XCHG REGISTER, LOCK | Tukarkan isi register dan kunci variabel CMP REGISTER, # 0 | Apakah kuncinya 0? JNE enter_region | Jika bukan 0, kunci telah disetel, dan loop RET | kembali ke pemanggil, memasuki wilayah kritis leave_region: MOVE LOCK, # 0 | menyimpan 0RET di kunci | kembali ke pemanggilInti dari XCHG sama dengan solusi TSL. Semua CPU Intel x86 menggunakan instruksi XCHG dalam sinkronisasi tingkat rendah.
Tidur dan bangun
Solusi Peterson, TSL, dan XCHG dalam solusi di atas semuanya benar, tetapi semuanya memiliki kelemahan yaitu menunggu sibuk. Inti dari solusi tersebut adalah sama, cek dulu apakah bisa masuk ke area kritis, jika tidak dibolehkan maka proses akan menunggu di tempat sampai diizinkan.
Metode ini tidak hanya membuang waktu CPU, tetapi juga dapat menyebabkan hasil yang tidak diharapkan. Perhatikan bahwa terdapat dua proses pada sebuah komputer, kedua proses tersebut memiliki prioritas yang berbeda, H adalah proses dengan prioritas lebih tinggi, dan L adalah proses dengan prioritas lebih rendah. Aturan penjadwalan proses adalah bahwa setiap kali proses H dalam keadaan siap, H mulai berjalan. Pada saat tertentu, L berada di bagian kritis, saat ini H menjadi status siap, siap dijalankan (misalnya, operasi I / O berakhir). Sekarang H sibuk menunggu, tetapi karena L tidak akan dijadwalkan saat H siap, L tidak akan pernah memiliki kesempatan untuk meninggalkan area kritis, sehingga H akan menjadi loop tanpa akhir. Situasi ini terkadang disebut masalah inversi prioritas (masalah pembalikan prioritas).
Sekarang mari kita lihat komunikasi primitif antar proses. Primitif ini memblokir daripada membuang waktu CPU sebelum mereka tidak diizinkan memasuki area kritis. Yang paling sederhana adalah tidur dan bangun. Tidur adalah panggilan sistem yang dapat menyebabkan pemanggil memblokir, yaitu panggilan sistem akan ditangguhkan hingga proses lain membangunkannya. Panggilan bangun memiliki satu parameter, yaitu proses yang akan dibangunkan. Cara lain adalah bahwa baik bangun maupun tidur memiliki parameter, yaitu alamat memori yang harus dicocokkan oleh tidur dan bangun.
Masalah produsen-konsumenSebagai contoh dari private primitif ini, mari kita pertimbangkan masalah produsen-konsumen, juga dikenal sebagai masalah buffer-terbatas. Kedua proses berbagi buffer ukuran tetap yang umum. Salah satunya adalah produsen (producer) yang menempatkan informasi ke dalam buffer, dan yang lainnya adalah konsumen (konsumen) yang akan dikeluarkan dari buffer. Masalah ini juga dapat digeneralisasikan sebagai masalah m produsen dan n konsumen, tetapi di sini kita hanya membahas situasi satu produsen dan satu konsumen, yang dapat mempermudah skema penerapan.
Jika antrian buffer sudah penuh, akan ada masalah saat produsen masih ingin menulis data ke buffer. Solusinya adalah membiarkan produsen tidur, yaitu menghalangi produsen. Tunggu hingga konsumen mengambil satu atau lebih item data dari buffer sebelum membangunkannya. Demikian pula, ketika konsumen mencoba mengambil data dari buffer, tetapi ternyata buffer itu kosong, konsumen akan tidur dan memblokir. Sampai produser memasukkan data baru ke dalamnya.
Logika ini terdengar relatif sederhana, dan metode ini juga memerlukan variabel yang disebut pemantauan. Variabel ini digunakan untuk memantau data di buffer. Untuk sementara kami menetapkannya sebagai hitungan. Jika buffer menyimpan hingga N item data, produser akan Setiap kali dinilai apakah hitungan mencapai N, jika tidak, produser menempatkan item data ke dalam buffer dan menambah nilai hitungan. Logika konsumen juga sangat mirip: tes pertama apakah nilai hitungan adalah 0, jika 0, konsumen tidur dan memblokir, jika tidak data diambil dari buffer dan hitungannya berkurang. Setiap proses juga memeriksa apakah utas lain harus dibangunkan, dan jika harus dibangunkan, maka bangun utasnya. Di bawah ini adalah kode konsumen produsen
#define N 100 / * Jumlah slot buffer * / int count = 0 / * Jumlah data buffer * / // Producer void producer (void) {int item; while (TRUE) {/ * Infinite loop * / item = production_item () / * Hasilkan item data berikutnya * / if (count == N) {sleep (); / * Jika buffer area penuh, itu akan memblokir * /} insert_item (item); / * put Data saat ini ditempatkan di buffer * / count = count + 1; / * Tingkatkan jumlah buffer count * / if (count == 1) {wakeup (consumer); / * Apakah buffer kosong? * /}}} // Konsumen membatalkan konsumen (void) {int item; while (TRUE) {/ * Infinite loop * / if (count == 0) {/ * Jika buffer kosong, buffer akan diblokir * / sleep ();} item = remove_item (); / * Hapus sebagian data dari buffer * / count = count-1 / * Kurangi jumlah buffer sebanyak satu * / if (count == N-1) {/ * Apakah buffernya penuh? * / bangun (produser);} consumer_item (item); / * print data item * /}}Untuk mendeskripsikan panggilan sistem seperti sleep dan wakeup dalam bahasa C, kami akan mengekspresikannya dalam bentuk panggilan fungsi perpustakaan. Mereka bukan bagian dari pustaka standar C, tetapi dapat digunakan pada sistem apa pun yang benar-benar memiliki panggilan sistem ini. Insert_item dan remove_item yang tidak diimplementasikan dalam kode digunakan untuk merekam item data ke dalam dan ke luar buffer.
Sekarang mari kita kembali ke masalah produsen-konsumen, akan ada kondisi balapan pada kode di atas, karena variabel count diekspos ke mata publik. Situasi berikut mungkin terjadi: buffer kosong, dan konsumen hanya membaca nilai count dan menemukan bahwa itu adalah 0. Pada titik ini penjadwal memutuskan untuk menangguhkan konsumen dan memulai produsen yang sedang berjalan. Produser menghasilkan sepotong data dan meletakkannya di buffer, lalu meningkatkan nilai hitungan, dan memperhatikan bahwa nilainya adalah 1. Karena hitungan 0, konsumen harus tertidur, sehingga produsen memanggil bangun untuk membangunkan konsumen. Namun secara logika konsumen tidak tidur pada saat ini, sehingga sinyal bangun akan hilang. Ketika konsumen mulai di lain waktu, ia akan memeriksa nilai hitungan yang dibaca sebelumnya, menemukan bahwa nilainya adalah 0, dan kemudian tidur di sini. Segera produsen akan mengisi seluruh penyangga, setelah itu akan memblokir, sehingga kedua proses akan tidur selamanya.
Inti dari masalah di atas adalah Bangun proses yang belum tidur akan menyebabkan bangun itu hilang . Jika tidak hilang, semuanya normal. Cara cepat untuk mengatasi masalah di atas adalah dengan menambahkan bit tunggu bangun. Saat sinyal bangun dikirim ke proses yang masih aktif, bit ini disetel ke 1. Kemudian, ketika proses mencoba untuk tidur, jika bit tunggu bangun adalah 1, bit tersebut dihapus, dan prosesnya tetap terjaga.
Namun, ketika ada banyak proses, Anda dapat mengatakan bahwa dengan meningkatkan jumlah bit tunggu bangun untuk membangunkan bit tunggu, ada 2, 4, 6, 8 bit tunggu bangun, tetapi ini tidak terselesaikan secara fundamental. masalah.
sinyal
Semaphore adalah metode yang diusulkan oleh E.W.Dijkstra pada tahun 1965, yang menggunakan variabel integer untuk mengakumulasi jumlah bangun untuk digunakan nanti. Dalam pandangannya, ada tipe variabel baru yang disebut semaphore. Nilai semafor bisa 0 atau bilangan positif apa pun. 0 berarti tidak perlu bangun, dan angka positif apa pun menunjukkan jumlah bangun.
Dijkstra mengusulkan agar semaphore memiliki dua operasi, sekarang down and up biasanya digunakan (yang masing-masing dapat diwakili oleh sleep dan wakeup). Operasi instruksi turun memeriksa apakah nilainya lebih besar dari 0. Jika lebih besar dari 0, nilainya dikurangi dengan 1; jika nilainya 0, proses akan tidur, dan operasi turun akan berlanjut saat ini. Memeriksa nilai, mengubah nilai variabel, dan kemungkinan operasi tidur semuanya diselesaikan oleh satu aksi atom tak terpisahkan. Ini akan memastikan bahwa setelah operasi semaphore dimulai, tidak ada proses lain yang dapat mengakses semaphore sampai operasi selesai atau diblokir. Atomicity ini sangat penting untuk memecahkan masalah sinkronisasi dan menghindari persaingan.
"
Operasi atom berarti bahwa di banyak bidang ilmu komputer lainnya, serangkaian operasi terkait semuanya dijalankan tanpa gangguan atau tidak dijalankan sama sekali.
Operasi up akan membuat nilai semaphore +1. Jika satu atau lebih proses tidur di semaphore dan tidak dapat menyelesaikan operasi down sebelumnya, sistem akan memilih salah satunya dan memungkinkan proses untuk menyelesaikan operasi down. Oleh karena itu, setelah operasi naik dilakukan pada semafor tempat proses tidur, nilai semafor masih 0, tetapi ada satu proses yang kurang tidur di atasnya. Meningkatkan nilai semaphore dan membangunkan suatu proses juga tidak dapat dipisahkan. Tidak ada proses yang akan diblokir dengan mengeksekusi, sama seperti tidak ada proses yang akan diblokir dengan menjalankan bangun di model sebelumnya.
Selesaikan masalah produsen-konsumen dengan semaphoresGunakan semaphore untuk menyelesaikan masalah bangun yang hilang, kodenya adalah sebagai berikut
#define N 100 / * Tentukan jumlah slot buffer * / typedef int semaphore; / * Semaphore adalah int * / semaphore mutex = 1; / * Control akses ke area utama * / semaphore empty = N; / * Hitung jumlah slot buffer kosong * / semaphore full = 0; / * Hitung jumlah slot buffer penuh * / void producer (void) {int item; while (TRUE) {/ * Konstanta TRUE adalah 1 * / item = producer_item (); / * Menghasilkan beberapa data di buffer * / down (kosong); / * Mengurangi jumlah slot kosong sebanyak 1 * / down (mutex); / * Masukkan area kunci * / insert_item (item); / * put Letakkan data di buffer * / up (mutex); / * Tinggalkan area kritis * / up (full); / * Isi buffer dengan jumlah slot penuh + 1 * /}) void consumer (void) {int item; while (TRUE ) {/ * Infinite loop * / down (full); / * Jumlah slot penuh di area buffer-1 * / down (mutex); / * Masukkan buffer * / item = remove_item (); / * Hapus data dari buffer * / up (mutex); / * Meninggalkan area kritis * / up (kosong); / * Jumlah slot kosong + 1 * / mengkonsumsi_item (item); / * Data proses * /}}Untuk memastikan bahwa semaphore dapat bekerja dengan benar, yang terpenting adalah mengimplementasikannya dengan cara yang tidak terpisahkan. Biasanya naik dan turun diimplementasikan sebagai panggilan sistem. Dan sistem operasi hanya perlu melindungi sementara semua interupsi saat melakukan operasi berikut: Periksa semaphore, perbarui, proses tidur jika perlu . Karena pengoperasian ini memerlukan sedikit instruksi, gangguan tidak akan menimbulkan dampak apa pun. Jika beberapa CPU digunakan, semaphore harus dilindungi oleh kunci. Gunakan instruksi TSL atau XCHG untuk memastikan bahwa hanya satu CPU yang beroperasi pada semafor pada waktu yang sama.
Menggunakan TSL atau XCHG untuk mencegah beberapa CPU mengakses semaphore pada saat yang sama sangat berbeda dengan menggunakan kesibukan menunggu oleh produsen atau konsumen untuk menunggu buffer lain dikosongkan atau diisi. Operasi sebelumnya hanya membutuhkan waktu beberapa milidetik, sedangkan produsen atau konsumen mungkin membutuhkan waktu lama.
Solusi di atas menggunakan tiga semaphore: satu disebut penuh, yang digunakan untuk mencatat jumlah slot buffer penuh; satu disebut kosong, yang mencatat jumlah slot buffer kosong; satu disebut mutex, yang digunakan untuk memastikan produsen dan konsumen Tidak akan masuk buffer pada saat bersamaan. Penuh diinisialisasi ke 0, kosong diinisialisasi ke jumlah slot di buffer, dan mutex diinisialisasi ke 1. Semaphore diinisialisasi ke 1 dan digunakan oleh dua atau lebih proses untuk memastikan bahwa hanya satu dari mereka yang dapat memasuki area kritis pada saat yang sama disebut semaphore biner. Jika setiap proses melakukan operasi turun sebelum memasuki area kritis dan melakukan operasi naik setelah meninggalkan area kritis, saling pengecualian dapat dipastikan.
Sekarang kami memiliki jaminan primitif antar proses yang baik. Kemudian mari kita lihat jaminan urutan interupsi
Dalam sistem yang menggunakan semaphore, cara alami untuk menyembunyikan interupsi adalah dengan melengkapi setiap perangkat I / O dengan semaphore, yang awalnya disetel ke 0. Setelah perangkat I / O dimulai, penangan interupsi segera melakukan operasi turun pada sinyal terkait, dan proses segera diblokir. Ketika interupsi masuk, penangan interupsi kemudian melakukan operasi naik pada semaphore terkait, yang dapat memulihkan proses yang diblokir. Pada langkah pemrosesan interupsi di atas, langkah kelima operasi server interupsi C adalah operasi naik yang dilakukan oleh penangan interupsi pada semaphore, sehingga pada langkah 6, sistem operasi dapat mengeksekusi driver perangkat. Tentu saja, jika beberapa proses sudah dalam status siap, penjadwal dapat memilih untuk menjalankan proses yang lebih penting selanjutnya, dan kita akan membahas algoritma penjadwalan nanti.
Kode di atas sebenarnya menggunakan semaphore dalam dua cara berbeda, dan perbedaan antara kedua semaphore ini juga sangat penting. Semaphore mutex digunakan untuk saling pengecualian. Ini digunakan untuk memastikan bahwa hanya satu proses yang dapat membaca dan menulis buffer dan variabel terkait setiap saat. Saling pengecualian adalah operasi yang diperlukan untuk menghindari kekacauan proses.
Semaphore lain adalah tentang sinkronisasi. Semaphore penuh dan kosong digunakan untuk memastikan terjadinya atau tidak terjadinya peristiwa. Dalam kasus ini, mereka memastikan bahwa produser berhenti berjalan saat buffer penuh; konsumen berhenti berjalan saat buffer kosong. Penggunaan kedua semaphore ini berbeda dengan mutex.
Mutex
Jika kemampuan penghitungan semaphore tidak diperlukan, versi sederhana dari semaphore dapat digunakan, yang disebut mutex (mutual exclusion). Keuntungan mutex terletak pada menjaga saling pengecualian di beberapa sumber daya bersama dan sepotong kode. Karena implementasi mutex sederhana dan efektif, ini membuat mutex sangat berguna saat mengimplementasikan paket thread ruang pengguna.
Mutex adalah variabel bersama di salah satu dari dua status: tidak terkunci dan terkunci. Dengan cara ini, hanya diperlukan satu bit biner untuk merepresentasikannya, tetapi dalam keadaan normal, biasanya diwakili oleh integer (integer). 0 berarti membuka kunci, semua nilai lainnya berarti mengunci, dan nilai yang lebih besar dari 1 berarti waktu penguncian.
Mutex menggunakan dua proses, ketika utas (atau proses) perlu mengakses area kunci, mutex_lock akan memanggil untuk mengunci. Jika mutex saat ini tidak terkunci (menunjukkan bahwa area kunci tersedia), panggilan berhasil dan thread pemanggil dapat dengan bebas memasuki area kunci.
mutex mutex_unlock mutex
mutex TSL XCHG mutex_lock mutex_unlock XCHG
mutex_lock:TSL REGISTER,MUTEX| 1CMP REGISTER,#0| 0 JZE ok| 0CALL thread_yield| JMP mutex_lock| ok: RET| mutex_unlcok:MOVE MUTEX,#0| mutex 0RET|mutex_lock enter_region
- TSL TSL TSL mutex mutex/TSL
- thread_yield CPU
enter_region mutex_lock thread_yield mutex_lock mutex_unlock
mutex_trylock
Futexes(synchronization)(locking) (Spin lock) CPU
futex (fast user space mutex)
futex Linux futex . (wait queue)
futex 32 (integer) 1(decrement and test) decrement and set Linux C futex (increment and test)
PthreadsPthreads mutex mutex mutex mutex
mutex Phread_mutex_init Pthread_mutex_destroymutex Pthread_mutex_lock Pthread_mutex_trylock mutex Pthread_mutex_unlock mutex
Pthreads (condition variables) mutex
mutex
pthread
Pthread_cond_wait Pthread_cond_signalPthread_cond_broadcast
"
#include < stdio.h > #include < pthread.h > #define MAX 1000000000/* */pthread_mutex_t the_mutex;pthread_cond_t condc,condp;/* */int buffer = 0;void *producer(void *ptr){/* */ int i; for(int i = 0;i < = MAX;i++){ pthread_mutex_lock(the_mutex);/* mutex */ while(buffer != 0){ pthread_cond_wait(condp,the_mutex); } buffer = i;/* */ pthread_cond_signal(condc);/* */ pthread_mutex_unlock(the_mutex); /* */ } pthread_exit(0); }void *consumer(void *ptr){/* */ int i; for(int i = 0;i < = MAX;i++){ pthread_mutex_lock(the_mutex);/* mutex */ while(buffer == 0){ pthread_cond_wait(condc,the_mutex); } buffer = 0;/* */ pthread_cond_signal(condp);/* */ pthread_mutex_unlock(the_mutex); /* */ } pthread_exit(0); }
Brinch Hansen Hoare (monitor) Pascal C C
monitor exampleinteger i;condition c;procedure producer();...end;procedure consumer();.end;end monitor;
(mutex) (binary semaphore)
-
(condition variables) wait signal full wait pthread signal
"
Brinch Hansen Hoare Hoare Brinch Hansen signal Brinch Hansen
signal
signal
Dengan kata lain, wait signal .
Pascal -
monitor ProducerConsumercondition full,empty;integer count;procedure insert(item:integer);beginif count = N then wait(full);insert_item(item);count := count + 1;if count = 1 then signal(empty);end;function remove:integer;beginif count = 0 then wait(empty);remove = remove_item;count := count - 1;if count = N - 1 then signal(full);end;count := 0;end monitor;procedure producer;beginwhile true do begin item = produce_item; ProducerConsumer.insert(item); endend;procedure consumer;beginwhile true dobeginitem = ProducerConsumer.remove;consume_item(item);endend;wait signal sleep wakeup sleep wakeup wait wait wait
Pascal Java Java Java synchronized Java synchronized synchronized
Java -
public class ProducerConsumer { static final int N = 100;// static Producer p = new Producer();// static Consumer c = new Consumer(); // static Our_monitor mon = new Our_monitor(); // static class Producer extends Thread{ public void run(){// run int item; while(true){// item = produce_item(); mon.insert(item); } } private int produce_item(){...}// } static class consumer extends Thread { public void run( ) {// run int item; while(true){ item = mon.remove();consume_item(item); } } private int produce_item(){...}// } static class Our_monitor {// private int buffer = new int; private int count = 0,lo = 0,hi = 0; // private synchronized void insert(int val){ if(count == N){ go_to_sleep();// }buffer = val;// hi = (hi + 1) % N; // count = count + 1;// 1 if(count == 1){ notify();// } } private synchronized void remove(int val){ int val; if(count == 0){ go_to_sleep();// } val = buffer;// lo = (lo + 1) % N;// count = count - 1;// 1 if(count = N - 1){ notify();// } return val; } private void go_to_sleep() { try{ wait( ); }catch(Interr uptedExceptionexc) {}; } } }(outer class) ProducerConsumer p c Producer Consumer Our_monitor
Our_monitor insert remove count lo hi lo = hi 0 N
Java Java Java wait notify sleep wakeup
. CPascal
CPU TSL XCHG CPU CPU
(messaage passing) send receive
send(destination, message);receive(source, message);send receive
(acknowledgement)
(authentication)
--
#define N 100/* buffer */void producer(void){ int item; message m;/* buffer */ while(TRUE){ item = produce_item();/* */ receive(consumer,m);/* */ build_message(m,item);/* */ send(consumer,m);/* */ } }void consumer(void){ int item,i; message m; for(int i = 0;i < N;i++){/* N */ send(producer,m);/* N */ } while(TRUE){ receive(producer,m);/* */ item = extract_item(m);/* */ send(producer,m);/* */ consume_item(item);/* */ } }N N N
- (mailbox) send receive
- (barrier)
ABD B C
--
A B A B
X "" X X A
B D A C A C B D B D B D --(Ready-Copy-Update,RCU)
Pilihan sebelumnya
|
Modern Operating Systemforth edition
https://www.encyclopedia.com/computing/news-wires-white-papers-and-books/interactive-systems
https://j00ru.vexillium.org/syscalls/nt/32/
https://www.bottomupcs.com/process_hierarchy.xhtml
https://en.wikipedia.org/wiki/Runtime_system
https://en.wikipedia.org/wiki/Execution_model
- Platform Seluler Baidu Menutup Saluran Android; Apple Akan Mendorong iPhone SE 2; Microsoft Open Sources Scalar | Berita Utama Geek
- Pembelajaran mesin mendominasi daftar gaji tinggi, dan blockchain sudah mati? Interpretasi status insinyur perangkat lunak pada tahun 2020
- Hitung tiga "kejahatan" Python! Mengapa orang yang memiliki kemampuan pemrograman 10 kali lebih baik dari saya memujinya?
- Kementerian Pendidikan mengumumkan daftar usulan 200 Pengawas Sekolah Nasional ke-11 dan 300 Pengawas Pendidikan Khusus