[Pert 11 & 12] Concurrency

Concurrency adalah :

- Komunikasi diantara proses

- Pembagian resource (sumber daya)

- Sinkronisasi dari beberapa proses

- Alokasi dari waktu proses

Masalah dalam Concurrency :

- Sumber daya disebar secara global

- Managemen dari alokasi sumber daya

- Programming yang error sulit untuk dicari

O/S Concern :

- Menjaga jalur dari proses yang aktif

- Mengalokasikan dan mengdelokasikan sumber daya, berupa :

  - Waktu processor

  - Memory

  - File

  - I/O Device

- Menjaga data dan sumber daya (resource)

- Hasil dari proses harus independen dari kecepatan eksekusi dari proses concurrent yang lain.

Kompetisi dalam proses untuk sumber daya :

- Mutual Exclusion

- Deadlock

- Starvation

Kerja sama dalam proses :

- Dalam hal Sharing (pembagian)

• Penulisan harus eksklusif satu sama yang lain
• Section yang critical digunakan untuk menyediakan integritas data

- Dalam hal Komunikasi

• Pesan dikirimkan
• Dapat memiliki deadlock
• Dapat memiliki starvation

Mutual Exclusion

- Hanya 1(satu) proses yang dapat berada di section critical dalam sebuah resource

- Sebuah proses yang menghentikan section non-critical harus melakukan hal tersebut tanpa menganggu proses lain

- Tidak ada deadlock ataupun starvation

- Sebuah proses harus tidak meng-delay akses ke section critical ketika tidak ada proses lain yang menggunakannya.

- Tidak ada asumsi yang dibuat tentang kecepatan relatif proses atau banyaknya proses

- Sebuah proses tetap berada di dalam critical section untuk waktu yang terbatas

Proposal untuk dapat mencapai Mutual Exclusion :

1. Menonaktifkan interupsi
2. Mengunci variable
3. Alternasi yang ketat
4. Solusi Peterson
5. Intruksi TSL

Penjelasan untuk poin-poin di atas :

1. Interrupt Disabling (pengnonaktifan interupsi)

• Proses berjalan sampai meminta servis dari operating system (OS) atau sampai proses tersebut di interupsi
• Pengnonaktifan interupsi di jamin akan mutual exclusion (pengecualian secara mutual)
• Processor dilimitkan dalam kemampuan untuk interleave program
• Multiprocessing (pengnonaktifan interupsi pada satu processor tidak akan menjamin mutual exclusion

2. Lock Variables

• Apabila lock = 0, lock akan diset ke = 1, kemudian akan masuk ke wilayah yang critical
• Apabila lock = 1, tunggu sampai lock = 0

3. Strict Alternation

(a) Proses 0

(b) Proses 1

4. Solusi Peterson

Solusi Peterson untuk mendapatkan mutual exclusion

5. Intruksi TSL

masuk dan meninggalkan critical region menggunakan intruksi TSL

masuk dan meninggalkan critical region menggunakan intruksi XCHG

Semaphore

- Variable yang spesial disebut semaphore digunakan untuk signaling

- Apabila proses sedang menunggu untuk sinyal, proses akan menunggu sampai sinyal tersebut sudah dikirim

- Menunggu dan operasi sinyal tidak dapat di-interupsi

- Queue (antrian) digunakan untuk menahan proses yang menunggu di dalam semaphore

- Semaphore merupakan variable yang memiliki nilai integer

   - Dapat di-inisialisasi ke angka non-negatif

   - Operasi untuk menunggu mengurangi nilai dari semaphore

   - Operasi untuk pensinyalan menambah nilai dari semaphore

Masalah dalam Producer dan Consumer :

• Satu atau lebih producer akan menghasilkan data dan meletakkan nya ke dalam sebuah buffer
• Consumer (single = satu) akan mengambil item keluar dari buffer sekaligus
• Hanya satu producer atau consumer yang dapat mengakses buffer dalam sekali waktu

(1)

(2)

Classic IPC Problem

1. Sleeping Barber's Problem

2. Dining Philosopher's Problem

• Philosopher eat / think (philosopher makan / mikir)
• Eating needs 2 forks (makan membutuhkan 2 garpu)
• Memilih 1(satu) garpu sekaligus
• Bagaimana cara mencegah deadlock

Solusi untuk masalah Dining Philosopher :

(1)

(2)

Read Writer's Problem :

• Berapa banyak pembaca pun masih dapat membaca file tersebut
• Hanya 1(satu) penulis saja dalam satu waktu yang dapat menulis file
• Ketika penulis sedang menulis pada file, tidak ada pembaca yang dapat mengakses nya (membaca)

Solusi untuk masalah Reader Writer :

(1)

(2)

Mutex

Mutex di pthread :

beberapa dari panggilan pthread berhubungan dengan kondisi variable

Contoh untk menyelesaikan masalah pada Produser - Konsumer :

(1)

(2)

(3)

Monitor

- Pembangun bahasa pemograman yang mengsupport akses terkontrol ke data yang dibagi

• Kompiler menambahkan sinkronisasi secara otomatis
• Dilaksanakan pada saat runtime

- Enkapsulasi

• Membagi struktur data
• Prosedur / fungsi yang mengoperasikan data
• Sinkronisasi antara proses memanggil prosedur tersebut

- Hanya 1 proses aktif di dalam monitor dalam waktu kapan pun

• Semua prosedur adalah bagian dari sektor critical

- Sinkronisasi tingkat tinggi mengijinkan sharing (pembagian) yang aman dari tipe data abstrak di antara proses concurrent

Cth :

monitor monitor-name

{

    shared variable declarations

    procedure body P1()

    {

       .....

     }

    procedure body P2()

    {

      ......

     }

    procedure body Pn()

    {

      ......

     }

     {

        initialization code

     }

}

- Mutual Exclusion

• Hanya 1(satu) proses yang dapat dieksekusi di dalam 
• Apabila proses kedua mencoba untuk masuk ke prosedur monitor, maka monitor akan mem-block sampai proses pertama selesai menggunakan monitor

- Setelah masuk ke monitor, proses dapat menemukan bahwa beliau sudah tidak dapat melanjutkan lagi

- kondisi variable disediakan oleh monitor

• proses dapat menunggu / memberikan sinyal ke yang lain untuk melanjutkan
• kondisi variable (condition variable) dapat di akses hanya dari dalam monitor
• proses menunggu menyerahkan monitor untuk sementara

- Untuk mengijinkan proses untuk menunggu di dalam monitor, variable kondisi harus di deklarasi sebagai :

condition x;

- Kondisi variable dapat digunakan dengan sistem menunggu (wait) dan signal

• Pengoperasian

wait (x);

signal (x);

• Operasi signal melanjutkan 1 proses yang ditunda. Apabila tidak ada proses yang ditunda, maka operasi signal tidak memiliki efek

Message Passing :

- Informasi berkomunikasi dari satu proses dengan proses lain melalui :

send (dest, &message)

receive (source, &message)

- Penerima dapat menentukan apapun
- Penerima dapat memutuskan untuk memblock atau tidak
- Tidak memerlukan ruang address yang dibagi (shared address spaces)
- pre-dates semaphore
- Dapat diaplikasikan ke single dan multi processor dan sistem terdistribusi


Operasi pada Message Passing :

- send ( )

• Synchronous
• Mengembalikan (return) setelah data dikirim
• Memblock apabila buffer telah penuh
• Asynchronous
• Mengembalikan (return) setelah I/O telah dimulai
• Selesai ?
• Pengecekan secara eksplisit
• Signal atau pengakuan (acknowledgement)

- receive ( )

• Synchronous
• Mengembalikan (return) setelah ada nya pesan (message)
• Akan memblock apabila belum ada
• Asynchronous
• Mengembalikan (return) pesan pertama apabila terdapat pesan
• Akan mengembalikan (return) indikasi apabila tidak ada pesan

- Komunikasi indirect (tidak langsung) - mailbox

• Pesan dikirim ke area yang sudah ditentukan -- mailbox
• Proses membaca pesan dari mailbox
• Mailbox harus dibuat dan diurus
• Pengirim akan di block apabila mailbox telah penuh
• Memungkinkan komunikasi many-to-many

- Di dalam 1 mesin dan di antara mesin

• MACH (CMU)
• GEC 4080

- Pesan yang diberikan kepada pengirim menandakan bahwa pesan yang asli telah diterima 

- Dapat saja synchronous atau asynchronous

- Bisa saja positif atau negatif

- Bisa saja dikirim satu sama lain di dalam pesan (implisit atau eksplisit)

binus.ac.id

skyconnectiva.com