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
최초로 N개의 프로세스의 ME문제를 SoftWare(SW)적으로 해결
각 프로세스마다 idle, want-in, in-CS의 세 가지 종류의 flag 모두 보유
flag[] 값 | 의미 |
idle | 프로세스가 Critical Section(임계지역) 진입을 시도하지 않고 있을 때 |
want-in | 프로세스의 CS(임계지역) 진입 시도 1단계일때(진입의사 알림) |
in-CS | 프로세스의 CS(임계지역) 진입 시도 2단계 및 CS내에 있을때(진입 직전) |
SW 기반 Solution 문제점
•
속도가 느림
•
구현 복잡
•
ME primitive 실행 도중
Preemption(선점) 될 수 있음
•
Preemption(선점) 될 경우,
공유 데이터 수정 중에는 interrupt를 억제해서 문제 해결 가능
But, Overhead 발생
•
Busy Waiting
◦
기다리면서 루프를 도는 것(비효울적)