Chapter 06. Process Syncronization and Mutual Exclusion (2of7) - SW solutions

Mutual Exclusion Solutions

• SW solutions
  • Dekker's algorithm (Peterson's alogorithm)
  • Dijstra's algorithm, Knuth's algo, Eisenberg and McGuire's algo, Lamport's algo
• HW solution
  • TestAndSet(TAS) instruction
• OS supported SW solution
  • Spinlock
  • Semaphore
  • Eventcount/sequencer
• Language-Level solution
  • Monitor

---

Dekker's Algorigthm

Two process ME을 보장하는 최초의 알고리즘

flag와 turn 둘 다 사용.

// P0 입장
flag[0] = true; // 일단 내깃발 들고
while(flag[1]){ 
// 상대방 깃발 들고 있다면
    if(turn == 1){ // 상대방 턴이네
        flag[0] = false; // 깃발 내리고
        while(turn == 1){ // 내 턴 기다리자

        }
        flag[0] = true; // 내 턴왔으면 깃발 올리자
    }
}  // 상대방 깃발 내려가있으면 건너띄고 cs접근
// cs 앞 부분

// cs 뒷 부분
turn = 1;
flag[0] = false; 
// 깃발 내리고 턴 넘기기;

N-Process Mutual Exclusion

2개짜리말고 N개짜리

• Dijstra's algorithm
  • 최초로 프로세스 n개의 상호배제 문제를 소프트웨어적으로 해결
  • 실행 시간이 가장 짧은 프로세스에 프로세서 할당하는 세마포어 방법
  • 가장 짧은 평균 대기시간 제공
• Knuth's algo, Eisenberg and McGuire's algo, Lamport's algo

Dijkstra's Algorithm

flag[] 값	의미
idle	프로세스가 임계 지역(cs) 진입을 시도하고 있지 않을 때
want-in	프로세스가 임계 지역 진입 시도 1단계일 때 ("들어가고 싶어" 의사밝히는 단계)
in-CS	프로세스가 임계 지역 진입 시도 2단계 및 임계 지역 내에 있을 때 (들어가기 직 전)

while(j < n){
    /* 임계 지역 진입 시도 1단계*/
    flag[i] = "want-in"; // 의사 밝힘
    while(turn != i){ // 내 턴이 아니면 기다린다
        if(flag[turn] == "idle"){ // 현재 turn인 process가 idle일 때까지!
            turn = i; // 턴을 뺏음
        }
    }

    /* 임계 지역 진입 시도 2단계*/
    // 여기도 여러명이 진입할 수 있음
    flag[i] = "in-CS"; // "나 2단계야" 
    j = 0; // 카운팅 변수
    while(j < n && (j == i || flag[j] != "in-CS")){
        // 나일때는 체크안해도 되니까 패스하겠다
        // 내가 아닌 누군가가 2단계라면 빠져나오겠다
        j ++;
    } // 나혼자 2단계라면 j가 n이되어서 나온다.
}// j가 n보다 작으면(누군가 있으면) 다시 위로....
// j가 n이 되면 (나혼자 2단계~) cs 접근
// cs 앞 부분

// cs 뒷 부분
flag[i] = "idle";

SW Solutions

• SW Solutions들의 문제점
  • 속도가 느림
  • 구현이 복잡하다
  • ME primitive 실행 중 preemption 될 수 있다.
    • (지금까지 한 줄의 코드가 실행된다는 가정하에 진행한것. 한줄의 코드도 instruction으로 바꾸면 여러줄. 보장받지 못한다.)
    • 공유 데이터 수정 중은 interrupt를 억제해서 해결 가능하지만 overhead가 크다
  • Busy waiting
    • 기다리는데 뺑뻉 돌면서 기다리는거 while(true)
    • 비효율적이다