Peterson’s Solution
- 두 개의 프로세스에 대한 소프트웨어 기반 해결책
- int turn: 임계 구역으로 진입할 순번
- boolean flag[2]: flag[i]==true; 일때, 프로세스 P(i)가 임계구역으로 진입할 준비가 되어있음을 표시
- critical section은 main에 있는 것이 아닌, thread에 있는 것. 같은 thread가 여러개 있으면, thread 개수만큼 critical section이 존재.
flag, turn 설정
flag = [False, False]
turn = 0프로세스 P0
P0:
flag[0] = True
turn = 1
while flag[1] and turn == 1:
pass
# critical section
flag[0] = False프로세스 P1
P1:
flag[1] = True
turn = 0
while flag[0] and turn == 0:
pass
# critical section
flag[1] = False- flag와 turn 전역변수를 사용, critical section의 3가지 조건 (Mutual Exclusion/ Progress/ Bounded Waiting)을 모두 만족.
- flag[i]: i 번째 프로세스가 임계영역을 사용하겠다고 알림. 임계영역을 사용할 때는 flag[i]==True가 됨.
- turn: 어떤 프로세스를 실행 할지 결정하는 변수
Problem of Peterson's Solution
while flag[0] and turn == 0:
pass- cpu 스케줄링에 의해 각 프로세스가 진행되게 되는데, 프로세스는 임계영역에 들어가기 위해 위의 무한루프를 돌며 임계영역 직전에 머무른다. 이 무한 루프에 cpu 자원을 할당하고 사용하고 있으므로 문제가 발생. 이 현상을 Busy Waiting 이라 함.
- busy waiting : 계속 무한루프를 돌면서 다른 thread에게 cpu를 양보하지 않는 것.
Bakery Algorithm
- 두 개 이상의 프로세스가 동작할 경우의 알고리즘
- 가장 낮은 번호를 받은 프로세스가 먼저 critical section에 입장.
- 번호는 증가하는 형식으로 부여. but 우연히 같은 번호를 받을 수 있음.
Dekker's Algorithm
- flag, turn 변수로 critical section에 들어갈 프로세스(thread)를 결정.
- flag: 프로세스 중 critical section에 들어가길 원하는 프로세스를 표시
- turn: 누가 critical section에 들어갈 차례인지 표시.
Synchronization Hardware
- Uni-processors(단일 처리기) 같은 경우 critical section일 때, interrupt를 disable 하면 됨. but 다중 처리기 환경에서는 비효율적.
-> interrupt를 disable를 하라는 메시지를 모든 처리기에 전달해야되고, 메시지 확인을 위해 ciritcal section에 들어가는 것을 지연하기 때문 - 따라서 하드웨어들은 동기화 문제 해결을 위해 TestAndSet()/ Swap() 이라는 명령어 사용
TestAndSet() Instruciton
- target 변수를 true로 변환하고 이전 값을 반환
- target을 true로 바꿀 때는 연산의 atomicity를 보장해야 함. (연산에서 interrupt가 걸리면 안됨)
- 처음 lock 변수는 false로 초기화 돼있음. 처음 TestAndSet() 함수에 lock이 들어가면 false가 리턴, 그 이후 true가 리턴. 맨 처음에 들어온 process는 ciritical section에 들어옴
- context switch 가 일어나도 lock은 계속 false 상태 -> 다른 프로세스들은 while loop를 돌게 됨.
- but) 임의의 순서대로 critical section에 들어가기 때문에 어느 한 프로세스는 계속 기다리는 경우가 생길 수도 있음. 따라서 bounded waiting을 만족시키지 못하는 문제 발생.
Swap() Instruction
Semaphore
- semaphore는 깃발 이라는 뜻!
- 기찻길이 있다고 생각해보면, 기찻길이 공유하는 부분이 critical section임. 즉 critical section에서 기차가 지나가도 되는지 안되는지 알려주는게 semaphore라고 이해하면 쉽다.
- Semaphore 접근 함수 ( wait() = P / signal() = V ): wait을 사용하면 세마포어 변수 S가 -1이 되고, signal은 +1을 해줌.
Semaphore 구현
- Counting semaphore:
도메인이 제한 없는 세마포어 (ex) 0~10까지 값을 갖음. 여기서 세마포어는 단순 공유자원의 개수를 나타냄.
생산자, 소비자 문제 해결 가능 - binary semaphore: 0 or 1 값만 는 세마포어. 상호배제, 동기화 목적으로 사용
- mutex= mutual exclusion (S로 해도 상관 없음)
Busy Waiting Semaphore
No Busy Waiting Semaphore
- block(): wait() 함수 내부에서 실행. list에 자신을 등록하고 sleep()하는 함수.
- wakeup(): signal() 함수 내부에서 실행. 대기하고 있는 프로세스가 있으면 그 중 한 프로세스를 깨워준다.
Deadlock and Starvation
- Deadlock: 두 개 이상의 프로세스들이 절대 일어나지 않을 사건을 기다리는 상태 (ex) 프로세스 p1이 자원 a를 가지고 자원 b를 기다림 & 프로세스 p2는 자원 b를 가지고 자원 a를 기다림.
- Starvation : 특정 프로세스가 자원을 할당받지 못하면 끝없이 기다리는 상태에 빠지는 것
Classical Problems of Synchronization
- 동기화로 인해 발생하는 대표적인 문제들:
• Producer and Consumer Problem with Bounded-Buffer
• Readers and Writers Problem
• Dining-Philosophers Problem
Producer and Consumer Problem with Bounded-Buffer
- 생산자는 원소를 생성, buffer에 빈공간이 생길 때까지 기다림 -> 빈 공간이 생기면 다시 mutex를 기다림 -> mutex를 획득하면 버퍼에 원소 추가
- buffer에 원소를 추가할 시, mutex를 놓아주고 full semaphore(buffer에 존재하는 원소의 개수)를 늘려줌
Readers and Writers Problem
- reader는 데이터를 읽는 프로세스 / writer는 읽고 수정하는 프로세스 (데이터의 수정 여부)
- 다수의 독자와 저자가 하나의 공유 데이터에 접근하는 경우 발생
- 여러 개의 readers가 공유 데이터에 접근하는 경우는 문제 X but 하나 이상의 writer가 개입하는 경우 데이터의 일관성이 무너진다
->sol:
- writer가 공유 데이터에 접근 준비를 안했다면 reader가 기다리는 시간을 길게 해서는 안됨.
- writer가 준비되었을 때 바로 데이터를 읽고, 수정하게 해줘야 됨
- but) 한 개 이상의 reader가 데이터를 읽는 작업을 수행 할 때, wirter의 개입은 배제될 가능성-> writer 측면에서 starvation을 일으킬 수 있음
-> Final Exam에는 안 나옴.
The Dining-Philosophers Problem
- 철학자 5명이 테이블에 앉아 있음.
- 각 철학자들은 식사를 위해 2개의 젓가락을 필요로 함. 자신의 왼쪽과 오른쪽 젓가락을 집어들 수 있음.
- 철학자는 한 번에 하나의 젓가락만 집어들 수 있음
- 철학자는 식사를 안하는 동안엔 생각을 함. 생각 중엔 다른 철학자와 교류 X
-> Deadlock과 Starvation을 발생 X 면서 철학자들이 식사할 수 있는 방법
-> 세마포어는 5개의 젓가락임.
- 인접한 두 철학자가 동시에 식사하지 않는 건 보장되지만, 각 철학자가 동시에 자신의 왼쪽의 젓가락을 드는 경우 Deadlock 발생. -> 알고리즘 사용 불가.
공부방