Noemura

Concurrency and Deadlock

-Concurrency
Concurrency adalah sebuah properti sistem dimana beberapa perhitungan dieksekusi secara bersamaan, dan berpotensi untuk berinteraksi antara satu dengan yang lainnya.

-Conccurency terjadi pada
Proses dalam suatu aplikasi
Thread dalam proses
Program itu sendiri

-Tujuan Concurrency
Proses komunikasi antar proses
Berbagi sumber daya
Sinkronisasi antara beberapa proses
Alokasi waktu proses

-Masalah-masalah dalam Concurrency
Berbagi sumber daya yang sama / bersifat global
Manajemen alokasi sumber daya
Error dalam programming susah diidentifikasi

-Fokus dalam OS
Menelusuri setiap proses yang sedang aktif
Mengatur alokasi dan de-alokasi dari sumber daya tertentu, misalnya : Memory, I/O Devices, Processor Time
Melindungi data dan sumber daya
Hasil dari proses harus bersifat independen dari proses concurrency lainnya

-Kompetisi antar Proses untuk mendapatkan sumber daya
1.Mutual Exclusion
Hanya satu program yang diperbolehkan untuk mengakses sumber daya ketika ada 2 program yang sama – sama membutuhkan sumber daya tersebut.

2.Deadlock
Ketika ada 2 proses / lebih yang saling berebut untuk mendapatkan suatu sumber daya yang sama

3.Starvation
Ketika ada 2 proses / lebih yang saling berebut untuk mendapatkan suatu sumber daya yang sama, namun semua proses saling mengalah sehingga tidak ada yang dapat mengakses sumber daya tersebut.

-Semaphore
Semaphore adalah sebuah variabel spesial yang digunakan untuk mengirimkan sinyal.

-Karakteristik dari Semaphore
Variable Semaphore merupakan sebuah integer
Operasi pengiriman sinyal yang dilakukan oleh Semaphore tidak dapat diinterupsi

-Cara kerja proses dalam Semaphore
Proses Inisialisasi menggunakan angka non-negatif
Proses Waiting akan mengurangi nilai Semaphore
Proses Signaling akan menambahkan nilai Semaphore

-Monitor
Monitor adalah sebuah bahasa pemrograman yang mensupport semua akses kontrol kedalam data yang dishare

-Beberapa kondisi yang tidak boleh dijalankan selama berada didalam monitor antara lain :
Proses menunggu signaling dari proses lain
Variable proses hanya dapat diakses dari dalam monitor
Proses waiting akan melepaskan monitor secara sementara

-Deadlock
Deadlock adalah sebuah kondisi dimana setiap proses dalam sebuah set saling menunggu event dalam proses lainnya sehingga tidak ada proses yang berjalan

-Beberapa hal yang dapat menyebabkan terjadinya Deadlock
1.Mutual exclusion
Hanya satu proses yang dapat mengakses sumber daya saat itu

2.Hold and Wait
Sebuah proses yang saat itu membawa sebuah sumber daya memerlukan sumber daya lain yang sedang dibawa oleh proses lain agar dapat berjalan

3.No preemption
Sebuah sumber daya dilepaskan oleh sebuah proses setelah proses tersebut selesai menjalankan tugasnya

4.Circular wait
Setiap set saling menunggu sumber daya dari set lain sehingga terbentuk sebuah looping

-Solusi Deadlock
Mengabaikan permasalahan yang terjadi
Sengaja membiarkan Deadlock terjadi, kemudian cari lokasi Deadlock terjadi dan selesaikan Deadlock tersebut
Pencegahan secara dinamik
Pencegahan dengan cara meniadakan salah satu dari 4 kondisi deadlock

-Stravation
Starvation adalah sebuah Algoritma untuk mengalokasikan sejumlah sumber daya.

-Karakteristik dari Starvation
Dapat memberikan prioritas kepada job yang paling singkat
Efektif untuk beberapa job singkat dalam sebuah system
Dapat menyebabkan sebuah job tertunda dalam jangka waktu yang lama

Soal Deadlock

Ada 3 proses dalam gambar diatas, yaitu proses A, B, C.

Dalam kondisi saat ini saldo yang ada di Bank adalah 3 + 3 + 2 + 2 = 10

Tentukan proses safe / unsafe dari setiap proses :
-Selisih saldo yang dibutuhkan dari proses A adalah 9 – 3 = 6
-Selisih saldo yang dibutuhkan dari proses B adalah 4 – 2 = 2
-Selisih saldo yang dibutuhkan dari proses C adalah 7 – 2 = 5
-Sedangkan saldo yang dimiliki Bank saat ini adalah 3, maka dapat kita simpulkan bahwa saat ini A & C bersifat unsafe, dan B bersifat safe

Bank meminjamkan saldonya ke proses yang bersifat safe, yaitu B. Maka proses yang terjadi adalah :
-Bank meminjamkan 2 saldo ke B, sehingga free = 1 dan B = 4
-B mengembalikan saldonya ke Bank, sehingga free = 5
-Bank meminjamkan 5 saldo ke C, sehingga free = 0 dan C = 7
-C mengembalikan saldonya ke Bank, sehingga free = 7
-Bank meminjamkan 6 saldo ke A, sehingga free = 1 dan A = 9
-A mengembalikan saldonya ke Bank, sehingga free = 10

Karena setiap proses berhasil mengembalikan saldonya ke bank, maka problem diatas bersifat safe

Solusinya :

www.skyconnectiva.com
www.binus.ac.id

Scheduling

-CPU Scheduler
CPU Scheduler memilih sebuah proses-proses dalam memory yang siap untuk dieksekusi, dan mengalokasikan CPU ke salah satu dari proses tersebut.

-Kapan Scheduling terjadi?
Ketika terjadi perubahan state dari running ke waiting.
Ketika terjadi perubahan state dari running ke ready.
Ketika terjadi perubahan state dari waiting ke ready.
Ketika terjadi Terminasi

-Jenis-jenis Scheduler
1.Long-term Scheduling
Keputusan untuk menambahkan suatu proses kedalam daftar proses yang akan dieksekusi

2.Medium-term Scheduling
Keputusan untuk menambahkan beberapa proses yang ada dalam main memory baik secara utuh maupun parsial

3.Short-term Scheduling
Keputusan untuk memilih proses mana yang dapat dieksekusi oleh prosesor

4.I/O Scheduling
Keputusan untuk menjalankan proses I/O yang belum berjalan oleh I/O device yang tersedia

-Dispatch
Dispatcher memberikan control CPU kepada proses yang dipilih oleh Short-term Scheduler.
Dispatch latency merupakan waktu yang diperlukan oleh dispatcher untuk menghentikan sebuah proses dan menjalankan proses lainnya.

-Elemen-Elemen dalam Scheduling
CPU Utilization : CPU harus berjalan sesering mungkin.
Throughput : Banyaknya proses yang selesai dikerjakan dalam satu satuan waktu.
Turnaround Time : Waktu yang dibutuhkan untuk menjalankan sebuah proses tertentu.
Waiting Time : Waktu tunggu sebuah proses dalam ready queue.
Response Time : Waktu yang dibutuhkan oleh sebuah proses dari minta dilayani hingga ada respon pertama yang menanggapi layanan tersebut.

-OPtimization
1.Max CPU Utilization
2.Max Throughput
3.Min Turnaround Time
4.Min Waiting Time
5.Min Response Time

-Tujuan Scheduling
1.All Systems
Fairness : Setiap proses mendapat pembagian CPU yang sama.
Policy Enforcement : Kebijakan dijalankan
Balance : Menjaga agar setiap part dari system berjalan

2. Batch Systems
Throughput : Memaksimalkan pekerjaan tiap jam.
Turnaround Time : Meminimalkan waktu antara submission dan termination.
CPU Utilization : Menjaga agar CPU selalu sibuk.

3. Interactive Systems
Response Time : Respon terhadap suatu request secepat mungkin.
Proportionality : Sesuai dengan ekspektasi user.

4. Real-Time Systems
Meeting deadlines : Menghindari kehilangan data
Predictability : Menghindari penurunan kualitas dalam system multimedia

-Batch-Scheduling Algorithm
1.First-Come First-Serve
Proses diassign ke dalam CPU secara urut. Kemudahan menggunakan algoritma ini adalah mudah dimengerti dan mudah untuk di buat programnya. Sedangkan kesulitannya adalah tugas yg kecil/sedikit akan menunggu telalu lama jika mengantri dibelakang tugas yg besar.

2.Shortest Job First – Non Preemptive
Ketika CPU diberikan suatu proses yg tidak bisa di interupsi sampai CPU burst-nya selesai.

3.Shortest Job First – Preemptive
Ketika CPU diberikan suatu proses yg bisa di interupsi sebelum CPU burst-nya selesai.

4.Interactive Scheduling Algorithm
Round-robin scheduling
Priority scheduling
Multiple queues
Shortest process next
Guaranteed scheduling
Lottery scheduling
Fair-share scheduling

e-book Halaman 447 Bagian 9.2

1. First-Come First-Serve

Waiting time for A=0, B=2, C=5, D=1, E=3
Average Waiting Time = (0+2+5+1+3)/5 = 2,2

2. Shortest Job First – Non Preemptive

Waiting time for A=0, B=4, C=0, D=1, E=3
Average Waiting Time = (0+4+0+1+3)/5 = 1,6

3. Shortest Job First – Preemptive

Waiting time for A=0, B=4, C=0, D=1, E=3
Average Waiting Time = (0+4+0+1+3)/5 = 1,6

www.skyconnectiva.com
www.binus.ac.id