CS 스터디 - 운영체제 : 병행제어 I

 Process Synchronization

데이터의 접근

• 컴퓨터에서 연산을 할 때 데이터를 불러와서 연산을 하고 결과를 반환하게 된다.
  • 문제
    • 여러 곳에서 데이터에 접근을 할때
    • Race Condition (경쟁 상태)
    • 운영체제가 개입을 할 때 발생 가능
      • 원래 프로세스는 자신의 데이터 영역만 접근하기 때문에 이런 문제가 있을 수 없지만 운영체제가 개입을 하는 경우 운영체제 안에 있는 데이터를 건드리게 되면 문제가 발생 가능
      • 시스템 콜을 사용해서 커널 모드로 진행 중에 CPU를 뺏기게 되면(Context Switch) 연산 중이던 값이 반영이 안 됨
      • 해결 방안
        • 커널 모드에서 수행 중일 때는 CPU를 preempt하지 않음
    • 커널 모드에서 인터럽트가 발생
      • 인터럽트 시에 변환된 값이 반영되지 않는다.
      • 해결 방안
        • 공유 변수를 조작할 때는 인터럽트를 받지 않는다.
    • 공유 메모리를 사용할 때 문제 발생 가능
    • CPU가 여러 개 일 때 문제 발생 가능
      • 해결 방안
        • 하나의 CPU만 운영체제를 실행할 수 있도록 한다.
          • 비효율적
        • 공유 데이터를 접근할 때 그 데이터에 대한 lock을 건다.

프로세스 간의 Synchronization 문제

• 공유 데이터에 동시 접근은 데이터의 불일치 문제가 발생할 수 있다.
• 일관성을 유지할 수 있도록 만들어주어야 한다.
• Critical section 문제
  • 여러 개의 프로세스가 같은 데이터를 동시에 사용하려 할 때
    • 하나의 프로세스가 critical section에 을 때 다른 모든 프로세스는 critical section에 접근할 수 없어야 한다.
  • 해결법의 충족 조건
    • Mutual Exclusion(상호 배제)
      • 하나의 프로세스만 사용이 가능해야 한다.
    • Progress(진행)
      • 아무도 critical section을 사용하지 않을 때 critical section을 원하는 프로세스가 있으면 들어가 수 있어야 한다.
    • Bounded Waiting(유한 대기)
      • 특정 프로세스들만 계속해서 사용하면 안 된다.
  • 구현 방식(Algorithm)
    • turn변수를 생성(Synchronization variable)해서 해결
      • 구현 
        • turn변수를 생성(Synchronization variable)
        • turn 변수를 확인해서 본인의 turn이면 critical section을 사용
        • critical section을 사용하고 난 후 turn을 변경
      • 문제
        • 다른 프로세스가 critical section을 사용 안 하고, 자신은 계속 사용하고 싶을 때는 들어갈 수가 없음
        • 상호 배제만 충족한 알고리즘이다.
    • flag 배열을 만들어서 해결하기
      • 구현 
        • flag배열을 프로세스만큼 생성
        • critical section을 사용할 거면 자신의 flag를 true변경
        • 사용 후 flag를 false로 변경
      • 문제
        • 만약에 flag만 true로 변경하고 CPU를 빼앗겼을 경우 모두가 critical section을 사용할 수 없게 됨
    • Peterson`s Algotithm
      • 구현 
        • flag와 turn을 모두 사용
        • flag를 true로 변경
        • turn을 상대방 turn으로 변경
        • 상대의 flag가 true고 turn이 상대방 차례일 때 critical section을 작동
      • 문제
        • 비효율적 Busy Waiting = spin lock
        • critical section에 못 들어갈 상황이면 while문만 계속 돌면서 cpu를 낭비

Synchronization Hardware

• 하드웨어적으로 Test & modify를 atomic(원자적 = 모두가 한 번에 수행)하게 수행하도록 지원

세마포어(Semaphores)

• 추상 자료형
• 위의 방식들을 추상화
• 변숫값이 정수로 정의됨
• 두 개의 연산이 존재

  

  • P
    • 자원을 획득하는 연산
    • 예
      • lock을 거는 것
  • V
    • 자원을 반납하는 연산
    • 예
      • unlock을 하는 것
• 세마포어 변수로 관리
• critical section에서 적용의 예



• busy wait 해결
  • 세마포어 변수로 판단해서 세마포어 V연산이 작동되어서 자신이 쓸 수 있을 때까지 wile문을 돌지 않고 기다림
• Block / Wakeup Implementation
  • 자원의 여유가 없을 때 아예 Block 시킴
  • block
    • 커널은 block을 호출한 프로세스를 suspend시킴
    • 이 프로세스의 PCB를 세마포어에 대한 wait queue에 넣음
  • wakup(P) 
    • block 된 프로세스 P를 wackup시킴
    • 이 프로세스의 PCB를 ready queue로 옮김
• 세마포어 정의

typedef struct 
{
		int value; /* semaphore */ 
        struct process *L /* process wait queue */ 
 } semaphore;

• 세마포어 연산

P(S): S.value--; /* prepare to enter */ 
	if(S.value < 0) /* Oops, negative, I cannot enter */ 
    { 
    	add this process to S.L; 
        block(); 
     }

 

• 일단 --를 하고 세마포어 벨류가 음수이면 block을 시킨다.
• V(S): S.value++; if(s.value <= 0) { remove a process P from S.L; wakup(P); }
• 그 후 누군가 벨류를 ++해서 0이면 block인 상태가 있다는 것이므로 wakeup으로 깨운다
• Block/wakeup의 오버헤드와 critical section의 경쟁이 어느 정도인지를 판단해서 비용을 계산해서 사용하면 좋지만 일반적으로는 Block/Wakeup을 사용

두 개의 세마포어

• Counting semaphore
  • 도메인이 0 이상의 값을 쓸 때
• Binary semaphore(=mutex)
  • 0 or 1만 쓸 때