Synchronization

Transcription

1 Synchronization

2 Command Execution 명령어수행과운영체제 UNIX: 프로그램이실행한프로세스가종료될때까지대기 Windows: 실행된모든프로세스는각자수행 Enter Loop Enter Loop Yes Another Command? No fork()code Exit Loop Yes Another Command? No Exit Loop CreateProcess()code Wait for Child to Terminate Execute Command (a) synchronization Execute Execute Command Command (b) no synchronization 2

3 FALSE FALSE FALSE TRUE TRUE TRUE 공유변수 Synchronizing Multiple Threads with a Shared Variable 공유변수 (e.g., run Flag) 를이용하여실행되는자식쓰레드를제어 runflag 가 FALSE 가될때까지지정된작업을지속적으로수행 안정적인방법은아님. 따라서안정적이고실용적인방법필요 Initialize CreateThread( ) Wait runtime seconds Thread Work runflag=false runflag? Exit Terminate 3

4 Concurrency( 병행성 ) 하나의자원에여러객체들이동시에접근하는것. 동기화를통해서 Concurrency 문제를해결 Process 관점 순서를정해서자원을사용해야함. Resource 관점 상호배제 : 자원은한 process 만이사용임계구역 (critical section) 내에서는한프로세스가한자원을사용 동기화를하는방법 소프트웨어적방법하드웨어적방법 OS에서지원하는방법 4

5 Critical Section ( 임계구역 ) Definition of Critical Section Two Programs Code for P1 - 어느한시점에서둘이상의프로세스가동시에자원또는데이터를사용하도록지정된영역을의미 shared double balance; Code for P2 balance = balance + amount; balance = balance - amount; Race Condition(critical section problem) 실행상태에있는두개의프로세스가동시에 Resource 에대한접근이나공유메모리 ( 예, balance 공유변수 ) 를놓고경쟁 Mutual Exclusion( 상호배제 ) Race Condition 에있는프로세스가 Critical Section 에진입하기위한전제조건. ( 한번에하나의 Process 만접근 ) 5

6 Two Programs Two Processes Code for P1 Example of Critical Section shared double balance; Code for P1... balance = balance + amount;... Code for P2... balance = balance - amount;... load load add store Code for P2 load load sub store R1, balance R2, amount R1, R2 R1, balance R1, balance R2, amount R1, R2 R1, balance P1 P2 P1 Critical Section CPU Instruction Processing Sequence CPU Instruction P1 :load R1, balance 500 P1: load R2, amount 200 Context Switching! 상호배제위반 P2: load R1, balance P2: load R2, amount P2: sub R1, R2 P2: store R1, balance Context Switching! P1: add R1, R2 P1: store R1, balance Result: balance = 700 Intend Result: balance = 600 Example of Critical Section Value Inconsistency Occur! balance = 500; P1.amout = 200; P2.amout = 100; 6

7 Problem of Critical Section Critical Sections (cont d) Critical Section 의기본필수조건 Mutual Exclusion 항상하나의프로세스만이임계구역에서수행. 임계구역이수행중이면다른프로세스는진입할수없음. Progress 임계구역이수행하는프로세스가없고어떤프로세스가진입하려할때, 임계구역으로바로진입이가능해야하고, 무기한연기될수없음 Bounded Waiting 하나의프로세스가진입을요청하고, 진입이허용될때까지다른프로세스가진입하는회수 ( 시간 ) 에한계를두는것 진입요청한프로세스가기아상태 (starvation) 에빠짐 7

8 Critical Section 문제해결책 경쟁하는모든프로세스들은데이터를공유 각프로세스는 critical section 이라는공통코드를가짐. 하나의프로세스가 critical section 을수행중이면다른프로세스는각각의 critical section 을수행할수없다. 예 ) 은행입출금문제의 Balance 증가 감소 8

9 Mechanisms Possible Mechanisms Software Solution Using Algorithms Hardware Solution Disabling Interrupt Test-And-Set, Swap Using a Lock Variable in Test-And-Set OS Solution Event, Signal Semaphores Monitors Message Passing 9

10 Using Algorithms Critical Section 을가진프로세스의구조 do { entry section critical section exit section reminder section while (1); 10

11 Shared variables: Using Algorithm 1 int turn; turn = 0 으로초기화 turn = i 일때, P i 이 critical section에진입가능 Process P i do { while (turn!= i); // turn 변수의상태정보이용 critical section turn = j; reminder section while (1); 만족조건 : mutual exclusion 불만족조건 : progress turn=0 에서 P 0 가수행중이아닐때, P 1 이진입하려하면진입불가 - 초기화상태 P 1 수행 P 1 진입불가 11

12 Using Algorithm 2 Shared variables: boolean flag[2]; flag [0] = flag [1] = false 로초기화 flag [i] = true 일때, P i 이 critical section 에진입가능 Process P i do { flag[i] = true; // Critical Section 진입준비 A while (flag[j]) ; // 다른프로세스의상태점검 critical section flag [i] = false; // 자신의상태변경 remainder section while (1); 만족조건 : mutual exclusion A 의문장이빠지면조건에위배된다. 불만족조건 : progress P 0 의 flag[0] = true set 직후다중프로그래밍으로인해 P 1 으로전환되어 flag[1] = true set 하면무한루프발생 (progress 위반 ) 12

13 Using Algorithm 3(Peterson) 앞의두알고리즘에서사용된공유변수를모두사용 Process P i do { A B while (1); flag [i] = true; // Critical Section 진입준비 turn = j; // 상태변경 while (flag [j] and turn = j) ; // 2 가지모두점검 flag [i] = false; critical section remainder section 만족조건 : mutual exclusion, progress 두프로세스사이에발생가능한 critical section 을동기화 A, B 2가지중반드시하나는만족하게됨 13

14 Problem of Software Solution 임계구역에진입하기를원하는프로세스 while 문장에의해 busy waiting이발생. CPU 시간을낭비. Busy waiting 이긴경우 임계구역진입을기다리는프로세스를대기상태로전환하는것 (blocking) 이효과적. 14

15 Using Hardware Solution 원자적으로실행 (executed atomically) 중간에인터럽트가되지않는하나의단위로수행됨 Disabling interrupt Test-and-Set 15

16 Disabling Interrupts Hardware Mechanism Hardware Solution Using Interrupts Timer Interrupt 를강제적으로가능 / 불가능하게하여 Context Switching 이발생하지않도록함. 과 영역에서 Interrupt 에의한 Context Switching 이발생하지않음. disableinterrupts(), enableinterrups() : System Call shared double balance; Code for P1 Code for P2... disableinterrupts(); balance = balance + amount; enableinterrupts(); disableinterrupts(); balance = balance - amount; enableinterrupts();... 16

17 Problem of Hardware Solution Problem Disabling Interrupts (cont d) P1 과 P2 의사용만을막고자하였으나, 다른모든 Process 의 Interrupts 가 Disabling 됨. I/O Interrupt 도처리할수없음. 전체 interrupt 를 Disabling 하지않아야함. Interrupts Disabling 이후 Enabling 되는시간을알수없음. P1 이 Interrupts Disabling 수행후, Schedule 의 Context Switching 이발생. 우선순위가낮으면 Process 가다시시작하는시간을알수없음. 17

18 Test-and-Set Test-and-Set 시스템에서제공하는하드웨어명령어 상태를점검 (Test) 하고변경 (Set) TAS 는프로세서에의해서나눠지지않게수행 TAS 수행중에 Lock 변수를사용하여 interrupt 되지않음 18

19 Test-and-Set Mutual Exclusion with Test-and-Set //Test-and-Set 을이용한한계대기상호배제 function Test-and-Set (var target: boolean): boolean; begin Test-and-Set := target; target := true; end; //Test-and-Set 으로상호배제구현 Repeat while Test-and-Set( lock ) do no-op; 임계구역 lock := false; 잔류구역 until false; 19

20 Lock - 1 해결방법 Using a Lock Variable OS 가제공하는공유변수를이용 Critical Section 의진입을 lock 상태정보를이용하여문제해결. 상태정보가 FALSE 이면 TRUE 로변경하며 CS 에진입하고 True 일때 Busy Waiting 상태정보를이용하여 Mutual Exclusion 을성립 shared boolean lock = FALSE; shared double balance; Code for P1 // Acquire the lock while(lock); lock = TRUE; // Execute critical section balance = balance + amount; // Release lock lock = FALSE; Code for P2 // Acquire the lock while(lock); lock = TRUE; // Execute critical section balance = balance - amount; // Release lock lock = FALSE; 20

21 Lock - 2 Code for P1 Using a Lock Variable (Cont d) Lock Variable 진행순서 shared boolean lock = FALSE; shared double balance; Code for P2 // Acquire the lock while(lock); lock = TRUE; // Acquire the lock while(lock); lock = TRUE; 시간 t0 임계영역진입 lock 을얻음 //Execute critical section balance=balance+amount; // Release lock lock = FALSE; //Execute critical section balance=balance-amount; // Release lock lock = FALSE; t1 t2 t3 t4 critical section lock 을양보 lock 을요청하지만다른프로세스가사용중이므로 임계영역진입 lock 을얻음 대기 t5 t6 critical section lock 을양보 21

22 Lock - 3 Using a Lock Variable (Cont d) Problem of a Lock Variable 또다른 race condition 이발생. 즉, Mutual Exclusion 생성하기위한공유변수가 Critical Section 이되는문제가발생. shared boolean lock = FALSE; shared double balance; Process Context Switching Code for P1 // Acquire the lock while(lock); lock = TRUE; // Execute critical section balance = balance + amount; // Release lock lock = FALSE; Code for P2 // Acquire the lock while(lock); lock = TRUE; // Execute critical section balance = balance - amount; // Release lock lock = FALSE; 22

23 Lock Manipulation as a Critical Section shared double amount, balance; /* 공유변수 */ Code shared for int P1 lock = FALSE; Code /* 동기화 for P2변수 */ enter( lock ); enter( lock ); balance = balance + amount; balance = balance + amount; exit( lock ); exit( lock ); 임계영역진입 enter( lock ) { disableinterrupts(); /* wait for lock */ while( lock ) { /* Let interrupt occur */ enableinterrupts(); disableinterrupts(); lock = TRUE; enableinterrupts(); 임계영역빠져나옴 exit( lock ) { disableinterrupts(); lock = FALSE; enableinterrupts(); disableinterrupts() : 인터럽트금지 enableinterrupts() : 인터럽트허용 23

24 Lock variable 사용 1 Windows 에서 MFC 예제 Lock 변수가 TAS 의기능을수행하여문제해결 CCriticalSection g_critical; // 전역변수로선언 function() { AfxBeginThread(ThreadFuncA, NULL); AfxBeginThread(ThreadFuncB, this); UINT ThreadFuncA(LPVOID pparam) { while(1) { g_critical.lock(); // Critical Section g_critical.unlock(); return 0; UINT ThreadFuncB(LPVOID pparam) { while(1) { g_critical.lock(); // Critical Section g_critical.unlock(); return 0; ThreadFuncA 를작업자스레드로생성하며, 보안특성은기본값 (NULL) 로설정 ThreadFuncB 를작업자스레드로생성하며, 보안특성은현재프로세스로부터상속 * 보안특성은사용자, 그룹등의권한정보로윈도우에서는 SECURITY_ATTRIBUTES 구조체로표현 24

25 Lock variable 사용 2 Linux 에서 C++ 예제 Linux thread 프로그램에서 LinuxThreads 가제공하는것은쓰레드루틴들의프로토타입을선언하는 /usr/include/pthread.h 헤더를통해서이용가능 #include <pthread.h> 동기화객체로사용할 lock을선언... pthread_mutex_t lock; pthread_mutex_init(&lock, NULL);... 공유변수들에 lock 을걸고쓰레드를만들기위한 pthread 루틴들을사용한다. pthreads_mutex_lock( &lock ); /* Critical Section */ pthreads_mutex_unlock( &lock ); 동기화객체의초기화 25

26 Semaphore - 1 Dijkstra Semaphore Semaphore 1960 년대, 동기화를해결하려는시도로개념적인이론 개념적인이론으로 P(), V() Operation 과같은의사코드임. 기본적으로 Process 기반으로작성. Thread 에서도적용가능하여대부분의 OS 동기화방법들의기초가됨. Semaphore 의종류 Counting Semaphore (integer value) 다수의프로세스들이동시에임계구역을수행가능 Binary (0, 1 or true, false) Semaphore 값의상태에따른수행증가 Semaphore보다간편한구현 26

27 Semaphore - 2 Dijkstra Semaphore (Cont d) Hardware/Software 모두적용가능 In semaphore, S 값 ( 세마포어변수 ) 은양수의숫자값으로 2 가지나눠지지않는 (Atomic) 함수에서만조작이가능 P(), V() Operation 은 Atomic 하다고가정. V(): Mutual Exclusion 상태에서 S 값이증가하는 Operation 즉, 실제 Critical Section 의수행. P(): S 값을검사하고대기하거나수행하는 Operation V(S): [S = S + 1] // 실행 P(S): [while(s == 0) {wait; S = S - 1] // 대기후감소 27

28 Processes Condition for Semaphore Dijkstra Semaphore (Cont d) Cooperating Processes 여러개의 Processes 가협동하며처리하기위한기본구성. <shared global declarations> 에처리할공유변수선언. fork() 이후의코드는순차적으로수행되는코드가순환하는형태를취해야함. Proc_0() { Proc_1() { while (TRUE) { while (TRUE) { 순환함 <compute section>; <critical section>; 순차적임 <compute section>; <critical section>; <shared global declarations> <initial processing> fork(proc_0, 0); fork(proc_1, 0); 28

29 Assumptions of Semaphore and Mutex Dijkstra Semaphore (Cont d) 해결방법에대한가정 메모리읽기 / 쓰기는나누어지지않음 (Invisible, Atomic). 프로세스간우선순위는존재하지않음프로세스와프로세서의속도는제외. 프로세스는순차적으로순환하는형태. Mutex Mutex 는 Binary Semaphore 임. Mutex 를 Lock 한프로세스만이 Unlock 가능 29

30 Basic Concept of Semaphore Code Dijkstra Semaphore (Cont d) Semaphore 의기본코드 (Skeleton Code) Cooperating Process의구조. Critical Section에진입하기전에반드시점검. Proc_0() { while (TRUE) { <compute section>; P(mutex); <critical section>; V(mutex); Proc_1() { while (TRUE) { <compute section>; P(mutex); <critical section>; V(mutex); semaphore mutex = 1; fork(proc_0, 0); fork(proc_1, 0); 30

31 Semaphore Code for Shared Account Problem Dijkstra Semaphore (Cont d) Semaphore 를이용한공유변수문제해결 Proc_0() { // Enter the CS P(mutex); Proc_1() { // Enter the CS P(mutex); balance = balance + amount; balance = balance - amount; // Exit the CS V(mutex); // Exit the CS V(mutex); semaphore mutex = 1; fork(proc_0, 0); fork(proc_1, 0); 31

32 Semaphore Code for Two Shared Variables Dijkstra Semaphore (Cont d) 2 개의프로세스간의동기화문제해결 Proc_A() { while(true) { <compute section A1>; update(x); // Signal to Proc_B V(s1); <compute section A2>; // Wait for Proc_B P(s2); retrieve(y); semaphore s1 = 0; semaphore s2 = 0; fork(proc_a, 0); fork(proc_b, 0); Proc_B() { while(true) { // Wait for Proc_A P(s1); retrieve(x); <compute section B1>; update(y); // Signal to Proc_A V(s2); <compute section B2>; Update 되기를기다려야하므로세마포어변수를 0 으로 Set 실행과정 1. Proc_B 는 에서 blocking 2. Proc_A 는 까지단독실행 3. Proc_A 의 ~ 사이의코드와 Proc_B 의 이후의코드가동시에실행 4. Proc_A 는 Proc_B 의 를실행할때까지 에서대기 5. Proc_B의 를실행한후 Proc_A의 이후의코드를실행 32

33 AND Synchronization Definition of AND Synchronization AND Synchronization Problem 문제정의다수의프로세스에의해동시접근될수있는자원이여러개존재각프로세스가수행되려면두개이상의자원을모두소유해야함문제 semaphore 의경우두개이상의자원에대한중첩된 lock 을사용할경우, Deadlock 이발생함. Semaphore mutex1 = 1; Semaphore mutex2 = 1; 중첩된 lock P(mutex1); 서로 lock을요청 P(mutex2); Deadlock 발생 Critical Section V(mutex1); V(mutex2); P(mutex2); P(mutex1); Critical Section V(mutex2); V(mutex1); 해결방법 p(),v() operation 을 ordering 한추상화된 semaphore 사용 P simultaneous (S 1,, S n ) 33

34 Conceptual Code of AND Synchronization AND Synchronization (cont.) Concept Code 모든자원에대해 AND 조건즉, 모두사용이가능한상태에서동기화하는방법. semaphore mutex = 1; semaphore block = 0; P.sim(int S, int R) { P(mutex); S--; R--; V.sim(int S, int R) { P(mutex); S++; R++; if((s < 0) (R < 0)) { V(mutex); P(block); else V(mutex); unlock S, R 둘중하나라도사용할자원이없으면 block if(((s >= 0) && (R >= 0)) && ((S == 0) (R == 0))) V(block); V(mutex); S, R 둘다 1 개이상의여분의자원을가지고있고, S,R 둘중하나또는둘다 1 개의자원을소유 ( 예, S == 0 or R == 0) 하게되었을때 34

35 Dijkstra Semaphore (Cont d) Semaphore 는논리적으로 Device Controller 에서 busy 와 done 으로사용 Driver 는 controller 에게 V(busy) signal 을보내고, P(done) 이완료될때까지대기 Controller는실행을위해 P(busy) 상태를기다리고, V(done) 가완료됨을알림.... busy done Error code... busy done Idle finished working (undefined) Command Status Data 0 Logic Data 1 Data n-1 35

36 Semaphore Example Code in the Driver-Controller Interface Dijkstra Semaphore (Cont d) 세마포어개념을이용한 Driver-Controller 예제 driver() { <preparation for device operation> // Start the device V(busy); // Wait for the device to complete P(done); <complete the operation> controller() { while (TRUE) { // Wait for a start signal P(busy); <perform the operation> // Tell driver // that H/W has competed V(done); // Map the hardware flags to software shared semaphores semaphore busy = 0; semaphore done = 0; 36

37 Using Semaphore (Cont d) Readers-Writers Problem( 성격이다른 Processes 간의동기화문제 ) 다수의 Reader 와다수의 Writer 존재 Semaphore Solution for Different Processes Property Reader 들은 Shared Resource 에동시에접근할수있음 단, 하나의 Reader 라도 Shared Resource 를사용하고있다면 Writer 는 Shared Resource 에접근할수없음 하나의 Writer 라도 Shared Resource 에접근하고있으면, 다른 Writer 와모든 Reader 는 Shared Resource 에접근할수없음 Reader Reader Reader Reader Reader Reader Reader Reader Shared Resource Request Writer Writer Writer Writer Writer Writer Writer 37

38 Semaphore Code for Different Processes Property: Case 1 Using Semaphore (Cont d) Readers wait for update reader() { while(true) { <other computing>; P(mutex); readcount++; if(readcount == 1) P(writeBlock); // 최초의 reader 는 writer 와경쟁 V(mutex); // Critical section A access(resource); P(mutex); readcount--; if(readcount == 0) V(writeBlock); // 마지막 reader 는 writer 에게 signal 전송 V(mutex); resourcetype *resource; int readcount = 0; semaphore mutex = 1; semaphore writeblock = 1; fork(reader, 0); fork(writer, 0); writer() { while(true) { <other computing>; P(writeBlock); B // 모든 writer 는 reader 가없을때까지대기 // Critical section access(resource); V(writeBlock); Problem A B Writer is Blocked 에서 Readers 는 writer 가데이터를 update 해주기를기대함 에서 Writer 는모든 readers 가작업을끝낼때까지무한정대기함 writeblock 은동기화목적으로사용 mutex는 Mutual Exclusion을위해사용 38

39 Problem of Semaphore for Different Processes Property: Case 1 Using Semaphore (Cont d) Problem of First Reader / Writer Writer가다시자원을사용할수없는경우가발생가능모든 reader가작업이끝날때까지 writer는대기 (Bounded Waitng Problem) Resource Accessing Reader Reader Reader Writer Reader Reader... 도착순서 : Waiting Queuing Sequence 39

40 reader() { while(true) { <other computing>; P(writePending); P(readBlock); P(mutex1); readcount++; if(readcount == 1) P(writeBlock); V(mutex1); V(readBlock); V(writePending); access(resource); P(mutex1); readcount--; if(readcount == 0) V(writeBlock); V(mutex1); Using Semaphore (Cont d) writer() { while(true) { <other computing>; P(mutex2); writecount++; if(writecount == 1) P(readBlock); V(mutex2); P(writeBlock); access(resource); V(writeBlock); P(mutex2); writecount--; if(writecount == 0) V(readBlock); V(mutex2); int readcount = 0, writecount = 0; semaphore mutex1 = 1, mutex2 = 1; semaphore readblock = 1, writeblock = 1, writepending = 1; fork(reader, 0); fork(writer, 0); Semaphore Code for Different Processes Property: Case 2 실행과정 1. 에서 writer 가 readblock 을잡음 2. 에서데이터에 access 중인 readers 가작업을완료할때까지 writer 는대기함 3. 에서데이터에접근중인 reader 가없다면 writeblock lock 을풀어줌 4. 하나의 writer 가 update 작업을수행함 writer 에게높은우선순위를주는방법 에의해서 reader 가 readblock 를잡는시간이지연됨 writepending : 동기화목적 readblock : writer 에게우선순위부여 40

41 Semaphore Code for Different Processes Property: Case 2 Using Semaphore (Cont d) Problem of Precedence Reader / Writer Reader 가다시자원을사용할수없는경우발생. 도착한순서에상관없이 Writer 는앞선 writer 가종료되는순간 Resource 를사용한다.,, 의순서에따름. 먼저도착한 Reader 는우선순위가낮아무조건대기상태발생. Resource Waiting Waiting Waiting Waiting Writer Reader Reader Writer Reader Reader Writer... 도착순서 : Queuing Sequence 41

42 Bounded Buffer Using Semaphore Semaphore Solution for Bounded Buffer 생산자는 empty buffer pool 에서한개의빈 buffer 를가져와정보를채워 full buffer pool 에둠 소비자는반대로 full buffer pool 에서한개의 buffer 를꺼내와정보를얻고, 재활용을위해그버퍼를 empty buffer pool 에둠 빈 buffer 가없을때는생산자의진행을막음또는채워진 buffer 가없을때는소비자의진행을못막음. P(empty) : Empty Pool 확인 생산자 Empty Buffer Pool 소비자 V(empty) : Empty Pool 사용 V(full) : Full Pool 사용 Full Buffer Pool P(full) : Full Pool 확인 42

43 Semaphore Solution for Bounded Buffer Using Semaphore (Cont d) Bounded Buffer 해결 producer() { buf_type *next, *here; while(true) { produce_item(next); // Claim an empty 1 P(empty); P(mutex); here = obtain(empty); V(mutex); copy_buffer(next, here); P(mutex); release(here, fullpool); V(mutex); // Signal a full buffer V(full); consumer() { buf_type *next, *here; while(true) { // Claim full buffer 2 P(full); P(mutex); here = obtain(full); V(mutex); copy_buffer(here, next); P(mutex); release(here, emptypool); V(mutex); // Signal an empty buffer V(empty); consume_item(next); semaphore mutex = 1; buf_type buffer[n]; semaphore full = 0; // A general (counting) semaphore semaphore empty = N;// A general (counting) semaphore fork(producer, 0); fork(consumer, 0); Problem 1 소비자는생산자가가데이터를 update 해주기를기대함 2 생산자는모든소비자가작업을 끝낼때까지무한정대기함 empty 와 full 은동기화목적으로사용 mutex 는 empty / full Mutual Exclusion 을위해사용 43

44 Semaphore Code for Bounded Buffer in Trouble Using Semaphore (Cont d) 실수에의한중첩 Lock 의사용 에서 mutex lock 을소유한상태에서 full lock 을요구하고있음 Deadlock producer() { buf_type *next, *here; while(true) { produce_item(next); // Claim an empty P(empty); P(mutex); here = obtain(empty); V(mutex); copy_buffer(next, here); P(mutex); release(here, fullpool); V(mutex); // Signal a full buffer V(full); Deadlock consumer() { buf_type *next, *here; while(true) { // Claim full buffer P(mutex); P(full); here = obtain(full); V(mutex); copy_buffer(here, next); P(mutex); release(here, emptypool); V(mutex); // Signal an empty buffer V(empty); consume_item(next); semaphore mutex = 1; buf_type buffer[n]; semaphore full = 0; // A general (counting) semaphore semaphore empty = N;// A general (counting) semaphore fork(producer, 0); fork(consumer, 0); 44

45 Implementing Semaphores I/O 시스템에대한영향을최소화 프로세스들은자신이임계영역에있을때만블록됨 인터럽트가금지되어있으면, 인터럽트금지시간의한계를정할것 45

46 Implementing Semaphores: enter() & exit() class semaphore { int value; public: semaphore(int v = 1) { value = v;; P(){ disableinterrupts(); while(value == 0) { enableinterrupts(); disableinterrupts(); value--; enableinterrupts(); ; V(){ disableinterrupts(); value++; enableinterrupts(); ; ; 46

47 Using the TS Instruction boolean s = FALSE;... while(ts(s)) ; <critical section> s = FALSE;... semaphore s = 1;... P(s) ; <critical section> V(s);... Counting Semaphore 가안됨 47

48 Implementing the General Semaphore struct semaphore { int value = <initial value>; boolean mutex = FALSE; boolean hold = TRUE; ; shared struct semaphore s; P(struct semaphore s) { while(ts(s.mutex)) ; s.value--; if(s.value < 0) ( s.mutex = FALSE; while(ts(s.hold)) ; else s.mutex = FALSE; V(struct semaphore s) { while(ts(s.mutex)) ; s.value++; if(s.value <= 0) ( while(!s.hold) ; s.hold = FALSE; s.mutex = FALSE; 48

49 Busy-Waiting Condition While(TS(s.hold)); while(ts(s.hold)) yield( *, scheduler ); yield() : 자신의프로세스사용시간을양보 - busy waiting 하지않고다른프로세스가수행됨 49

50 Active vs Passive Semaphores A process can dominate the semaphore Performs V operation, but continues to execute Performs another P operation before releasing the CPU Called a passive implementation of V Active implementation calls scheduler as part of the V operation. Active Semaphore V 후 wait 한프로세스에게권한양보 Passive Semaphore V 후자신이계속수행 50

51 Problem of Semaphore 상호배제 (mutual exclusion) 와프로세스동기화에유용한도구. 상호배제 : set 1 동기화 : set 0 P(S) 와 V(S) 가여러프로세스사이에분산될수있어전체적인동작의이해가어려움. 모든프로세스들이 Semaphore 의정상적사용필요. 하나의프로세스에서 Semaphore 사용에오류가발생하면전체프로세스가실패할수있음. 51