[운영체제(2)]Process Synchronization 3

이유정·2024년 4월 15일
0

운영체제

목록 보기
38/49

목표

  • Classical Problems of Syncronization
  • Bounded-Buffer Problem
  • Readers-Writers Problem
  • Dining-Philosophers Problem
  • Monitor

Classical Problems of Syncronization

01. Bounded-Buffer Problem

Buffer: 데이터를 임시로 저장하는 공간.
Bounded-Buffer: 버퍼의 크기가 유한함.

Producer-Consumer 문제

process 두가지 종류

이 문제에는 process가 두가지 종류가 있음.

  • Producer 프로세스
    • 여러개 있음
    • 역할: 버퍼에다가 공유 데이터를 만들어서 집어 넣음
    • 주황색 : producer가 데이터를 만들어서 집어넣은 상태
  • Consumer 프로세스
    • 여러개 있음
    • 역할: 버퍼에 있는 데이터 빼가서 사용
    • 비어있음: 애초에 비어있든지, cousumer가 데이터를 꺼낸 상태

Synchronization 문제 3가지

이 곳에서 Synchronization 관련한 어떤 문제가 발생할 수 있을까?

  1. 공유 버퍼이기 때문에 producer가 동시에 도착해서 비어있는 하나의 버퍼동시에 데이터를 만들어 집어넣는 문제
    => producer가 비어있는 buffer를 확인하고, 데이터를 집어넣는걸 그냥 하지않고,
    buffer에다가 lock을 걸어서 다른 process들의 접근을 막은 다음에
    buffer에다가 데이터를 넣고
    그 작업이 끝나면
    lock 풀고 다른 producer나 consumer가 버퍼에 접근하게 한다.
  • idx를 비어있는 버퍼로 위치
  1. consumer가 동시에 같은 데이터를 꺼내가려고 할 때
    => buffer에다가 lock을 걸어서
    데이터를 꺼내가고,
    lock을 풀고
  • idx를 채워있는 데이터로 위치
  1. buffer가 유한하기 때문에 생기는 문제
    buffer에 data가 다 찼을 때, consumer는 안오고 producer가 또 올 때
    => producer 입장에선 더이상 생산할 수 있는 자원이 없는 상태임/
  • producer 입장에선 비어있는 자원의 개수가 counting 해야하는 자원이다.
  • consumer 입장에서 자원은 내용이 들어있는 buffer다.

semaphore가 역할 2가지

  1. 공유 버퍼에 접근하는 것을 막기 위해서 버퍼 전체에다가 lock을 걸어서 나 혼자 접근 가능하게 lock을 걸고, 접근이 끝났으면 lock을 풀어줘야 한다.
  2. 버퍼가 가득 차거나 비었을 때 가용자원의 개수를 세는 counting semaphore 용도

semaphore 변수

semaphore 변수 3가지

  1. full : 내용이 들어있는 개수를 세기위한 변수
  • 처음에 full은 0개야. 채워져있는게 없다는 뜻임.
  1. empty : 비어있는 buffer를 세기위한 변수
  • 처음에 empty는 n개야. 모두다 비어있다는 뜻임.
  1. mutex : lock을 걸고 풀기 위한 변수

생산자 process들은 어떤 절차를 거치는지


item x를 만든 다음 이걸 공유 버퍼에 넣고 싶은데, 그 전에 ~~

빈 버퍼가 있는지 확인부터 한다.

버퍼에다가 데이터를 집어넣기 위해서 lock을 건다.

버퍼에다가 데이터를 집어넣는다.

버퍼에 걸었던 lock을 푼다.

내용 들어있는 버퍼 개수 1증가 시키는게 full에 대한 V연산

소비자는 반대로 ~! ...아래 사진 참고 !

02. Readers-Writers Problem


Readers-Writer 문제는 process가 2문제가 있음.

  • 읽는 process
  • 쓰는 process
    여기서는 공유 data를 DB로 명명. (읽고 쓰는 문제는 보통 DB에서 일어나기 때문)

그런데 DB에서는,

  • 쓰는 작업은 여러 Process가 접근하면 안되지만,
  • 읽는 작업은 여러 Process가 접근해도 괜찮다.



Writer

  • DB는 공유데이터를 뜻함. : 데이터에 접근하려면 lock을 걸어야함.
  • db: DB에 대한 lock에해당하는 semaphore 변수 : 공유 데이터 DB에 접근하기 위해 P연산 lock을 건 것임.
    Reader
  • 읽는 작업은 여러명이 해도 되는데 lock을 걸어버리면 비효율적
  • readcount: reader 몇명이 읽고 있는지 세는 변수 , 이것도 공유변수라서 이에 대한 lock을 거는 mutex라는 semaphore 변수가 있는거야. (이 변수를 lock 걸지 않으면 여러 reader가 와서 혼잡해질 때 readcount를 제대로 세지 않는 경우가 생길 수 있음.) , 내가 만약 readcount를 최초로 올린 reader라면 DB에다가 lock을 거는 P(db)연산을 해야함.
  • 빠져나갈 때, 내가 만약 마지막으로 읽었던 process라면 readcount가 0이 되고 DB에 걸었던 lock을 푸는 V(db) 연산을 한다.
    Starvation 문제
  • Reader가 DB에서 읽고 있는데, 또 다른 Reader와 Writer가 왔다. 이미 Reader가 읽고 있다면 Reader가 들어오고, Writer는 기다려야 한다. 그런식이면 마지막Reader가 나가려고 하는데 또 Reader 1000개가 들어오면, Writer의 starvation 문제가 있음.
    => 어느정도 많이 기다리면 이제 Writer가 접근할 수 있게 한다.

03. Dining-Philosophers Problem

철학자들은 밥을 먹거나 생각하거나

밥 먹기 전에 왼쪽 젓가락, 오른쪽 젓가락 잡는 연산

밥 먹고 나면, 왼쪽 젓가락이랑, 오른쪽 젓가락을 놓는 연산

  • 철학자들은 일단 왼쪽 젓가락 잡았으면 밥 먹을 때까지. 절대 놓지 않아요
    => 모두가 왼쪽 젓가락 잡고 안놔
    => Deadlock

해결 방안

  • 4명만 동시에 앉아라.
  • 젓가락 양쪽 잡을 수 있을 때만 권한을 준다.
  • 각 철학자마다 우선순위의 젓가락을 잡아야만 다음 젓가락 잡을 수 있게 권한을 준다.

철학자는 젓가락을 잡고pickup, 먹고eat, 젓가락 내려놓고pickdown, 생각한다think

  • semaphore self[i] = 1
    : 철학자 i번째 사람이 젓가락 잡을 권한 있다는 뜻 .
    ex) semaphore self[i] = 0;
    : 젓가락 잡을 권한 없다는 뜻.

  • enum (thinking, hungry, eating) state[5]
    : 다섯명의 철학자 상태를 나타내는 공유 변수

    • 생각하는 상태
    • 배고픈 상태
    • 먹는 상태
  • semaphore mutex = 1
    : i번째 철학자의 상태를 바꾸는 건 본인 뿐 아니라, 옆 철학자(i-1, i+1)도 가능함.

    • 따라서, state는 공유변수이고,
    • 공유변수에 대한 동시접근을 막기 위해서 mutex가 있음.
    • mutex는 lock을 나타냄

Monitor

예) 프로그래머의 한번의 실수가 모든 시스템에 치명적

  • V연산과 P연산 순서를 바꿨을 때 => 둘이 동시에 들어가는 문제 발생.
    예2) P연산만 두번했을 때 => 영원히 어느 프로세스도 Critical section에 못들어감.

이런 문제 때문에 Monitor 제공

monitor는 프로그래밍 언어 차원에서 synchronization 문제 를 해결하는 high-level synchronization construct

객체지향 프로그래밍 언어들을 보면 객체를 중심으로 operation 들이 정의가 됨. 그런거에 기반해서 monitor는 이런식으로 공유 data에 접근하기 위해서는 이 monitor라고 정의된 내부의 procedure를 통해서만 가능하다.


예를들어, 이 공유데이터가 안에 있으면 밖에서 아무나 접근할 수 있는게 아니라 monitor 안에다가 shared data와 그것에 접근할 수 있는 procedure 즉, operations를 정의해놓는다.

monitor는 원천적으로 내부에 있는 procedure는 동시에 여러개 실행이 안되도록 통제를 한다. => 프로그래머 입장에선 lock을 걸 필요가 사라짐


semaphore처럼 lock을 걸 필요는 없어졌지만, 여전히 자원의 개수를 세는건 필요하다. 왜냐하면 자원이 없으면 프로세스를 기다리게 함. condition variable

  • 자원의 개수를 세는 condition x;
  • 자원이 없으면 기다리는 함수 x.wait()
  • 접근 다하고 빠져나가면서 기다리는 프로세스 있으면 깨우는? 함수 x.signal()


생산자-소비자 문제의 semaphore 코드를 monitor 코드로 conversion

아까 여기선 lock을 걸고 푼다.

하지만, monitor는 lock을 걸고 풀 필요 없음.

공유 buffer가 monitor 안에 정의되어 있음.

생산하거나 소비하는 작업을 하기 위해서는 monitor 내부 코드를 실행해야함.

그러면 생산자든, 소비자들 하나의 코드만 monitor 안에서 활성화되기 때문에 굳이 lock을 걸지 않아도 또 다른 생산자나, 소비자가 접근해서 생기는 문제를 고려할 필요 없다.


만약에 비어있는 버퍼가 없다면, 버퍼 기다리는 줄에 줄서게 blocked 상태로 보냄

비어있는 버퍼가 있다면, 그냥 버퍼에다가 내용을 하나 넣어주면 됨.

그 작업이 끝났으면 버퍼 없어서 잠들어있던 프로세스를 깨워주는 코드

  • 프로그래머한테 semaphore보다 monitor가 더 쉽다.
profile
강의 기록 블로그

0개의 댓글