Microsoft PowerPoint - o6.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - o6.pptx"

가인 부
6 years ago
Views:

1 목표 6 장. 프로세스동기화 임계구역 (Critical Region) 문제소개 이문제에대한해결책은공유데이터의일관성유지에사용가능 임계구역문제의하드웨어및소프트웨어해결책제시 전통적인프로세스동기화문제소개 프로세스동기화문제해결에사용되는도구조사 배경 생산자 - 소비자문제 공유데이터사용 협력프로세스 (Cooperating process) 다른프로세스의실행을영향을주거나받는프로세스 서로비동기적으로수행하면서데이터를공유할수있음 공유방법 :(1) 직접공유 - 논리주소공간 ( 메모리 ) 공유 (2) 간접공유 파일또는메시지를경유 공유데이터에대한병행 / 병렬접근은데이터일관성을보장하지못할수있음 (data inconsistency) 병행 / 병렬실행환경 CPU 스케줄링 : 한프로세스가일부만실행한상태에서다른프로세스로스케줄될수있음 인터럽트 : 프로그램의어떠한지점에서도인터럽트가가능 병렬실행 : 여러개의프로세스가동시에실행됨 데이터일관성유지 협력프로세스들이바른순서로실행 (orderly execution) 하는것을보장하는메커니즘이필요 3 유한버퍼를사용한생산자 - 소비자문제 Producer while (TRUE) { while (count == BUFFER_SIZE) ; // do nothing during full // add an item to the buffer count = count + 1; buffer[in] = item; in = (in + 1) % BUFFER_SIZE; buffer out in shared variable : count Consumer while (TRUE) { while (count == 0) ; // do nothing during empty // remove an item from the buffer count = count 1; item = buffer[out]; out = (out + 1) % BUFFER_SIZE; buffer out in 4

2 경쟁조건 (race condition) 경쟁조건에서의가능한결과 경쟁조건 예 여러개의프로세스가공유자료를접근하여조작하고 그실행결과가자료접근순서에영향을받는상황 non-deterministic 결과 machine language Process A count = count + 1 r1 = count r1 = r1 + 1 count = r1 Process B count = count 1 r2 = count r2 = r2 1 count = r2 machine language 3 가지결과가가능함 sequential order (count=5) r1 = count r1 = r1+1 count = r1 > r2 = count > r2 = r2 1 > count = r2 (r1=5) (r1=6) (count=6) (r2=6) (r2=5) (count=5) correct interleaved order (count=4) r1 = count r1 = r1+1 > r2 = count > r2 = r2 1 count = r1 > count = r2 (r1=5) (r1=6) (r2=5) (r2=4) (count=6) (count=4) incorrect interleaved order (count=6) r1 = count r1 = r1+1 > r2 = count > r2 = r2 1 > count = r2 count = r1 (r1=5) (r1=6) (r2=5) (r2=4) (count=4) (count=6) incorrect 5 6 병행접근 (Concurrent Access) 병렬 (Parallel) 접근 단일프로세서시스템에서 다중프로세서시스템에서 shared data shared data 선점 (preemptive) 스케줄링을사용할때에, 경쟁조건이발생할수있음 스케줄링알고리즘에관계없이, 경쟁조건이발생할수있음 7 8

3 6.2 임계구역 (Critical-Section) 문제 임계구역문제의해결책 임계구역 (Critical section: ) 프로세스 ( 쓰레드 ) 가공유자원을변경할수있는코드부분 공유자원 공유변수, 테이블, 파일등 critical section 임계구역문제 P1 shared resource critical section 프로세스들이임계구역에서경쟁조건이발생하지않도록서로협력하기위해사용할수있는프로토콜 ( 대화규약 ) 을설계하는것 프로세스동기화 (synchronization) 와조정 (coordination) P2 프로세스의일반구조 while (true) {... remainder section entry section critical section exit section remainder section ; 3가지필요조건 1. 상호배제 (Mutual Exclusion) 2. 진행 (Progress) 3. 한정대기 (Bounded Waiting) 가정 프로세스들의상대속도를가정하지않음. 프로세스들은 0 이아닌속도로실행됨 // request permission to enter 9 10 상호배제 (Mutual Exclusion) 진행 (Progress) 프로세스가자신의 에서실행중이라면다른프로세스들은자신의 에서실행될수없음 enter exit 에서실행되는프로세스가없고, 자신의 로진입하려는프로세스가있다면 나머지구역 (remainder section) 에서실행하지않는프로세스들만이 에진입하는프로세스결정에참여하고 이선택이무한히 (indefinitely) 지연될수없음 progress P1 selection P2 req enter exit 동시에두개이상의프로세스가임계구역 () 에서실행될수없음 P1 P2 P3 req req req 밖에서수행중인프로세스는다른프로세스를 block 할수없음 11 12

4 한정대기 (Bounded Waiting) 커널에서의경쟁조건과선점 / 비선점커널 프로세스가 진입을요청한후에요청이허용될때까지다른프로세스가 진입이허용되는횟수에제한이있어야함 T1 T2 T3 T4 Tn req bounded 커널에서의경쟁조건 커널에서여러개의커널모드프로세스 ( 루틴 ) 이활성화될수있으며커널자료구조를공유할수있음 경쟁조건발생가능 커널은경쟁조건이발생하지않도록설계해야함. 임계구역을다루기위한운영체제커널의두가지방식 선점형커널 커널모드에서프로세스가선점되는것을허용 경쟁조건이발생하지않도록설계해야함 SMP 시스템에서는특히어려움 비선점형커널 커널모드에서프로세스가선점되는것을허용하지않음 경쟁조건이발생하지않도록다음상황까지프로세스를계속실행 (1) 커널모드종료 (2) 봉쇄 (block) (3) 자발적양보 (yield) 어떤프로세스도 진입을영원히기다리지않아야함 Peterson 의해결안 Peterson 알고리즘 Peterson 알고리즘 임계구역문제에대한고전적인소프트웨어기반해결방안 두프로세스에대해서만적용가능 (P 0, P 1 ) 동기화변수 프로세스들의동작을동기화하는데사용하는공유변수 Peterson 알고리즘에서의동기화변수 int turn; (initially turn=0) boolean flag[2]; (initially, flag[0]=flag[1]=false) if (turn==i) then P i can enter its critical section (Pi 차례 ) if (flag[i] == true) then P i y to enter its critical section (Pi 준비 ) if flag[0] is true and flag[1] is false P 0 s turn ( 하나만 진입요청 ) if both flag[0] and flag[1] are true P turn s turn ( 둘다 진입요청 ) 15 Process P i 의구조 ( 다른프로세스 : P j, j = 1 i ) do { flag[i]:= true; entry turn = j; while (flag[j] and turn == j) ; critical section exit flag [i] = false; remainder section while (1); 세필요조건을충족 if (flag[j]==false or turn==i) then enter 상호배제준수 둘다진입불가 (turn 에의해서하나만진입가능 ) 진행 상대장의 flag 가 false 이면바로 진입, 두 flag 모두 true 이면 turn 이 0 또는 1 의값을가지므로둘중하나는 로진입 한정대기 상대방의수행이끝나면 flag 가 false 가되므로 진입. 상대방 flag 가다시 true 가되어도, turn 을넘겨주므로 진입 16

5 임계구역을구현하는소프트웨어알고리즘 2 프로세스알고리즘 Peterson 알고리즘 Dekker 알고리즘 (Exercise 6.2) n- 프로세스알고리즘 훨씬복잡 Eisenberg and McGuire 알고리즘 (Exercise 6.3) Dekker 알고리즘의확장 Bakery 알고리즘 Lamport 알고리즘방식은실제로널리사용되지않음 매우복잡함 정확성 ( 올바르게동작함 ) 에대한증명이복잡함 6.4 동기화하드웨어 (Synchronization Hardware) lock을사용하는임계구역문제해결책 while (true) { acquire lock... critical section release lock... remainder section 임계구역을 lock으로보호하여, 경쟁조건을방지함 Lock 의구현 소프트웨어알고리즘 복잡하고비효율적 하드웨어지원 인터럽트금지 (disable) Atomic 명령어 인터럽트금지 (Interrupt Disable) 인터럽트금지 (disable) 임계구역실행동안인터럽트를방지하여선점을허용하지않음 현재수행중인코드가선점되지않고계속수행됨 단일프로세서시스템에서는임계구역문제해결가능 cli ; interrupt disable (80x86)... critical section sti ; interrupt enable 멀티프로세서시스템에서는적용불가능 한 CPU 의인터럽트를금지시켜도, 다른 CPU 는여전히임계구역에진입할수있음. 모든 CPU 의임계구역진입을방지하기위해서, 모든 CPU 의인터럽트를금지시키는것은시간이소요되므로비효율적임. 시스템클록 ( 시계 ) 에대한영향 시스템클록이인터럽트에의해서갱신되는시스템에서, 인터럽트금지는시간에영향을줄수있음 원자적명령어 (Atomic Instruction) Atomic 명령어 = Indivisible Instruction 연속되는여러개동작 (-modify-write 동작 ) 을원자적으로 ( 인터럽트되지않고 / 분리되지않고 ) 수행하는기계어명령어 Atomic 명령어의예 Test and Set (TAS) instruction: word 내용을검사 (test) 하고변경 (set) 하는동작을원자적으로수행 (ex) 80386: bit test and set test set BTS [100], 2 ; CF M[100] 2, M[100] : test and set test set TAS $5000 ; N M[5000] 7, M[5000] 7 1 Swap instruction: 두 word의내용의교환 (swap) 을원자적으로수행 (ex) 80386: exchange XCHG AX, [BX] ; AX M[BX] 19 20

6 Lock 변수사용하기 Atomic 명령어사용 Lock 변수의사용 두상태 : 0 (unlock, open, 사용중이아님 ), 1 (lock, close, 사용중 ) atomic 명령어를사용하여 lock 변수를조작함 TAS 또는 SWAP 명령어를사용한 lock 변수의조작 Test and Set (TAS) instruction Flag TAS lock 1 CPU test set memory lock r1 SWAP instruction 1 F mov r1, 1 // set 값설정 swap r1, lock CPU F 1 lock Test-and-Set 을사용한상호배제 공유데이터 lock = 0; // global shared data unlock Process P i entry section while ( TestAndSet(&lock) ) ; critical section exit section lock = 0; remainder section 필요조건충족여부 이알고리즘은상호배제및진행조건을만족시킴 한정대기조건은만족시키지못함 busy ing loop TestAndSet() 연산은 TAS 또는 Swap 명령어로구현가능함 Test&Set 를사용한한정대기를만족하는상호배제 공유자료구조 boolean ing[n]; // initialized to false(0) boolean lock; // initialized to false(0) Process Pi entry section ing[i] = TRUE; key = TRUE; while (ing[i] && key) key = TestAndSet(&lock); ing[i] = FALSE;... critical section exit section j = (i + 1) % n; while ( (j!= i) &&! ing[j] ) j = (j + 1) % n; if (j == i) lock = FALSE; else ing[j] = FALSE;... remainder section unlock 상태이면 key=0 이됨 cyclic ordering : Pi 다음프로세스부터대기여부검사 (ing[j]=true) 임계구역진입을기다리는프로세스는최대 n-1 회내에진입가능 6.5 뮤텍스락 (Mutex Locks) 임계구역문제에대한하드웨어기반해결안 응용프로그래머에게는복잡하며일반적으로직접사용할수없음 해결방법 운영체제에서응용프로그래머에게이를위한소프트웨어도구를제공 Mutex Lock Mutex Lock ( 상호배제락 ) Mutual Exclusion의줄임말 acquire(&lock) 두함수제공 acquire() lock 획득 release() lock 반환 release(&lock) 스핀락 (Spinlock) : busy-ing mutex lock 루프를반복실행하면서 lock 획득을기다림 CPU cycle 이낭비됨 단일프로세서시스템에서특히문제임 멀티프로세서시스템에서짧은시간내에 lock 획득이예상되면 spinlock 이유용함 - context switching 이없음 23 24

7 Busy-ing 이없는 Mutex Lock Busy-ing 이없는 Test and Set 을사용한상호배제 lock 을획득하지못하면프로세스는 lock 을기다리는대기상태로전환하고 CPU 를내어놓음 알고리즘 lock = 0; entry section = acquire( ) exit section = release( ) Process P i while ( TestAndSet(&lock) ) block(); critical section lock = 0; non-critical section nobusy ing 다른프로세스가 release() 를호출하여 unlock 이될때에 wakeup() 이호출되어 상태에있는 block 된프로세스를깨움 세마포 (Semaphores) 세마포 (Semaphore) Mutex Lock 보다더정교하고강력한프로세스동기화도구 세마포 S 특별한표준동기화연산을통해서만접근할수있는정수변수. 세마포값은대개사용가능한특정자원의수를나타냄 Semaphore 연산 초기화연산 semaphore S 값초기화 두개의원자적 (atomic) 연산 (by Dijkstra) P operation (Proberen = test) (S), acquire(s) V operation (Verhogen = increment) signal(s), release(s) P(S) while (S 0) ; // busy- // now S > 0 S = S - 1; V(S) S = S + 1; 사전뜻 : 수기신호 다른표기 세마포 S 값 ( 검사및 ) 변경은원자적으로실행되어야함 26 Semaphore 용도 용도 상호배제 (Mutual exclusion) 이진세마포 (binary semaphore) 유한개수의자원접근, 한정된 concurrency counting semaphore 프로세스동기화 : signaling Binary semaphore 상호배제구현 (mutex lock과유사 ) semaphore 값 : 0 or 1 (1로초기화 ) (S) signal(s) 임계구역접근제어에사용 Semaphore S = 1; // initialize Process 1 critical section Process 2 critical section S=1 : unlock S=0 : lock acquire(s) release(s) 카운팅세마포 (Counting Semaphore) acquire(s) release(s) Counting semaphore 한정된 concurrency, 유한개수자원접근 semaphore 값 : 가용자원개수를의미 ( 최대가용자원개수로초기화 ) 유한개수의자원의접근제어에사용 Semaphore S = n; // initialize Process 1 critical section Process 2 critical section 최대 n 프로세스가병행하여수행될수있음 Process N critical section 27 28

8 일반적인동기화 동기화 (synchronization) ( 예 ) 프로세스 P 1 의 A 부분실행후에프로세스 P 2 의 B 부분이실행되어야함 Code: Semaphore S = 0; // intialize Semaphore 를 0 으로초기화 Semaphore 구현 바쁜대기 (Busy ing) Semaphore spinlock 과유사하게구현 바쁜대기없는 (No Busy ing) Semaphore 프로세스의 block-wakeup 방법이용 signal(s) S=0 S=1 Process P 1 Process P (S) S=0 A P(S) until P 1 executes V(S) V(S) B S=0... semaphore 를획득할수없을때 semaphore 대기큐에자기프로세스를추가하고자신을 block 시킴 semaphore 를사용가능하게되면, semaphore 대기큐에서한프로세스를꺼내어 y queue 로이동하여, 대기중인하나의프로세스를 wakeup 시킴 코드 다음 slide No busy-ing 세마포구현 Sempahore S 다음두 item 으로자료구조가구성됨 value 세마포값 list 이세마포를대기하는프로세스리스트 ( 세마포대기큐 ) Semaphore 연산 P(S) { S.value - -; if (S.value < 0) { add this process to S.list block() V(S) { S.value++; if (S.value <= 0) { remove a process Q from S.list wakeup(q); - 세마포값을먼저감소 음수가능 - 음수의크기는세마포를대기하는프로세스들의개수임 ( 세마포검사와감소의순서가 busy-ing 방법과반대 ) - 두프로세스가같은세마포에대해 P 또는 S 연산이중첩되어실행되지않도록해야함. (atomic 실행 ) 31 교착상태 (Deadlock) 와기아 (Starvation) Semaphore 를사용한코드는교착상태와기아가발생할수있음 교착상태 (Deadlock) 둘째 P 연산들이교착상태가됨 두개이상의프로세스들이그들중한프로세스에의해서만발생될수있는사건을무한정기다리고있어서, 진행이되지않는상황 (ex) 두 binary semaphore S, Q: S=1, Q=1로초기화됨 P 0 P 1 P(Q); V(Q) P(Q); V(Q); 기아 (Starvation) 무한봉쇄 (indefinite blocking) 일부프로세스가무한정대기할수있는상황 ( 예 ) 세마포대기리스트가 LIFO 순서로되어있으면리스트앞쪽에있는프로세스는제거되지못할수있음 ( 세마포가빈번히사용되는경우 ) get S P 0 P 1 Q get 32

6.7 고전적인동기화문제 Bounded-Buffer Problem 세마포사용 유한버퍼문제 (Bounded-Buffer Problem) Producer Readers 와 Writers 문제 write exclusive write write bounded buffer exclusive /write shared data Consumer simultaneous

empty = n; Semaphore mutex = 1; Producer do {.

9 6.7 고전적인동기화문제 Bounded-Buffer Problem 세마포사용 유한버퍼문제 (Bounded-Buffer Problem) Producer Readers 와 Writers 문제 write exclusive write write bounded buffer exclusive /write shared data Consumer simultaneous 식사하는철학자문제 (Dining-Philosophers Problem) P P P several processes R R R several shared resources 두프로세스가하나의자료공유 여러프로세스가하나의자료공유 - 일부는읽기만수행 - 일부는갱신수행 여러프로세스가여러자료공유 33 int n; Semaphore full = 0; Semaphore empty = n; Semaphore mutex = 1; Producer do {. produce an item P(empty); P(mutex); ++count; buffer[in]=item; in=(in+1)%bufsize; V(mutex); V(full); // n: buffer size // empty, full: counting semaphore for synchronization // mutex: semaphore for buffer accesses Consumer do { P(full); P(mutex); --count; item = buffer[out]; out=(out+1)%bufsize; V(mutex); V(empty); consume the item 34 Readers-Writers Problem 세마포사용 Semaphore mutex = 1 Semaphore rw_mutex=1; int _count = 0 // mutex: for updating _count // rw_mutex: for updating shared database (common to er/writer) Writer P(rw_mutex); acquirewritelock writing is performed V(rw_mutex); releasewritelock Reader P(mutex); acquirereadlock _count++; if (_count==1) // first er P(rw_mutex); V(mutex); ing is performed P(mutex); releasereadlock _count --; if (_count==0) // last er V(rw_mutex); V(mutex); 일부시스템에서는 -writer lock(rwlock) 과이를위한연산을제공한다. rwlock을획득하고반환할때에용도 (er용, writer용 ) 를지정해야한다. 35 Dining-Philosophers Problem 식사하는철학자문제 philosopher chopsticks 5 명의철학자가 thinking 과 eating 을반복하며시간을보냄 양쪽젓가락을내려놓는다. 양쪽젓가락을집는다 여러프로세스들에게여러자원을할당할필요가있는병행제어 (concurrency control) 문제를단순하게나타낸예임. 철학자 프로세스 (process), 젓가락 자원 (resource) 36

10주차.key

10주차.key 10, Process synchronization (concurrently) ( ) => critical section ( ) / =>, A, B / Race condition int counter; Process A { counter++; } Process B { counter ;.. } counter++ register1 = counter register1