[13주차]Bakery Algorithm

두 개 이상의 프로세스가 동작하고 있을 경우의 알고리즘

 

가장 낮은 번호를 받은 프로세스가 가장 먼저 임계 영역에 들어갈 수 있음

 

번호 부여는 증가하는 방식으로 하지만 우연히 같은 번호를 받을 수 있음 -> 은행에서는 번호표 지급기가 1개뿐인 이유

---

Bakery Algorithm

• Notaion <= lexicographical order (ticket #, process id #)

• (a, b) < (c, d)는 a와 b를 비교하고 b와 c를 비교한다는 의미
• max는 이중 가장 큰 값을 의미

• 공유 데이터(shared data)

• boolean choosing[n]; 
• int number[n];
• 이 두 값의 초기값은 각각 모두 false와 0

• 알고리즘 코드

1. 각각의 프로세스들이 이 형태의 구조로 되어있어서 각자가 알아서 판단
2. 하나의 프로세스만 임계 영역에 들어감 - 프로세스들은 각자의 임계 영역이 있음
3. choosing을 true로 만듦 -> 이제 번호표를 받을 것이라는 의미
4. 현재 대기 중인 가장 큰 번호보다 1이 큰 number를 받음
5. 번호를 받은 후에는 choosing이 flase가 됨
6. for문에서 0~n까지의 번호를 확인하게 됨
7. 첫 번째 while문은 어떤 프로세스가 번호표를 받고 있는 중에는 잠시 대기한다는 의미
8. 두 번째 while문은 서로를 존중해주는 알고리즘
9. number가 0이라는 것은 아직 번호표를 받지 못했거나 이미 끝난 프로세스라는 의미(임계 영역에 들어가지 않겠다는 의미)
10. 어떤 번호가 0이 아니면 현재 자신의 번호와 비교하여 작은 지를 비교 -> 작다면 우선순위에서 밀리므로 대기
11. 만약 내 번호가 n개의 프로세스들의 번호 중에 가장 작다면 임계 영역에 들어간 후 번호를 0으로 바꿈
12. 우연하게 같은 번호의 번호표를 받을 경우에는 프로세스 고유번호를 비교하여 더 작은 프로세스가 먼저 임계 영역에 들어갈 수 있음
13. choosing과 number 또한 critical section문제를 가지기 때문에 이러한 조건을 준 것(동시에 같은 번호를 받을 수 있음)
14. 앞 시간에 배운 3가지 조건을 만족하는지 확인해볼 것

• Synchronization Hardware

• 베이커리 알고리즘은 훌륭하고 좋은 알고리즘(n개의 프로세스가 동시에 작동 가능) -> 모두 SW적으로 구현이 되어 있으므로 복잡함
• 이런 것들을 제공하는 하드웨어적인 명령어가 있고 제공받는 명령어가 CPU에 있다면? - Synchronization Hardware
• 조건을 판별해본 뒤에 한 word의 값을 바꾸거나 word사이의 내용을 바꿔치기하는 작업들을 Atomic 하게 처리
• Synchronization Hardware는 자신이 어떤 일을 하는 동안에 쪼개지지 않고 한 번에 실행되어야 함
• ex) test and set이라는 명령어

1. CPU의 하나의 명령어 - 쪼개지지 않고 atomic 하게 실행
2. 어떤 CPU가 혹은 어떤 hardware 시스템이 test and set 명령어를 지원한다면 쉽게 critical section을 구현 가능
3. lock이라는 boolean변수를 선언하고 TestAndSet(&lock - 주소)로 사용
4. 두 프로세스의 처리 속도가 다른 경우(Pi가 빠름(먼저 처리), Pj가 그 후)
5. TestAndSet에 들어간 Pi의 rv(리턴 값)가 flase가 되고 lock값은 ture가 됨 -> 그 후 임계 영역에 들어감
6. Pj는 그 후에 실행되는데, 아직 Pi가 임계 영역을 끝내지 않았으므로 lock은 아직 true이고 따라서 rv값 또한 true -> while문에서 대기
7. Pi가 나오면 lock이 false가 되고 Pj가 while문을 탈출하게 됨 -> 임계 영역 접근 가능
8. Pi는 Pj가 실행되는 동안 while문에서 대기

• 두 프로세스의 속도가 같은 경우를 생각해보자
• Swap이라는 명령도 존재하므로 232 page 환인하고 예제 해결해 볼 것

---

Semaphores(정수 변수)

• 영역을 나눠서 각각 하나씩 처리하는 것은 같지만(atomic) 실제로 돌아가는 것은 조금 다름
• 임계 영역 중 하나를 제외한 모든 프로세스들이 while문에서 대기 - Busy waiting(바쁜대기)

• 대기만 하는 것이 아니라 대기하는 동안 계속 무언가를 검사해야 함 - CPU 사용
• 동작을 하지는 않지만 동작하는 순간을 기다리기 위해 CPU를 사용 - CPU는 바쁘지만 일은 못함
• 불필요한 CPU의 동작이 문제

• 단지 두 개의 개별적인 atomic 한 연산(wait와 signal)을 가지고 접근 가능

• wait(S)

1. 만약 S값이 0보다 작거나 같으면 동작을 하지 않음(no-operation)
2. while문에 대기시키지 말고 no-op부분에서 할 수 있는 일을 시키라는 의미
3. S가 0보다 작거나 같은 동안에는 no-op를 실행하고 벗어나면 S값을 줄임

• Signal(S) : 단순하게 S를 증가시키는 연산

• Critical Section of n Processes

• 공동 semaphore인 mutex라는 변수를 공유 initially mutex = 1(1로 초기화)
• 사용 방식

1. P0가 접근 - 데이터 구조에 mutex를 1로 주고 wait에 넣음
2. mutex가 0보다 작거나 같지 않으므로 mutex 값을 1 감소시키고 critical section에 들어감
3. 그 후 P1이 들어왔을 때 mutexr값이 0이므로 no-op 실행(waiting 시킴 - CPU를 사용하지 않고 대기)
4. P0가 critical section을 벗어나면 mutex를 1 증가시킨 후(signal) remainder section실행
5. 그 순간 대기 중이던 P1은 waiting상태에서 ready queue로 넘어감
6. 어느 순간에 P1이 다시 CPU를 차지하게 되면 공유 변수인 mutex가 1이므로 wait에서 1 감소시킨 후 critical section에 들어갈 수 있음

• Semaphore Implementation

• semaphore의 정의

1. value값을 줌 - S
2. 프로세스 리스트를 만듦 -> block 시켜서 suspend시킴(waiting영역에 넣음) - 동작을 안 함
3. busy waiting 문제 해결

• 자세하게 살펴보자

1. wait(S)에서 Semaphore의 value값을 1 감소시키고 0보다 작을 경우 이 프로세스를 wait list에 집어넣고 block시킴(waiting)
2. signal(S)에서 value값을 1 증가시키고 만약 0보다 작거나 같을 경우 wait list에서 제외시키고 wakeup시킴
3. 운영 프로세스가 동작하는 것이 아니라 운영체제가 이 동작들을 맡아서 처리
4. 효율적으로 동기화 문제를 해결할 수 있음

• Semaphore as a General Synchronization Tool

1. 하나의 프로세스는 우선적으로 자신의 일을 하고 나머지 프로세스는 wait를 시킴
2. Pi가 critical section을 수행하는 동안 Pj는 wait
3. Pi가 다 끝난 후 signal -> Pj는 대기상태에서 나와 자신의 일을 수행
4. 운영체제 기능을 이용하여 Busy waiting을 안 하게 하는 것

• Deadlock and Starvation

• semaphore가 2개인 경우

1. P0는 S를 먼저 wait 하고 Q를 그 후에 wait 함, P1은 반대로 수행
2. 수행을 마친 후 순서대로 signal을 해줌
3. 프로세스 하나가 먼저 수행된 후 다음 프로세스가 수행되면 상관이 없지만 한 줄씩 번갈아가며 수행된다면 문제가 생김
4. critical section에 들어가기 전, S와 Q가 0보다 작아지게 되므로 두 프로세스 모두 blocking 됨
5. 두 프로세스 모두 blocking 되어 누군가 꺼내주기를 기다리지만 나갈 수 없는 상태가 됨 - deadlock(교착) 상태
6. 프로세스가 실행되면서 정해놓은대로 잘 진행되지만 한 프로세스가 계속 blocking 당하는 상황 - starvation상태

• Two Types of Semaphores

• Counting semaphore(계수) - 정수값에 제한을 가지지 않음
• Binary semaphore(이진) - 0 또는 1로 한정 -> 구현하기 쉬움(계수 세마포어도 구현 가능)

---

Classical Problems of Synchronization

• Bounded-Buffer Problem

• 공유 데이터 : full, empty, mutex;
• 초기값 : full = 0, empty = n, mutex = 1
• Producer Process

1. 첫 번째 wait는 비어있는지를 확인하는 것 - 채울 것이 있는 상태인지
2. 두 번째 wait는 사용할 수 있는지를 확인하는 것
3. 첫 번째 signal은 critical section 사용을 끝냈음을 의미
4. 두 번째 signal은 다 채웠음을 의미

• Consumer Process

1. 첫 번째 wait는 채워져 있는지 확인
2. 두 번째 wait는 사용할 수 있는지 확인
3. 첫 번째 signal은 다 사용했음을 의미
4. 두 번째 signal은 하나를 다 비웠음을 의미
5. 잘 보고 이해해볼 것

• Readers-Writers Problem

• text 파일을 편집하는 중에 이 파일을 다른 사용자가 열려고 할 때

1. 접근을 아예 하지 못하게 하는 방법
2. 파일을 편집 중임에도 불구하고 읽게 해 줄 수는 있음
3. 어떤 방식이든 하나의 방법(알고리즘)을 정해놓고 세마포어로 어떻게 해결할 것인지 살펴보는 것은 우리가 해야 할 일

• 공유 데이터 : mutex, wrt;
• 초기값 : mutex = 1, wrt = 1, readcount = 0
• 흐름

1. writer가 공유데이터에 배타적으로 접근(두 개 이상이 동시에 쓸 수 없음)
2. 데이터를 두 개 이상이 읽고 있다면 쓰기는 안됨
3. 어떤 기준을 가지고 동작하는지를 잘 봐야 함
4. 이 기준은 언제든 바뀔 수 있으며 바뀔 때 이미 짜여 있던 코드를 수정할 수 있어야 함

• Writer Process

1. 세마포어의 값을 확인하고 쓸 수 있는 상태면 write 해줌
2. 그 후 signal - 끝났음을 알림
3. 쓸 수 있느냐 없느냐를 확인하는 것

• Reader Process

1. 쓰는 사람은 하나밖에 없지만 읽는 사람은 여러 명이 될 수 있음
2. 첫 번째는 readcounter를 변경하기 위함
3. if문은 readcounter가 1일 경우(첫 번째 read process인지를 물어보는 것)
4. 첫 번째 read process일 때, 쓰는 중인 프로세스가 있는지 확인하는 것 -> 있으면 기다림
5. read counter가 2 이상이면 signal을 거쳐 아래 내용을 수행 -> 2개 이상이면 안 기다리고 바로 넘어간다는 의미
6. 첫 번째 read process가 기다리는 중에 다음 read process가 들어오더라도 첫 번째 wait에서 대기
7. write process가 끝나면 내려감
8. signal로 인해 mutex가 증가하고 대기하고 있던 나머지 read process들은 모두 readcounter를 증가시키면서 reading is performed부분으로 한꺼번에 들어감 -> 두 개 이상의 read process들은 동시에 읽을 수 있음을 의미
9. read가 끝나면 readcount가 1 감소
10. write는 그냥 할 수 있으면 write 하는 것이지만 read는 위와 같이 동작
11. 한 줄 한 줄 의미를 확인하며 잘 생각해볼 것
12. 읽는 동안에 다른 readers와 writers는 어떻게 동작해야 하는지를 잘 생각해볼 것