Sekolah Tinggi Teknologi Adisutjipto Yogyakarta
Materi Kuliah : Sistem Operasi / OS Semester Genap E.N. Tamatjita
- 0S
STTA-TF
E.N. Tamatjita -
1
Pertemuan Ke-5 Pararel Processing Paralel processing is a situation in which two/more processor operate in unison. – Executing instruction simultaneously
Benefits: increase reliability & faster processing
Evolution:Evolution: – Job level : each job has its own processor and all processes and threads are run by the same processor – Process level: unrelated process, are assigned to any available processor – Thread level : threads are assigned to avaliable processor
- 0S
STTA-TF
E.N. Tamatjita -
2
Mengapa perlu Sinkronisasi ? Sinkronisasi diperlukan untuk menghindari terjadinya ketidak konsistenan data akibat adanya akses data secara konkuren. Diperlukan adanya suatu mekanisme untuk memastikan urutan / giliran Diperlukan adanya suatu mekanisme untuk memastikan urutan / giliran pengaksesan suatu data yang saling bekerjasama sehingga terjadi sinkronisasi If we don’t make process synchronization: – Race Condition
- 0S
STTA-TF
E.N. Tamatjita -
3
Producer and Consumer
#define BUFFER_SIZE 10 typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; int counter = 0;
- 0S
STTA-TF
E.N. Tamatjita -
4
Producer
while (true) { /* produce an item and put in nextProduced */ while (count ==BUFFER_SIZE){ } // do nothing buffer [in] = nextProduced; in = (in + 1) % BUFFER_SIZE; count++; }
- 0S
STTA-TF
E.N. Tamatjita -
5
Consumer
while (true) { while (count == 0){ } // do nothing nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; count--; /* consume the item in nextConsumed }
- 0S
STTA-TF
E.N. Tamatjita -
6
Automic Process
The statements counter++; counter--; must be performed atomically. Atomic operation means an operation that completes in its entirety without interruption.
- 0S
STTA-TF
E.N. Tamatjita -
7
Bounded Buffer Perintah “count++” diimplementasikan pada bahasa mesin: – register1 = counter – register1 = register1 + 1 – counter = register1 Perintah “count--” diimplementasikan pada bahasa mesin: – register2 = counter – register2 = register2 – 1 – counter = register2
- 0S
STTA-TF
E.N. Tamatjita -
8
Race Condition Race condition: situasi dimana beberapa proses mengakses dan memanipulasi suatu data secara konkuren. – Nilai akhir dari data tersebut tergantung dari proses mana yang terakhir mengubah data proses mana yang terakhir mengubah data Untuk menghindari terjadinya situasi tersebut, semua proses yang dapat mengakses suatu data tertentu harus disinkronisasi
- 0S
STTA-TF
E.N. Tamatjita -
9
Critical Section Lebih dari satu proses berlomba-lomba pada saat yang sama untuk menggunakan data yang sama. Setiap proses memiliki segmen kode yang digunakan untuk mengakses data yang digunakan secara bersama-sama. – Segmen kode tersebut disebut critical section. Masalahnya: menjamin bahwa jika suatu proses sedang menjalankan critical section, maka proses lain tidak boleh masuk ke dalam critical section tersebut.
- 0S
STTA-TF
E.N. Tamatjita -
10
Solusi Masalah Critical Section Peterson’s Algorithm The two processes share two variables: – int turn; – Boolean flag[2]; – Boolean flag[2]; The variable turn indicates whose turn it is to enter the critical section. The flag array is used to indicate if a process is ready to enter the critical section. flag[i] = true implies that process Pi is ready!
- 0S
STTA-TF
E.N. Tamatjita -
11
Algorithm for Process Pi while (true) { flag[i] = TRUE; turn = j; while ( flag[j] && turn == j); CRITICAL SECTION flag[i] = FALSE; REMAINDER SECTION } Mutual exclusion, progress, and bounded waiting! If P0 want to access critical section, P0 will set flag[0] to true and turn to P1.
- 0S
STTA-TF
E.N. Tamatjita -
12
Bakery Algorithm Critical section for: n processes Sebelum memasuki critical section, setiap proses menerima sebuah nomor. Yang memegang ID terkecil yang dilayani dahulu. Skema penomoran selalu naik secara berurut, contoh: 1, 2, 2, 2, 3, 3, 4, 5… Diperkenalkan pertama kali oleh Leslie Lamport. Data yang digunakan bersama – boolean choosing [n]; – int number [n]; Struktur data diinisialisi awal ke false dan 0. (a,b) < (c,d) jika a < c atau jika a = c dan b < d
- 0S
STTA-TF
E.N. Tamatjita -
13
Contoh : Bakery Algorithm Lihat Whiteboard …
- 0S
STTA-TF
E.N. Tamatjita -
14
Sinkronisasi Metode dalam sinkronisasi hardware – Processor Synchronous ( Disable Interrupt ) – Memory Synchronous ( Instruksi Test-And-Set ) Processor synchronous – Dengan men-disable interupsi (interrupt) – Dalam lingkungan multiprocessor: • Hanya satu processor bisa didisable interruptnya Memory synchronous – Instruksi Test-And-Set dan Semaphore – Dalam lingkungan multiprocessor: • Bisa dilakukan • Semua processor tidak dapat memakai resource karena proteksi dilakukan di memory – Instruksi harus bersifat atomik
- 0S
STTA-TF
E.N. Tamatjita -
15
Mutual Exclusion : Memory synchronous Kelebihan : – Dapat diaplikasikan ke beberapa prosesor, dengan sharing memory – Simpel – Dapat digunakan untuk banyak critical section Kekurangan : – Busy-waiting memakan processor time yang besar – Mungkin terjadi starvation – Deadlock (not responding) * Jika low priority process mendapat critical region dan higher priority process butuh juga, higher priority process akan mendapat processor dan low priority process akan menunggu - 0S
STTA-TF
E.N. Tamatjita -
16
Semaphore Invented by Djikstra (1960) Semaphore digunakan untuk memberi sinyal/tanda Non negative integer, untuk melambangkan jumlah resources Jika proses menunggu sinyal, maka dia akan ditunda sampai sinyal yg ditunggu Jika proses menunggu sinyal, maka dia akan ditunda sampai sinyal yg ditunggu tersebut terkirim Operasi: wait dan signal Wait dan signal operations tidak dapat diinterupt Queue digunakan untuk menahan proses proses yang sedang menunggu semaphore
- 0S
STTA-TF
E.N. Tamatjita -
17
Semaphore, lanjutan … Two standard operations modify S: wait() and signal() – Originally called P() and V() Can only be accessed via two indivisible (atomic) operations Semaphore: Wait Semaphore: Wait – Spinlock Semaphore: Wait Semaphore: Wait – non spinlock Semaphore: Signal Contoh Semaphore & Implementasi Lihat whiteboard …
- 0S
STTA-TF
E.N. Tamatjita -
18
Reader & Writers
Diketahui dua macam proses: – Pembaca (reader) – Penulis (writer) Kedua jenis proses berbagi sumber daya penyimpanan yang sama, Misal: Basis data Tujuan: data tidak korup dan inkonsisten Kondisi: – Proses-proses pembaca dapat membaca sumber daya secara simultan – Hanya boleh ada satu penulis menulis pada setiap saat – Bila ada yang menulis, tidak boleh ada yang membaca
Contoh Reader – Writers (Shared Data), Lihat whiteboard …
- 0S
STTA-TF
E.N. Tamatjita -
19
Shared Data
Data set Semaphore mutex initialized to 1, tanda mutual exclusion Semaphore wrt initialized to 1, tanda • Semaphore wrt initialized to 1, tanda untuk menulis Integer readcount initialized to 0, tanda untuk membaca
- 0S
STTA-TF
E.N. Tamatjita -
20
Dining Philosopher Diketahui: – Mie (Data) – Sebuah meja bundar – N filsuf duduk melingkar di meja bundar – Antara dua filsuf terdapat sebuah sumpit – Didepan setiap filsuf terdapat semangkuk mie Setiap filsuf hanya dapat berada pada salah satu kondisi berikut: – Berpikir – Lapar – Makan
- 0S
STTA-TF
E.N. Tamatjita -
21
Dining Philosopher, lanjutan … Shared data –Bowl of rice (data set) – Semaphore chopstick [5] initialized to 1 Dua hal yang harus diperhatikan: • Dua hal yang harus diperhatikan: – Deadlock: Semua filsuf ingin makan dan telah memegang sumpit – Starvation: Ada filsuf yang kelaparan dalam waktu yang lama
- 0S
STTA-TF
E.N. Tamatjita -
22
The Structure of Philosopher i Philosopher I While (true) { wait ( chopstick[i] ); //kanan wait ( chopStick[ (i + 1) % 5] ); //kiri // eat signal ( chopstick[i] ); //kanan signal (chopstick[ (i + 1) % 5] ); //kiri // think }
- 0S
STTA-TF
E.N. Tamatjita -
23
*** Minggu Depan ________
Penjadwalan CPU
- 0S
STTA-TF
E.N. Tamatjita -
24
