Session 11&12 – Concurrency

Concurrency digunakan untuk mengelola interaksi dari semua proses.

Concurrency hadir pada:

• Banyak aplikasi -> Waktu sharing
• Aplikasi terstruktur -> Ekstensi dari rancangan modular
• Struktur sistem operasi -> Sistem operasi sendiri diimplementasikan sebagai sekumpulan proses atau thread

Masalah pada concurrency :

• Sharing sumber daya global

->Penulisan suatu shared variable: urutan penulisan sangat penting

->Masalah besar adalah penulisan tidak lengkap

• Pengelolaan alokasi resource secara optimal
• Sulit menemukan error pemrograman karena hasilnya bersifat tidak deterministic and reproducible.

Contoh masalah concurrency pada multiprocessor :

Jika diterapkan suatu aturan yang hanya satu proses dapat memasuki fungsi tersebut pada suatu waktu, maka:

• P1 & P2 berjalan pada processor berbeda
• P1 memasukkan echo lebih dahulu -> P2 mencoba masuk tetapi diblok – P2 suspend
• P1 melengkapi eksekusi -> P2 me-resume & mengeksekusi echo

Fokus Sistem Operasi

• Menjaga track dari berbagai proses
• Meng-alokasi-kan dan men-dealokasi-kan sumber daya
• Melindungi data & resource dari gangguan proses lain
• Memastikan bahwa proses & output terbebas dari kecepatan pemrosesan

Kompetisi antara proses dan resources :

1. Mutual Exclusion -> 1 proses diberikan hak khusus untuk menggunakan resources.
2. Deadlock -> banyak proses memperebutkan 1 resources
3. Starvation -> setiap proses berfikir bahwa ada proses lain yang sedang memakai resources tersebut padahal sebenarnya tidak ada yang memakai.

Kerja sama antar proses:

1. By Sharing (berbagi)
2. By Communication (berkomunikasi)

Syarat Mutual Exclusion :

• Hanya satu proses pada satu waktu yang dibolehkan ada dalam critical section bagi suatu resource
• Proses yang berhenti pada noncritical section-nya harus melakukan demikian tanpa gangguan dengan proses lain
• Tidak ada deadlock atau starvation
• Proses harus tidak didelay akses ke suatu critical section saat tidak ada proses lain yang menggunakannya
• Tidak ada asumsi mengenai kecepatan proses relatif atau jumlah proses
• Proses tetap di dalam critical section-nya hanya selama waktu terbatas tertentu (finite)

Interrupt Disabling

• Proses berjalan sampai ia meng-invoke suatu layanan SO atau sampai ia diinterupsi
• Disabling interrupts menjamin terwujudnya mutual exclusion
• Tidak akan bekerja pada arsitektur multiprocessor

Race Condition

1. Race condition terjadi ketika

• Banyak proses atau thread membaca &menulis item data
• Hasil akhir dari aktifitas baca & tulis tersebut tergantung pada urutan eksekusi dari proses yang terlibat.

2. Output tergantung pada siapa yang terakhir menyelesaikan race.

Semaphores

• Suatu nilai integer (bilangan bulat) yang digunakan untuk pensinyalan (signalling)antar proses.
• Hanya tiga operasi dapat dikerjakan pada suatu semaphore, semuanya bersifat atomik:
  • initialize
  • Decrement (semWait)
  • increment (semSignal)
• Antrian (queue) digunakan untuk menangani proses yang menunggu (waiting) pada semaphore
• Semaphore Kuat menggunakan FIFO
• Semaphore Lemah tidak menentukan urutan penghapusan dari antrian

Masalah Procesur-Consumer

• Situasi Umum:
  • Satu atau lebih producer membangkitkan data &menempatkannya dalam suatu buffer
  • Consumer tunggal mengambil item keluar buffer satu pada satu waktu
  • Hanya satu producer atau consumer yang boleh mengakses buffer pada satu waktu
  • Masalahnya:
  • Pastikan bahwa Producer tidak dapat menambahkan data ke dalam buffer yang penuh & comsumer tidak dapat menghapus data dari buffer kosong

Sleeping Barber Problem

Masalah sleeping barber menganalogikan proses dimana seorang barber bertugas menggunting rambut pelanggan, dan beristirahat jika tak ada pelanggan yang menunggu.

Masalah

Sleeping barber problem berdasar pada suatu barber shop dan barber-nya. Si barber hanya memiliki satu buah kursi untuk menggunting rambut dan beberapa kursi di ruang tunggu. Pada saat si barber telah selesai menggunting rambut seorang pelanggan, ia akan berjalan menuju ruang tunggu untuk melihat keadaannya. Jika ada pelanggan yang menunggu, ia akan membawanya ke kursi dan memotong rambutnya. Jika tidak, ia akan kembali ke ruangannya, dan beristirahat.

Setiap pelanggan ketika datang ke barber shop tersebut, harus melihat keadaan si barber terlebih dahulu. Jika si barber sedang tidur, ia akan membangunkannya dan duduk di kursi. Jika si barber sedang memotong rambut, ia akan berjalan menuju ruang tunggu, duduk dan menunggu gilirannya.

Solusi

Semua contoh permasalahan diatas dapat di dipecahkan oleh adanya mutex (mutual exclusion) yang memberi sebuah batasan dimana hanya satu unsur (si barber, atau satu pelanggan) yang dapat berubah status pada satu waktu. Si barber harus mendapatkan mutex sebelum melihat keadaan ruang tunggu, dan melepaskannya sebelum menggunting rambut dan istirahat. Setiap pelanggan wajib mendapatkan mutex sebelum masuk ke barber shop, dan melepaskannya ketika ia duduk di ruang tunggu dan kursi barber.

Dining Philosophers Problem

Masalah

Pada masalah Dining Philosophers ini, beberapa proses dianalogikan sebagai 5 orang yang berkumpul pada sebuah meja makan dengan masing-masing makanan mereka yang telah disediakan. Pada dasarnya, setiap orang hanya dapat melakukan dua hal dan hanya satu pada satu waktu, memakan dan/atau menunggu. Terdapat pula 5 buah sumpit (bukan 5 pasang) diantara setiap piring makanan, yang merupakan analogi dari shared resources.

Agar seseorang dapat makan, ia membutuhkan sepasang sumpit, dan hanya dapat mengambilnya dari sisi kiri atau sisi kanannya. Setiap orang tak pernah berbicara pada orang-orang yang lainnya, maka ada peluang yang sangat besar akan terjadi deadlock. Apabila seseorang telah mengambil sebuah sumpit, dan menunggu sumpit kedua yang sedang dipakai oleh orang lain, dan orang itu pula menunggu sumpit kedua yang sedang dipakai, dan seterusnya, hingga terjadi sebuah rantai dimana setiap keingingan orang-orang tersebut tidak dapat terpenuhi.

Masalah yang dihadapi oleh orang-orang di meja makan menjadi analogi masalah-masalah pada pemrograman komputer secara nyata, ketika program-program membutuhkan akses eksklusif kepada shared resources.

Solusi

A. Solusi Waiter: solusi sederhana ini dilakukan dengan mengadakan seorang waiter yang senantiasa mengawasi penggunaan sumpit di meja makan. Ketika empat buah (dua pasang) sumpit sedang dipakai, orang berikutnya yang ingin memakai sumpit harus meminta izin kepada sang waiter, yang hanya dapat diberi ketika salah satu sumpit telah selesai terpakai.

Contoh: Misalkan ke-lima orang tersebut dinamakan dari A sampai E secara berurutan. Ketika A dan C sedang makan, 4 buah sumpit sedang terpakai. B tidak memiliki kedua sumpit, dan D dan E memiliki satu buah sumpit diantara mereka. Apabila D ingin makan dan mengambil sumpit ke-lima, deadlock sangat mungkin terjadi. Maka waiter akan meminta D untuk menunggu, hingga pada saat salah satu sumpit telah selesai dipakai.

B. Solusi Hirarki Resource: pada intinya, resources (sumpit) di meja makan telah diberi susunan hirarki. Setiap permintaan orang terhadap sebuah sumpit harus dilakukan pada susunan tertentu, dan dikembalikan pada susunan sebaliknya. Dalam hal ini, setiap orang dapat mengambil sumpit dimanapun diatas meja. Misalkan setiap sumpit diberi nomor sebagai tingkat hirarki dari 1 sampai 5, seseorang hanya dapat mengambil sumpit dengan nomor yang paling rendah, kemudian mengambil sumpit yang setingkat lebih tinggi. Ketika ia hendak mengembalikannya, orang itu harus meletakkan sumpit dengan nomor yang lebih tinggi terlebih dahulu, lalu yang lebih rendah.

Readers-Writers Problem

Suatu area data dishare antar banyakproses

Beberapa proses hanya membaca area data, beberapa hanya menulis ke area tersebut.

Kondisi :

• Banyak readers boleh membaca file at
• Hanya satu writer pada satu waktu yang

dapat menulis

• Jika suatu writer sedang menulis ke file, maka tidak ada reader yang dapat membacanya

Monitor

Monitor merupakan suatu konsepsi bahasa pemrograman yang menyediakan fungsi sama dengan semaphore & lebih mudah dikontrol.

Diimplementasikan dalam sejumlah bahasa pemrograman, termasuk Concurrent Pascal, Pascal-Plus,Modula-2, Modula-3, dan Java.

Message Passing

Digunakan untuk komunikasi antara 1 proses dengan proses lainnya.

Fungsi aktual dari message passing normalnya disediakan dalam bentuk pasangan primitif:

–   send (destination, message)

–   receive (source, message)

 

Session 13&14 – Deadlock

Deadlock

• Pada sistem multiprogramming, beberapa proses mungkin saja harus berkompetisi untuk menggunakan sumber daya yang jumlahnya terbatas. Jika sebuah proses me-request sumber daya dan sumber daya tersebut tidak tersedia pada saat itu (sedang dipegang oleh proses lain), maka proses tersebut akan memasuki status wait (proses diblok). Status proses yang sedang menunggu tersebut bisa saja tidak akan pernah berubah karena sumber daya yang di-request proses tersebut sedang dipegang oleh proses lain yang juga sedang menunggu. Situasi demikian dinamakan sebagai deadlock.
• Berdasarkan uraian pada poin di atas, dapat disimpulkan bahwa deadlock terjadi saat dua atau lebih proses menunggu suatu kejadian selama tak terhingga karena kejadian tersebut hanya bisa disebabkan oleh sebuah proses yang sedang menunggu.
• Permanent blocking dari sekumpulan proses yang saling bersaing mendapatkan sumber daya sistem atau komunikasi
• Tidak ada solusi yang efisien
• Mencakup  kebutuhan yang bertentangan bagi sumber daya oleh dua atau lebih proses

Ilustrasi Deadlock

 

1. Kejadian sebelum deadlock
2. Kejadian setelah deadlock

Contoh Deadlock :

 

Contoh tidak deadlock :

Kondisi untuk Deadlock :

• Mutual exclusion -> Hanya satu proses yang boleh menggunakan suatu sumber daya pada satu waktu
• Hold-and-wait -> Suatu proses boleh memegang sumber daya yang dialokasikan selama menunggu assignment yang lain
• No preemption -> tidak ada sumber daya yang dapat dipaksa dihilangkan dari suatu proses yang memegangnya
• Circular wait -> adanya rantai tertutup (closed-chain) proses-proses, sehingga setiap proses memegang setidaknya satu sumber daya yang diperlukan oleh proses berikutnya dalam rantai tersebut

Pada gambar (a) diatas merupakan gambar kemungkinan terjadinya suatu deadlock, sedangkan gambar (b) merupakan kejadian disaat deadlock sudah terjadi.

Gambar saat kondisi deadlock :

 

Solusi masalah deadlock :

 

Strategi untuk mencegah deadlock  :

• Biarkan saja masalahnya (menurut algoritma Ostrich)
• deteksi dan recorvery
• Dynamic avoidance dengan pengalokasian resource dengan hati-hati.
• Pencegahan

 

Deadlock Avoidance

• Kebutuhan resource maksimum harus dinyatakan sebelumnya
• Proses di bawah konsiderasi harus bersifat independen, tidak ada kebutuhan

Sinkronisasi

• Harus ada sejumlah fix sumber daya yang akan dialokasikan
• Tidak ada proses yang boleh exit selama memegang resource

Contoh safe state:

Contoh unsafe state :

Contoh safe dan unsafe state :

Ket : a)safe state , b)safe state, c)unsafe state

Pencegahan Deadlock :

• Mutual Exclusion -> Harus didukung oleh sistem operasi
• Hold and Wait -> Mengharuskan suatu proses meminta (request) semua sumber daya yang dibutuhkannya pada satu waktu
• No Preemption

-> Proses harus melepaskan sumber daya dan merequest lagi

-> SO boleh men-preempt suatu proses untuk mengharuskannya melepas sumber dayanya

• Circular Wait -> Mendefinisikan suatu pengurutan linier dari jenis-jenis sumber daya

STARVATION

Starvation adalah sebuah algoritma untuk mengalokasikan sejumlah sumber informasi, dan mungkin memberikan shortest job first, tapi memungkinkan juga untuk terjadi penundaan waktu yg sangat panjang, meskipun tidak diblock. Maka solusi untuk mengatasi starvation adalah first-come first-serve algorithm.

Deadlock Recovery

Digunakan untuk membatalkan semua proses yg sudah deadlock (untuk proses terminasi). Untuk mencegah terjadinya interupsi sumber informasi adalah dengan :

• memilih korbannya (mengurangi biaya)
• rollback, artinya mengembalikan semua nilai menjadi safe state
• starvation, proses yang sama mungkin bisa diambil dengan diambil sebagai korban

Deadlock Handling

Dengan mengkombinasikan 3 pendekatan yaitu :

• Prevention
• Avoidance
• Detection

Memungkinkan untuk memilih pendekatan yang optimal untuk setiap sumber daya dalam suatu sistem. Partisi sumber informasi digambarkan dalam urutan kata dalam sistem.

Memastikan menggunakan pendekatan yang tepat dalam mengatasi deadlock dalam setiap class.

—————————————————————————————————————————————-

Contoh soal Deadlock :

Tugas dari Slide Binusmaya

1.

 

Terdapat 3 proses yaitu proses A, proses B dan proses C.

Saldo awal di bank yaitu 3+2+2+3=10

Tapi karena sudah dipakai oleh proses A,B dan C maka sisa saldo menjadi 3.

Sekarang kita mau membuktikan apakah state tersebut safe atau non safe dan berapa nilai RB (resources bank).

Langkah pertama melihat berapa kekurangan saldo yang dibutuhkan dari masing-masing proses.

• Proses A membutuhkan 9, sedangkan baru memiliki 3, jadi 9-3=6
• Proses B membutuhkan 4, sedangkan baru memiliki 2, jadi 4-2=2
• Proses C membutuhkan 7, sedangkan baru memiliki 2, jadi 7-2=5

Dari ketiga nilai tersebut maka yang memungkinkan untuk bank meminjamkan saldonya adalah proses B.

Langkah-langkahnya adalah:

• Bank meminjamkan proses B sebanyak 2, jadi sekarang saldo di bank tersisa 1.
• B mengembalikan pinjamannya sebesar 4, jadi sekarang saldo di bank menjadi 1+4=5
• Bank meminjamkan C sebanyak 5, jadi sekarang saldo di bank menjadi 5-5=0
• C mengembalikan pinjamannya sebesar 7, jadi sekarang saldo di bank menjadi 0+7=7
• Bank meminjamkan A sebanyak 6, jadi sekarang saldo di bank menjadi 7-6=1
• A mengembalikan pinjamannya sebesar 9, jadi sekarang saldo di bank menjadi 1+9=10

Jadi state tersebut safe dan RB nya adalah 10.

 

2. Banker’s Algorithm

Jawab :

a. Pembuktian

Rumusnya adalah Current allocation(A,B,C,D) + available yang kemudian dicocokan dengan resource dari masing-masing type

A = 2+0+4+1+1+1+6=15 (terbukti sama)

B= 0+1+1+0+1+0+3 = 6 (terbukti sama)

C = 2+1+0+0+0+0+5 = 9 (terbukti sama)

D = 1+1+2+1+0+1 +4 = 10(terbukti sama)

b. Need Matrix

Caranya adalah mengurangkan maximum demand dengan current allocation pada masing-masing prosess dan type

Process	A	B	C	D
P0	7	5	3	4
P1	2	1	2	2
P2	3	4	4	2
P3	2	3	3	1
P4	4	1	2	1
P5	3	4	3	3

c. Membuktikan apakah state tersebut safe atau non safe

Saldo awal yang tersedia di bank adalah A=6, B=3, C=5, D=4.

Lalu kita melihat pada need matrix proses manakah yang memungkinkan bank untuk meminjamkan proses tersebut. Setelah ditelusuri maka ditemukan bahwa proses P0,P2 dan P5 tidak memungkinkan untuk dipinjamkan terlebih dahulu dikarenakan saldo di bank tidak mencukupi.

Maka proses yang bisa dijalankan terlebih dahulu adalah P1, P3 dan P4.

Dari ketiga proses tersebut kita dapat memilih secara bebas proses mana yang mau dijalankan terlebih dahulu.

Misalnya dimulai dari proses P1.

Keterangan	A	B	C	D	Operasi
Saldo awal bank	6	3	5	4
Dipinjam P1	2	1	2	2	–
Sisa saldo bank	4	2	3	2	=
P1 mengembalikan pinjamannya	2	2	3	3	+
Saldo bank	6	4	6	5	=
Dipinjam P2	3	4	4	2	–
Sisa saldo bank	3	0	2	3	=
P2 mengembalikan pinjamannya	7	5	5	4	+
Saldo bank	10	5	6	7	=
Dipinjam P0	7	5	3	4	–
Sisa saldo bank	3	0	3	3	=
P0 mengembalikan pinjamannya	9	5	5	5	+
Saldo bank	12	5	8	8	=
Dipinjam P5	3	4	3	3	–
Sisa saldo bank	9	1	5	5	=
P5 mengembalikan pinjamannya	4	4	4	4	+
Saldo bank	13	5	9	9	=
Dipinjam P4	4	1	2	1	–
Sisa saldo bank	9	4	7	8	=
P4 mengembalikan pinjamannya	5	2	2	1	+
Saldo bank	14	6	9	9	=
Dipinjam P3	2	3	3	1	–
Sisa saldo bank	12	3	6	8	=
P3 mengembalikan pinjamannya	3	3	3	2	+
Saldo bank	15	6	9	10	=

Jadi state tersebut safe dan RB nya adalah A=15, B=6, C=9 dan D=10

d. Diijinkan karena saldo bank mencukupi.

6	3	5	4
3	2	3	3	–
3	1	2	1	=

www.binus.ac.id

www.skyconnectiva.com