2/19/2015
Tahun Akademik 2014/2015 Semester II
DIG1I3 - Instalasi dan Penggunaan Sistem Operasi Mutual Exclusion dan Sinkronisasi Mohamad Dani (MHM) Alamat E-mail:
[email protected]
Hanya dipergunakan untuk kepentingan pengajaran di lingkungan Telkom Applied Science School
Tujuan Pembelajaran Mahasiswa mampu : Menjelaskan konsep dasar yang berhubungan dengan konkurensi seperti race condition, Permasalahan Sistem Operasi dan kebutuhan mutual exclusion, Memahami pendekatan perangkat keras untuk mendukung mutual exclusion, Menjelaskan Semaphore, Menjelaskan Monitor, Menjelaskan Message Passing.
1
2/19/2015
Multiple Processes
Central to the design of modern Operating Systems is managing multiple processes
Multiprogramming Multiprocessing Distributed Processing
Big Issue is Concurrency
Managing the interaction of all of these processes
Concurrency Concurrency arises in: Multiple applications
Structured applications
Sharing time Extension of modular design
Operating system structure
OS themselves implemented as a set of processes or threads
2
2/19/2015
Interleaving and Overlapping Processes
Earlier (Ch2) we saw that processes may be interleaved on uniprocessors
Interleaving and Overlapping Processes
And not only interleaved but overlapped on multiprocessors
3
2/19/2015
Difficulties of Concurrency
Sharing of global resources
Writing a shared variable: the order of writes is important Incomplete writes a major problem
Optimally managing the allocation of resources Difficult to locate programming errors as results are not deterministic and reproducible.
A Simple Example void echo() { chin = getchar(); chout = chin; putchar(chout); }
4
2/19/2015
A Simple Example: On a Multiprocessor Process P1 . chin = getchar(); . chout = chin; putchar(chout); . .
Process P2 . . chin = getchar(); chout = chin; . putchar(chout); .
Mengapa Sinkronisasi
Sinkronisasi diperlukan untuk menghindari terjadinya inkonsistensi data akibat adanya akses data secara konkuren (bersamaan) Diperlukan adanya suatu mekanisme untuk memastikan urutan / giliran pengaksesan suatu data yang saling bekerjasama sehingga terjadi sinkronisasi Jika kita tidak membuat sinkronisasi proses:
Race Condition
10
5
2/19/2015
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
Untuk menghindari terjadinya situasi tersebut, semua proses yang dapat mengakses suatu data tertentu harus disinkronisasi
Operating System Concerns
What design and management issues are raised by the existence of concurrency? The OS must
Keep track of various processes Allocate and de-allocate resources Protect the data and resources against interference by other processes. Ensure that the processes and outputs are independent of the processing speed
6
2/19/2015
Process Interaction
Competition among Processes for Resources Three main control problems: Need for Mutual Exclusion
Critical sections
Deadlock Starvation
7
2/19/2015
Requirements for Mutual Exclusion
Only one process at a time is allowed in the critical section for a resource A process that halts in its noncritical section must do so without interfering with other processes No deadlock or starvation
Requirements for Mutual Exclusion
A process must not be delayed access to a critical section when there is no other process using it No assumptions are made about relative process speeds or number of processes A process remains inside its critical section for a finite time only
8
2/19/2015
Mutual Exclusion: Hardware Support
17
Disabling Interrupts
Uniprocessors only allow interleaving Interrupt Disabling
A process runs until it invokes an operating system service or until it is interrupted Disabling interrupts guarantees mutual exclusion Will not work in multiprocessor architecture
9
2/19/2015
Pseudo-Code while (true) { /* /* /* /*
disable interrupts */; critical section */; enable interrupts */; remainder */;
}
Special Machine Instructions
Compare&Swap Instruction
also called a “compare and exchange instruction”
Exchange Instruction
10
2/19/2015
Compare&Swap Instruction int compare_and_swap (int *word, int testval, int newval) { int oldval; oldval = *word; if (oldval == testval) *word = newval; return oldval;
}
Mutual Exclusion (fig 5.2)
11
2/19/2015
Exchange Instruction
(fig 5.2)
Hardware Mutual Exclusion: Advantages
Applicable to any number of processes on either a single processor or multiple processors sharing main memory It is simple and therefore easy to verify It can be used to support multiple critical sections
12
2/19/2015
Hardware Mutual Exclusion: Disadvantages
Busy-waiting consumes processor time Starvation is possible when a process leaves a critical section and more than one process is waiting.
Some process could indefinitely be denied access.
Deadlock is possible
Semaphore
Semaphore:
An integer value used for signalling among processes.
Only three operations may be performed on a semaphore, all of which are atomic:
initialize, Decrement (semWait) increment. (semSignal)
13
2/19/2015
Semaphore Primitives
Binary Semaphore Primitives
14
2/19/2015
Strong/Weak Semaphore
A queue is used to hold processes waiting on the semaphore
In what order are processes removed from the queue?
Strong Semaphores use FIFO Weak Semaphores don’t specify the order of removal from the queue
Example of Strong Semaphore Mechanism
15
2/19/2015
Example of Semaphore Mechanism
Mutual Exclusion Using Semaphores
16
2/19/2015
Producer/Consumer Problem
General Situation:
One or more producers are generating data and placing these in a buffer A single consumer is taking items out of the buffer one at time Only one producer or consumer may access the buffer at any one time
The Problem:
Ensure that the Producer can’t add data into full buffer and consumer can’t remove data from empty buffer
Producer/Consumer Animation
Functions • Assume an infinite buffer b with a linear array of elements Producer
while (true) { /* produce item v */ b[in] = v; in++; }
Consumer
while (true) { while (in <= out) /*do nothing */; w = b[out]; out++; /* consume item w */ }
17
2/19/2015
Buffer
Incorrect Solution
18
2/19/2015
Possible Scenario
Semaphores
19
2/19/2015
Bounded Buffer
Semaphores
20
2/19/2015
Functions in a Bounded Buffer • .
Producer
while (true) { /* produce item v */ while ((in + 1) % n == out) do nothing */; b[in] = v; in = (in + 1) % n }
Consumer
while (true) { while (in == out) /* /* do nothing */; w = b[out]; out = (out + 1) % n; /* consume item w */ }
Daftar Pustaka
William Stallings(2012). Operating Systems 7th Edition. Prentice Hall. New Jersey halaman 395 – 426. Avi Silberschatz, Peter Galvin, dan Grag Gagne (2013). Operating Systems CONCEPTS ninth Edition. John Wiley & Sons. USA Halaman 261 – 312.
21
2/19/2015
Th4nx
43
22
