운영체제 (Operating Systems) (Process Synchronization)

운영체제 (Operating Systems) (Process Synchronization)
프로세스 동기화 (Process Synchronization) 문양세 강원대학교 IT대학 컴퓨터과학전공

강의 목표 공유 데이터의 일관성 보장을 위한 임계 영역(critical section) 문제를 이해한다.
프로세스 동기화 공유 데이터의 일관성 보장을 위한 임계 영역(critical section) 문제를 이해한다. 임계 영역 문제에 대한 소프트웨어 및 하드웨어 해결책을 학습한다. 원자적 트랜잭션 개념을 이해하고, 원자성을 보장하기 위한 기법들을 학습한다.

강의 목차 배경 임계 영역 문제 피터슨의 해결책 동기화 하드웨어 세마포(Semaphores) 고전적 동기화 문제들
프로세스 동기화 배경 임계 영역 문제 피터슨의 해결책 동기화 하드웨어 세마포(Semaphores) 고전적 동기화 문제들 모니터(Monitors) 요약

배경(Background) 프로세스 동기화 공유 데이터에 대한 동시 접근은 데이터 불일치(data inconsistency)를 초래할 수 있다. 데이터 일관성(data consistency) 유지를 위해서는 협력 프로세스들이 순차적으로 수행되는 것을 보장하는 메커니즘이 필요하다. 버퍼 모두를 사용하는 생산자-소비자 문제에서 해결책을 생각해 보면, 버퍼에 있는 아이템의 개수를 기록하는 counter 변수를 사용하여 해결할 수 있다. 처음에, counter는 0으로 초기화된다. 생산자가 새 아이템을 생산한 후에 생산자에 의해 값이 증가된다. 소비자가 아이템을 소비한 후에 소비자에 의해 값이 감소된다.

item buffer[BUFFER_SIZE]; int in = 0; // initial state
생산자와 소비자의 데이터 공유 프로세스 동기화 #define BUFFER_SIZE 10 typedef struct { int content; } item; item buffer[BUFFER_SIZE]; int in = 0; // initial state int out = 0; // empty int counter = 0;

생산자(Producer) while (TRUE) {
프로세스 동기화 while (TRUE) { // produce an item and put in nextProduced while (counter == BUFFER_SIZE) // is buffer full? ; // do nothing buffer [in] = nextProduced; in = (in + 1) % BUFFER_SIZE; counter++; }

소비자(Consumer) while (TRUE) { while (counter == 0) // is buffer empty?
프로세스 동기화 while (TRUE) { while (counter == 0) // is buffer empty? ; // do nothing nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; // consume the item in nextConsumed }

경쟁 조건(Race Condition) (1/6)
프로세스 동기화 생산자와 소비자 작업이 올바르게 작성되었다 하더라도, 이들 작업이 동 시에 수행되면 바르게 동작하지 않을 수 있다. 가정 counter 변수 값이 현재 5이고, 생산자와 소비자가 동시에 “counter++”와 “counter—” 명령을 수행한다고 자자. 이 두 명령의 실행 순서에 따라, counter 변수 값은 바른 값인 5가 될 수 도 있으나, 원치 않게 4나 6이 될 수 도 있다. 왜 그러할까?

프로세스 동기화 counter++ 명령어는 내부적으로 다음과 같이 구현될 수 있다. register1 = counter register1 = register counter = register1 counter-- 명령어는 내부적으로 다음과 같이 구현될 수 있다. register2 = counter register2 = register2 – 1 counter = register2 상기 실행이 “counter = 5”에서 다음과 같이 섞여 수행되었다 가정하자. S0: 생산자가 수행 register1 = counter {register1 = 5} S1: 생산자가 수행 register1 = register {register1 = 6} S2: 소비자가 수행 register2 = counter {register2 = 5} S3: 소비자가 수행 register2 = register {register2 = 4} S4: 생산자가 수행 counter = register1 {counter = 6 } S5: 소비자가 수행 counter = register2 {counter = 4} counter = 4

프로세스 동기화 “counter++”는 원자적(atomic) 연산이 아니다! S-Box E-Box 2. 피연산자 (operand) 1. 데이터 (data) 3. 실행 (execution) 4. 결과(result) 예 E-box S-box CPU 메모리 컴퓨터 디스크 실행 박스와 저장 박스의 분류

프로세스 동기화 counter++, counter--는 원자적 연산이 아니다! 생산자 E-Box 소비자 E-Box S-Box counter-- counter++ counter

프로세스 동기화 경쟁 조건의 예제 CPU1 CPU2 P1 P2 메모리 X == 2 X = X + 1; X = X – 1; Load X, R1 Inc R1 Store X, R1 Load X, R2 Dec R2 Store X, R2 두 실행이 섞이게 되면?

프로세스 동기화 경쟁 조건에 의해, 앞서 예제와 같이 불확정적인 상태에 도달할 수 있다. 이는 두 개의 프로세스가 동시에 counter 변수를 조작하는 것을 허용했기 때문이다. 경쟁 조건 여러 프로세스들이 동일한 데이터에 동시에 접근해서 조작할 수 있다. 이 경우 실행 결과 값은 접근과 갱신이 일어나는 순서에 따라 달라질 수 있다. 경쟁 조건의 예방을 위하여 한번에 오직 하나의 프로세스만이 counter 변수를 조작하는 것을 보장할 필요가 있다. 프로세스들이 어떤 방법으로든 동기화(synchronization)될 필요가 있다.

임계 영역(Critical Section) 문제
프로세스 동기화 n 개의 프로세스 {P0, P1, …, Pn-1}로 이루어진 시스템 각 프로세스는 임계 영역으로 불리는 코드 부분을 가지고 있다. 프로세스들은 임계 영역 에서 공통 변수를 변경하거나, 테이블을 수정하거나, 파일을 쓰는 등의 작업을 한다. 시스템은 어떤 두 개의 프로세스도 동시에 임계 영역에서 수행되지 않도록 해야 한다. 임계 영역 문제의 해결 방안 프로세스들이 협동하기 위해 사용할 수 있는 프로토콜을 설계한다. 각 프로세스는 CS에 들어가는 승인을 요청해야만 한다. 이 요청을 구현하는 코드 부분은 진입 영역(entry section)이다. CS에는 퇴출 영역(exit section)이 뒤따른다. 임계 영역과 관련 없는 나머지 코드가 나머지 영역(remainder section)이다.

전형적인 프로세스 Pi의 일반적 구조 do { 진입 영역(entry section) 임계 영역(critical section)
프로세스 동기화 do { 진입 영역(entry section) 임계 영역(critical section) 퇴출 영역(exit section) 나머지 영역(remainder section) } while ( TRUE );

임계 영역 문제의 해결 임계 영역 문제 해결을 위해서는 세 가지 요구사항을 충족해야 한다.
프로세스 동기화 임계 영역 문제 해결을 위해서는 세 가지 요구사항을 충족해야 한다. 1. 상호배제(mutual exclusion): 만약 한 프로세스가 임계 영역을 수행하고 있다 면, 다른 프로세스들은 누구도 그 임계 영역 부분을 수행할 수 없다. 2. 진행(progress): 임계 영역을 수행하는 프로세스가 없고, 그 영역에 들어가길 희망하는 프로세스들이 있다면, 다음에 임계 영역에 들어갈 프로세스를 선택 하는 것이 무한 지연되어서는 안 된다.  교착상태-자유(deadlock-free) 조건 3. 한정된 대기(bounded waiting): 다른 프로세스들이 임계 영역에 들어가는 것 이 허락되는 한계 시간은 일정 시간으로 유한해야 한다. (프로세스가 임계 영 역에 들어가기를 요청하고 그 요청이 허락되기 전까지 기다리는 시간)  기아-자유(starvation-free) 조건

임계 영역에 대한 피터슨(Peterson)의 해결책
프로세스 동기화 두 프로세스 {Pi, Pj}에 대한 해결 방안 소프트웨어 기반 해결책이다. LOAD, STORE 명령어는 원자적(atomic)이라 가정한다. 즉, 도중에 방해(interrupt) 받지 않는다. (소프트웨어 해결책으로, 현대 컴퓨터 구조에서 바르게 동작한다는 보장은 없다!) 두 프로세스는 두 개의 변수를 공유한다. int turn; boolean flag[2]; 변수 turn은 누가 임계 영역에 들어갈 차례인지를 나타낸다. 배열 flag는 프로세스가 임계 영역에 들어갈 준비가 되었는지를 나타내는 데 사용된다. flag[i] == true는 프로세스 Pi가 준비가 되었음을 의미한다.

피터슨 해결책의 증명 피터슨의 해결책은 임계 영역 해결책의 세 가지 조건을 충족한다!
프로세스 동기화 피터슨의 해결책은 임계 영역 해결책의 세 가지 조건을 충족한다! 상호 배제(mutual exclusion) 각 Pi는 flag[j]==false거나 turn==i인 두 조건 중 하나가 만족되어야만 임계 영역에 들어간다. 각 Pi는 flag[i]==true인 상태에서만 임계 영역에 들어간다. Pi 와 Pj는 동시에 임계 영역에 들어갈 수 없다. 진행(progress) Pi는 flag[j]==true이고 turn==j인 경우에만 멈춰진다. 한정된 대기(bounded waiting) Pi는 기껏해야 Pj의 한 번의 출입 후에 임계 영역에 들어가게 된다.

피터슨의 해결책에서 프로세스 Pi 구조 do { flag[i] = TRUE; turn = j;
프로세스 동기화 do { flag[i] = TRUE; turn = j; while ( flag[j] && turn == j); CRITICAL SECTION flag[i] = FALSE; REMAINDER SECTION } while (TRUE); // 진입 영역 (entry section) // 퇴출 영역 (exit section)

동기화 하드웨어(Synchronization Hardware)
프로세스 동기화 많은 시스템들은 임계 영역 구현을 위한 하드웨어 기능을 지원한다. 단일 프로세서(uni-processor): 인터럽트 불가능(disable interrupts)하게 하여 구현할 수 있다. 현재 수행되고 있는 코드는 중단 없이 수행될 수 있다. 일반적으로 다중프로세서 시스템에서는 너무 비효율적이며, 운영체제가 확장성 (scalable)을 지원하지 못한다. 현대 컴퓨터들은 특별한 원자적(atomic) 하드웨어 명령어를 제공한다. 원자적의 의미는 인터럽트 발생이 가능하지 않음(non-interruptible)을 의미한다. 메모리 워드 테스트와 값 설정 = TestAndSet() 두 메모리 워드 내용 교환 = Swap()

TestAndSet() 명령어 boolean TestAndSet (boolean *target) {
프로세스 동기화 boolean TestAndSet (boolean *target) { boolean rv = *target; *target = TRUE; return rv: } TestAndSet()은 원자적으로 수행되며, 하드웨어에 의해 제공된다. 기능을 보면, *target 값이 FALSE이면 이를 TRUE로 세팅하고 FALSE를 리턴한다. *target 값이 TRUE이면 이를 TRUE로 세팅하고 TRUE를 리턴한다.

TestAndSet()을 사용한 임계 영역 해결책
프로세스 동기화 공유 boolean 변수 lock은 FALSE로 초기화된다. do { while ( TestAndSet (&lock ) ) ; // do nothing CRITICAL SECTION lock = FALSE; REMAINDER SECTION } while ( TRUE); 바쁜 대기 (busy waiting) lock이 FALSE라면(사용 가능), TRUE로 설정하고 임계 영역에 들어간다. lock이 TRUE라면(이미 점유 중), TRUE로 설정하고 바쁜 대기로 기다린다.

void Swap (boolean *a, boolean *b) { boolean temp = *a; *a = *b;
프로세스 동기화 void Swap (boolean *a, boolean *b) { boolean temp = *a; *a = *b; *b = temp: } Swap()은 원자적으로 수행되며, 하드웨어에 의해 제공된다. 기능은 두 변수의 값을 교환한다. 실제 임계 영역 구현에서, *a는 공통(전역) 변수이고, *b는 지역 변수가 된다.

Swap()을 사용한 임계 영역 해결책 공유 boolean 변수 lock은 FALSE로 초기화된다.
프로세스 동기화 공유 boolean 변수 lock은 FALSE로 초기화된다. 각 프로세스는 지역 boolean 변수인 key를 갖는다. do { key = TRUE; while (key == TRUE) Swap (&lock, &key); CRITICAL SECTION lock = FALSE; REMAINDER SECTION } while ( TRUE); 바쁜 대기 (busy waiting) lock이 FALSE라면(사용 가능), key에 의해 TRUE가 되고 임계 영역에 들어간다. lock이 TRUE라면(이미 점유 중), key=TRUE라서 바쁜 대기로 기다린다.

한정된 대기 조건의 해결 (1/2) 앞서의 임계 영역 해결책은 한정된 대기 문제를 해결하지 못한다.
프로세스 동기화 앞서의 임계 영역 해결책은 한정된 대기 문제를 해결하지 못한다. 즉, 어떤 프로세스가 무한정 기다리는 상황이 발생할 수 있다. 한번 서비스 받았으면, 다른 프로세스가 서비스될 수 있도록 보완이 필요하다. 한정된 대기 조건을 고려한 TestAndSet() 해결책 공유 boolean 변수 waiting[n]과 lock은 FALSE로 초기화한다. 각 프로세스는 지역 boolean 변수인 key를 갖는다.

한정된 대기 조건의 해결 (2/2) 프로세스 동기화 do { waiting[i] = TRUE; key = TRUE; while ( waiting [i] && key ) key = TestAndSet(&lock); waiting[i] = FALSE; CRITICAL SECTION j = (i+1)%n; while( (j != i) && !waiting[j] ) j=(j+1)%n; if(j == i) lock = FALSE; else waiting [j] = FALSE; REMAINDER SECTION } while (TRUE); busy waiting 임계 영역에 들어갈 수 있는 조건은 waiting[i]==FALSE 이던지 key==FALSE여야 한다. (처음에 TestAndSet()을 수행하면 key==FALSE가 되어 진입한다.) 임계 영역에서 나올 때는 다음 프로세스(i+1)에 순서를 넘기는 작업이 진행된다. 다음 프로세스가 waiting하지 않으면 그 다음 프로세스로 설정한다. (while 루프) 다시 자기(==i)이면, lock=FALSE로 하여 자신이, 다른 프로세스(==j)이면 waiting[j]=FALSE로 하여 해당 프로세스가 다음 번에 임계 영역에 진입한다.

세마포(Semaphore)? 프로세스 동기화 세마포 알파벳

세마포(Semaphore) (1/2) 임계 영역 문제 해결을 위한 하드웨어 기반 접근법
프로세스 동기화 임계 영역 문제 해결을 위한 하드웨어 기반 접근법 TestAndSet(), Swap() 그러나…., 응용 프로그래머가 사용하기에는 복잡하다. 이 어려움을 극복하기 위해, 세마포가 사용될 수 있다. 세마포는 … 바쁜 대기가 필요하지 않는 동기화 툴이다. 세마포 S – 정수 변수 S를 수정하기 위한 두 개의 표준 연산: wait() and signal()  근본적으로 P()는 wait()를 위해 V()는 signal()을 위해 호출된다. 세마포의 수정은 원자적(atomic)으로 취급된다. 사용하기가 비교적 용이하다.

세마포(Semaphore) (2/2) wait(S);를 위한 정의 signal(S);를 위한 정의
프로세스 동기화 wait(S);를 위한 정의 signal(S);를 위한 정의 세마포에 대한 모든 수정은 원자적(atomic)이다. 한 프로세스가 세마포 값을 수정하려고 할 때, 다른 어떤 프로세스도 동 시에 같은 세마포 값을 수정할 수 없다. wait(S) { while ( S <= 0 ) ; // no-op S--; } busy waiting(바쁜 대기) signal(S) { S++; }

세마포의 사용 (1/3) 카운팅 세마포(counting semaphore) 이진 세마포(binary semaphore)
프로세스 동기화 카운팅 세마포(counting semaphore) 주어진 영역의 값을 가질 수 있다. 예제: 이진 세마포(binary semaphore) 정수 값은 단지 0과 1 값만을 가질 수 있다. 이를 특별히 mutex lock이라 부른다. 1. 임계 영역 문제를 해결하기 위한 이진 세마포 n개의 프로세스들이 세마포(mutex)를 공유한다 mutex 는 1로 초기화된다. 프로세스 Pi 의 구조는 오른쪽과 같다. do { wait (mutex); CRITICAL SECTION signal (mutex); REMAINDER SECTION } while (TRUE);

세마포의 사용 (2/3) 2. 카운팅 세마포는 유한 개수 자원의 접근을 제어하는데 사용할 수 있다.
프로세스 동기화 2. 카운팅 세마포는 유한 개수 자원의 접근을 제어하는데 사용할 수 있다. 세마포는 사용 가능한 자원의 개수로 초기화된다. 자원을 사용하기 위해, 프로세스는 wait()을 수행한다. 자원을 반환하기 위해 프로세스는 signal()을 수행한다 세마포 값이 0일 때는 모든 자원이 사용되고 있음을 의미한다. 3. 이진/카운팅 세마포로 다양한 동기화 문제를 해결할 수 있다. 예: 동시에 수행되는 두 개의 프로세스 P1, P2 명령문 S1을 수행하는 P1, 명령어 S2를 수행하는 P2 S2는 S1이 완료된 후에 수행되어야 한다. 세마포를 사용하여 이것을 어떻게 해결할 수 있을까?

세마포의 사용 (3/3) 문제 3(P1/P2가 S1/S2를 수행하는 문제)의 해결 초기화 P1 구조
프로세스 동기화 문제 3(P1/P2가 S1/S2를 수행하는 문제)의 해결 초기화 P1 구조 P2 구조 Semaphore synch = 0; S1; signal(synch); wait(synch); S2;

바쁜 대기(Busy Waiting) 기반 세마포 구현
프로세스 동기화 어떤 두 프로세스도 같은 세마포에 대해 wait()와 signal()을 동시에 수행하지 않도록 보장해야 한다. 따라서, 구현은 wait()와 signal()이 임계 영역에 위치하는 임계 영역 구현의 문제가 된다. 지금까지의 임계 영역 구현에서는 바쁜 대기(busy waiting)이 사용된다. 한 프로세스가 임계 영역에 있는 동안, 다른 프로세스들은 끊임없이 wait()를 반복한다. 이를 spinlock이라고도 부른다. 단점: wait()을 수행하는 동안 CPU 사이클을 낭비한다. 때때로 유익하기도 하다. wait(), signal()을 위한 문맥 전환이 필요하지 않다. 구현 코드가 짧다. 임계 영역이 드물게 나타난다면 바쁜 대기가 거의 발생하지 않는다. BUT, 응용들이 임계 영역에서 많은 시간을 소비할 수 있으므로, 바쁜 대 기의 사용은 좋은 해결 방안은 아니다!

바쁜 대기를 사용치 않는 세마포 구현 (1/3) 바쁜 대기 문제를 해결하기 위해, 두 연산이 추가적으로 사용된다.
프로세스 동기화 바쁜 대기 문제를 해결하기 위해, 두 연산이 추가적으로 사용된다. block(): 연산을 호출한 프로세스가 봉쇄되고, 적절한 대기 큐에 추가시킨다. wakeup(): 대기 큐에 있는 여러 프로세스 중 하나를 준비완료 큐로 이동시킨다. wait()는 block()을 사용하여 바쁜 대기 대신 스스로를 봉쇄한다. signal()은 wakeup()을 사용하여 대기 중인 프로세스를 깨운다. 위 개념 하에 세마포 구현을 위해 다음 구조체를 정의한다. 각 세마포에는 연관된 대기 큐가 있다. typedef struct { int value; // 세마포 값 struct process *list; // 대기 중인 PCB 리스트를 가리키는 포인터 }

바쁜 대기를 사용치 않는 세마포 구현 (2/3) wait() 구현 signal() 구현 wait(semaphore *S) {
프로세스 동기화 wait() 구현 signal() 구현 wait(semaphore *S) { S->value--; if (S->value < 0) { add this process to S->list; // PCB를 대기 큐에 놓는다. block(); // 실행 상태에서 대기 상태로 이동 } signal (semaphore *S) { S->value++; if (S->value <= 0) { remove a process P from S->list; // 큐에서 한 프로세스 선택 wakeup(); // 프로세스를 준비완료 큐로 이동 }

바쁜 대기를 사용치 않는 세마포 구현 (3/3) 세마포의 대기 큐를 어떻게 구현할 것인가?
프로세스 동기화 세마포의 대기 큐를 어떻게 구현할 것인가? 세마포 구조체에 연결된 연결 리스트로 구현한다. 대기 중인 프로세스들의 PCB를 연결한다. 음수 값은 대기 중인 프로세스의 개수를 의미한다. 양수 값은 이용 가능한 자원의 개수를 의미한다. 한정된 대기(bounded waiting) 조건을 만족시키기 위해서 대기 큐로 FIFO 큐를 사용하여 구현할 수 있다. PCB 리스트의 처음과 끝을 가리키는 두 개의 포인터 변수를 관리한다. BUT, 대기 큐(리스트)는 어떤 큐잉 전략이든 목적에 따라 사용할 수 있다. value:-3 list PCB

교착상태(Deadlock) 프로세스 동기화 교착상태(deadlock): 둘 이상의 프로세스가 어떤 사건을 무한정 기다리 고 있고, 이 사건은 기다리는 프로세스 중 하나만이 발생시킬 수 있는 상 황을 일컫는다. 교착상태 사례: S와 Q 두 개의 세마포를 1로 초기화 한다. P0는 wait(S)를 실행하고, P1은 wait(Q)를 실행한다. P0는 wait(Q) 실행을 위해 P1의 signal(Q)를 기다린다. P1은 wait(S) 실행을 위해 P0의 signal(S)를 기다린다.  제7장에서 교착상태를 다루는 다양한 기법을 학습한다.. P0 wait(S); wait(Q); ... signal(S); signal(Q); P1 wait(Q); wait(S); ... signal(Q); signal(S);

기아(Starvation) 기아(starvation)
프로세스 동기화 기아(starvation) 무한 봉쇄(indefinite blocking)이라고도 불린다. 프로세스가 세마포에서 무기한 대기하는 것을 의미하며, 특정 프로세스가 세 마포 큐로부터 결코 제거되지 못하는 경우이다. 대기 큐를 가진 세마포 구현 방법은 기아를 유발할 수도 있다.  특히, 큐가 LIFO(last-in, first-out) 순서일 경우에 그럴 수 있다.

고전적 동기화 문제들 유한 버퍼 문제(Bounded-Buffer Problem)
프로세스 동기화 유한 버퍼 문제(Bounded-Buffer Problem) Readers-Writers 문제(Readers-Writers Problem) 식사하는 철학자 문제(Dining Philosophers Problem)

유한 버퍼 문제(1/3) 프로세스 동기화 둘 이상의 생산자(producers): 한 개의 아이템을 생산하고, 이를 버퍼에 저장하고, 일을 계속한다. 둘 이상의 소비자(consumers): 버퍼에서 한 개의 아이템을 소비하고, 일을 계속한다. 버퍼는 최대 N개의 아이템을 저장할 수 있을 때, 이 유한 버퍼를 동기화 하여 사용하는 문제를 일컫는다. 세마포를 사용한 해결책 세마포 mutex 1로 초기화된다. (이진 세마포) 세마포 full 0으로 초기화된다. (카운팅 세마포) 세마포 empty N으로 초기화된다. (카운팅 세마포) mutex는 버퍼에 접근하기 위한 상호 배제 기능을 제공하고, full은 버퍼에 있는 아이템의 개수를 나타내며, empty는 버퍼에 넣을 수 있는 아이템의 개수를 각각 나타낸다.

유한 버퍼 문제(2/3) 생산자 프로세스 구조 do { // 한 개의 아이템을 생산한다.
프로세스 동기화 생산자 프로세스 구조 do { // 한 개의 아이템을 생산한다. wait(empty); // 버퍼가 가득 찼는지 아닌지 점검한다. wait(mutex); // 임계 구역에 들어간다. // 아이템을 버퍼에 추가한다 // 임계 영역 signal(mutex); // 임계구역을 떠난다. signal(full); // 한 개의 아이템이 생산된다. } while (TRUE);

유한 버퍼 문제(3/3) 소비자 프로세스 구조 do { wait(full); // 버퍼가 비었는지 아닌지 점검한다.
프로세스 동기화 소비자 프로세스 구조 do { wait(full); // 버퍼가 비었는지 아닌지 점검한다. wait(mutex); // 임계 구역에 들어간다. // 버퍼로 부터 한 아이템을 제거한다. // 임계 영역 signal(mutex); // 임계 구역을 떠난다. signal(empty); // 한 개의 아이템이 소비됨을 알린다. // 한 개의 아이템을 소비한다. } while (TRUE);

Readers-Writers 문제 (1/5)
프로세스 동기화 데이터베이스는 동시에 수행되는 많은 프로세스들에 의해 공유된다. Readers: 데이터베이스를 읽기만 한다. 어떤 변경도 수행하지 않는다. Writers: 데이터베이스를 갱신할 수 있다.  데이터베이스를 읽고 쓸 수 있다. 문제 다수의 readers가 동시에 데이터베이스를 읽는 것이 허용된다. Writer가 쓰기 작업을 하는 동안에는 데이터베이스에 대한 배타적 접근 권한을 갖는다. (한 writer가 쓰기 작업을 하는 동안 다른 readers/writers는 대기해야 한다.) 교재에서는 “writer가 공유 객체의 사용 허가를 얻지 못한 상태에서 어느 reader도 기다 리지 못한다”는 원칙을 사용한다. 일반적으로, 데이터베이스 시스템에서는 이와 같은 락킹(locking) 메커니 즘을 지원한다.

프로세스 동기화 공유 데이터 데이터베이스 세마포 mutex 1로 초기화된다. 세마포 wrt 1로 초기화된다. 정수 readcount 0으로 초기화된다. 공유 데이터의 활용/의미 세마포 mutex: readcount를 갱신할 때 상호 배제를 보장하기 위해 사용된다. 세마포 wrt: (1) writer들을 위한 상호 배제에 사용된다. (2) 임계 영역에 진입하는 첫 번째 reader가 사용한다. (3) 임계 영역을 빠져나오는 마지막 reader도 사용한다. 정수 readcount: 몇 개의 reader가 객체를 읽고 있는지를 나타낸다.

프로세스 동기화 Writers 프로세스 구조 do { wait(wrt); // 임계 영역에 들어간다. // writing is performed. // 임계 영역 signal(wrt); // 임계 영역을 떠난다. } while(TRUE);

프로세스 동기화 Readers 프로세스 구조 do { wait(mutex); readcount++; if(readcount == 1) wait(wrt); // 첫 번째 독자일 경우, write 방지! signal(mutex); // reading is performed // 둘 이상 독자가 동시에 읽을 수 있다. readcount--; if(readcount == 0) signal(wrt); // 마지막 독자일 경우, write 허가! } while(TRUE);

프로세스 동기화 기아(starvation)가 발생할 수 있다. 앞서의 해결책에서 writers에 기아가 발생할 수 있다. (readers에 의해 무한 대기!) 자세히 말해, writers가 공유 객체에 대한 갱신 허가를 획득하지 못했다면, 객체를 읽고 자 하는 readers가 계속 발생할 수 있기 때문이다. Readers-Writers 문제의 다른 변형 일단 writer가 준비되면, 해당 writer는 가능한 빨리 수행되도록 한다. 만일 writer가 객체 접근을 기다리고 있다면, 더 이상의 새로운 reader는 읽기를 시작하 지 않는다. 이 경우 readers에 기아가 발생할 수 있다.

식사하는 철학자 (Dining Philosophers) 문제 (1/4)
프로세스 동기화 철학자들이 어떻게 생활하냐 하면, 삶을 생각하고 식사하는 데만 소비하는 다섯 명의 철학자 그들이 다섯 의자에 둘러 쌓인 테이블을 공유한다. 테이블 가운데는 밥을 담은 그릇이 놓여있다. 철학자와 철학자 사이에 한 개씩 젓가락이 놓여 있다. 철학자는 생각하는 동안, 이웃과 상호작용을 하지 않는다. 때때로, 철학자는 배가 고파지면, 자신 옆에 놓인 두 개의 젓가락을 집으려 한다. 철학자는 한 번에 한 개의 젓가락만을 집을 수 있다. 철학자는 자신 이웃의 손에 이미 들려 있는 젓가락을 집을 수는 없다. 철학자가 두 개의 젓가락을 잡으면, 젓가락을 내려 놓는 것 없이 밥을 먹는다. 밥 먹는 것을 끝내면, 두 개의 젓가락을 내려 놓고 다시 생각한다. 어떻게 교착상태와 기아를 피하며 이를 구현할 수 있을까?

프로세스 동기화 철학자를 조롱하고자 하는 것은 절대 아니며, 이는 큰 규모의 동시-제어 문제이다. 이것은 여러 프로세스 사이에서 여러 자원 (밥, 젓가락)을 교착상태-자유(deadlock-free), 기아 자유(starvation-free) 방법으로 할당할 필요가 있는 문제의 추상적 표현이다. 세마포를 이용한 간단한 해결책 밥공기 (데이터 집합) 세마포 chopstick[5]는 1로 초기화한다.

프로세스 동기화 철학자 i의 구조 do { wait( chopstick[i] ); // 왼쪽 젓가락 들기 wait( chopstick[(i+1)%5] ); // 오른쪽 젓가락 들기 ... // 식사하기 – 임계 영역 signal( chopstick[i] ); // 왼쪽 젓가락 놓기 signal( chopstick [(i+1)%5] ); // 오른쪽 젓가락 놓기 // 생각하기 – 나머지 영역 } while(TRUE);

프로세스 동기화 이 해결 방안은 다음을 보장한다. 이웃한 두 철학자가 동시에 식사를 할 수는 없다. 그러나, 이 해결 방안은 교착상태를 유발할 수 있다. 다섯 철학자 모두가 동시에 배가 고파지고, 각자 왼쪽 젓가락을 잡는다고 가정해 보자. 다섯 철학자에 의해 모든 젓가락이 다 잡혀있다. 각 철학자가 자신의 오른쪽 젓가락을 잡으려고 영원히 기다려야 한다. 교착상태를 피할 수 있는 세 가지 해결 방안 한 번에 최대 네 명의 철학자만이 함께 앉도록 허락한다. 철학자가 양쪽 젓가락이 모두 사용 가능할 경우에만 젓가락을 집는 것을 허락한다. 비대칭 해결방안을 사용한다. 즉, 홀수 번째 철학자는 왼쪽 젓가락을 먼저 집고, 짝수 번째 철학자는 오른쪽 젓가락을 먼저 잡는다.

세마포 사용의 문제 세마포를 잘못 사용하면 상호배제 위반, 교착상태 등 문제가 발생한다. 세마포 오사용의 사례
프로세스 동기화 세마포를 잘못 사용하면 상호배제 위반, 교착상태 등 문제가 발생한다. 이러한 상황은 프로그래밍 오류 또는 비협조적 프로그래밍에 의해 야기된다. 세마포 오사용의 사례 mutex는 1로 초기화되는 세마포에서의 사례이다. signal(mutex) wait(mutex)  둘 이상이 임계영역에 들어갈 수 있어, 상호배제를 위반하는 결과를 유발한다. wait(mutex) wait(mutex)  모두 기다리기만 하여 교착상태를 유발한다. wait(mutex) 혹은 signal(mutex) (또는 둘 다)의 생략  상호배제 위반이나 교착상태가 발생할 수 있다. 상기 에러 처리를 위해, 모니터(monitor)가 사용될 수 있다.

모니터(Monitor) 프로세스 동기화를 위한 편리하고 효율적인 방법론을 제공하는 높은 수 준의 추상화(abstraction)
모니터는 객체 지향 언어(C++, Java)의 클래스와 같은 추상화 데이터 타입 (abstract data type: ADT)이다. 모니터 인스턴스(instance)는 다중 프로세스들 사이에서 공유된다. 한 순간에 오직 하나의 프로세스만이 모니터 내에서 활성화될 수 있다. monitor monitor-name { shared variable declarations procedure P1(…) { ... } … procedure Pn(…) {...} initialization(…) { ... } } 개인 데이터 공개 방법 초기화 방법

모니터의 도식적 표현 모니터 구성 공유 데이터는 연산들에 의 해서만 접근될 수 있다.
프로세스 동기화 모니터 구성 공유 데이터 (공유 데이터를 다루는) 연산들 초기화 코드 공유 데이터는 연산들에 의 해서만 접근될 수 있다. 한 순간에 오직 하나의 프로 세스만이 모니터에서 활성화 된다. 프로그래머는 이 동기화를 코딩 할 필요가 없다.

조건 변수(Condition Variables)
프로세스 동기화 기본 모니터는 여러 동기화 기법(scheme) 모델링을 위해서 충분히 강력 하지 않다. 이를 해결하기 위해서, 조건 변수(condition variables)가 소개되었다. 조건(condition) x, y 프로그래머는 하나 이상의 조건 타입의 변수를 정의할 수 있다. 조건 변수에 적용되는 두 가지 연산 x.wait(): 이 연산을 호출한 프로세스는 보류하게 된다. x.signal() (보류 중인 프로세스가 있다면) x.wait()를 호출한 프로세스 중 하나가 재개된다. x.signal()은 정확히 한 개의 보류 중이던 프로세스만을 재개한다. 보류하는 프로세스가 한 개도 없다면, 아무것도 일어나지 않는다.  세마포에서 signal()은 항시 세마포 상태에 영향을 주는 것과 차이가 있다.

조건 변수를 가진 모니터 프로세스 동기화

식사하는 철학자 해결방안 (1/4) 식사하는 철학자에 대한 교착상태가 없는 해결책 제시
프로세스 동기화 식사하는 철학자에 대한 교착상태가 없는 해결책 제시 기본 전략: 철학자는 양쪽 젓가락을 모두 얻을 수 있을 때만 젓가락을 잡을 수 있다.

식사하는 철학자 해결방안 (2/4) monitor DiningPhilosophers {
프로세스 동기화 monitor DiningPhilosophers { enum {THINKING; HUNGRY, EATING) state[5]; condition self[5]; void pickup(int i) { state[i] = HUNGRY; test(i); if(state[i] != EATING) self[i].wait(); } void putdown(int i) { state[i] = THINKING; // 왼쪽과 오른쪽 이웃을 테스트한다. test((i+4) % 5); test((i+1) % 5); 철학자들의 세가지 상태 Ph_i는 배고파졌을 때, 양쪽 젓가락 두 개를 모두 잡을 수 없으면 대기한다. Ph_i는 식사 전에 pickup(i)을 호출한다. Ph_i는 식사 후에 putdown(i)을 호출한다.

식사하는 철학자 해결방안 (3/4) void test(int i) {
프로세스 동기화 void test(int i) { if( (state[(i+4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i+1) % 5] != EATING) ) state[i] = EATING; self[i].signal(); } initialization_code() { for (int i = 0; i < 5; i++) state[i] = THINKING; Ph_i는 젓가락을 집기 위해 test(i)연산을 수행한다. 또한, 젓가락을 놓기 위해 test(i+1)와test((i+1)%5)를 수행한다. 양쪽 이웃이 먹지 않을 때, 자신의 상태를 먹기(EATING)로 바꾸고 자기 자신을 호출한다 모든 철학자들의 상태는 생각하는(THINKING) 상태로 초기화된다.

식사하는 철학자 해결방안 (4/4) 철학자 i는 다음 순서로 pickup()과 putdown() 연산을 호출해야 한다. do
프로세스 동기화 철학자 i는 다음 순서로 pickup()과 putdown() 연산을 호출해야 한다. do { thinking DiningPhilosophers.pickup(i); ... eat DiningPhilosophers.putdown(i); } while(TRUE);

요약 (1/2) 프로세스 동기화 협력 프로세스들은 공유 데이터를 사용하는데, 한번에 한 프로세스에 의해서만 사용되어야 하는 임계 영역(critical section)의 코드를 가진다. 임계 영역 문제의 해결 방안 소프트웨어 기반의 해결방안: 피터슨의 알고리즘, (Bakery 알고리즘) 하드웨어 기반의 해결방안: TestAndSet(), Swap() 임계 영역 문제를 위한 세 가지 요구사항 상호배제(mutual exclusion) 진행(progress) 한정된 대기(bounded waiting) 이 해결방안들의 단점은 모두 바쁜 대기(busy waiting)를 한다는 것이다.  세마포(semaphore)는 이 문제점을 해결한다

요약 (2/2) 세마포는 다양한 동기화 문제를 해결하기 위해 사용된다.
프로세스 동기화 세마포는 다양한 동기화 문제를 해결하기 위해 사용된다. 유한 버퍼(bounded-buffer) 문제 Readers-Writers 문제 식사하는 철학자(dining-philosophers) 문제  이들은 모두 대규모의 동시성 제어 문제의 예제에 해당한다. 모니터는 공유 추상 데이터 타입(abstract data type)을 위한 동기화 메 커니즘을 제공한다.

운영체제 (Operating Systems) (Process Synchronization)

Similar presentations

Presentation on theme: "운영체제 (Operating Systems) (Process Synchronization)"— Presentation transcript:

Similar presentations

About project

지원

로그인

Auth with social network:

운영체제 (Operating Systems) (Process Synchronization)

Similar presentations

Presentation on theme: "운영체제 (Operating Systems) (Process Synchronization)"— Presentation transcript:

Similar presentations

About project

지원