Concurrency

 

A)   Concurrency

• Komunikasi antara proses.
• Berbagi sumber daya.
• Sinkronisasi beberapa proses.
• Alokasi waktu prosesor.
• Multiple applications.
  – Multiprogramming.
• Structured application.
  – Aplikasi dapat menjadi serangkaian proses konkuren.
• Struktur sistem operasi.
  – Sistem operasi adalah seperangkat proses atau thread.

B)   Masalah dalam Concurrency

• Berbagi sumber daya global.
• Pengelolaan alokasi sumber daya.
• Pemrograman error sulit untuk ditemukan.

C)   Contoh dari Masalah Concurrency

void echo()

{

chin = getchar();

chout = chin;

putchar(chout);

}

Process P1              Process P2

.                                .

in = getchar();              .

.                           in = getchar();

chout = chin;          chout = chin;

putchar(chout);               .

.                         putchar(chout);

.                                  .

D)   Tujuan O/S

• Melacak proses yang aktif.
• Alokasi dan dealokasi sumber daya.
  – Processor time
  – Memory
  – Files
  – I/O devices
• Melindungi data dan sumber.
• Hasil proses harus independen dari kecepatan eksekusi proses konkuren lainnya.

E)   Persaingan antara Proses untuk Sumber Daya

• Mutual exclusion.
  – Critical section
  *Hanya satu program pada satu waktu yang diperbolehkan dalam critical section.
  *Misalnya hanya satu proses pada suatu waktu diperbolehkan untuk mengirim perintah ke printer.
• Deadlock.
• Starvation.

F)   Kerjasama antara Proses

• Dengan berbagi.
  – Menulis harus eksklusif satu sama lain.
  – Critical section yang digunakan untuk menyediakan integritas data.
• Dengan komunikasi.
  –  Pesan yang lewat.
  * Mutual exclusion bukan persyaratan kontrol.
  – Mungkin untuk memiliki deadlock.
  * Setiap proses menunggu pesan dari proses lainnya.
  – Mungkin untuk memiliki starvation.
  * Dua proses mengirim pesan satu sama lain sementara proses lain menunggu pesan.

G)   Mutual Exclusion

• Hanya satu proses pada suatu waktu yang diperbolehkan dalam critical section untuk sumber daya.
• Sebuah proses yang menghentikan non-critical sectionnya harus melakukannya tanpa mengganggu proses lainnya.
• Tidak ada deadlock atau starvation.
• Sebuah proses tidak harus menunda akses ke critical section ketika tidak ada proses lain menggunakannya.
• Tidak ada asumsi yang dibuat tentang kecepatan proses relatif atau jumlah proses.Sebuah proses tetap dalam critical section untuk waktu yang terbatas.

H)   Mutual Exclusion dengan Busy Waiting

• Saran untuk mencapai mutual exclusion :
  1. Menonaktifkan interupsi.
  2. Variabel Lock.
  3. Pergantian ketat.
  4. Solusi Peterson.
  5. Instruksi TSL.

1. Menonaktifkan Interupsi
   – Sebuah proses berjalan sampai memanggil sebuah layanan sistem operasi atau sampai terganggu.
   – Menonaktifkan interupsi menjamin mutual exclusion.
   – Prosesor terbatas dalam kemampuannya untuk program interleave.
   – Multiprocessing.
   – Menonaktifkan interupsi pada satu prosesor tidak akan menjamin mutual exclusion.
2. Variabel Lock
   – Berbagi (lock) variabel, awalnya diatur ke 0.
   – Jika lock = 0, lock diatur ke = 1, kemudian memasuki critical region.
   – Jika lock = 1, menunggu sampai lock = 0.masalah: kondisi balapan.
3. Pergantian ketat
   Gambar 2-23. Sebuah solusi yang diusulkan untuk masalah critical region. (a) Proses 0. (b) Proses 1. Dalam kedua kasus, pastikan untuk mencatat titik koma mengakhiri pernyataan while. (Tanenbaum, A, 2008)
4. Solusi Peterson
   Gambar 2-24. Solusi Peterson untuk mencapai mutual exclusion. (Tanenbaum, A: 2008)
5. Instruksi TSL
   Gambar 2-25. Memasuki dan meninggalkan critical region menggunakan instruksi TSL. (Tanenbaum, 2007)        
   Gambar 2-26. Memasuki dan meninggalkan critical region menggunakan instruksi XCHG. (Tanenbaum, 20808)

I)   Semaphores

• Variabel khusus yang disebut semaphore digunakan untuk sinyal.
• Jika suatu proses menunggu sinyal, proses ditunda sampai sinyal dikirimkan.
• Operasi wait dan signal tidak dapat diganggu.
• Antrian digunakan untuk menyimpan proses yang menunggu di semaphore.
• Semaphore adalah variabel yang memiliki nilai integer.
  – Mungkin diinisialisasi ke nomor nonnegatif.
  – Operasi wait menurunkan nilai semaphore.
  – Operasi sinyal meningkatkan nilai semaphore.

J)   Masalah Produser-Konsumer

• Satu atau lebih produser menghasilkan data dan menempatkannya di dalam buffer.
• Konsumen tunggal membawa item keluar dari buffer satu per waktu.
• Hanya satu produser atau konsumer yang dapat mengakses buffer pada satu waktu.

K)   Masalah Produser-Konsumer menggunakan Semaphore

                        

L)   Masalah Klasik IPC

 

1. Masalah Sleeping Barber’s

 

     2. Masalah Dining Philospher’s

– Philospher makan/berpikir.
– Makan membutuhkan 2 fork.
– Memilih 1 fork.
– Bagaimana mencegah deadlock.

 

 

 

 

Solusi untuk masalah Dining Philsopher’s

 

      3. Masalah Reader’s Writer’s
– Sejumlah pembaca secara bersamaan dapat membaca file.
– Hanya satu penulis apat menulis ke file.
– Jika seorang penulis sedang menulis ke file, tidak ada pembaca yang dapat membacanya.Solusi untuk masalah Reader’s Writer’s

M)   Mutex

Implementasi dari mtex lock dan mutex unlock.

N)   Mutex dalam pthread

Beberapa pthread berkaitan dengan kondisi variabel.

O)   Menggunakan thread untuk Memecahkan Masalah Producer-Consumer

      

P)   Monitor

• Bahasa pemrograman mendukung akses kontrol ke data bersama.
  – Compiler menambahkan sinkronisasi secara otomatis.
  – Dilaksanakan saat runtime.
• Mengenkapsulasi.
  – Berbagi struktur data.
  – Prosedur / fungsi yang beroperasi pada data.
  – Sinkronisasi antara proses memanggil prosedur tersebut
• Hanya satu proses aktif di dalam monitor setiap saat.
• Semua prosedur merupakan bagian dari critical section.
• Sinkronisasi tingkat tinggi memungkinkan sharing yang aman dari tipe data abstrak antara proses konkuren.
  monitor monitor-name
   {
       shared variable declarations
       procedure body P1 (…) {
           . . .
       }
       procedure body P2 (…) {
           . . .
       }
       procedure body Pn (…) {
           . . .
       }
       {
           initialization code
  }
  }

 

• Mutual exclusion
  – Hanya satu proses dapat mengeksekusi di dalam, setiap saat.
  – Jika proses kedua mencoba memasukkan prosedur monitor, maka akan di blok sampai yang pertama telah melepaskan monitor.
• Sekali di dalam monitor, proses mungkin menemukan bahwa itu tidak dapat dilanjutkan.
• Variabel kondisi tersedia dalam monitor.
  – Proses bisa wait atau signal yang lain untuk melanjutkan.
  – Variabel kondisi hanya dapat diakses dari dalam monitor.
  – Proses menunggu melepaskan monitor untuk sementara.
• Untuk memungkinkan proses menunggu di dalam monitor, variabel kondisi harus dinyatakan, sebagai
  Condition x;
• Variabel kondisi hanya dapat digunakan dengan operasi wait dan signal.
  – Operasinya :
  wait (x);
  berarti bahwa proses meminta operasi ini ditunda sampai memanggil proses yang lain.signal (x);
  Operasi signal melanjutkan tepat satu proses yang ditunda. Jika tidak ada proses ditunda, maka operasi signal tidak        berpengaruh.

Q)   Message Passing

• Mengkomunikasikan informasi dari satu proses ke yang lainnya melalui :
  – send(dest, &message)
  * Synchronous
  – Return setelah data dikirim.
  – Blok jika buffer penuh.* Asynchronous
  – Pengembalian secepat I / O mulai.
  – Selesai?
  * Cek eksplisit
  * Signal atau acknowledgement
  – Blok jika buffer penuh (mungkin).– recieve (source, &message)
  * Synchronous
  – Return jika ada pesan.
  – Blok jika tidak.* Asynchronous
  – Pengembalian pesan pertama jika ada.
  – Pengembalian indikasi jika tidak ada pesan.
• Penerima dapat menentukan ANY.
• Penerima dapat memilih untuk memblokir atau tidak.
• Berlaku untuk single dan multi-processor dan sistem terdistribusi.
• Pre-dates semaphores.
• Tidak memerlukan ruang alamat bersama!
• Komunikasi tidak langsung – mailbox.
  – Pesan akan dikirim ke daerah bernama – mailbox.
  – Proses membaca pesan dari mailbox.
  – Mailbox harus diciptakan dan dikelola.
  – Pengirim memblok jika mailbox penuh.
  – Memungkinkan komunikasi many-to-many.
• Dalam satu mesin dan di antara mesin.
  – MACH (CMU)
  – GEC 4080 (pertukaran telepon British)
• Sebuah pesan kembali ke pengirim yang menunjukkan bahwa pesan asli telah diterima dengan benar.
• Dapat dikirimkan piggy-back pada pesan lain
  – Implisit atau eksplisit
• Mungkin synchronous atau asynchronous.
• Mungkin positif atau negatif.

R)   Menggunakan Message Passing untuk Memecahkan Masalah Producer Consumer

  

S)   Message Passing Issues

• Pesan scramble (checksum).
• Pesan hilang (acknowledgements).
• Acknowledgement hilang (urutan no.).
• Tujuan tidak terjangkau (bawah, berakhir).
• Mailbox penuh.
• Penamaan.
• Pembuktian keaslian.
• Kinerja (menyalin, membuat pesan).

 

*ADDITIONAL