5 장병행성 : 상호배제와동기화 5 장의강의목표 병행성 (concurrency) 의원리와주요용어를이해한다. 경쟁상태 (race condition) 의문제점에대해이해한다. 상호배제 (mutual exclusion), 교착상태 (deadlock), 기아상태 (starvation) 의 3 가지제어문제를이해한다. 상호배제를보장하기위한하드웨어적접근방법을이해한다. 세마포어를이용한상호배제기법을이해한다. 모니터를이용한상호배제기법을이해한다. 메시지전달을이용한상호배제기법을이해한다. 전형적인상호배제의예인생산자 / 소비자문제와판독자 / 기록자문제를이해하고해결방법을이해한다. 병행성 : 상호배제와동기화 2
목차 5.1 병행성원리 (Principles of Concurrency) 5.2 상호배제 (Mutual Exclusion): 하드웨어지원 5.3 세마포어 (Semaphore) 5.4 모니터 (Monitor) 5.5 메시지전달 (Message Passing) 5.6 판독자 / 기록자 (Readers/Writers) 문제 병행성 : 상호배제와동기화 3 다중프로세스 5.1 병행성원리 프로세스 / 쓰레드관리를위한현대운영체제의설계핵심주제 Multiprogramming Multiprocessing Distributed Processing Interleaving vs. Overlapping Big Issue is Concurrency Managing the interaction of all of these processes 병행성 : 상호배제와동기화 4
병행처리의문제점 5.1 병행성원리 전역자원의공유가어렵다. 운영체제가자원을최적으로할당하기어렵다. 프로그래밍오류를찾아내는것이어렵다. 인터리빙이나오버래핑으로인해발생하는문제점은단일처리기시스템과다중처리기시스템모두에서발생 다중처리기시스템에서는병렬처리로인한추가적문제발생 병행성 : 상호배제와동기화 5 5.1 병행성의원리 병행성 (concurrency) 의간단한예 두개이상의스레드 ( 또는프로세스 ) 들이동일한전역데이터접근 #include <pthread.h> #include <stdio.h> #include <unistd.h> #include <stdlib.h> int a[4] = {150,100,200,50; void *func1() { int tmp; // pre processing tmp = a[1]; tmp = tmp + 10; a[1] = tmp; // post processing void *func2() { int tmp; // pre processing tmp = a[1]; tmp = tmp + 20; a[1] = tmp; // post processing int main() { pthread_t p_thread1, p_thread2; // 스레드를생성하여 func1() 을수행 if ((pthread_create(&p_thread1, NULL, func1, (void*)null)) < 0) { exit(1); // 스레드를생성하여 func2() 을수행 if ((pthread_create(&p_thread2, NULL, func2, (void*)null)) < 0) { exit(1); pthread_join(p_thread1, (void **)NULL); pthread_join(p_thread2, (void **)NULL); printf("a[1] = %d\n", a[1]); 병행성 : 상호배제와동기화 6
5.1 병행성의원리 경쟁상태 (race condition) 병행성의예 앞의예제수행결과 Why?? 병행성 : 상호배제와동기화 7 5.1 병행성의원리 병행성과관련된주요용어 경쟁상태이해를돕는에니메이션 그외 : 공유자원 (Shared Resource), 동기화 (Synchronization) 병행성 : 상호배제와동기화 8
5.1 병행성의원리 병행성의다른예들 공유함수 (shared functions) // shared functions void echo() { chin = getchar(); chout = chin; putchar(chout); Process P1 Process P2.. chin = getchar();.. chin = getchar(); chout = chin; chout = chin; putchar(chout);.. putchar(chout);.. 연관된공유데이터집합 // coordinated data set Process P1 a = a + 1; b = b + 1; Process P2 b = b * 2; a = a * 2; // Real Execution a = a + 1; b = b * 2; b = b + 1; a = a * 2; 병행성 : 상호배제와동기화 9 5.1 병행성의원리 프로세스간상호작용 경쟁, 공유, 통신 병행성 : 상호배제와동기화 10
5.1 병행성의원리 상호배제 (mutual exclusion) 요구조건 어느한순간에는오직하나의프로세스만이임계영역 (critical section) 에진입할수있다. 임계영역이아닌곳에서수행이멈춘프로세스는다른프로세스의수행을간섭해서는안된다. 임계영역에접근하고자하는프로세스의수행이무한히미뤄져서는안된다. 즉, 교착상태 (deadlock) 및기아 (starvation) 가일어나지않아야한다. 임계영역이비어있을때, 임계영역에진입하려고하는프로세스가지연되어서는안된다. CPU 의개수나상대적인프로세스수행속도에대한가정은없어야한다. 프로세스는유한시간동안만임계영역에존재할수있다. 병행성 : 상호배제와동기화 11 5.1 병행성의원리상호배제요구조건 상호배제해결방법 어느한순간에는오직하나의프로세스만이임계영역에진입 병행성 : 상호배제와동기화 12
5.1 병행성의원리상호배제요구조건 entercritical(), exitcritical() 구현방법 소프트웨어적접근방법 수행부하가높고, 논리적오류의위험성이크다. 하드웨어지원 인터럽트금지 ( 오버헤드가크다.) 특별한기계명령어지원이바람직 : Test and Set, Exchange 세마포어 (semaphore: 철도의까치발신호기, 시그널 ) 모니터 (monitor) 메시지전달 병행성 : 상호배제와동기화 13 인터럽트금지 5.2 상호배제 : 하드웨어지원 // 인터럽트금지 while (true) { /* disable interrupt */ /* critical section */ /* enable interrupt */ /* remainder */ Multiprocessor 시스템에서는효과없음 특별한기계명령어 // 특별한기계명령어 : compare&swap int compare_and_swap (int *word, int testval, int newval) { int oldval; oldval = *word; if (oldval == testval) *word = newval; return oldval; // 특별한기계명령어 : exchange void exchange (int register, int memory) { int temp; temp = memory; memory = register; register = temp; // XCHG in IA, SWAP in ARM architecture 원자적연산 (atomic operation) 병행성 : 상호배제와동기화 14
5.2 상호배제 : 하드웨어지원특별한기계명령어 특별한기계명령어사용예 Compare&Swap 사용버전 Exchange 사용버전 병행성 : 상호배제와동기화 15 5.2 상호배제 : 하드웨어지원특별한기계명령어 기계명령어접근방법의특성 특별한기계명령어장점 임의개수의프로세스에적용가능 단일프로세서와공유메모리기반다중프로세서에모두적용가능 간단하고검증하기쉬움 서로다른변수를사용하면다중임계영역지원 특별한기계명령어단점 바쁜대기 (Busy-waiting) 기아상태발생가능 교착상태발생가능 예를들어우선순위가낮은프로세스가임계영역에진입한상태이고, 우선순위가높은프로세스가그임계영역에진입하기위해바쁜대기를하고있다면교착상태발생 병행성 : 상호배제와동기화 16
세마포어 (semaphore) 정의 5.3 세마포어 상호배제를운영체제와프로그래밍언어수준에서지원하는메커니즘 블록 ( 수면 ) 과깨움을지원 세마포어는정수값을갖는변수로다음 3 가지인터페이스를통해접근할수있다 초기화연산 (Initialize operation): 세마포어값을음이아닌값으로초기화한다. 대기연산 (Wait operation): 세마포어값을감소시킨다. 값이음수이면호출한프로세스는블록된다. 음수가아니면프로세스는계속수행될수있다. 시그널연산 (Signal operation): 세마포어값을증가시킨다. 값이양수가아니면블록된프로세스를깨운다. 병행성 : 상호배제와동기화 17 5.3 세마포어 카운팅 ( 범용 ) 세마포어 여러개의공유자원에대한액세스를제어할목적 Proberen( 시도하다 ), Verhogen( 증가시키다 ) 연산 병행성 : 상호배제와동기화 18
5.3 세마포어 이진 ( 바이너리 ) 세마포어 이진세마포어 :mutex 의역할 병행성 : 상호배제와동기화 19 5.3 세마포어 상호배제 세마포어를이용한상호배제 병행성 : 상호배제와동기화 20
5.3 세마포어상호배제 세마포어를이용한상호배제동작예 1 가정 : 3 개의프로세스존재 세마포어를이용한상호배제동작애니메이션 세마포어변수의값과블록된프로세스개수와의관계는? 병행성 : 상호배제와동기화 21 5.3 세마포어상호배제 세마포어를이용한상호배제동작예 2 가정 : 프로세스 A,B,C 는프로세스 D 가생산한데이터를소비 strong semaphore, weak semaphore 병행성 : 상호배제와동기화 22
5.3 세마포어 세마포어구현 원자성 (atomicity) 병행성 : 상호배제와동기화 23 5.3 세마포어 생산자 / 소비자문제 생산자 / 소비자 (producer/consumer) 문제정의 1 병행수행되는생산자와소비자 무한공유버퍼 // 생산자의사코드 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 */ 병행성 : 상호배제와동기화 24
5.3 세마포어생산자 / 소비자문제 이진세머포어를이용한방법 ( 무한버퍼 ) 부정확한버전 병행성 : 상호배제와동기화 25 5.3 세마포어생산자 / 소비자문제 이진세머포어를이용한방법 ( 무한버퍼 )( 계속 ) 부정확한버전동작과정 병행성 : 상호배제와동기화 26
5.3 세마포어생산자 / 소비자문제 이진세머포어를이용한방법 ( 무한버퍼 ) ( 계속 ) 정확한버전 병행성 : 상호배제와동기화 27 5.3 세마포어생산자 / 소비자문제 범용세마포어를이용한해결방법 ( 무한버퍼 ) 병행성 : 상호배제와동기화 28
5.3 세마포어생산자 / 소비자문제 문제정의 2 생산자 / 소비자문제 ( 유한버퍼 ) 병행수행되는생산자와소비자 유한공유버퍼 동작과정에니메이션 // 생산자의사코드 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 */ 병행성 : 상호배제와동기화 29 5.3 세마포어생산자 / 소비자문제 범용세마포어를이용한해결방법 ( 유한버퍼 ) 병행성 : 상호배제와동기화 30
모니터 (Monitor) 의정의 5.4 모니터 상호배제를위한소프트웨어모듈 ( 프로그래밍언어수준에서제공 ) 세마포어처럼상호배제기능제공 ( 사용이훨씬쉽다 ) Concurrent-Pascal, Pascal-Plus, Module-2/3, Java 등에서지원 시그널기반모니터의특징 지역변수는모니터내부에서만접근가능 프로세스는모니터프로시저중하나를호출함으로써모니터내부로진입 한시점에단하나의프로세스만모니터내부에서수행가능 병행성 : 상호배제와동기화 31 5.4 모니터 시그널기반모니터 구조 동기화 : 조건변수 (Condition variables) cwait (c): 호출한프로세스를조건 c에서일시중지시킨다. csignal (c): cwait에의해서중지되었던프로세스를재개시킨다. 병행성 : 상호배제와동기화 32
5.4 모니터시그널기반모니터 모니터를이용한생산자 / 소비자문제해결방법 프리미티브구현예 병행성 : 상호배제와동기화 33 5.4 모니터시그널기반모니터 모니터를이용한생산자 / 소비자문제해결방법 ( 계속 ) append()/take() 사용예 병행성 : 상호배제와동기화 34
5.4 모니터시그널기반모니터 변경사항 csignal() cnotify() if while Mesa 모니터 병행성 : 상호배제와동기화 35 5.5 메시지전달 메시지전달 (message passing) 인터페이스 send (destination, message) receive (source, message) mailbox (port) 기본적으로정보교환을위해사용 blocking operation 또한상호배제와동기화를위해사용가능 병행성 : 상호배제와동기화 36
5.5 메시지전달 관련용어 Blocking, non-blocking Addressing Direct, Indirect Message format Queuing discipline FIFO 병행성 : 상호배제와동기화 37 5.5 메시지전달 상호배제 메시지전달을이용한생산자 / 소비자문제해결방법 동작과정에니메이션 병행성 : 상호배제와동기화 38
5.6 판독자 / 기록자문제 5.6 판독자 / 기록자문제 판독자 / 기록자 (readers/writers) 문제정의 병행수행되는판독자와기록자 공유자원 ( 파일, 데이터베이스 ) 요구조건 여러판독자들이공유데이터를동시에읽을수있다. 한시점에오직하나의기록자만공유데이터를변경할수있다. 기록자가데이터를변경하고있는동안판독자가그데이터를읽을수없다. 생산자 / 소비자문제와차이점은? 병행성 : 상호배제와동기화 39 5.6 판독자 / 기록자문제 세마포어를이용한해결방법 1: 판독자우선 Reader 를우대하는버전 readcount--; 병행성 : 상호배제와동기화 40
5.6 판독자 / 기록자문제 세마포어를이용한해결방법 2: 기록자우선 x: readcount 보호 rsem: writer 가먼저들어가있을때첫번째 reader 가기다리는세마포어 z: writer 가먼저들어가있을때두번째이후의 reader 가기다리는세마포어 y: writecount 보호 wsem: reader 건 writer 건먼저들어온프로세스가갖는세마포어 writecount--; 병행성 : 상호배제와동기화 41 5.6 판독자 / 기록자문제 메시지전달을이용한해결방법 병행성 : 상호배제와동기화 42
애니메이션 http://williamstallings.com/os/animation/animatio ns.html 세마포어 Demonstrates the bounded-buffer consumer/producer problem using semaphores 생산자 / 소비자 Illustrates the operation of a producer-consumer buffer 입력기 / 출력기 Illustrates the interaction of readers and writers 메시지패싱 Demonstrates the bounded-buffer consumer/producer problem using messages 병행성 : 상호배제와동기화 43 병행성원리 공유자원과경쟁상태 상호배제와임계영역 상호배제 요약 하드웨어지원 : 인터럽트금지, 특별한기계명령어 세마포어 모니터 메시지전달 병행성문제 생산자 / 소비자문제 판독자 / 기록자문제 병행성 : 상호배제와동기화 44