[운영체제] Process Synchronizationtion (1)

Race condition: 여러 프로세스가 동시에 같은 데이터에 접근할 때

=> 동기화 필요

 

Race condition 예시

The Critical-Section Problem

• n개의 프로세스들이 공유된 데이터에 경쟁적으로 접근할 때, 공유된 데이터에 접근하는 코드를 critical section이라 함
• 어떤 프로세스가 critical section을 수행 중이면 다른 어떤 코드도 critical section을 수행하지 못하게 해야 함
• 수행하지 못하게 막는 방법 -> solution

Solution of the critical-section problem

• Mutual Exclusion: 어떤 프로세스가 critical section을 수행 중이면 다른 어떤 코드도 critical section을 수행하지 못하게 해야 함
• 과도하게 막으면 throughput이 떨어짐
• Progress: 현재 critical section을 수행하는 프로세스가 없으면 어떤 프로세스가 들어갈 수 있어야 함
• Bounded Waiting: 어떤 프로세스가 들어가고자 할 때 무한정 기다리면 안됨, 기다리는 시간의 bound가 지정돼야 함

Initial attempts to solve problem

• entry section: critical section에 진입해도 되는지 확인하는 부분
• exit section: critical section 다 썼으니까 다른 애들한테 알려주는 부분

 

Algorithm 1 

int turn = 0; // shared variable
do {
    whlie (turn != 0);
    critical section
    turn = 1;
    remainder section
} while (1);

• 프로세스 P0, P1은 각각 turn의 값에 따라 critical section에 진입 가능, 동시 진입 불가능하므로 mutual exclusion 보장해줌
• swap-turn: 2개의 프로세스가 번갈아가며 동작하는 코드이므로 progress를 보장하지 못함

Algorithm 2

boolean flag[2]; // 들어가고자 하는 의지를 보여줌
flag[i] = flag[j] = false;

do{
    flag[i] = true; // 나 들어갈 거야
    	while (flag[j]); // 상대방 flag 체크, true면 기다려
        critical section // 
    flag[i] = false; // 나 나옴
    remainder section
} while(1);

• mutual exclusion 보장하지만 여전히 progress 안됨
• 두 놈이 다 flag가 true면 둘 다 while에서 막혀버림

Algorithm 3 (Peterson's Algorithm)

do {
    flag[i] = true; // 나 들어갈래
    turn = j; // 일단 니가 먼저 들어가
    while (flag[j] and turn == j); // 상대가 들어갈 마음이 있고, 순서도 상대 순서면 기다려
    critical section 
    flag[i] = false; // 상대가 빠져나오면서 flag가 false가 되면서 while 빠져나와서 내가 들어갈 수 있음
    remainder section
} while(1);

• turn이 교통 정리를 해줌
• while문을 계속 돌음 => busy waiting(CPU를 계속 쓰면서 대기함)
• entry section이 너무 길어

더 나은 해결책

do {
    acquire lock
    	critical section
    release lock
    	remainder section
} while(TRUE);

• 기계적으로 코딩이 가능하게 primitive를 제공해주는 게 더 좋음 like systemcall
• 이 함수만 호출하면 돼 라는 믿음만 있다면 기계적으로 그 함수만 호출하면 됨
• locking system
  • 열쇠를 가진 자만이 critical section에 진입 가능
  • 빠져나오면서 열쇠 반납
  • 열쇠는 한 순간 한 놈에게만 줘야 한다는 것이 보장되어야 함
  • locking 시스템이 잘 코딩돼있으면 개발자 입장에서 정말 편함
• CPU가 하나일 경우 CPU 스케줄링에 의해 프로세스 간 왔다갔다 하는 상황 생김
  • 스케줄링이 발생하지 않게 한다면 다른 프로세스로 안 넘어가 
  • 스케줄링만 안 일어나면 동시에 critical section에 접근하려는 일은 발생하지 않음
  • critical section에 진입하면 CPU를 놓지 않고, 빠져나와서야 CPU를 놓으면 됨 => Interrupt
  • CPU 스케줄링이 발생하는 경우 == 내가 CPU를 잡고 있는 상황에서 CPU를 놔야 되는 경우: 나한테 주어진 시간이 끝이 났을 경우, I/O를 발생시켰을 경우(critical section에서는 I/O를 발생시키지 않음)
  • I/O 디바이스가 timer 인터럽트를 발생시켰을 때 
  • RR에서 time quantum을 주고, 그놈한테 time quantum이 다 됐는지 확인하는 주체 - timer
  • critical section에 들어가기 전에 타이머 인터럽트를  disable 시킴 -> time quantum을 소진했더라도 인터럽트를 발생시키지 않아서 계속 CPU 사용 가능 -> critical section 빠져 나오면서 타이머 인터럽트 enable
  • 하지만 멀티코어, 멀티프로세스 환경에선 general한 솔루션이 될 수 없음

General한 솔루션

: single cycle의 기능을 끝마친다는 것을, 중간에 끊기지 않는다는 것을 보장 해주는 특별한 하드웨어 회로 Atomic 제공

• Test-and-Set

boolean TestAndSet(boolean &target) {
    boolean rv = target;
    target = true; // target에는 true 주고
    return rv; // 원래 target 값을 return
}

 

               ㄴ 먼저 들어간 놈이 lock을 false로 바꿔주는 순간 대기하던 프로세스가 false를 리턴하면서 while문을 빠져나옴

• Swap

void Swap(boolean &a, boolean &b) {
    boolean temp = a;
    a = b;
    b = temp;
}

boolean lock = false;

do {
    key = true;
    while(key == true) Swap(lock, key);
    critical section
    lock = false;
    remainder section
}

                ㄴ 먼저 들어간 놈은 lock이 true, key가 false가 되면서 while 문을 빠져나옴

                ㄴ 두번째 들어온 놈은 lock, key가 모두 true -> 먼저 들어온 놈이 lock을 false로 바꿔주면 key가 false가 되어 while문 나옴

 

Semaphore S

동기화를 위해 하드웨어를 사용하지 않고 소프트웨어만으로는 primitive를 제공할 수 없을까?

• 정수 변수 S에 접근하는 operation은 단 2개
• P(): wait, 조건 충족 시까지 대기
• V(): signal, 다음 프로세스에게 알려주는 역할

P(S): //S가 양수가 될 때까지 while 문에서 돌다가 0보다 커지는 순간 S를 감소시키고 빠져나옴
	while (S<=0) do no-op ;
	S--;
V(S): //V 하나 감소시킴
	S++;

 

• 동기화 방법: 모든 프로세스는 critical section 들어가기 전에 P 호출, 나오면서 V 호출

semaphore mutex; //initially 1

do {
    P(mutex); 
    critical section
    V(mutex);
    remainder section
} while(1);

• P나 V는 atomic 함수(중간에 끊기지 않고 한번 실행되면 끝까지)이기 때문에 소프트웨어로만 가능해짐
• 만약 atomic 하게 동작하지 않는다면? 여러 프로세스가 동시에 critical section 진입
• Semaphore 구현 방법
  • single process 
    • P 함수 시작 전에 interrupt disable
    • P 함수 끝나면 interrupt enable
  • multiple processes
    • 알고리즘 사용
    • semaphore 변수 S 값에 대한 접근 자체가 critical section이 됨
    • P, V의 S 값을 peterson's algorithm으로 보호 -> 동시 접근 불가
      • P, V 만 알고리즘으로 보호하면 함수 사용 시에는 peterson's algorithm을 사용하지 않아도 됨
      • peterson's algorithm을 만들면 busy waiting을 해야 하는 문제 생김 -> critical section이 커지면 overhead 커짐
    • Block/Wakeup Semaphore
      • while에서 busy wait를 하는 대신 P 호출 시 조건에 안 맞으면 sleep 시킴(CPU 사용 X)->조건 충족 시 하나씩 깨워
      • semaphore변수를 구조체로 만듦

typedef struct {
    int value;
    struct process *L; // Linked list를 가리키도록 함
} semaphore;

P(S):
    S.value--; //초기값 1이니까 0으로 바꿈 
    if (S.value < 0) { 
    	//처음 놈은 0이므로 이 조건에 충족되지 않아 critical section으로 들어감 
        //다음 놈부터는 linked list에 추가되고 block됨
    	add this process to S.L;
        block;
    }
    
V(S):
    S.value++; 
    if (S.value <= 0) {
    	//처음 놈은 그냥 빠져나가고
        //다음 놈부터는 기다리는 놈 하나 깨워줌
    	remove a process P from S.L;
        wakeup(P);
    }

• 성능 상 하드웨어로 하는 게 좋긴 함

OS 내부에서의 동기화 문제가 발생하는 경우

1. Interrupt 발생 시, Interrupt handler code 실행 시
2.  프로세스 간 스케줄링 시 systemcall 
3. 시스템 안에 프로세스가 여러개인 경우

 

한양대학교 강수용 교수님 운영체제 강의 내용 정리