#7 동기화(Synchronization) 4 - OS Supported Solution

CS/운영체제

#7 동기화(Synchronization) 4 - OS Supported Solution

Scala0114 2021. 12. 27. 17:04

1. Spinlock

// s는 임계영역에 진입하기 위한 권한의 갯수

// P 연산
// s가 1이상이 될 때까지 대기하여 권한을 획득
void P(*s) {
    while(*s <= 0);
    *s -= 1;
}
    

// V 연산
// 획득한 권한을 반납
void V(*s) {
    *s -= 1;
}

초기화, P, V 의 세 가지 연산을 지원
위 세 가지 연산은 원자적으로 수행됨을 보장한다.(수행중에 interrupt 당하지 않는다.)
임계영역 진입전에 P연산을, 작업 완료후 V연산을 수행하는 것으로 간단하게 상호배제를 구현할 수 있음
멀티프로세서 시스템에서만 사용 가능한 방식(P, V연산 실행중에는 interrupt가 발생하지 않기때문)
Busy Waiting 문제는 여전히 해결되지 않음

2. Semaphore

// P 연산
// 세마포어 값이 1 이상이라면 권한을 획득(s -= 1)하고 임계영역에 접근
// 그렇지 않다면 대기열에 들어가 기다린다
void P(*s) {
    if(s > 0)
        s -= 1;
    else
        /* wait in ready_queue */
}


// V 연산
// 작업을 끝낸 뒤 만약 ready_queue에서 대기중인 프로세스가 있다면
// 대기중인 프로세스중 하나를 깨워 실행되도록 해준다.
// 대기중인 프로세스가 없다면 권한을 반납(s += 1)한다.
void V(*s) {
    if(/* ready_queue is not empty */)
        /* wake up one of waiting processes */
    else
        s += 1;
}

Dijkstra 가 고안한 방식
Spinlock 과 유사하게 초기화, P, V 연산을 지원
권한을 획득하지 못한 프로세스는 계속 실행되지 않고 ready_queue에 들어가 block 상태로 대기
Busy Waiting 문제를 해결함
그러나 ready_queue 에서 대기중인 프로세스중 어느것을 먼저 깨울지는 비결정적(기아문제 발생할 수 있음)
Semaphore의 종류
- Binary Semaphore
  - 세마포어 값(s)이 0 또는 1 두 종류의 값만 가지는 경우
  - 상호배제와 프로세스 동기화의 목적으로 사용
  - 뮤텍스(mutex)가 이에 속한다
- Counting Semaphore
  - 세마포어 값(s)이 0 이상의 정수값을 가지는 경우
  - 생산자-소비자 문제 등의 해결을 위해 사용

Semaphore로 해결할 수 있는 문제

상호배제(Mutual Exclusion)
- 임계영역 진입전에 P연산을, 작업 완료후 V연산을 수행하여 해결
프로세스 동기화(Process Synchronization)
- 세마포어 값을 0으로 초기화
- 먼저 수행되어야할 작업은 P연산 없이 작업을 수행 후 V연산 수행
- 나중에 수행되어야할 작업은 P연산을 수행하여 대기, 먼저 수행되어야할 작업이 완료되어
  V연산이 실행되면 세마포어 값이 증가하여 작업을 수 행할 수 있게 됨

생산자-소비자(Producer-Cosumer)

// 생산자 프로세스
void Producer() {
    while(true) {
        /* produce data K */
    
        // 버퍼의 데이터가 소비자에 의해 소비될 때 까지 대기
        P(consumed)
    
        // 소비자가 데이터를 가져가면 버퍼에 생성한 데이터를 저장
        write(buffer, K)
    
        // 데이터 생성이 완료되었음을 알림
        V(produced)
    }
}


// 소비자 프로세스
void Consumer() {
    while(true) {
        // 생산자가 데이터를 생성할 때 까지 까지 대기
        P(produced)
    
        // 생산자가 데이터를 버퍼에 저장하면 이를 읽어옴
        K = read(buffer)
    
        // 데이터가 소비되었음을 알림
        V(consumed)
    
        // 읽어온 데이터 소비
        /* consume data(k) */
    }
}
}

생산자가 데이터를 생산하기전에 소비자가 데이터를 읽으려할 때 생기는 문제
생산자 둘이 서로 같은 영역(버퍼 등)에 동시에 데이터를 생성, 저장하려 할 때 생기는 문제
Single Buffer일 때 사용가능한 방법

버퍼가 여러개일 때의 생산자-소비자 문제

// 생산자 프로세스
void Producer() {
    while(true) {
        /* create data K */
        
        // 다른 작업중인 생산자가 없을 때 까지 대기
        P(mutexP)
        
        // 비어있는 버퍼가 생길 때 까지 대기
        P(nrempty)
        
        // buffer[in]에 생성한 데이터를 저장하고 in의 위치를 한칸 이동
        write(buffer[in], K)
        in = (in + 1) % N
        
        // 버퍼 하나가 채워졌음을 알림
        V(nrfull)
        
        // 생산자의 작업이 끝났음을 알림
        V(mutexP)
    }
}


// 소비자 프로세스
void Producer() {
    while(true) {
        // 다른 작업중인 소비자가 없을 때 까지 대기
        P(mutexC)
        
        // 채워진 버퍼가 생길 때 까지 대기
        P(nrfull)
        
        // buffer[out]에서 데이터를 읽어오고 out의 위치를 한칸 이동
        K = read(buffer[out])
        out = (out + 1) % N
        
        // 버퍼 하나가 비워졌음을 알림
        V(nrempty)
        
        // 소비자의 작업이 끝났음을 알림
        V(mutexC)
    }
}

mutexP : 생산자 뮤텍스
mutexC : 소비자 뮤텍스
buffer[0] ~ buffer[n-1] : n개의 버퍼
in, out : 생산한 데이터를 넣을 위치, 데이터를 소비할 위치
nrfull : 채워진 버퍼의 수
nrempty : 비어있는 버퍼의 수
환형 큐를 사용하여 문제를 해결

Reader-Writer

// Reader 프로세스
void Reader() {
    while(true) {
        /* 읽기작업 진입 전 단계 */
        P(mutexR);
        // 다른 Reader가 없을 경우
        // Writer가 작업을 수행하지 않도록 막아둠
        // 다른 Reader가 있을경우 이미 이 작업이 수행됐기에 다시 수행할 필요가 없음
        if(nreaders == 0)
            P(mutexW);
            
        // Reader의 수 증가
        nreaders += 1;
        V(mutexR);
        
        /* 읽기 작업 수행 */
        
        /* 읽기작업 완료 후 단계 */
        P(mutexR);
        // 더이상 다른 Reader가 없을 경우
        // Writer가 작업을 수행할 수 있도록 lock을 해제
        // 다른 Reader가 남아있을경우 아직 lock을 해제해선 안됨
        if(nreaders == 0)
            V(mutexW);
            
        // Reader의 수 감소
        nreaders -= 1;
        V(mutexR);
    }
}


// Writer 프로세스
void Writer() {
    while(true) {
        // 쓰기 작업 진입
        P(mutexR);
        
        /* 쓰기 작업 수행 */
        
        // 쓰기 작업 완료
        V(mutexR);
    }
}

Writer는 동시에 작업을 수행해선 안됨(상호 배제 보장이 필요)
Reader의 경우 기본적으로는 여러 작업이 동시에 실행되어도 문제가 없음
Reader쪽에게 우선권을 주는 Reader Preference 와 Writer에게 우선권을 주는
Writer Preferece 두가지 방법이 있으며 위의 코드는 Reader Preference 기준의 설명

3. Eventcount / Sequencer

은행의 번호표와 유사한 개념을 사용한 기법
Sequencer
- 정수형 변수 S는 지금까지 발생한 사건(실행된 프로세스)의 수를 의미(처음엔 0으로 초기화)
- ticket(S)
  - 프로세스는 실행되기 전에 ticket(S) 를 호출하여 자신의 순번(번호표)을 발급받음
  - ticket 연산이 수행될 때마다 S값은 1씩 증가
Eventcount
- 정수형 변수 E는 깨워야할 차례인 사건(다음으로 실행될 프로세스)의 순번을 의미(처음엔 0으로 초기화)
- read(E)
  - 현재 E값 반환
- advance(E)
  - E번에 해당하는 프로세스를 깨움(wake-up)
  - E를 1 증가시켜 다음에 실행될 순번을 갱신
- await(E, V)
  - V는 프로세스가 발급받은 순번
  - E < V 일 경우, 즉 자신의 순번이 아직 오지 않았을 경우 E에 연결된 대기열에 프로세스를 삽입
  - CPU 스케줄러에 E 값이 V가 됐을 때, 즉 자신의 순번이 왔을 때 깨워줄것을 요청

Eventcount / Sequence 를 활용한 생산자-소비자 문제 해결

// 버퍼의 갯수는 n개
// 생산자, 소비자의 Sequencer 는 각각 Pticket, Ctikcet
// 생삱자, 소비자의 Evnetcount 는 각각 In, Out

// 생산자 프로세스
void Producer() {
    int u;
    while(true) {
        /* create data K */
        
        // 순번 발급
        u = ticket(Pticket);
        
        // 자신의 순번이 올 때까지 대기
        await(In, u);
        
        // 데이터를 삽입할 버퍼가 있을 때 까지 대기
        // 버퍼의 총 갯수는 n개
        // 버퍼가 채워진 횟수는 u개(생산자가 실행된 횟수)
        // 버퍼가 비워진 횟수는 Out개(소비자가 실행된 횟수)
        // 남은 버퍼의 갯수는 (n - u + Out)개
        // n - u + Out > 0, 즉 Out > u - n 이어야 빈 버퍼가 존재하므로
        // u - n + 1 까지 기다려야 빈 공간이 생긴다.
        await(Out, u - n + 1);
        
        // buffer[u % n]에 데이터를 저장
        buffer[u % n] = K;
        
        // 생산자의 작업이 하나 완료되었음을 알림
        advance(In);
    }
}


// 소비자 프로세스
void Producer() {
    int v;
    while(true) {
        // 순번 발급
        v = ticket(Cticket);
        
        // 자신의 순번이 올 때까지 대기
        await(Out, v);
        
        // 데이터를 읽을 버프가 있을 때 까지 대기
        // In 이 자신의 순번보다 크다면 채워진 버퍼가 있음
        await(In, v + 1);
        
        // buffer[v % n] 의 데이터를 읽어옴
        K = buffer[v % n];
        
        // 소비자의 작업이 하나 완료되었음을 알림
        advance(Out);
    }
}

프로세스는 대기열에서 순번을 기다리다가 스케줄러에 의해 깨어나기에 Busy Waiting 문제 없음
Semaphore에서 대기중인 프로세스의 wake-up 순서가 비결정적이기 때문에 생길 수 있었던
기아(starvation) 문제는 발생하지 않음 => 티켓을 발급받은 순번대로 깨우기 때문
Sequencer 를 통해 프로세스가 실행되는 순서를 컨트롤할 수 있음

저작자표시 (새창열림)