Recap

CPU(프로세서)의 활용률을 높이기 위해 스케쥴링 알고리즘을 사용하는데, 데이터의 일관성을 유지하기 위해서 상호배제(실행중인 프로세스가 있으면, critical section에 다른 프로세스가 못 들어옴) 개념 필요 (Mutual Exclusion) 또한, 무한한 대기 없이 일정 시간이 지나면 critical section에 진입해야함(Bounding Waiting)

• Progress

ch6_part1에서 시작

Two Process ME

ME(Mutual Exculsion) version1

프로세스가 나의 turn이 아니면 while문 내에서 대기 CS에서 나오면, turn을 넘겨줌 P0가 CS에 진입하지 않으면, Progress 조건에 위배 → 완전한 ME가 아니다!

turn값은 어떤 프로세스가 진행할 차례인지 나타내는 값 → turn값이 1이면, P1차례 → turn값이 0이면, P0차례

ME version2

프로세스가 CS진입 전, flag(P0가 flag[1]을 == 상대의 flag)를 확인 → 상대 flag가 true면 대기, false면 flag[0](== 자신의 flag)을 true로 만들고 진입 CS에서 나오면, 자신의 flag(P0가 flag[0]을 == 자신의 flag)를 false로 전환 제3의 프로세스에 의해 Preemption(선점)이 발생하면, Mutual Exclusion(상호배제) 위배 → 완전한 ME가 아니다!

ME version3 flag[0]을 먼저 true로 설정(진입 의사를 밝힘) Preemption(선점)이 발생하면 → Progress조건 위반, Bounding Waiting 위반

Dekker’s Algorithm

윗 3가지의 불완전함을 데커 알고리즘에서 해결했다 turn, flag 모두 사용 vs [이전 : turn 또는 flag 사용 ]

EX)

• flag[1]이 true다 → P1이 CS에 진입의사가 있음
• turn값 → 어떤 프로세스가 진행할 차례인지 나타내는 숫자값
  • turn값이 1이면, P1이 CS에 진입
  • turn값이 0이면, P0가 CS에 진입

여기부턴 ch6_part2 내용

N-Process Mutual Exclusion

Dijkstra