정규 세마포를 이용해서 다중 세마포가 어떻게 구현될

chapter 6. 프로세스 동기화 연습문제

6.1. 두 개의 프로세스를 위한 임계 영역 문제에 대한 Dekkers 알고리즘이, 임계영역 문제의 세 가지 요건을 모두 충족시킴을 증명하라.

1. 상호배제 

-> 프로세스는 상대 프로세스가 들어가있는지를 flag[j] 로 확인할 수 있다. 이 값이 false 일 때 까지 계속 대기 하기 때문에 상호배제를 충족시킬 수 있다. flag[j]가 true 값을 가질 때는, j 프로세스가 임계영역에 들어가 있다는 뜻이고, j 가 작업을 끝내고 나올 때 이 값을 false 로 바꾸기 때문에 임계영역에는 동시에 들어가지 않는다.

2. 진행, 한정된 대기

-> 프로세스는 임계영역에서 나오기 전에, 다른 프로세스에게 turn 을 넘긴다. 그렇기 때문에 기다리던 프로세스들도 반드시 임계영역으로 진입할 수 있다. i 프로세스가 while(flag[j]) 에서 j 프로세스가 끝나기를 기다리고 있다고 가정한다. j 프로세스는 임계영역에서 나오면서 turn 을 i 로 넘기고 자신의 flag를 false로 바꿀 것이다. 기다리고 있던 i 프로세스는 while 문에서 벗어날 수 있으며, turn 이 j 가 아니기 때문에 조건문을 지나 임계영역으로 진입할 수 있다.

6.2. 다중 처리기 시스템을 위한 동기화 프리미티브를 구현할 때 인터럽트를 사용하는 것이 부적합한 이유를 설명하시오.

-> 다중 처리기 환경에서는 모든 처리기에서 인터럽트를 금지해야만 하는데, 이는 매우 어려운 작업이며 성능을 심각하게 감소시킬 수 있다. 따라서 이를 해결하기 위해 spinlocks 과 같은 다른 락킹 기법을 제공한다.

6.3. 최소 기다리는 시간이 n-1 번인 n개의 프로세스 임계영역 문제에 대한 올바른 소프트웨어 해결 방안을 제시한 사람은 Eisenberg와 McGuire 였다. 이 알고리즘이 임계영역 문제가 요구하는 세 가지 요건을 모두 충족시킴을 증명하시오.

->1. 

6.7. 연습문제 4.12 는 부모 스레드가 계산 결과를 출력하기 전에 자식 스레드가 종료하기를 기다려야 한다. 자식스레드가 종료하기를 기다리지 않고, 자식스레드가 Fibonacci 수를 계산하자마자 부모 스레드가 접근할 수 있게 하려면, 이 문제의 해결방안을 어떻게 수정해야 하는가? 

-> 자식 스레드와 부모 스레드간 세마포어를 이용한다. 자식 스레드가 먼저 락을 얻어 연산을 수행하고, 부모스레드는 wait 연산으로 락을 얻을 때 까지 기다린다. 자식 스레드가 fibonacci 를 다 계산하고 난 후, signal 을 호출하여 락을 반납하게 한다. 부모스레드가 락을 얻으면 결과를 출력하도록 한다.

6.9. 서버는 개방된 연결의 개수를 제한하도록 설계될 수 있다. 동시 연결의 개수를 제한하기 위해 서버가 세마포를 어떻게 사용할 수 있는가?

-> 카운팅 세마포를 사용하여 연결 개수를 조절할 수 있다. 가용한 연결 개수가 없을 때, 세마포의 값이 0 이 아닌 양수가 될 때 까지 대기하도록 만들 수 있다.

-> 세마포는 연결 가능한 소켓의 개수만큼 초기화 되고, 소켓이 연결되면 acquire() 가 호출된다. 연결이 호출되면 release() 가 호출된다. 만약 시스템의 모든 소켓이 연결되었을 경우, 현재의 연결이 종료되고 release() 가 호출될 때 까지 다음 acquire()은 블락된다.

6.11. wait() 와 signal() 연산이 원자적으로 실행되지 않으면 상호 배제가 보장될 수 없음을 보여라.

-> wait()과 signal() 연산은 프로세스들이 공유하는 정수 변수 S 를 증감하는 역할을 한다. 간발의 차로 한 프로세스가 S 변수를 변화시키고 있는 과정에서 다른 프로세스가 wait() 혹은 signal() 연산을 수행하는 경우가 생길 수도 있으므로, 상호 배제가 보장될 수 없다.

6.12. 다중 처리기 환경에서 TestAndSet() 명령을 사용해 wait() 와 signal() 세마포 연산을 구현하는 방법을 보여라. 해결방안은 바쁜 대기를 최소화해야한다.

-> 바쁜 대기를 최소화 하기 위해서, 교재의 세마포 대기큐 개념을 쓰고, 조건을 조금 고쳐줬다. TestAndSet() 연산에 이용되는 lock 이라는 전역 변수는 false로 초기화 된다.

-> TestAndSet 연산은, 매개변수의 값을 true 로 바꾸고, 처음 받았을 때의 값을 반환한다. 처음 임계영역에 진입한 프로세스는 lock이 false이기 때문에 line 10에서 false를 리턴받아 임계영역에 바로 들어간다. 다음에 프로세스가 line 10에 도달했을 때에는 lock이 true 로 바뀐 상태이다. value 값을 하나 감소시키고, list(대기큐) 에 들어가고 봉쇄된다.

-> 임계영역에서 실행을 끝마친 프로세스는 대기큐에 들어가있는 프로세스가 있다면 깨워서 임계영역에 들어갈 수 있게 하고, 아무런 프로세스가 없다면, lock을 반환한다.

6.13. 모니터의 wait() 와 signal() 연산을 await(B) 라는 단일 연산으로 교체하고자 한다. 여기서 B는 일반적인 boolean 수식이며, await(B) 를 실행시킨 프로세스를 B가 true 가 될 때 까지 기다리게 만든다.

a. readers-writers 문제에 대한 해결 방안을 구현하는 모니터를 이 기법을 사용해 작성하시오.

-> 

b. 일반적으로 이 기법이 효율적으로 구현될 수 없는 이유를 설명하시오.

-> 

c. 이 기법이 효율적으로 구현되기 위해서는 어떠한 제약조건이 await 명령문에 가해져야 하는가? 

->

6.15. 모니터의 signal() 연산과 세마포에서 정의한 signal() 연산이 어떻게 다른지 설명하시오.

-> 세마포의 signal() 은 프로세스가 자신의 락을 방출하는 의미이다. 그렇기에 세마포의 signal 연산은 항상 세마포의 상태에 영향을 준다고 볼 수 있다. 반면, 모니터의 signal() 연산은, 정확히 하나의 보류된 프로세스를 재개시키며, 보류된 프로세스가 없으면 아무런 동작을 하지 않는것과 같다. 또한 모니터에서는 signal()을 보낸 프로세스는 재개된 다른 프로세스가 모니터를 떠날 때 까지 대기하거나 또는 다른 조건을 기다려야만 한다.

6.17. 동기화 프리미티브가 사용자 수준 프로그램에서 사용되는 경우, 단일 처리기 시스템에서 인터럽트 불능을 이용하여 동기화 프리미티브를 구현하는 것이 왜 부적당한지 설명하시오.

-> 인터럽트 불능으로 인해 타이머 인터럽트를 불능으로 만들 수 있고, 문맥교환이 일어나는 것을 막을 수 있다. 그러므로, 처리기를 사용하는 것을 허용한다. 다른 프로세스를 실행하는 것 없이. (한 프로세스만이 처리기를 사용할 수 있게 만든다.)

6.18. 어떤 시스템에는 P1, P2, ... PN 프로세스들이 있고 이들은 각각 고유한 우선순위 번호를 가지고 있다. 할당 순서를 결정하는 데 우선순위 번호를 사용해 세 개의 동일한 프린터를 이들 프로세스들에게 할당하는 모니터를 작성하시오.

-> 

6.19. 경쟁 조건이 발생할 가능성이 있는 커널 자료구조 2개를 기술하시오. 경쟁 조건이 어떤 경우에 발생할 수 있는지에 대한 설명이 반드시 포함되어야 함.

-> 시스템의 모든 열린 파일리스트를 유지하는 커널 자료구조 - 두 프로세스가 동시에 파일을 열려고 할 때, 리스트에 대한 개별적인 갱신이 경쟁조건을 일으킬 수 있다.

-> 메모리 할당을 관리하는 자료 구조, 프로세스 리스트를 유지하는 자료구조

6.23. 한정된 대기 요구 조건을 충족하는 상호 배제를 제공하기 위해 swap() 명령이 어떻게 사용될 수 있는지 설명하시오.

-> 교재의 TestAndSet() 명령어처럼, 최소한 n-1 번 안에는 대기하고 있는 모든 프로세스들이 임계영역에 진입할 수 있도록, waiting[] 배열을 추가하고, line 7~13 부분을 수정했다.

-> swap() 연산은, 임계영역에 다른 프로세스가 들어가 있을 때 '상호배제'를 충족시키는 역할을 한다. 전역변수 lock 은 초기값이 true 이지만, 누군가 임계영역에 진입했을 경우에true가 된다. 임계영역에 들어가있는 프로세스를 제외하고, 각 프로세스가 가지고 있는 지역변수 key는 현재 true 이다. 그렇기 때문에, 대기할 때에는 항상 두 값이 같다. swap 연산은 다른 프로세스들이 락이 해제될 때 까지 대기하도록 만드는 역할을 한다.

6.24. Windows Vista~~

6.26. Readers-writer 문제에서 공평성과 처리량 간의 균형을 논의하시오. 기아 현상을 유발하지 않는 readers-writers 문제의 해결책을 제시하시오.

-> 공평성과 처리량은 서로 충돌될 수 있다. reader-writer 문제에서는 기아현상이 유발되는데, reader들의 작업이 처리되는 도중에 writer는 중간에 낄 수 없고, writer가 준비되면 reader들은 임계영역에 들어갈 수가 없기 때문이다. 이는 결국 공평성이 떨어지는 것이다. 반면 한꺼번에 쭉 처리하기 때문에 처리량은 좋아질 수 있다.

-> reader 와 writer 모두 쓰기에 대한 세마포어를 사용하면 된다. 대기하던 writer와 readers들은 쓰기 작업이 끝날 때 까지 기다린다. 임계영역에 있는 writer가 signal을 호출하면, 스케쥴러의 결정에 따라 대기하던 writer든, reader들이든 누군가 임계영역에 진입하게 된다. reader와 writer들이 번갈아가면서 임계영역에 진입할 수 있다는 점에서 기존의 방법과 다르며 기아현상을 해결할 수 있다.

6.29. 동일한 유형의 동기화 문제를 푸는 데 사용될 수 있다는 측면에서 모니터와 세마포어가 동등함을 보이시오.

-> 모니터의 wait 은, signal 이 호출될 때 까지 보류 되어야 한다는 것을 의미한다. signal이 늘 하나의 프로세스를 재개시키기 때문에, 재개시킬 프로세스가 없다면 아무것도 하지 않는 것과 같다.

-> 그와 조금 다르게 세마포어의 signal은 늘 세마포의 상태에 영향을 준다(호출되면 값을 1 올린다). 대기하는 프로세스는 wait 연산 안에서 세마포어 값이 1 이 될 때 까지 바쁜 대기를 하고 있기 때문에 signal 이 호출되면 바로 임계영역으로 진입한다. 하지만, wait 연산 안에서 대기하는 프로세스가 없는 경우에는 값을 올려도 아무런 일이 일어나지 않는다. 그냥 값만 올라간 것 뿐이다.

-> 따라서, 각각의 wait 과 signal 연산의 방식에는 차이가 있지만 결국 같은 결과를 보인다는 점에서 동등하다.

6.32. 유한 버퍼 문제를 위한 모니터 코드를 작성하시오. 단, 버퍼들은 모니터 내부에 내장되어 있다.

6.33. 연습문제 6.32 의 유한 버퍼용 모니터는 그 안에서 상호 배제를 아주 엄격히 시행하므로 버퍼 개수가 적은 문제들에게만 적합하다.

a. 위의 설명이 과연 타당한 것인지에 대해 논하시오.

-> 위의 코드에서, 생산자는 자신의 value 값을 버퍼에 그대로 복사하고, 소비자는 그것을 읽는 형태로 작업이 이루어지고 있다. 유한 버퍼인 상태에서는, 버퍼 개수가 크다는 것은, 모니터 내의 소비 혹은 생산의 작업을 할 때, 오랜시간 머무른다는 것과 같다. 따라서 복사를 하는 데 드는 시간적인 비용이 많이 들기 때문에 그만큼 처리량이 줄어들 수 있다.

b. 보다 많은 개수의 문제를 위한 새로운 기법을 설계하시오.

-> 버퍼에 데이터를 '복사'해서 옮기는 것이 아닌, 옮기고 싶은 데이터의 '주소값'을 버퍼에 저장하는 방법으로 바꾼다면(즉, 포인터를 사용한다면), 상대적으로 더 효율적인 방법이 될 수 있다.

**그냥 공부한 내용 정리하려고 쓴 거라서 정답인지 아닌지 모릅니당**