PRINSIP Concurrency dan MUTUAL EXCLUSION

Problem 5.1 (PRINSIP Concurrency)


Sepintas, mungkin tampak bahwa interleaving dan tumpang tindih merupakan modus fundamental berbeda dari eksekusi dan masalah yang berbeda sekarang. Bahkan, baik teknik dapat dilihat sebagai contoh pengolahan bersamaan, dan keduanya hadir sama masalah. Dalam kasus sebuah uniprocessor, masalah berasal dari dasar karakteristik sistem multiprogramming: Kecepatan relatif pelaksanaan proses yang tidak dapat diprediksi. Tergantung pada proses kegiatan lain, cara menangani OS menyela, dan kebijakan penjadwalan dari OS. Itu kesulitan berikut muncul:

  1. Berbagi sumber daya global penuh bahaya. Misalnya, jika dua proses baik menggunakan variabel global yang sama dan keduanya melakukan membaca dan menulis pada variabel itu, maka urutan yang membaca dan menulis berbagai dieksekusi adalah kritis. Satu contoh masalah ini ditunjukkan dalam ayat berikut.
  2. Hal ini menjadi sangat sulit untuk menemukan kesalahan pemrograman karena hasilnya biasanya tidak deterministik dan direproduksi

Race Condition
A race condition terjadi ketika banyak proses atau benang membaca dan menulis data item sehingga hasil akhir tergantung pada urutan pelaksanaan instruksi dalam beberapa proses. Mari kita mempertimbangkan dua contoh sederhana. Sebagai contoh pertama, anggaplah bahwa dua proses, P1 dan P2, berbagi global variabel a. Pada titik tertentu dalam pelaksanaannya, P1 update ke nilai 1, dan di beberapa titik dalam pelaksanaannya, update P2 ke nilai 2. Jadi, dua tugas dalam perlombaan ke menulis variabel a. Dalam contoh ini yang kalah “” dari perlombaan (proses yang update terakhir) menentukan nilai akhir a. Sebagai contoh kami yang kedua, mempertimbangkan dua proses, P3 dan P4, berbagi global variabel b dan c, dengan nilai awal b = 1 dan c = 2. Pada titik tertentu dalam perusahaan eksekutif-SI, P3 melaksanakan tugas b = b + c, dan pada beberapa titik dalam pelaksanaannya, P4 melaksanakan tugas c = b + c. Perhatikan bahwa dua proses update yang berbeda variabel. Namun demikian, nilai akhir dari kedua variabel tergantung pada urutan yang kedua proses menjalankan kedua tugas. Jika P3 menjalankan perusahaan menetapkanan pernyataan pertama, maka nilai final b = 3 dan c = 5. Jika P4 menjalankan perusahaan Tugas pertama pernyataan, maka nilai final dan b = 4 c = 3. Sulit bagi OS untuk mengelola alokasi sumber daya secara optimal. Misalnya, proses A dapat meminta penggunaan, dan diberikan kontrol, yang saya khusus / O saluran dan kemudian dihentikan sebelum menggunakan saluran tersebut. Ini mungkin tidak diinginkan untuk OS hanya untuk mengunci saluran tersebut dan mencegah penggunaannya oleh proses lain, memang ini dapat mengakibatkan kondisi deadlock.

Operating System Concerns

Apa desain dan isu-isu manajemen yang dibangkitkan oleh adanya konkurensi? Kita bisa daftar keprihatinan berikut:

  1. OS harus dapat melacak berbagai proses. Hal ini dilakukan dengan penggunaan blok kontrol proses dan diuraikan dalam Bab 4.
  2. OS harus mengalokasikan dan deallocate berbagai sumber daya untuk setiap proses aktif. Pada kali, beberapa proses menginginkan akses ke sumber daya yang sama. Sumber daya ini memasukkan
    • Processor waktu: ini adalah fungsi penjadwalan, dibahas dalam Bagian Keempat.
    • Memori: Sebagian besar sistem operasi menggunakan skema memori virtual. Topik kali ini adalahdibahas dalam Bagian Ketiga.
    • File: Dibahas di Bab 12.
    • perangkat I / O: Dibahas di Bab 11.
  3. OS harus melindungi data dan sumber daya fisik setiap proses terhadap yang dimaksudkan gangguan proses lainnya. Hal ini melibatkan teknik yang berhubungan dengan memori, berkas, dan I / O device. Perawatan umum ditemukan di perlindungan Bab 14.
  4. Fungsi proses, dan output yang dihasilkannya, harus independen kecepatan di mana pelaksanaannya dilakukan relatif terhadap kecepatan lain
  5. konkuren proses. Ini merupakan pokok bab ini.

Untuk memahami bagaimana masalah kecepatan kemerdekaan dapat diatasi, kita perlu melihat cara-cara proses dapat berinteraksi.

Process Interaction

  • Proses tidak menyadari satu sama lain: Ini adalah proses independen yang tidak dimaksudkan untuk bekerja sama. Contoh terbaik dari situasi ini adalah multiprogramming beberapa proses independen. Ini dapat menjadi batch pekerjaan atau sesi interaktif atau campuran. Meskipun proses tidak bekerja bersama-sama, OS perlu khawatir tentang persaingan untuk sumber daya. Misalnya, dua aplikasi independen mungkin baik ingin mengakses sama disk atau file atau printer. OS harus mengatur akses ini.
  • Proses tidak langsung mengenali satu sama lain: Ini adalah proses yang tidak selalu menyadari satu sama lain dengan ID masing-masing proses tapi berbagi akses ke beberapa objek, seperti I / O buffer. Proses tersebut menunjukkan kerjasamadalam berbagi objek umum.
  • Proses langsung mengenali satu sama lain: Ini adalah proses yang dapat berkomunikasi satu sama lain dengan ID dan proses yang dirancang untuk bekerja bersama pada beberapa kegiatan. Sekali lagi, proses seperti pameran kerjasama. Kondisi tidak akan selalu sama yang jelas seperti yang disarankan dalam Tabel 5.2. Sebaliknya, beberapa proses mungkin menunjukkan aspek dari kompetisi dan kerjasama. Namun demikian, adalah produktif untuk memeriksa masing-masing dari tiga item dalam daftar sebelumnya secara terpisah dan implikasinya untuk menentukan OS.

Competition among Processes for Resources
Proses datang bersamaan ke dalam konflik satu sama lain ketika mereka bersaing untuk penggunaan sumber daya yang sama. Dalam bentuk murni, kita dapat menggambarkan situasi sebagai berikut ini. Dua atau lebih proses perlu untuk mengakses sumber daya selama eksekusi mereka. Setiap proses menyadari adanya proses lainnya, dan setiap yang akan terpengaruh oleh eksekusi proses lain. Memang benar bahwa setiap proses harus meninggalkan negara dari setiap sumber daya yang menggunakan terpengaruh. Contoh sumber daya termasuk I / O, memori, waktu prosesor, dan jam. Tidak ada pertukaran informasi antara proses bersaing. Namun, pelaksanaan satu proses dapat mempengaruhi perilaku proses bersaing. Secara khusus, jika akses dua proses kedua ingin satu sumber daya, maka satu proses akan dialokasikan bahwa sumber daya oleh OS, dan yang lain harus menunggu. Oleh karena itu, proses yang ditolak akses akan melambat. Dalam kasus yang ekstrim, diblokir proses mungkin tidak pernah mendapatkan akses ke sumber daya dan karenanya tidak akan pernah berakhir dengan sukses. Dalam hal proses bersaing tiga masalah kontrol harus dihadapi. Pertama adalah kebutuhan untuk saling pengecualian. Misalkan dua atau lebih proses membutuhkan akses ke sumber daya nonsharable tunggal, seperti printer. Selama eksekusi, setiap proses akan mengirimkan perintah ke I / O device, menerima informasi status, mengirim data, dan / atau menerima data. Kita akan lihat seperti sumber daya sebagai sumber daya kritis, dan bagian dari program yang menggunakannya kritis Bagian dari program. Adalah penting bahwa hanya satu program pada satu waktu diizinkan pada bagian yang kritis. Kita tidak bisa hanya bergantung pada OS untuk memahami dan menegakkan pembatasan ini karena persyaratan rinci mungkin tidak jelas. Dalam hal printer, misalnya, kita menginginkan proses individu untuk memiliki kontrol terhadap sedangkan printer mencetak seluruh file. Jika tidak, baris dari proses bersaing akan akan disisipkan.

Cooperation among Processes by Sharing
Kasus kerjasama oleh berbagi mencakup proses yang berinteraksi dengan proses-proses lain tanpa secara eksplisit menyadarinya. Sebagai contoh, beberapa proses mungkin memiliki akses ke variabel bersama atau berbagi file atau database. Proses dapat menggunakan dan memperbarui data bersama tanpa referensi untuk proses yang lain tapi tahu bahwa proses lain mungkin memiliki akses ke sama data. Dengan demikian proses harus bekerja sama untuk memastikan bahwa data mereka berbagi telah dikelola secara baik. Mekanisme kontrol harus menjamin integritas berbagi data. Karena data yang diadakan pada sumber daya (perangkat, memori), masalah kontrol saling pengucilan, kebuntuan, dan kelaparan yang kembali hadir. Satunya perbedaan adalah bahwa item data dapat diakses dalam dua mode yang berbeda, membaca dan menulis, dan hanya operasi menulis harus saling eksklusif.
Cooperation among Processes by Communication


kedua kasus pertama yang telah kita bahas, setiap proses memiliki lingkungan yang terisolasi sendiri yang tidak termasuk proses lainnya. Interaksi di antara proses-proses yang tidak langsung. Dalam kedua kasus, ada berbagi. Dalam kasus persaingan, mereka berbagi sumber daya tanpa menyadari proses lainnya. Pada kasus kedua, mereka berbagi nilai-nilai, dan meskipun masing-masing proses tidak secara eksplisit menyadari proses-proses lain, sadar dari kebutuhan untuk mempertahankan integritas data. Ketika proses bekerja sama dengan komunikasi, namun berbagai proses berpartisipasi dalam upaya umum yang menghubungkan semua proses. Komunikasi menyediakan cara untuk sinkronisasi, atau koordinat, yang berbagai kegiatan. Biasanya, komunikasi dapat dicirikan sebagai terdiri dari pesan-pesan beberapa macam. Primitif untuk mengirim dan menerima pesan mungkin disediakan sebagai bagian dari bahasa pemrograman atau disediakan oleh kernel OS. Karena tidak ada yang dibagi antara proses dalam tindakan lewat pesan, saling pengecualian bukan persyaratan kontrol untuk kerjasama semacam ini. Namun, masalah kebuntuan dan kelaparan yang masih ada. Sebagai contoh tentang kunci, dua proses mungkin tersumbat, masing-masing menunggu untuk komunikasi dari lainnya. Sebagai contoh kelaparan, pertimbangkan tiga proses, P1, P2, dan P3, bahwa mantan hibit perilaku berikut. P1 berulang kali berusaha untuk berkomunikasi dengan baik P2 atau P3, dan P2 dan P3 keduanya berusaha untuk berkomunikasi dengan P1. A urutan bisa muncul di mana pertukaran informasi P1 dan P2 berulang kali, sedangkan P3 diblokir menunggu untuk komunikasi dari P1. Tidak ada jalan buntu, karena P1 tetap aktif, tapi P3 adalah kelaparan

Requirements for Mutual Exclusion
Setiap fasilitas atau kemampuan yang memberikan dukungan untuk dikecualikan harus saling memenuhi persyaratan sebagai berikut:

  1. Reksa pengecualian harus dilaksanakan: Hanya satu proses pada suatu waktu yang dibolehkan masuk bagian kritis, di antara semua proses yang memiliki bagian penting untuk hal yang sama berbagi sumber daya atau objek.
  2. Sebuah proses yang menghentikan di bagian tidak kritis yang harus melakukannya tanpa mempengaruhi proses lainnya.
  3. Ini tidak boleh mungkin untuk proses yang membutuhkan akses ke critical section harus meletakkan tanpa batas: tidak ada jalan buntu atau kelaparan.
  4. Ketika proses tidak ada bagian kritis, proses apapun yang masuk ke permintaan yang critical bagian harus diperbolehkan untuk masuk tanpa penundaan.
  5. Tidak ada asumsi yang dibuat tentang kecepatan relatif proses atau jumlah prosesor.
  6. Sebuah proses tetap dalam bagian penting dalam waktu yang terbatas saja.

Problem 5.2 (MUTUAL EXCLUSION: HARDWARE SUPPORT)


Dalam sistem uniprocessor, proses konkuren tidak dapat memiliki eksekusi tumpang tindih; mereka hanya dapat disisipkan. Selain itu, proses akan terus berjalan sampai memanggil layanan OS atau sampai terganggu. Oleh karena itu, untuk menjamin saling pengecualian, itu sudah cukup untuk mencegah proses dari diganggu. Kemampuan ini dapat diberikan dalam bentuk primitif didefinisikan oleh kernel OS untuk menonaktifkan dan memungkinkan interupsi. Sebuah proses kemudian dapat menegakkan saling pengecualian dengan cara berikut

(true) { while
/* disable interrupts */;
/* critical section */;
/* enable interrupts */;
/* remainder */;
}

Karena bagian kritis tidak dapat terganggu, saling pengecualian dijamin. Harga pendekatan ini, bagaimanapun, adalah tinggi. Efisiensi eksekusi bisa akan tampak rusak karena prosesor terbatas pada kemampuannya untuk interleave proses.

Special Machine Instructions
Pada tingkat perangkat keras, seperti yang disebutkan, akses ke lokasi memori mengecualikan setiap akses lain ke lokasi yang sama. Dengan ini sebagai landasan, prosesor desainer telah mengusulkan beberapa instruksi mesin yang melakukan dua tindakan atomically, 2 seperti membaca dan menulis atau membaca dan pengujian, dengan memori tunggal lokasi dengan satu instruksi mengambil siklus. Selama pelaksanaan instruksi, akses ke lokasi memori yang diblokir untuk referensi instruksi lainnya yang lokasi.

Compare&Swap Instruction

int compare_and_swap (int *word, int testval, int newval)
{ int oldval;
oldval = *word
if (oldval == testval) *word = newval;
return oldval;
}

Versi dari cek instruksi lokasi memori (* kata) terhadap nilai tes (testval). Jika nilai sekarang lokasi memori adalah testval, itu diganti dengan newval, kalau dibiarkan tidak berubah. Nilai memori tua selalu kembali; demikian, lokasi memori telah diperbarui jika nilai dikembalikan adalah sama dengan nilai tes. Oleh karena itu instruksi atom ini memiliki dua bagian: A membandingkan adalah dibuat antara nilai memori dan nilai tes, jika nilai berbeda swap terjadi. The membandingkan seluruh & swap fungsi dilakukan atomically, yaitu, tidak tunduk untuk interupsi. Versi lain dari instruksi ini mengembalikan nilai Boolean: true jika swap terjadi; palsu sebaliknya. Beberapa versi dari instruksi ini tersedia di hampir semua prosesor keluarga (x86, IA64, sparc, / 390, dll), dan sebagian besar sistem operasi menggunakan instruksi untuk mendukung konkurensi.

Exchange Instruction

void exchange (int register, int memory)
{ temp;
int
temp = memory;
memory = register;
register = temp;
}

Instruksi pertukaran isi register dengan sebuah lokasi memori. Kedua arsitektur Intel IA-32 (Pentium) dan arsitektur IA-64 (Itanium) mengandung instruksi XCHG. Menunjukkan protokol pengecualian timbal balik yang didasarkan pada penggunaan pertukaran instruksi. Sebuah baut bersama variabel diinisialisasi ke 0. Setiap proses menggunakan lokal variabel kunci yang diawali dengan 1. Proses hanya yang dapat masuk critical section adalah salah satu yang menemukan baut sama dengan 0. Ini termasuk semua proses lain dari kritis bagian dengan mengatur baut ke 1. Ketika sebuah proses meninggalkan critical section, ia ulang baut untuk 0, memungkinkan proses lain untuk mendapatkan akses ke critical section.

Properties of the Machine-Instruction Approach
Penggunaan khusus instruksi mesin untuk menegakkan pengecualian saling memiliki sejumlah keuntungan:

  • Hal ini berlaku untuk sejumlah proses di kedua prosesor tunggal atau beberapa prosesor berbagi memori utama.
  • Sangat sederhana dan karena itu mudah untuk memverifikasi.
  • Hal ini dapat digunakan untuk mendukung beberapa bagian kritis; setiap bagian kritis dapat didefinisikan oleh variabel sendiri. Ada beberapa kelemahan serius:
  • Sibuk menunggu digunakan. Jadi, sementara proses sedang menunggu akses ke bagian kritis, terus untuk mengkonsumsi waktu prosesor.
  • Kelaparan adalah mungkin. Ketika sebuah proses meninggalkan critical section dan lebih dari satu proses sedang menunggu, pemilihan proses menunggu adalah sewenang-wenang. Dengan demikian, beberapa proses tanpa batas bisa mengakses.
  • Deadlock adalah mungkin. Pertimbangkan skenario berikut pada prosesor-tunggal sistem. Proses P1 mengeksekusi instruksi khusus (misalnya, membandingkan & swap,pertukaran) dan memasuki critical section. P1 kemudian menyela untuk memberikan prosesor untuk P2, yang memiliki prioritas lebih tinggi. Jika P2 sekarang mencoba untuk menggunakan sumber daya yang sama dengan P1, itu tidak akan dapat mengakses karena saling eksklusi mekanisme. Oleh karena itu akan masuk ke dalam lingkaran menunggu sibuk. Namun, P1 akan pernah dikirim karena prioritas lebih rendah daripada proses lain siap, P2.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: