SISTEM OPERASIMINGGU #5

MANAJEMEN PROSES

V2008-KA

PROSES: SINKRONISASI

•Outline Bahasan:• Definisi

• Latar Belakang: Race Condition

• Letak Masalah: Critical Section

• Kondisi Syarat

• Solusi Sinkronisasi

SINKRONISASI

• Definisi? Sinkronisasi adalah mekanisme untuk memastikanoperasi berjalan secara sinkron pada proses-proseskonkuren yg saling bekerja sama, sehingga terjaminkonsistensi data yang dimanipulasi bersama..

• Latar Belakang diperlukannya sinkronisasi proses:• Akses proses-proses konkuren secara berselingan ke suatu data

bersama (share-data) bisa menyebabkan ketidakkonsistenan data.Urutan eksekusi yg berbeda menghasilkan nilai yg berbeda.Kondisi ini dinamakan race condition. Kesalahan ini susah untukdilacak(debug), karena tidak bisa diulangi dan jarang terjadi. Racecondition cuma terjadi pada timing tertentu.

• Untuk menghindari race condition dibutuhkan koding yang teliti.Sistem yg mendukung proses harus menyediakan mekanismeataupun suatu kontruksi operasi (primitive) sinkronisasi.

1

2

3

X Y

1

23

X Y

(a) Operasi sinkron (a) Operasi asinkron

Gambar. Contoh alur eksekusi operasi sinkron dan asinkron

CONTOH KASUS SINKRONISASI

• Contoh Kasus Deposit:

• Fungsi deposit menambahkan sejumlah uang pd variabel global balance(saldo).

• Misalkan pada skenario transaksi yg bersamaan oleh proses P1 yangmendeposit 10 dan proses P2 yg mendeposit 20 dengan balance awal=100.Balance akhirnya seharusnya 120.

• Terjadinya interleaving P1 dan P2 ditingkat intruksi assembly, menyebabkanterjadinya race condition. Nilai akhir balance ditentukan bagaimana urut-urutan instruksi P1 dan P2 dieksekusi. Ini dikarenakan P1 dan P2 berusahamemanipulasi nilai variabel bersama (balance) pada saat yg hampirbersamaan.

• Untuk contoh ditas, Race condition dapat dihindari seandainya fungsi depositdieksekusi secara atomic (tdk boleh disela).

CRITICAL SECTION

• Letak masalah? Masalah Sinkronisasi prosesterfokus pada bagian kode proses yang disebutCritical Section.• Critical section adalah bagian atau segmen kode dari

suatu proses yg berisi intruksi pengaksesan data yangdipakai bersama oleh proses lainnya.

• Masalah (race condition) muncul ketika ada sejumlahproses berusaha mengeksekusi kode di bagian criticalsectionnya masing-masing untuk menggunakan data yangdipakai secara bersama (shared data) tadi.

• Sinkronisasi proses bertugas:Memastikan bahwa ketika suatu proses menjalankan kodedi bagian critical sectionnya, tidak ada proses lain yangdiijinkan untuk mengeksekusi kode critical section prosesyang bersangkutan.

SYARAT SINKRONISASI

• Kondisi Syarat? Sinkronisasi proses haruslah memenuhibeberapa kondisi berikut ini:

• Mutual Exclusion. Ketika suatu proses memasukieksekusi kode critical sectionnya. Maka tidak boleh adaproses lain yang juga memasuki critical section mereka.

• Progress. Ketika ada proses yg mau memasuki criticalsectionnya, dan saat itu tidak ada proses lain yang sedangmelakukan critical section, permintaan untuk masuk kecritical section haruslah dipenuhi

• Bounded Waiting. Haruslah ada batasan tentangberapa kali proses lain boleh menyalib suatu prosesyang telah lebih dulu meminta ijin untuk memasukicritical sectionnya.

BENTUK SINKRONISASI

• Solusi Sinkronisasi Proses bisa berbentuk:• Sinkronisasi Software

Sinkronisasi proses terletak sepenuhnya pd kodeprogram yang ditulis oleh programmer aplikasi.

• Sinkronisasi HardwareSinkronisasi proses dibantu oleh instruksi-instruksi atomic yang disediakan oleh CPU, untukmemastikan kondisi mutual exclusion pd eksekusiproses.

• SemaphoreSinkronisasi proses dibantu pada routine yangdisediakan oleh OS untuk memastikan tercapainyakondisi syarat terjadinya sinkronisasi.

SINKRONISASI S/W

• Sinkronisasi Software dilakukan dengan membuat struktur kode proses sbb:

• Ketika P1 masuk ke critical section variabel giliran =0, P2 akan tertahan di entrysectionnya, sampai P1 mengeksekusi Exit sectionnya, yaitu menset giliran=1.

SINKRONISASI H/W

• Sinkronisasi Hardware tersedia melalui instruksi atomic

yang disediakan oleh CPU. Intruksi atomic membantu

implementasi mutual exlusion pada proses.

Misalkan : Test and Set (ts) pada IBM 370

Exchange (xchg) pada Intel 80x86

• Intruksi tersebut bersifat atomic (tidak bisa disela atau

diinterupsi). Instruksi tersebut biasanya diletakkan pada bagian

entry section dari kode proses. Contoh:do {

while (TestAndSet(lock)) ;

critical section

lock = false;

remainder section

}

SEMAPHORE

• Semaphore merupakan fasilitas sinkronisasi yang disediakan oleh

routine OS. Implementasi Semaphore terdiri atas 2 fungsi atomic yang

berkaitan:

• Wait(S)

ditaruh di entry section kode proses. Fungsi ini akan mengecek apakah ada

proses lain yang masuk ke critical section yg serupa (S). Jika ada, maka proses

akan ke status waiting, jika sebaliknya, proses akan mengeset S (sbg tanda

critical section lagi diakses) dan mengeksekusi critical sectionnya.

• Signal(S)

ditaruh di exit section kode proses. Fungsi ini mereset variable S (sbg tanda

tersedianya akses ke critical section), dan membangunkan proses-proses yang

lagi waiting critical section serupa.

MASALAH KLASIK SINKRONISASI (1/2)

• Bounded Buffer (Producer-Consumer)

• Producer mengisi buffer, consumer mengambil dari buffer

• Masalah terjadi jika:

• Buffer penuh saat producer akan mengisi buffer

• Buffer kosong saat consumer akan mengambil isi buffer

• Readers and Writers

• Sebuah data digunakan secara bersama-sama oleh sejumlah

proses (write maupun read)

• Banyak readers bersamaan mengakses data tidak masalah

• Masalah terjadi jika ada satu proses writer yang mengakses

V2008-KA

BOUNDED BUFFER (PRODUCER-CONSUMER)

V2008-KA

READERS AND WRITERS

V2008-KA

MASALAH KLASIK SINKRONISASI (2/2)

• Dining Philosopher

• 5 filsuf berpikir dan makan bersama mengelilingi meja dengan bakul nasi di

tengah. Terdapat 5 piring yang dibatasi dengan 1 sumpit.

• Saat lapar ambil 2 sumpit dan makan; selesai makan kedua sumpit dilepas dan

berpikir lagi

• Permasalahan pada pengalokasian sumber daya

• Sleeping Barber

• Tempat potong dengan 1 kursi potong dan n kursi tunggu

• Saat tidak ada pelanggan barber tidur di kursi potong, jika ada yang datang

dibangunkan. Jika ada pelanggan lain, tunggu di kursi tunggu. Jika kursi tunggu

penuh, tinggalkan tempat potong

V2008-KA

DINING-PHILOSOFER

V2008-KA

SLEEPING BARBER

V2008-KA

PROSES: PENANGANAN DEADLOCK

• Outline Bahasan

• Definisi & Ilustrasi

• Contoh Kasus

• Kondisi Penyebab

• Penanganan Deadlock

• Prevention & Avoidance

• Detection & Recovery

DEADLOCK

• Definisi? Deadlock adalah suatu kondisi dimana 2 proses atau

lebih tidak bisa meneruskan eksekusinya karena saling menunggu

aksi dari proses lainnya.

• Ilustrasi: Kemacetan di persimpangan jalan

SYARAT TERJADINYA DEADLOCK

• Ada 4 Kondisi syarat penyebab yang jika terjadibersama akan menyebabkan terjadinya deadlock:• Mutual exclusion: Sumber daya cuma bisa dipakai

oleh satu proses dlm suatu waktu.• Hold and wait: Suatu proses yg memegang suatu

sumber daya dan lagi menunggu sumber daya lain yangdipegang oleh proses yang lain.

• No preemption: Suatu sumber daya hanya bisadilepaskan secara sukarela oleh proses ygmemegangnya, yaitu setelah proses itu selesai.

• Circular wait: Ada sekumpulan proses yg waiting {P0,P1, …, P0} sedemikian rupa P0 menunggu sumber dayayg dipegang P1, P1 menunggu sumber daya yg dipegang

P2, …, Pn–1 menunggu sumber daya yg dipegangoleh Pn

PENANGANAN DEADLOCK

• Pendekatan Penanganan Deadlock:

• Mencegah dan menghindari kondisis-kondisi yang

menyebabkan terjadinya deadlock.

(Prevention dan Avoidance)

• Membuat mekanisme deteksi dan pemulihan sistem

terhadap keadaan deadlock.

(Detection dan Recovery)

• Mengabaikan masalah dan menganggap deadlock tidak

pernah terjadi di sistem. (Misalnya pada UNIX, asumsi

deadlock sangat jarang terjadi).

DEADLOCK PREVENTION

• Deadlock Prevention mengekang permintaan thp sumber daya(resource) untuk mencegah kondisi penyebab deadlock:• Mutual Exclusion: Pakai resource yg bisa dishare. Untuk

Resource yg tidak bisa dishare, menolak permintaan terhadapresource yg sedang dipakai proses lain.

• Hold and Wait: Proses hanya boleh memegang satu resourcedlm suatu waktu, ataupun semua resource hrs dialokasi sebelumproses dimulai.

• No Preemption –• Jika proses tidak bisa mendapatkan suatu resource dengan

segera, resource yang lagi dipegangnya dilepas dulu, sehinggaproses yg lagi menunggu resource tersebut bisa memakainya.

• Proses akan meneruskan eksekusi jika resource yang lama danbaru sudah tersedia untuknya.

• Circular Wait : Menerapkan nomer urut untuk semua resourcedan setiap proses hanya boleh meminta resource dengan nomerurut yg lebih tinggi.

DEADLOCK AVOIDANCE (1/2)

• Deadlock Avoidance memastikan bahwa sistem selalu dalam

status safe sehingga deadlock tidak terjadi. Alokasi suatu resource

tidak boleh membuat sistem unsafe.

Gambar. Status Sistem: Safe, Unsafe, dan Deadlock

DEADLOCK AVOIDANCE (2/2)

• Mekanisme Deadlock Avoidance butuh:

• Tiap proses menyatakan jumlah maksimum tiap

jenis resource yg dibutuhkannya

• Algoritma deadlock-avoidance secara dinamis

memeriksa status alokasi resource untuk

memastikan tidak akan ada kondisi circular-wait.

• Status alokasi resource dinyatakan dengan jumlah

resource yang tersedia dan yang dialokasikan, dan jumlah

maksimum permintaan dari proses proses.

DEADLOCK DETECTION & RECOVERY

• Penanganan deadlock dengan Detection &

Recovery :

• Tidak ada pencegahan deadlock, sehingga sistem

berpotensi memasuki keadaan deadlock.

• Menyediakan algoritma untuk mendeteksi

terjadinya deadlock.

• Menyediakan skenario pemulihan dari keadaan

deadlock

DEADLOCK DETECTION

• Deadlock Detection: Dengan secara berkala

memeriksa keberadaan siklus tertutup dlm resource-

allocation graph.

Gambar. Contoh Resource-Allocation Graph

DEADLOCK RECOVERY

• Deadlock Recovery bisa dilakukan dengan:• Penghentian Proses, misalkan dengan cara:

• Membatalkan semua proses yang terlibatdeadlock.

• Membatalkan proses satu persatu sampai siklustertutup deadlock hilang.

• Ambil alih resource ( Resource preemption)• Memilih proses yg akan dikorbankan.• Proses yg dikorbankan di Rollback (resource

proses dilepaskan), membawa sistem kembali kekondisi atau status safe dan proses diulangi lagidari status safe.

MIND MAPPING SESSION

QA