Process Synchronization 2

kocw 강의 : 이화여자대학교 반효경 교수님의 운영 체제 강의,13강 process syncrhonization

 

critical section problem

race condition 이 발생할 수 있는 부분인 critical section 이 있을 때, 여러 process가 해당 section에 접근하려 한다면, entry/exit section이 있어, 하나의 프로세스가 이 부분을 지나면 다른 프로세스는 접근을 하지 못하게 lock 걸어주는 software 접근 방식

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

• mutual exclusion : 프로세스 P_i 가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section 에 들어가면 안된다
• progress : 아무도 critical section 에 있지 않은 상태에서 critical section에 들어가고 싶으면 들어가게 해줘야 함
• bounded waiting : 프로세스가 critical section 에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical secgion에 들어가는 횟수에 한계가 있어야 함 -> 기다리는 것도 정도가 있어야 한다는 뜻

Algorithm 1

int turn = 0;

$process_i$가 자기 차례가 되면, turn 이 $i$ 가 됨. $process_i$ 의 turn 을 바꿔주는 것은 $process_j (i !=j)$ 가 해준다.

해당 알고리즘은 progress 조건을 충족하지 못한다. (i 가 한번 주고 j 는 여러 번 받아야 한다면, i 는 일이 끝나서 지나치고 j는 하염없이 j를 기다린다)

Algorithm 2

boolean float[2] = [false, false];

 

내가 들어가고 싶으면 flag 를 true 로 놓는다. 다른 얘들 중에 true 인 얘들이 있는지를 보고 없으면 (방이 비었으면) critical section으로 들어가고 나올 때, false 로 바꿔두고 나온다.

해당 알고리즘도 문제가 있는데, 둘 다 깃발만 들고 있으면 둘 다 기다리고 있음. 눈치 게임 시작...

 

Algorithm 3 (Peterson's Algorithm)

boolean flag[2] = [false, false];
int turn = 0;

• 순서
  • $process_i$ 가 하고 싶으면 일단 flag 를 바꿔둔다. (나 해도 될까..?)
  • 그런 다음에 turn 을 $j$ 로 둔다. (그대신 다음에 꼭 너 해)
  • 들어가기 전에 체크를 한다.
    • 상대방이 깃발을 들고 있고, 동시에 상대방 차례면 기다리고 아니면 critical section으로 진입
    • 상대방이 먼저 flag 를 바꿨을 때 해당 조건이 성립한다.
  • 나올 때, flag 를 돌려놓는다. (잘 썼습니다)
• 해당 알고리즘은 flag 의 눈치싸움 문제, turn 의 외로움 문제를 해결한다. 이와 더불어 위의 3가지 조건을 다 만족한다고 함
• 근데 busy waiting 문제가 있다고 함 
  • 계속 cpu 와 memory 를 쓰면서 wait -> 계속 while 문 돌면서 check, check 한다고 자기 차례 오는 것도 아닌데 그냥 계속 check 만 하면서 resource 쓰다가 timer interrupt 가 되어서 끝나버림

 

Synchronization Hardware

• 하드웨어적으로 test&modify 를 atomic 하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결
• 데이터를 읽는 것과 쓰는 것을 동시에 진행할 수 있다면 앞의 문제는 간단히 해결
• 우리가 lock을 열고 풀고 하는걸 했던 이유는 instruction 하나 하나가 실행되는 도중에 cpu 가 뺏길 수 있기 때문이다. 그래서 hardware 적으로 여러 instruction으로 존재했던 과정을 하나로 통합해버리면, 읽었는데 쓰기 전에 뺏길 일은 없다.

어려운데, 이전 강의에서 race condition 에 대해서 이야기할 때, process 1이 kernel memory 에 뭘 쓰려고 load 했다가 process 2 한테 뺏겨서 load -> inc++ -> store 를 한 후에 다시 cpu 를 받아서 쓰면 process 1 것만 적용되는 이슈가 있었는데, 보면 load -> write 에 대한 instruction 이 나눠져있고, 이로 인해 race condition 이 발생함을 알 수 있다. 이에 따라 hareware 적으로 load/write 를 하나의 instruction으로 통합해버린다면 lock 을 software 적으로 복잡하게 잡아줄 수고가 없어지게 된다는 뜻이다.

 

Semaphores

• 앞의 방식들을 추상화시킴. (추상 자료형은 object와 operation으로 구성이 됨)
• Semaphore S
  • 공유 자원을 획득하고 반납하는 과정을 semaphore 가 지원해준다 
  • integer variable : 자원의 개수
  • 아래의 두 가지 atomic 연산에 의해서만 접근 가능
    • P(S) : 자원을 하나씩 꺼내가는 것, lock 을 건다
      • P(S)에서 busy-waiting 이 똑같이 발생하긴 함 (spin-lock)
      • Block & Wakeup 방식 구현도 있음 (sleep-lock) -> 이게 cpu resource 사용이 더 효율적
    • V(S) : 자원을 하나씩 반납하는 것, lock 을 푼다

 

Critical Section of n Processes with Semaphore

• mutex : mutual exclusion, int variable. 3 가지 program 적 해결 가정 중 하나

 

Block & Wakeup Implementation

typedef struct
{
    int value; /* semaphore */
    struct process *L; /* process wait queue, L에는 PCB에 대한 주소를 가리키고 있다 */
}

• P(S) :
  • 자원에 여분이 없다면, 본인을 semanphore의 wait queue 인 L에 넣고, 잠든다. block() -> cpu 반납
  • 이 때, 자원을 하나 빼놓고 간다. 잠들어도 semaphore 하나는 챙긴다.
• V(S) :
  • 볼 일 다 봤으면, semaphore 를 1 늘려주고, S<=0 가 걸리면 (누군가 잠들어있다..!) wait queue 에 있는 얘를 꺼내서  깨워준다.
  • S.value 를 확인하는 것은 음수인 경우엔 누군가가 자원을 기다리고 있고, 양수면 자원에 여유가 있다는 상태를 의미한다. 즉, 깨울 놈이 있는지를 확인하는 것

일반적으로는 busy waiting 보다는 block & wake up 이 효율적, critical section의 길이가 더 길 수록 효율적

 

Deadlock and Starvation

• Deadlock : 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event 를 무한히 기다리는 현상
• 어떤 프로그램이 S와 Q에 대한 리소스를 둘 다 필요로 할 때, 하나의 프로세스가 하나를 물고 잠들고 나머지 하나가 하나를 물고 잠들면서 서로의 프로세스가 각 자원을 놓기를 기다리게 되면, 영원이 두 프로세스는 종료되지 않는다.
  • 이 경우 프로그램을 S 리소스를 물고 나서 그 다음에 Q를 물게 짜면, deadlock 을 해결할 수 있다.