Concurrency: Mutual Exclusion and Synchronization (상호배제와 동기화)

Presentation on theme: "Concurrency: Mutual Exclusion and Synchronization (상호배제와 동기화)"— Presentation transcript:

1 Concurrency: Mutual Exclusion and Synchronization (상호배제와 동기화)
Lecture #5 Concurrency: Mutual Exclusion and Synchronization (상호배제와 동기화)

2 다중 프로세스 처리 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 The central themes of operating system design are all concerned with the management of processes and threads: • Multiprogramming: The management of multiple processes within a uniprocessor system. • Multiprocessing: The management of multiple processes within a multiprocessor. • Distributed processing: The management of multiple processes executing on multiple, distributed computer systems. E. G clusters Concurrency encompasses a host of design issues, including communication among processes, sharing of and competing for resources (such as memory, files, and I/O access), synchronization of the activities of multiple processes, and allocation of processor time to processes.

3 병행성(Concurrency) Concurrency arises in: Multiple applications
Sharing time Structured applications Extension of modular design Operating system structure OS themselves implemented as a set of processes or threads • Multiple applications: Multiprogramming was invented to allow processing time to be dynamically shared among a number of active applications. • Structured applications: As an extension of the principles of modular design and structured programming, some applications can be effectively programmed as a set of concurrent processes. • Operating system structure: The same structuring advantages apply to systems programs, and we have seen that operating systems are themselves often implemented as a set of processes or threads.

4 Interleaving and Overlapping Processes (1)
processes may be interleaved on uniprocessors

5 Interleaving and Overlapping Processes (2)
And not only interleaved but overlapped on multi-processors

6 Difficulties of Concurrency
Sharing of global resources Optimally managing the allocation of resources Difficult to locate programming errors as results are not deterministic and reproducible. The sharing of global resources If two processes both make use of the same global variable and both perform reads and writes on that variable, then the order in which the various reads and writes are executed is critical. Managing Resources It is difficult for the OS to manage the allocation of resources optimally. E.G. A process may request use of, and be granted control of, a particular I/O channel and then be suspended before using that channel. It may be undesirable for the OS simply to lock the channel and prevent its use by other processes; indeed this may lead to a deadlock condition, Locating Programming Errors It becomes very difficult to locate a programming error because results are typically not deterministic and reproducible

7 프로세스 상호작용(Process Interaction)
We can classify the ways in which processes interact on the basis of the degree to which they are aware of each other’s existence. This table (continues on the next slide) lists three possible degrees of awareness plus the consequences of each. Introduce each degree of awareness briefly – mention that things are often as clear cut as in this table. Processes unaware of each other: Independent processes that are not intended to work together. E.G. multiprogramming of multiple independent processes. Although the processes are not working together, the OS needs to be concerned about competition for resources. E.G. two independent applications may both want to access the same disk or file or printer. Processes indirectly aware of each other: Processes that are not necessarily aware of each other by their respective process IDs but that share access to some object, such as an I/O buffer. Such processes exhibit cooperation in sharing the common object. Processes directly aware of each other: Processes that are able to communicate with each other by process ID and that are designed to work jointly on some activity. Again, such processes exhibit cooperation.

8 프로그램 실행 (Program Execution)
프로그램은 프로세스의 집합으로 이루어진다 프로그램 실행(Program Execution) 순차 실행(Sequential Execution) 병행 실행(Concurrent Execution) 병렬 실행(Parallel Execution) 병행성(동시성:Concurrency) > 병렬성(Parallelism) 프로그램 병행 실행은 실행 시간 최적화에 접근 Operating System

9 병렬 실행(Concurrent Execution)의 문제점
병행 프로세스들(Concurrent processes (or threads))는 일반적으로 데이터와 자원을 공유한다 만약 공유 데이터에 대한 접근을 적절하게 제어하지 않으면 일부 프로세스는 잘못된 데이터를 접근하게 된다 병행 프로세스의 실행 결과는 병행 프로세스 간의 실행이 섞이는 순서에 의하여 결정되어 진다 Operating System

10 Race Condition (경쟁 상태) 경쟁 상태 (Race Condition)
다수의 프로세스들 또는 쓰레드들이 공유자원을 동시에 읽거나 쓰려고 하는 상태 최종 실행 결과는 프로세스나 쓰레드의 실행 순서에 의해 달라짐. 자원공유(Resource Sharing) 자원경쟁(Resource Competition)

11 공유 데이터 접근의 예 3 variables: A, B, C which are shared by thread T1 and thread T2 T1 computes C = A+B T2 transfers amount X from A to B T2 must do: A = A -X and B = B+X (so that A+B is unchanged) But if T1 computes A+B after T2 has done A = A-X but before B = B+X then T1 will not obtain the correct result for C = A + B The resource sharing requires the synchronization between threads Operating System

12 병행 실행의 예(1) 생산자 & 소비자 프로세스 생산자 프로세스 (Producer Process) 소비자 프로세스
(Consumer Process) 1 n n-1 2 3 … 4 in out Operating System

13 병행 실행의 예(2) 소비자 프로세스 코드 생산자 프로세스 코드 repeat repeat
. . . nextp에서 한 항목을 생산 while count == n do no-op; buffer[in] = nextp; in = (in + 1) mod n; count = count + 1; until FALSE; 소비자 프로세스 코드 repeat while count == 0 do no-op; nextc = buffer[out]; out = (out + 1) mod n; count = count - 1; . . . nextc에서 한 항목을 소비 until FALSE; Operating System

14 병행 실행의 예(3) 소비자 프로세스 코드 생산자 프로세스 코드 count = count - 1;
 register2 = count register2 = register2 - 1 count = register2 생산자 프로세스 코드 count = count + 1;  register1 = count register1 = register1 + 1 count = register1 Operating System

15 병행 실행의 예(4) 생산자 프로세스와 소비자 프로세스가 병행 실행되는 경우 :
T0: 생산자  register1 = count {register1 = 5} T1: 생산자  register1 = register1+1 {register1 = 6} T2: 소비자  register2 = count {register2 = 5} T3: 소비자  register2 = register2-1 {register2 = 4} T4: 소비자  count = register2 {count = 4} T5: 생산자  count = register1 {count = 6} 문제점: 두 개의 프로세스가 동시에 count 변수에 접근 해결책: count 변수에 접근하는 순서를 제어, 즉 한번에 하나의 프로세스만이 count 변수에 접근하도록 제어 프로세스 동기화(Process Synchronization)가 필요 Operating System

16 병렬 실행에서의 자원 공유 병행 실행에서의 자원 공유에 따른 문제점 상호 배제(Mutual Exclusion)
병행 프로세스들이 공유 자원을 동시에 접근함으로써 전혀 예기치 못하는 결과가 발생할 수 있다 한 시점에 공유 자원을 접근하는 실행 단위(프로세스 또는 쓰레드)는 단지 하나만 존재하여야 한다 실행 동기화 (Execution Synchronization) 하나의 프로그램은 구성하는 병행 프로세스들은 상호간에 일련의 실행 순서에 맞추어 실행되어야 한다 예: 생산자-소비자 모델에서 생산자가 버퍼에 데이터를 저장하여야 소비자가 데이터 처리가 가능해진다 Operating System

17 임계구역(critical section) 문제(1)
임계구역(Critical Section: CS) 하나의 프로세스가 공유 데이터를 접근하는 코드를 실행할 때에 그 프로세스가 임계구역에 있다라고 정의 상호 배제(Mutual Exclusion) The execution of critical sections must be mutually exclusive 다중 프로세서 환경에서도 임계구역에서 실행하고 있는 프로세스는 오직 하나만 있어야 한다 상호 배제에 대한 접근법 병행 실행되는 각 프로세스는 임계구역에 들어가기 위해서는 임계구역 실행에 대한 허용(permission)을 얻어야 한다 Operating System

18 임계구역(critical section) 문제(2)
프로세스 동기화 프로토콜을 설계 병행 프로세스의 실행 결과가 실행 순서에 상관없이 일정하도록 프로세스 상호간에 협조하는 프로토콜을 설계 Operating System

19 임계 구역 문제의 기본 가정(1) 병행 프로세스의 전형적인 구조 진입 구역(entry section)
임계 구역에 진입하기 위해 허용을 요구하는 코드 영역 출구 구역(exit section) 임계 구역 다음에 나오는 영역으로 임계 구역을 벗어나기 위한 코드 영역 잔류 구역(remainder section) 프로그램의 나머지 코드 영역 Operating System

20 임계 구역 문제의 기본 가정(2) Repeat entry section critical section exit section
병행 프로세스의 전형적인 구조(계속) Repeat entry section critical section exit section remainder section until FALSE Operating System

21 임계 구역 문제의 기본 가정(3) 각 프로세스는 0이 아닌 속도로 실행된다
n개의 프로세스의 상대적인 실행 속도에 대한 가정은 없다 n 개의 프로세스의 실행순서에 대한 가정은 없다 많은 CPU가 존재할 수 있다 동일한 메모리 영역을 동시에 접근할 수 없도록 제어하는 메모리 하드웨어가 있다 임계 구역 문제에 대한 해결책을 찾는 것은 진입 구역과 출구 구역의 코드를 정의하는 것이다 Operating System

22 임계 구역 문제의 해결책에 대한 세 가지 요구조건(1)
임계 구역 문제의 해결책에 대한 세 가지 요구조건(1) 상호배제(Mutual Exclusion) 항상 최대한 하나의 프로세스만이 임계구역에서 실행할 수 있다 한 프로세스가 임계구역에 있으면 다른 프로세스는 임계구역에 진입할 수 없다 진행(Progress) 임계구역에 있는 프로세스가 없고 다른 프로세스들이 임계 구역 진입을 요구할 때에 단지 잔류 구역에서 실행되고 있지 않은 프로세스 만이 임계 구역에 진입할 수 있다 임계 구역 진입 프로세스 선택은 무기한 연기될 수 없다 Deadlock Avoidance Operating System

23 임계 구역 문제의 해결책에 대한 세 가지 요구조건(2)
임계 구역 문제의 해결책에 대한 세 가지 요구조건(2) 한계 대기(Bounded Waiting) 하나의 프로세스가 임계 구역 진입을 요청한 후에 진입이 허용될 때까지 다른 프로세스가 임계 구역을 진입하는 회수(시간)에 한계를 두어야 한다 그렇지 않으면 진입 요청한 프로세스는 기아상태(starvation)가 될 수 있다 Operating System

24 임계 구역 문제 해결책의 분류 소프트웨어 해결책(Software solutions)
software algorithms who’s correctness does not rely on any other assumptions 하드웨어 해결책(Hardware solutions) rely on some special machine instructions 운영체제 해결책(Operation System solutions) OS provide some functions and data structures to the programmer Operating System

25 소프트웨어 해결책 2개의 프로세스를 위한 해결책 n 개의 프로세스를 위한 해결책 Notation
Algorithm 1 and 2 are incorrect Algorithm 3 is correct (Peterson’s algorithm) n 개의 프로세스를 위한 해결책 the bakery algorithm Notation 2 processes: P0 and P1 When presenting processes, Pi, Pj always denote the other processes (i != j) Operating System

26 Algorithm 1 Process Pi: repeat while(turn!=i){}; CS turn:=j; RS
The shared variable turn is initialized (to 0 or 1) before executing any Pi Pi’s critical section is executed iff turn = i Pi is busy waiting if Pj is in CS: mutual exclusion is satisfied Progress requirement is not satisfied Process Pi: repeat while(turn!=i){}; CS turn:=j; RS until FALSE Ex: P0 has a large RS and P1 has a small RS. If turn=0, P0 enter its CS and then its long RS (turn=1). P1 enter its CS and then its RS (turn=0) and tries again to enter its CS: request refused! He has to wait that P0 leaves its RS. Operating System

27 Algorithm 2 Process Pi: repeat flag[i]:=true; while(flag[j]){}; CS
Keep one BOOL variable for each process: flag[0] and flag[1] Pi signals that it is ready to enter it’s CS by: flag[i]:=true Mutual Exclusion is satisfied but not the progress requirement If we have the sequence: T0: flag[0]:=true T1: flag[1]:=true Both process will wait forever to enter their CS: we have a deadlock Process Pi: repeat flag[i]:=true; while(flag[j]){}; CS flag[i]:=false; RS until FALSE Operating System

28 Algorithm 3 (Peterson’s algorithm)
Initialization: flag[0]:=flag[1]:=false turn := 0 or 1 Willingness to enter CS is specified by flag[i]:=true If both processes attempt to enter their CS simultaneously, only one turn value will last Exit section: specifies that Pi is unwilling to enter CS Process Pi: repeat flag[i]:=true; turn:=j; do {} while (flag[j]and turn=j); CS flag[i]:=false; RS until FALSE Operating System

29 Algorithm 3: proof of correctness(1)
Mutual exclusion is preserved since: P0 and P1 are both in CS only if flag[0] = flag[1] = true and only if turn = i for each Pi (impossible) The progress and bounded waiting requirements are satisfied: Pi cannot enter CS only if stuck in while() with condition flag[ j] = true and turn = j. If Pj is not ready to enter CS then flag[ j] = false and Pi can then enter its CS Operating System

30 Algorithm 3: proof of correctness(2)
If Pj has set flag[ j]=true and is in its while(), then either turn=i or turn=j If turn=i, then Pi enters CS. If turn=j then Pj enters CS but will then reset flag[ j]=false on exit: allowing Pi to enter CS but if Pj has time to reset flag[ j]=true, it must also set turn=i since Pi does not change value of turn while stuck in while(), Pi will enter CS after at most one CS entry by Pj (bounded waiting) Operating System

31 n-process solution: The bakery algorithm (1)
Before entering their CS, each Pi receives a number. Holder of smallest number enter CS (like in bakeries, ice-cream stores...) When Pi and Pj receives the same number: if I < j then Pi is served first, else Pj is served first Pi resets its number to 0 in the exit section Notation: (a, b) < (c, d) if a < c or if a = c and b < d max(a0,…,ak) is a number b such that b >= ai for i=0,..k Operating System

32 The bakery algorithm (2)
Shared data: choosing: array[0..n-1] of boolean; initialized to false number: array[0..n-1] of integer; initialized to 0 Correctness relies on the following fact: If Pi is in CS and Pk has already chosen its number[k]!= 0, then (number[i], i) < (number[k], k) Operating System

33 The bakery algorithm (3)
Process Pi: repeat choosing[i]:=true; number[i]:=max(number[0]..number[n-1])+1; choosing[i]:=false; for j:=0 to n-1 do { while (choosing[j]) {}; while (number[j]!=0 and (number[j],j)<(number[i],i)){}; } CS number[i]:=0; RS until FALSE Operating System

34 소프트웨어 해결책의 단점 임계 구역에 진입하기를 원하는 프로세스는 busy waiting 한다
필요 없이 CPU 시간을 낭비한다 임계 구역이 긴 경우에는 임계 구역 진입을 기다리는 프로세스를 대기 상태로 전환하는 것( blocking)이 효과적이다 Operating System

35 하드웨어 해결책: interrupt disabling
On a uniprocessor: mutual exclusion is preserved but efficiency of execution is degraded while in CS, we cannot interleave execution with other processes that are in RS On a multiprocessor: mutual exclusion is not preserved Generally not an acceptable solution Process Pi: repeat disable interrupts critical section enable interrupts remainder section until FALSE Operating System

36 하드웨어 해결책: special machine instructions
일반적으로 하나의 메모리 영역에 대한 접근은 배타적이다 하나의 메모리에 대해 동시에 여러 개의 접근이 이루어질 수 없다 명령어 확장: 같은 메모리 영역에 2 가지의 동작을 원자적으로 (atomically) 실행하는 명령어 제공 예 - reading and writing a memory location test-and-set, xchg(swap) instructions The execution of such an instruction is mutually exclusive (even with multiple CPUs) 상호배제 문제를 해결하기 위해 이용 Operating System

37 test-and-set instruction(1)
A C++ description of test-and-set instruction: bool testset(int& i) { if (i==0) { i=1; return true; } else { return false; } Operating System

38 test-and-set instruction(2)
An algorithm that uses testset instruction for Mutual Exclusion: Shared variable b is initialized to 0 Only the first Pi who sets b enter CS Process Pi: repeat repeat{} until testset(b); CS b:=0; RS until FALSE Operating System

39 test-and-set instruction (3)
Mutual exclusion is preserved if Pi enter CS, the other Pj are busy waiting Problem: still using busy waiting When Pi exit CS, the selection of the Pj who will enter CS is arbitrary: no bounded waiting Hence starvation is possible Operating System

40 xchg instruction Processors (ex: Pentium) often provide an atomic xchg(a,b) instruction that swaps the content of a and b. void xchg(int a, int b) { int temp; temp = a; a = b; b = temp; } xchg(a,b) suffers from the same drawbacks as test-and-set instruction Operating System

41 Using xchg for mutual exclusion
Shared variable b is initialized to 0 Each Pi has a local variable k The only Pi that can enter CS is the one who finds b=0 This Pi excludes all the other Pj by setting b to 1 Process Pi: repeat k:=1 repeat xchg(k,b) until k=0; CS b:=0; RS until FALSE Operating System

42 운영체제 해결책 운영체제는 프로세스 동기화를 위한 도구를 제공 세마포어(Semaphores) / 뮤텍스(Mutex)
모니터(Monitors) 메시지 전송(Message Passing) Operating System

43 세마포어(Semaphores) (1) 정의 definition Busy waiting avoidance
Busy waiting을 요구하지 않는 Synchronization tool (provided by the OS) 운영체제가 제공하는 하나의 자원 세마포어 S는 다음의 2 atomic and mutually exclusive operations에 의해서만 접근할 수 있는 정수 wait(S) signal(S) Busy waiting avoidance when a process has to wait, it will be put in a blocked queue of processes waiting for the same event Operating System

44 세마포어(Semaphores) (2) A semaphore is a record (structure):
type semaphore = record count: integer; queue: list of process end; var S: semaphore; wait 연산에서 프로세스가 세마포어 S을 기다려야 할 때에는 대기 상태로 전환되어 세마포어 큐에 들어간다 signal 연산은 세마포어 큐로부터 하나의 프로세스를 꺼내어 준비 큐에 저장한다 Operating System

45 세마포어 연산 (atomic) S.count must be initialized to a nonnegative value
wait(S): S.count--; if (S.count<0) { block this process place this process in S.queue } signal(S): S.count++; if (S.count<=0) { remove a process P from S.queue place this process P on ready list S.count must be initialized to a nonnegative value (depending on application) Operating System

46 Semaphores: observations (1)
S.count >=0 일 때 the number of processes that can execute wait(S) without being blocked = S.count S.count<0 일 때 the number of processes waiting on S = |S.count| Atomicity and mutual exclusion no 2 process can be in wait(S) and signal(S) (on the same S) at the same time (even with multiple CPUs) The blocks of code defining wait(S) and signal(S) are critical sections Operating System

47 Semaphores: observations (2)
The critical sections defined by wait(S) and signal(S) are very short typically 10 instructions Solutions: uniprocessor: disable interrupts during these operations (i.e: for a very short period) This does not work on a multiprocessor machine multiprocessor: use previous software or hardware schemes The amount of busy waiting should be small. Operating System

48 Using semaphores for solving critical section problems
S.count을 1로 초기화 단지 하나의 프로세스만 CS 진입이 허용된다 (mutual exclusion) S.count을 k로 초기화하면 k 개의 프로세스가 CS에 진입할 수 있다 Process Pi: repeat wait(S); CS signal(S); RS until FALSE Operating System

49 Using semaphores to synchronize processes
We have 2 processes: P1 and P2 Statement S1 in P1 needs to be performed before statement S2 in P2 Then define a semaphore ‘synch’ Initialize ‘synch’ to 0 Proper synchronization is achieved by having in P1: : S1; signal(synch); And having in P2: wait(synch); S2; Operating System

50 생산자/소비자 문제 (producer/consumer problem)
A producer process produces information that is consumed by a consumer process 예: a print program produces characters that are consumed by a printer 생성된 정보를 사용할 때까지 저장할 buffer가 필요하다 A common paradigm for cooperating processes Operating System

51 P/C Problem: unbounded buffer(1)
in 은 다음에 생성된 정보를 저장할 위치를 지정 Out 은 다음에 소비될 저장하고 있는 위치를 지정 Operating System

52 P/C Problem: unbounded buffer(2)
semaphore S : to perform mutual exclusion on the buffer only 1 process at a time can access the buffer semaphore N : to synchronize producer and consumer on the number N (= in - out) of items in the buffer an item can be consumed only after it has been created Operating System

53 P/C Problem: unbounded buffer(3)
생산자는 항상 자유롭게 생성된 정보를 버퍼에 추가할 수 있다 버퍼에 저장하기 전에 wait(S) 버퍼에 저장한 후에 signal(S) 생산자는 버퍼에 새로운 정보를 추가한 후에 새로운 정보가 생성되었음을 동기화 하기 위해 signal(N) 수행 소비자는 먼저 소비할 정보가 있는지를 검사하기 위해 wait(N)을 수행하고, 정보가 버퍼에 있으면 버퍼를 접근하기 위해 wait(S)/signal(S) 을 수행 Operating System

54 P/C Problem: unbounded buffer(4) - Solution
append(v): b[in]:=v; in++; Initialization: S.count:=1; N.count:=0; in:=out:=0; take(): w:=b[out]; out++; return w; Operating System

55 P/C Problem: unbounded buffer(5) - Solution
Producer: repeat produce v; wait(S); append(v); signal(S); signal(N); until FALSE Consumer: repeat wait(N); wait(S); w:=take(); signal(S); consume(w); until FALSE critical sections Operating System

56 P/C Problem: unbounded buffer(6)
Remarks: The consumer must perform wait(N) before wait(S), otherwise deadlock occurs if consumer enter CS while the buffer is empty Operating System

57 P/C Problem: finite circular buffer(1)
저장된 정보의 수인 N이 최소한 1 이상일 때에 소비자가 버퍼 접근이 가능하다(ie. N != in – out) 생산자는 버퍼의 빈 공간의 수 E가 1 이상일 때에 버퍼에 정보를 저장할 수 있다 Operating System

58 P/C Problem: finite circular buffer(2)
필요한 세마포어: semaphore S : to have mutual exclusion on buffer access semaphore N : to synchronize producer and consumer on the number of consumable items semaphore E : to synchronize producer and consumer on the number of empty spaces Operating System

59 P/C Problem: finite circular buffer(3) - Solution
Initialization: S.count:=1; in:=0; N.count:=0; out:=0; E.count:=k; append(v): b[in]:=v; in:=(in+1) mod k; Producer: repeat produce v; wait(E); wait(S); append(v); signal(S); signal(N); until FALSE Consumer: repeat wait(N); wait(S); w:=take(); signal(S); signal(E); consume(w); until FALSE take(): w:=b[out]; out:=(out+1) mod k; return w; Operating System critical sections

60 The Dining Philosophers Problem(1)
5 philosophers who only eat and think each need to use 2 forks for eating we have only 5 forks A classical synchronization problem Illustrates the difficulty of allocating resources among process without deadlock and starvation Operating System

61 The Dining Philosophers Problem(2)
Each philosopher is a process One semaphore per fork: fork: array[0..4] of semaphores Initialization: fork[i].count:=1 for i:=0..4 A first attempt  Deadlock if each philosopher start by picking his left fork! Process Pi: repeat think; wait(fork[i]); wait(fork[i+1 mod 5]); eat; signal(fork[i+1 mod 5]); signal(fork[i]); forever Operating System

62 The Dining Philosophers Problem(3)
A solution: admit only 4 philosophers at a time that tries to eat Then 1 philosopher can always eat when the other 3 are holding 1 fork Hence, we can use another semaphore T that would limit at 4 the number of philosophers “sitting at the table” Initialize: T.count:=4 Process Pi: repeat think; wait(T); wait(fork[i]); wait(fork[i+1 mod 5]); eat; signal(fork[i+1 mod 5]); signal(fork[i]); signal(T); forever Operating System

63 이진 세마포어 (Binary semaphores) (1)
계수 세마포어(counting (or integer) semaphores) 이진 세마포어(binary semaphores) counting semaphores와 유사하나 “count”가 Boolean 값 (0 또는 1)을 가진다 일반적으로 counting semaphores 보다 사용하기 어렵다 예 : k > 1인 값으로 초기화하기 힘들다 Operating System

64 이진 세마포어 (Binary semaphores)(2)
waitB(S): if (S.value = 1) { S.value := 0; } else { block this process place this process in S.queue } signalB(S): if (S.queue is empty) { S.value := 1; remove a process P from S.queue place this process P on ready list Operating System

65 뮤텍스(Mutex) 이진 세마포어와 비슷한 개념 차이점:
이진 세마포어 경우, 락을 설정한 프로세스와 락을 해제하는 프로세서가 다를 수 있다. Operating System

66 Spinlocks wait(S): S--; while S<0 do{}; signal(S): S++;
They are counting semaphores that use busy waiting (instead of blocking) Useful on multi processors when critical sections last for a short time We then waste a bit of CPU time but we save process switch wait(S): S--; while S<0 do{}; signal(S): S++; Operating System

67 세마포어의 문제점 세마포어는 상호배제(mutual exclusion)과 프로세스 동기화에 유용한 도구
wait(S) 와 signal(S)가 여러 프로세스 사이에 분산될 수 있어 전체적인 동작을 이해하는데 어렵다 모든 프로세스에서 세마포어를 정상적으로 사용하여야 한다 하나의 프로세스에서 세마포어 사용에 오류가 발생하면 전체 프로세스가 실패할 수 있다 Operating System

68 모니터(Monitors) (1) 고급 프로그래밍 언어에서 제공하는 동기화 구조 (Synchronization Construct) 세마포어와 동일한 기능을 제공 보다 쉬운 제어 기능을 제공 많은 병행 프로그래밍 언어(Concurrent Programming Language)에서 지원 Concurrent Pascal, Modula-3, uC++, Java... Operating System

69 모니터(Monitors) (2) 다음 항목을 포함하는 소프트웨어 모듈: 모듈 구성 지역 변수
하나 이상의 프로시듀어(procedures) 초기화 코드(initialization sequence) 모듈 구성 type monitor-name = monitor local variable declarations procedure entry P1(…) begin … end; procedure entry P2(…) procedure entry Pn(…) begin initialization code end Operating System

70 모니터(Monitors) (3) 모니터 동작 특징: 모니터는 상호배제(mutual exclusion)를 보장한다
지역 변수는 모니터 내의 프로시저에 의해서만 접근할 수 있다 프로세스는 모니터의 프로시저 호출을 통해 모니터에 진입할 수 있다 언제나 단지 하나의 프로세스만이 모니터 안에 있을 수 있다 모니터는 상호배제(mutual exclusion)를 보장한다 프로그래머가 상호배제를 위하여 별도의 프로그램을 작성할 필요가 없다 공유 데이터 또는 자원을 모니터 안에 둠으로써 보호할 수 있다 공유 자원을 지역 변수로 정의 Operating System

71 조건 변수(Condition variables)
하나의 프로세스가 모니터 내에서 실행되기 전에 기다려야 하는 조건을 나타내는 변수 병행 처리에서의 동기화 도구 단지 모니터 내에서만 접근 가능하다 다음의 두개의 연산에 의해서만 접근 및 수정이 가능하다 cwait(a): 조건 변수 a 에 대해 호출한 함수를 대기 상태로 전환한다 csignal(a): 조건 변수 a 에 대해 대기 상태인 프로세스 중 하나의 프로세스를 선택하여 실행을 재개한다 프로그래머에 의해 프로세스 동기화에 이용된다 Operating System

72 모니터의 동작 대기 프로세스는 진입 큐 또는 조건 변수 큐에서 대기한다
하나의 프로세스가 cwait(cn)을 호출하여 조건 변수 cn 의 큐에서 대기하게 된다 csignal(cn)은 모니터가 조건 변수 cn 의 큐에서 하나의 프로세스을 가져와 실행하게 한다 csignal(cn)을 호출한 프로세스는 실행을 중단하고 urgent queue에서 대기한다 Operating System

73 생산자/소비자 프로세스 문제(1) Producer_I: repeat produce v; Append(v);
Two types of processes: producers consumers Synchronization is now confined within the monitor append(.) and take(.) are procedures within the monitor The procedures are the only means by which P/C processes can access the buffer If these procedures are correct, synchronization will be correct for all participating processes Producer_I: repeat produce v; Append(v); until FALSE Consumer_I: Take(v); consume v; Operating System

74 생산자/소비자 프로세스 문제(2) 버퍼를 공유하기 위해 모니터(Monitor)가 필요 두개의 조건 변수:
buffer: array[0..k-1] of items; 두개의 조건 변수: notfull: csignal(notfull)는 버퍼가 차지 않았음을 나타낸다 notempty: csignal(notempty)는 버퍼가 비어 있지 않음을 나타낸다 버퍼 조작을 위한 포인터와 카운터: nextin: 다음 항목을 저장할 위치 포인터 nextout: 다음 항목을 가져올 위치 포인터 count: 현재 버퍼에 저장된 항목의 수 Operating System

75 생산자/소비자 프로세스 문제(3) Monitor boundedbuffer:
buffer: array[0..k-1] of items; nextin:=0, nextout:=0, count:=0: integer; notfull, notempty: condition; Append(v): if (count=k) cwait(notfull); buffer[nextin]:= v; nextin:= nextin+1 mod k; count++; csignal(notempty); Take(v): if (count=0) cwait(notempty); v:= buffer[nextout]; nextout:= nextout+1 mod k; count--; csignal(notfull); Operating System

76 메시지 전송(Message Passing)
프로세스간의 통신(interprocess communication : IPC)을 위한 일반적인 방법: 하나의 컴퓨터 내의 프로세스간 통신 분산 시스템 내의 프로세스간 통신 프로세스 동기화 및 상호배제 문제를 위한 방법으로 이용 두개의 기본적인 연산: send(destination, message) receive(source, message) 위의 연산에서 프로세스는 대기상태로 전환될 수도 있고 안될 수도 있다 Operating System

77 메시지 전송을 통한 동기화 (1) 송신측: 일반적으로 send(.,.) 호출한 다음에 실행을 계속한다(non-blocking)
다수의 수신자에게 메시지 전송이 가능하다 보통 수신자가 메시지 수신 여부를 알려 주기를 기대한다 수신측: 일반적으로 receive(.,.) 호출한 다음에 메시지가 수신될 때까지 대기상태가 된다(blocking) 보통 수신자는 실행을 계속하기 위해 정보를 요구한다- 정보가 전송될 때까지 기다린다 송신자가 메시지를 전송 전에 실패한다면 수신자는 무한정 기다리게 된다 Operating System

78 메시지 전송을 통한 동기화 (2) 다른 가능성을 제공된다 예: blocking send, blocking receive:
both are blocked until the message is received occurs when the communication link is unbuffered (no message queue) provides tight synchronization (rendez-vous) Operating System

79 메시지 전송에서의 주소 지정 직접 주소 지정(direct addressing):
메시지 전송 연산에서 송신자/수신자를 위해 특정 프로세스 ID를 사용한다 간접 주소 지정(indirect addressing): 메시지는 메시지 큐로 구성된 mailbox로 전송된다 송신자는 mailbox로 메시지를 보내고, 수신자는 mailbox에서 메시지를 가져온다 좀 더 일반적이고 편한 전송 방식 Operating System

80 Mailboxes and Ports A mailbox can be private to one sender/receiver pair The same mailbox can be shared among several senders and receivers Port: a mailbox associated with one receiver and multiple senders used for client/server applications: the receiver is the server Operating System

81 Ownership of ports and mailboxes
요청한 프로세스가 소유하게 된다 소유권을 가진 프로세스의 요청이나 종료로 인해 해제된다 Operating System

82 메시지 형식(Message Format)
헤드와 메시지 본체로 구성 control information: what to do if run out of buffer space sequence numbers priority etc. Operating System

83 메시지 전송을 통한 상호배제 N 개의 프로세스가 공유할 mailbox mutex 을 생성한다
send() 는 non blocking receive()는 mutex 가 비어 있으면 blocking empty 초기화: send(mutex, “go”); receive()를 처음 호출하는 프로세스 Pi가 임계구역 (CS)에 진입한다 다른 프로세스는 Pi 가 메시지를 전송할 때가 대기한다 Process Pi: var msg: message; repeat receive(mutex,msg); CS send(mutex,msg); RS forever Operating System

84 메시지 전송을 통한 생산자/소비자 프로세스 문제(1)
메시지 전송을 통한 생산자/소비자 프로세스 문제(1) const capacity = …; // buffering capacity null = …; // empty message var i : integer; procedure producer; var pmsg : message; begin while true do receive(mayproduce, pmsg); pmsg ;= produce; send(mayconsume, pmsg); end end; procedure consumer; var cmsg : message; receive(mayconsume, cmsg); consume(cmsg); send(mayproduce, null); Operating System

85 메시지 전송을 통한 생산자/소비자 프로세스 문제(2)
메시지 전송을 통한 생산자/소비자 프로세스 문제(2) { parent process } begin create_mailbox(mayproduce); create_mailbox(mayconsume); for i=1 to capacity do send(mayproduce, null); parbegin producer; consumer; parend end Operating System

86 입력기/출력기 문제 (Readers/Writers Problem)
Any number of readers may simultaneously read the file Only one writer at a time may write to the file If a writer is writing to the file, no reader may read it Operating System

87 Operating System

88 Operating System