[운영체제] 병행제어3

프로세스 동기화
공유 데이터에 여럿이 동시에 접근할 때,
데이터를 읽어서 수정하고 다시 저장하는게 원자적으로 수행되지 않고
연산 도중에 CPU 빼앗겨서 넘어갔을 때 생기는 문제를 다루고 있다.

데이터를 읽고, 수정하고, 저장하는 연산이 CPU에서 한번에 수행되게 하고 중간에 CPU 빼앗기지 않게 하는 방법을 통해 해결이 가능하다

Semaphores

• 자원 세는 값을 세마포어 변수로 하는 이유
  • Semaphores P와 V는 변수를 빼거나 더하는 연산이 원자적으로 수행된다고 가정한다
  • Semaphores가 지원되면 크리티컬 섹션에서 프로세스가 중복되지 않게 해준다
  • 불가능할 때는 프로세스 잠들게 하는 방법 => 블록 앤 웨이크업

데드락과 스타베이션

*데드락 : 뒤 챕터에서 더 자세히

데드락: 어느 누구도 진행이 불가능한 상황 (전체 입장)
스타베이션: 영원히 아래 부분이 수행이 안되는 기아 현상 (각각의 입장)

• P0 / P1 : S, Q 자원을 동시에 얻어서 일하고 일이 끝나면 반납

• 문제점
  P0가 S를 얻은 다음 CPU를 뺏겨서 P1한테 CPU가 넘어 가서 P1이 Q 획득 >
  P1이 아래 S를 획득하려고 해도 P0가 가지고 있기 때문에 획득하지 못한다 >
  두 개 자원을 동시에 가져야지만 일을 할 수 있는 경우 >
  각각 하나씩 자원을 가지고 기다리면서 영원히 아래 작업이 수행 안된다

  • 자원은 일이 끝난 다음에만 내어놓고, 그 전에는 절대 내어놓지 않는다

동기화와 관련된 전통적인 문제 3가지

획득 순서를 만들어주면 데드락이 생기지 않는다

1. 생산자 소비자 문제

공유 버퍼는 크기가 유한
여기서 버퍼는 여러 프로세스가 동시에 접근할 수 있는 데이터

• 생산자 프로세스

  • 데이터를 만들어서 버퍼(주황색 동그라미)에 집어넣는다
  • 생산자 입장에서 빈 버퍼가 있으면 데이터를 넣을 수 있는 자원이다. 생산자는 빈 버퍼가 생길 때까지 기다린다.

• 소비자 프로세스

  • 버퍼에서 데이터를 꺼내간다
  • 소비자 프로세스는 데이터를 꺼내가는 역할 하기 때문에 데이터가 이미 들어가 있는 것이 자원이다. 생산자가 나타나서 데이터를 생산해서 버퍼가 생길 때까지 기다려야 한다

• 문제점

  • 생산자 프로세스가 비어있는 곳에 데이터를 집어넣으려는 도중,
    CPU를 다른 생산자에게 빼았긴 경우 동시에 데이터를 집어넣으려고 하다가 데이터 하나는 유실이 될 수 있다
  • 소비자 프로세스가 데이터 꺼내가려고 하는 도중, CPU 빼앗겨서 데이터가 하나인데 동시에 꺼내가려는 문제가 발생한다

• 해결

  • 공유 데이터 접근시, 락을 걸어서 비어있는 위치에 다른 생산자나 소비자의 접근을 막은 뒤 작업을 후 빈 버퍼의 위치를 다음으로 넘겨주어야 한다
    • 확실하게 넣고 꺼내갈 수 있게 동시접근을 막는다!
    • 버퍼 자체가 공유데이터이기 때문에 이 방식으로 해결
  • 자원의 개수를 세는데 가장 적당한 것은 Semaphores
    • 락을 걸기 위한 Semaphores
    • 빈 버퍼와 내용 들어있는 버퍼의 개수 세기 위한 카운팅 Semaphores

Bounded-Buffer 문제

빈 버퍼의 개수 n개
내용 들어있는 버퍼 0개
락을 거는 변수 mutex

• 생산자
  우선 빈 버퍼를 하나 얻어야 한다 => 못 얻었으면 기다린다(소비자가 하나 꺼내갈 때까지) >
  집어넣으려면 먼저 락을 걸어 나만 접근하도록 한다 >
  작업 끝나면 락을 푼다 >
  내용이 들어있는 버퍼가 하나 생긴다

• 소비자
  생산자와 반대로 생각
  내용 들어있는 버퍼 하나 획득 >
  공유 버퍼에 락을 걸어서 버퍼 조작 끝났으면 락을 풀어준다 >
  빈 버퍼 하나를 추가해서 생산자를 깨워서 생산할 수 있게 한다

2. 읽기 쓰기 문제

공유 데이터에 접근하는 프로세스 두 개
하나는 읽는 프로세스
다른 하나는 쓰는 프로세스

*읽고 쓰는 동시접근을 막는 것은 DB에서 하기 때문에 공유 데이터를 DB 라고 부른다, DB에 대한 접근을 막아야 한다는 것이 핵심

• DB 접근 전에 락 걸고 접근 끝나면 락을 풀어준다
  • Reader(읽는 프로세스)는 동시에 해도 괜찮지만 무조건 락을 건다
  • Reader 들에 대해서 동시에 접근할 수 있게 해주고, Writer 대해서는 무조건 배타적으로 혼자만 접근할 수 있게 해준다

조건

• Reader는 여러 개가 동시에 DB 접근 가능
• Write하는 도중에는 모든 Reader와 Writer의 접근을 막는다
  • 하지만 또 다른 Reader가 왔을 때는 같이 읽을 수 있게 한다

락을 위한 변수

• 스몰디비(db)

  • DB 자체에 락을 걸기 위한 역할
    • 배타적 접근을 하게 한다
  • Reader가 락을 걸었더라도 다른 Reader의 접근을 허용해준다

• readcount

  • 현재 읽고있는 프로세스의 수
    현재 디비 접근하는 Reader가 몇 명인지 세는 공유 데이터
  • 양수면 다른 Reader가 DB에 접근하고 있다는 것
    • 여기서 또 다른 Reader가 도착하면 락은 걸려있지만 같이 읽을 수 있다
  • 0이면 다른 리더가 접근하고 있지 않다
  • 이것도 공유 데이터이고 동시접근 막기 위해 바이너리 세마포어인 mutex 사용
  • 즉, Writer가 락걸면 어느 누구도 막는데 Reader가 락걸었으면 read count를 확인하고 같이 읽을 수 있게도 한다
  • read count 조작할 때는 뮤텍스라는 락을 걸어서 증감을 관리

로직

• Writer는 DB에 접근하기 위해 락을 걸고 작업이 끝나면 락을 푼다
• Reader는 read count라는 공유 변수를 만지기 전에 락을 걸고
  접근이 끝났으면 락을 풀어준다(mutex)

read count가 0인 경우,
Reader 도착 > read count 1 증가 > DB에 락을 건다(Writer 접근 막기 위함)

read count가 1보다 더 큰 경우,
DB를 읽고있는 다른 Reader가 있고 걔가 락을 걸어놓은 상태이고 DB 접근
접근이 끝났으면 read count 감소시킨다
마지막 reader인지 체크 >
0이면 DB의 락을 풀어준다 >
(내가 마지막인 상황이면) 기다리고 있는 Writer가 잇으면 DB 접근할 수 있게 한다

• 문제점
  • 스타베이션 발생
    Writer가 제일먼저 도착해서 락을 건다 >
    Reader가 100개 도착했는데 다 읽고 나가야 차례가 오는 경우 >
    마지막 Reader가 DB 빠져나갈 때 Reader가 또다시 1000개 도착 >
    Writer는 또 기다림
    영원히 기다리게 될 수 있다
• 해결
  • 일정 시간까지 도착하는 Reader들에 대해서만 동시접근하게 하고 그 이후에 온 것은 끊어버린다
    기다리고 있는 Writer에게 기회를 준다
  • 시간 간격을 줘서 해결한다

3. 식사하는 철학자 문제

• 5명의 철학자가 원탁에 앉아서 크게 두 가지 일 반복
  • 생각하는 일
  • 밥을먹는 일
  • 배가 고파질 때, 밥을 먹어야 하는데 젓가락 두 개(공유 데이터 왼쪽과 오른쪽) 모두 잡아야 먹을 수 있다
  • 젓가락 내려놓는 행위는 밥 다 먹은 뒤에만 가능, 잡은 젓가락은 절대 내려놓지 않기 때문에 데드락(진행 불가능)이 생긴다
  • 동시 접근이 안되고 철학자가 굶어 죽으면 안된다
• 문제점
  • 모든 철학자가 동시에 배가 고파져서 다 왼쪽 젓가락을 잡아버리면 오른쪽은 어느 누구도 잡지 못한다
• 로직
  • 밥을 먹기 위해 오른쪽, 왼쪽을 다 잡고 먹고, 다 먹으면 내려놓고 다른 사람에게 기회 주도록 바이너리 세마포어로 관리한다(한명만 잡고 동시에 잡을 수 없게)
• 해결
  
  1. 생각은 내려가서 하고 밥먹을 때만 앉게 한다
     최대 4명만 앉게하면 (젓가락은 그래도) 한 명은 먹을 수 있게 된다, 한명이 다 먹으면 다음 사람이 먹을 수 있다
  2. 젓가락 두 개를 모두 잡을 수 있을 때만 젓가락 잡을 수 있는 권한을 준다
     왼쪽/오른쪽이 모두 가능할 때만 젓가락을 잡는다
  3. 짝수와 홀수로 철학자로 나눈다(어느 하나를 잡아야지만 다른걸 잡을 수 있게 하자) 동시에 못잡아서 생기는 문제를 없앤다

젓가락 두 개가 모두 사용 가능한지 체크한다
5명 철학자 각각에 대해 셀프가 1이면 모두 잡을 수 있다
0이면 다 잡을 수 없다
*초기값은 테스트 전까지 0으로 놓고 출발한다(특이사항)

• mutex
  상태 변수를 건드리기 위해 락을 거는 용도로 mutex를 사용
  mutex는 젓가락 자체의 권한만 체크한다
• 편의상 변수 5개를 두고 상태를 체크(배고픔, 생각, 먹기)
• 밥먹기(eat) 전에 젓가락 드는 함수(pickup), 내려놓는 함수(putdown)가 추가되어 있다
  1은 젓가락 잡을 수 있음, 0은 젓가락 못잡음

pickup

뮤텍스로 락을 건다 >
상태를 헝그리로 변경 >
양쪽 모두 잡을 수 있는지 테스트 >
테스트 통해서 젓가락 두 개 사용 가능하면 V연산을 통해 권한을 1로 만들어준다
(젓가락 잡을 수 있도록) >
뮤텍스로 락을 푼다

테스트 끝나고 돌아오면 P연산을 통해 1을 0으로 바꾸고(젓가락 못잡도록), 젓가락 권한을 끝내고 밥먹는다
젓가락이 가능하지 않다면 픽업으로 되돌아왔을 때 P연산에서 잠들게 된다

언제 젓가락 얻을 권한이 생기는가?

• test
  누군가가 다 먹고 젓가락 내려놓을때(putdown) 본인 상태는 생각하는 상태로 해놓고,
  왼쪽과 오른쪽 철학자를 테스트해서 그들이 배고픈 상태면 젓가락 잡을 권한을 준다
  (젓가락만 내려놓는 것이 아니라 왼쪽, 오른쪽 철학자 테스트해서 깨어날 수 있게 해준다)

모니터

• 세마포어 문제점
  프로그래머 실수로 연산을 잘못하면
  크리티컬 섹션에 동시에 여럿이 들어가거나 또는 아무도 못들어가게 된다

• 모니터는 동시접근을 아예 막아줄 수 있다

  • 동시에 활성화된 프로세스를 한 개로 한정하는 역할

고급언어차원에서 제공하는 동기화 수단인 모니터
*동기화 쉽게하기 위해 등장했다

• 공유 데이터 중심으로 함수들이 정의된다
• 모니터 안에 있는 프로시져를 통해서만 접근할 수 있는 구조 제공
  • 모니터 안 함수를 통해 동시접근을 책임진다
• 세마포어는 동시접근을 책임져주지 않고 연산만 제공한다
• 모니터 안에서 액티브하게 실행하는 프로세스는 하나로 제한한다
  락을 걸 필요없고 프로그래머는 모니터 안의 코드로 공유데이터에 접근한다
• 모니터 안의 공유 데이터를 여러 프로세스가 동시접근할 때, 모니터 안의 연산으로만 데이터를 접근한다
• 여분 없을때 줄새워서 잠재우는 큐 역할

프로세스가 데이터를 접근하겠다고하면 모니터 안 코드를 수행한다
프로세스가 접근할 때는 모니터가 진입을 막는다
프로세스가 연산 수행중이면 큐에 줄세우고, 진입 자체를 막는다 이를 통해 동기화 문제 해결한다

만약 자원 여분이 없는 상황인 경우, 세마포어는 자원 줄여나가는 식이다

모니터는 자원 여분있을 때 그냥 수행, 없으면 블락
큐에 줄서서 x.wait()을 통해 블럭상태로 바꿔야 한다

• condition variable
  • 자원 여분이 없을때, 줄세워서 잠들게 하는 변수
  • wait 호출해서 잠들게 하는 역할
  • 자원 여분이 생기면, 반환할 때 siginal연산으로 잠들어있는 것이 있다면 깨워라

각각의 철학자가 하는 역할 밥먹기와 생각하기
밥먹기 전에는 젓가락을 들고 다먹으면 내려놓는다
모든 철학자가 젓가락 한쪽만 잡고 데드락 문제가 발생한다
두개를 잡을 수 있을 때만 잡게 해주도록 코딩한다

모니터를 통한 해결

공유 데이터(젓가락) 접근을 모니터 안에 정의해놓고,
잡기위한 코드를 모니터 안 코드로만 실행되도록 한다
실제 젓가락 잡는것은 구현해놓지 않고 현재 상태가 무엇인지 확인한다

• condition variable
  젓가락 두 개 모두 잡을 수 있으면 잡고
  아니면 condition variable 에 잠들게 한다
  잠재우기 위한 큐가 존재한다

왼쪽, 오른쪽이 안먹고 있으면 내 상태는 밥먹기
철학자에 대한 signal 연산을 한다
밥먹고 나서 젓가락 내려놓을 때, 인접 철학자들이 나 때문에 밥을 못먹었는지 테스트 하는 함수
그때 깨워주기 위함이다
테스트 끝나서 잡았으면 픽업 끝. 밥먹기

인접 철학자 중 한명이 밥 먹고있었으면 헝그리에서 끝.
나는 권한 없어서 내 큐에 줄서서 잠들게 된다
다 먹었으면 젓가락 내려놓는 put down
생각하는 상태로 바뀜.

• test 함수
  인접 철학자 둘이 배고픈지 확인한다
  양쪽이 배고픈 상태가 맞다면, 밥먹는 상태로 변경 후 깨워줘서 큐에서 빠져나오게 한다(밥을 먹게 한다)