[운영체제] 프로세스 동기화

 

 운영체제 강의(이화여대,반효경 교수님)를 듣고 정리한 내용입니다.

---

 

데이터의 접근

• 데이터를 읽고 연산하는 과정에서 누가 먼저 읽고 연산했는지 순서에 따라 결과가 달라짐.

Race Condition

• 저장소를 한곳에서만 실행하면 문제가 없음.
• 두개의 프로세스에서 동시에 데이터에 접근해서 데이터를 연산하면 연산 결과가 의도치 않게 나올 수 있음.
  -> 레이스 컨디션
  이런 상황을 조율하는 방법이 필요
• race condition 이 일어날 수 있는 상황
• 저장소를 공유하는 실행박스가 여럿 있는 경우 Race Contion 가능성이 있음.
  • CPU가 여러개 있는 시스템
  • 공유 메모리를 사용하는 프로세스들
  • 커널 내부 데이터를 접근하는 루틴 (커널모드 수행 중 인터럽트로 커널모드 다른 루팅 실행시)

OS에서의 Race Condition

• 커널 수행 중 인터럽트 발생 시
  • 새로운 인터럽트 처리하면서 데이터 변경하면 기존의 처리하던 내용에 영향을 줄 수 있음.
• 프로세스가 시스템콜을 하여 커널모드로 수행중인데 context switch가 일어나는 경우
• 여러개의CPU에서 공유 메모리 내의 커널 data

• 커널 모드running중 인터럽트 발생하여 인터럽트 처리 루틴이 수행.
• 양쪽 다 커널코드이므로 커널 주소 공간 공유
  -> 해결 방안 : 한쪽이 중요한 연산 수행중일 땐 다른 인터럽트를 중지 시킴

Process Synchronization 문제

• 공유데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다.
• 일관성 유지를 위해서는 협럭프로세스 간의 실행 순서를 정해주는 매커니즘이 필요하다.
• Race Contndition
  • 여러 프로세스들이 동시에 공유데이터를 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐.
• Race contition 을 막기 위해서는 concurrent process는 동기화 (Synchronize) 되어야 한다.
• Example of a Race Condition
  
  -> shared memory를 쓰거나 커널 실행중에 인터럽트 발생하면 오류가 생길 수 있음.
• The Critical-Section Problem
  • n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
  • 각 프로세스의 code segment 에는 공유 데이터를 접근하는 코드인 critical section이 존재
  • Problem
    • 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

프로그램적 해결법의 충족조건

• Initial Attempts to Solve Problem

Semaphores

• 추상화 시킨 연산
• Semaphore S
  • integer variable
  • 아래 두가지 atomic 연산에 의해서만 접근 가능.
    

    

    
    P 연산 : 자원 사용
    V 연산 : 자원 반납

Critical Section of n Processes

• 

busy wait 누군가 계속 세마포어 사용중이면 효율적이지 못함. = spin lock
block & wake up = sleep lock

Block / Wakeup Implementation

• 세마포어를 사용할 수 없으면 잠듦.
• 사용 가능하면 깨어남.
• 세마포어를 얻지 못하면 큐에서 잠들어있음.

자원이 없으면 block()
V로 자원 반납 할 때 잠들어있는 연산이 있으면 wakeup(P)으로 꺠워줌
s를 빼고 잠들었기 때문에 s값이 0부터 자원이 있는거임.

• Busy wait vs Block and wakeUp
  • 보통은 block and wake up방식이 효율적.
  • 그러나
    • Critical section 의 길이가 매우 짧은 경우 Block/Wakeup 오버헤드가 busy-wait보다 길어질 수 있음.
      • 재우고, 깨우는 과정에도 오버헤드가 있기 때문에 이를 짧은 시간에 반복하면 오버헤드 커짐.
    • Critical section의 길이가 긴 경우 Block/Wakeup 방식이 적당.
    • 일반적으로 Block/wakeup방식이 더 좋음.

Two Types of Semaphores

• Counting Semaphore
  • 도메인이 0이상인 임의의 정수값
  • 주로 resource counting에 사용
• Binary semaphore ( = mutex)
  • 0 또는 1 값만 가질 수 있는 semaphore
  • 주로 mutual exclusion(lock/unlock)에 사용

Deadlock and Starvation

• Deadlock
  • 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상.
    

    

• Starvation
  • indefinite blocking
  • 프로세스가 suspend 된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상.

Classical Problems of Syncronization

Bounded-Buffer Problem (Producer-Consumer Problem)

• 

• 

• mutex : 공유 버퍼를 하나의 프로세스만 접근하기 위한 세마포어
• empty: 처음엔 모든 자원 사용 가능하므로 n개
• full : 사용중인거 ( 내용이 들어있는 것)

Readers-Writers Problem

• 한 프로세스가 DB에 write 중일 때 다른 프로세스가 접근하면 안됨.
• Read는 여럿이 해도 됨.
• 해결책
  • write가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다.
  • Writer는 대기중인 Reader가 하나도 없을 때 DB에 접근이 허용된다.
  • 일단 writer가 DB에 접근중이면 Reader들은 접근이 금지된다.
  • Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.
• Shared Data
  • DB 자체
  • read count : 현재 DB에 접근중인 Reader의 수
• Synchronization variables
  • mutex : 공유 변수 readcaount를 접근하는 코드 (critical section)의 mutual exclusion 보장을 위해 사용
  • db : reader와 writer가 공유 db 자체를 올바르게 접근하는 역할

리드할때도 락은 무조건 걸어야됨. 안그럼 writer가 접근함.
따라서 readcount를 사용함.
최초의 reader(증가한 카운트가 1이라면)라면 db에 락을 건다.
이후의 리더는 그냥 디비를 읽기만 함.
readcount도 공유 변수라서 세마포어로 뮤텍스를 사용함.
리더가 마지막 리더라면 디비 락을 풀어줌.
reader 락이 걸리면 writer는 마지막 리더가 나가기 전까지 계속 기다려야 함.
reader만 계속 들어오면 writer는 지나치게 오래 기다려서 굶어죽어버릴 수 있는 starvation 발생 가능함.

Dining-Philosophers Problem

식사하는 철학자
5명이 원탁에 앉아서 밥을 먹음.
하는일

• 생각하기
• 밥먹기

배고파지면 왼쪽, 오른쪽 젓가락을 사용해 밥을 먹음.
밥을 먹으려면 젓가락 두개가 다 필요함.
옆 사람이 식사중이라면 옆 사람이 다 먹고 젓가락 놓을 때 까지 기다려야 함.

• 솔루션 문제점
  • 데드락 가능성
  • 모든 철학자가 왼쪽 젓가락을 잡아버리는 경우 -> 모두 오른쪽을 잡지 못함.
  • 왼쪽 -> 오른쪽 -> 젓가락 놓기 순서로 수행하기 떄문에 오른쪽 잡기 전까지 끝내지 않음.
• 해결 방안
  • 4명만 테이블에 동시에 앉을수 있도록 한다.
  • 젓가락을 두개다 집을 수 있을 때에만 젓가락을 집을 수 ㅣㅆ게 한다
  • 비대칭
    • 짝수 철학자는 왼쪽 젓가락 부터 집도록.
    • 홀수 철학자는 오른쪽 젓가락 부터 집도록.

젓가락을 모두 잡을 수 있는 상황의 코드

• self[i] : i 번째 철학자가 젓가락을 모두 집을수 있는 권한이 있다.
• state : 철학자 상태
• mutex : 젓가락 상태는 여러 철학자가 바꿀 수 있으므로 두는 공유 변수
• test에서 권한을 체크하고 만족하면 V로 권한을 줌.

Monitor

• 세마포어의 문제점
  • 코딩이 어렵다
  • 정확성의 입증이 어렵다
  • 자발적 협력이 필요하다
  • 한번의 실수가 모든 시스템에 치명적 영향

  • 

• 동시 수행중인 프로세스 사이에서 abstract data type 의 안전한 공유를 보장하기 위한 high-level synchronization construct
  
• 공유데이터는 내부 프로시저를 통해서만 접근 가능.

• 모니터가 원천적으로 내부 프로시저들이 동시에 실행되지 않도록 하는 권한 갖고 있음.
• 세마포어 처럼 락을 걸고 풀 필요 없음.

모니터

• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요 없음
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해서 contiton variable 사용 : condition x,y;
• Condition variable은 wait과 signal 연산에 의해서만 접근 가능
  • x.wait()
    • x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend됨.
  • x.signal()
    • x.signal()은 정확하게 하나의 suspend된 프로세스를 resume 한다.
    • suspend된 프로세스가 없으면 아무 일도 일어나지 않음.

모니터를 사용하는 생각하는 철학자 문제

모니터 자체가 하나의 프로세스만 실행하게 해줌.
내용이 들어있는 버퍼를 기다리는 애, 빈 버퍼를 기다리는 애들을 따로 큐에 줄세워둠.