병행프로세스

1. 임계구역문제 : 공영변수를 읽고, 테이블을 갱신하고, 파일에 쓰는 일을 하는 프로세스

 

1) 임계구역
(1) n개의 유기적 프로세스(cooperation process)으로 구성된 시스템
   ․ n개의 유기적 프로세스(cooperation process) {P0, P1,....,Pn-1}을 가정한다.
   ․ 각 프로세스는 임계구역(critical section)이라 불리우는 코드 세그먼트를 가진다.
   ․ 프로세스가 하는 일 : 공통변수를 읽고, 테이블을 갱신하고, 파일에 쓰는 등이다.
   ․ 시스템의 가장 중요한 특징 : 하나의ㅣ 프로세스가 임계구역에서 수행중일 때 다른 어떠한 프로세스도 이 임계 구역에서 수행될 수 없다.

 

(2) 프로세스에 의한 임계구역의 수행
   ․ 임계구역 문제는 프로세스들이 서로 유기적으로 사용해야 하는 프로토콜을 설계하는 데 있다.
   ․ 각 프로세서는 그 임계구역에 들어갈 수 있는지의 여부를 미리 요청하여야 한다.
     이런 요구를 구현하는 코드 구역을 진입구역(entry section)이라 한다.
   ․ 임계 구역 다음에는 출구구역(exit section)이 있다.
   ․ 나머지 코드는 잔류구역(remainder section)이라고 한다.
   ※ 프로세스에 의한 임계구역의 수행은 상호 배제적(mutually exclusive)이다.

2) 상호배제
   ․ 프로세서에 의한 임계구역의 수행은 상호배제적(mutually exclusive)이다??

 

(1) 상호배제(mutually exclusive) 문제
   ․ 임계구역문제 : 하드웨어에서 제공할 수 있는 명령이나 프로세서의 개수에 관한 가정에 제한을 두지 않는다.
   ․ 단위적 수행 : 기본적인 기계어 명령은 단위적으로 수행된다고 가정한다.
     2개의 기본적인 기계어 명령들이 동시에 수행된 결과는 어떠한 임의의 순서로 그들을 수행시킨 결과와 동일하다.

 

(2) 상호배제(mutullay exclustive)의 문제 요구사항

상호배제	프로세스 Pi가 임계구역에서 수행중일 때 다른 어떤 프로세서도 임계구역에서 수행될 수 없다.
진 행	임계구역에서 수행되는 프로세스가 없고 여러 개의 프로세스들이 임계구역에 들어오고자 할 때에는 잔류구역에서 수행되지 아니한 프로세스들만이 다음에 누가 임계구역에 들어갈 것인가 하는 결정에 참여할 수 있다. 또한 이 결정은 무한정 미루어질 수 없다.
제한대기	한 프로세스가 임계구역에 대한 요청 후부터 요청의 수락까지의 기간 내에 다른 프로세스가 임계구역을 수행할 수 있는 횟수에는 제한이 있어야 한다.

2. 상호배제

 

1) 상호배제를 보장해주는 초기 알고리즘
(1) 프로세스의 표시 
   ․ 프로세스는 P0와 P1으로 번호를 붙이고 알고리즘이ㅣ 주어졌을 때 단지 공통변수들만을 정의하고 프로세스는 Pi로 표시한다.
   ․ 편의를 위한 프로세스 표시법
     Pj는 j = 1 - i인 다른 프로세스를 표시

 

(2) 프로세스 Pi의 일반적인 구조
   ․ 진입구역(entry section)과 출구구역(exit section)으로 코드 중의 중요한 세그먼트임을 표시하기 위해서 네모 안에 나타낸다.
   ․ 편의를 위한 프로세스 표시법   

2) 두 개의 프로세스를 위한 상호배제
(1) 상호배제를 보장해 주는 초기 알고리즘 1
   ․ 처음에 접근은 프로세스가 0(혹은 1)으로 초기화 된 공통정수변수 turn을 공유하도록 하는데서 시작한다.

   ․ 아래 방법은 한 프로세스만이 임계구역 내에 있을 수 있게 한다.   

   ․ 알고리즘 1은 임계구역의 수행에 엄격한 프로세스의 교대를 요구하기 때문에 진행요구를 만족시키지 못한다.

 

※ 알고리즘의 예
   turn = 0 이고 P1이 그 임계구역 내에 들어가고자 할 때에는 비록 P0이 임계구역의 잔류구역부분 수행하는 도중이라고 할지라도 들어갈 수 없다.

 

(2) 상호배제를 보장해 주는 초기 알고리즘 2
   ․ 알고리즘 1에 대한 문제는 각 프로세스(process)의 상태를 기억하지 않고 어떤 프로세스만이 임계구역(critical sectin)에 들어갈 수 있는지 만을 기억하는 데 있다.
   ․ 알고리즘 1에 의한 문제를 해결하기 위하여 변수 turn을 다음 배열로 대치한다.

   ․ 배열의 요소는 false로 초기화됩니다. 만약 flag[i]가 true이면 프로세스 Pi가 임계구역에서 수행중이다.
   ․ 프로세스 Pi의 일반적인 구조

   ․ 알고리즘 2는 오직 하나의 프로세스만이 그 임계구역을 수행한다는 것을 보장하지 못한다.
※ 알고리즘 2의 한계  

   ․ 위의 사례에서 P0과 P1이 상호배제(mutual exclusion) 요구를 깨고 둘 다 임계구역에 들어감을 알 수 있다.
   ․ 이 알고리즘은 두 프로세스의 정밀한 타이밍(timing)에 결정적으로 좌우됨을 보여준다. 
   ․ 이 순서는 여러 개의 프로세스가 동시에 수행되거나, T0가 끝난 직후 인터럽트 (타이머 인터럽트 등)가 발생할 때(또는 T2이후 다른 인터럽트가 발생할 때) CPU가 다음 프로세스로 전화되는 것과 같은 결과를 가져오게 된다.

 

(3) 상호배제를 보장해주는 초기 알고리즘 3
   ․ 알고리즘 2에 의한 문제는 프로세스는 Pi에서 프로세스 Pj가 변수 flag[j]의 상태를 변경하기 전에 Pj의 상태에 대한 검사를 하는 데 있다.

   ․ 위의 설명을 바탕으로 알고리즘 3의 프로세스를 예상해 봅시다.
    프로세서 Pi를 작성한 후 실제 알고리즘 3과 비교해 보세요.

※ 알고리즘 3의 특성
   ․ 알고리즘3 에서는 flag[i]를 true로 만들어 임계구역에 들어가고자 하는 신호를 보낸다
   ․ 다음은 다른 프로세스 또한 임계구역에 들어가기를 원하지 않는지를 검사한다.
   ․ 만일 원하는 다른 프로세스가 있는 경우에는 기다린다.
   ․ 다음에 임계구역을 수행하고, 이곳에서 벗어날 때 flag를 false로 만들어(기다리고 있는)다른 프로세스로 하여금 임계구역을 수행할 수 있도록 허락한다.  

 

§해결방법은 알고리즘 2와는 달리 상호배제의 요구조건은 만족하지만 진행요구를 만족하지 못합니다. 
   이 문제를 해결하기 위해 다음 수행순서를 생각해 봅시다.

     여기서 P0과 P1은 각각의 while 문장에서 영원히 루핑(looping)을 수행하게 된다.

 

(4) 상호배제를 보장해 주는 초기 알고리즘 4
   ․ 임계구역 문제는 간단히 해결 할 수 있는 문제는 아닙니다.
   ․ 마지막으로 타당한 해결책은 기본적으로 알고리즘 3과 알고리즘 1의 약간 수정된 상태를 조합한 것이다.   

   ․  초기에는 flag[0] = flag[1] = false이고, turn의 값은 어떻든지 상관이 없다. 그러나 0 또는 1의 값이어야 한다.
   ․ 프로세서 Pi의 일반적 구조

2) 두개의 프로세스를 위한 상호배제  

  >> 명제 1 증명
     ․ ①의 성질을 증명하기 위해서는 각 Pi가 flag[j] = false이거나 turn = i일 때에만 임계구역에 들어간다는 점에 주목해야 한다
     ․ 만약 두 프로세스가 임계구역을 동시에 수행하게 될 경우에는 flag[0] = flag[1] = true가 될 것이다.
     ․ 만약 Pj가 flag[j] = true인 상태로 while 문장을 수행중일 때라면 turn 〓 i이거나 turn = j일 것이 turn = i일 때에는 Pi가 임계구역에 들어가게 되고 turn 〓 j이면 Pj가 임계구역에 들어가게 된다. 
     ․ 일단 Pj가 임계구역에서 벗어난 후에는 flag[j]를 false를 만들어 주게 되므로 Pi가 임계구역에 들어갈 수 있게 된다. 
     ․ 바로 그 지점에서는 flag[j] = true이고 turn = j이며, 이 조건은 Pj가 임계구역 내에 있는 동안은 변하지 않으므로 그 결과 상호배제가 유지된다.     

    

>> 명제 2, 3 증명
     ․ ②와 ③의 성질을 증명하기 위해서는프로세스 Pi가 flag[j] = true와 turn = j 라는 조건을 가지고 while 루프를 계속 돌고 있을 때에만 임계구역으로의 접근이 방지됨을주목하여야 합니다. 
     ․ 이것이 유일한 루프(loop)입니다.  Pj가 임계구역에 들어갈 필요가 없을 때에는 flag[j] = false가 되며, Pi가 되며 임계구역에 들어갈 수 있게 됩니다. 
     ․ 만약 Pj가 flag[j] = true인 상태로 while 문장을 수행중일 때라면 turn = I이거나 turn = j일 것이 turn = i일 때에는 Pi가 임계구역에 들어가게 되고 turn = j이면 Pj가 임계구역에 들어가게 됩니다.
     ․ 일단 Pj가 임계구역에서 벗어난 후에는 flag[j]를 false를 만들어 주게 되므로 Pi가 임계구역에 들어갈 수 있게 됩니다.
     ․ 만일 Pj가 flag[j]를 true로 만들어 주어야 한다면, turn = i로 만들어 줄 수밖에 없습니다.
     ․ Pi가 while 문장을 수행하는 동안 turn의 값을 변화시키지 않기 때문에, Pi는 P가 많아야 한 번 임계구역에 들어간 후(제한된 대기조건)에는 임계구역에 들어갈 수 있게 됩니다(진행 요구조건).   
      ※ 위의 알고리즘은 제한된 대기(bounded waiting) 요구를 만족하지 못한다.

3) N개의 프로세스를 위한 상호배제 1
   ․ 이제 n개의 프로세스에 대한 임계구역 문제를 해결하는 알고리즘으로 확장해 봅시다.
(1) 알고리즘 5
   ․ 공통의 자료 구조   

    flag의 모든 요소는 초기에는 idle이다.  
    turn의 초기값은 상관이 없다. (0 과 n-1 사이의 값)  
   

※ 프로세스 Pi의 일반적인 구조     

      
    ․ 알고리즘 5가 옳다는 것을 증명해 봅시다.
     ① 상호배제(mutual exclustion)가 보장되어야 한다.
        * ①의 성질을 증명하기 위해서는 각 Pi가 모든 j ≠ i에 대하여   flag[i] ≠ in-cs일때에만 임계구역에 들어간다는 점에 주목해야 한다.  
        * flag[i] = in-cs는 Pi에 의해서만 수행 되며, flag[i] = in-cs일 때에만 Pi가 flag[j]를 검사하므로 그 조건이 성립된다.

 

     ② 진행요구(progress requiremet)가 만족되어야 한다.
       * ②의 성질을 증명하기 위해 turn의 값은 프로세스가 임계구역에 들어가고 나올때만 수정된다는 것에 주의해야 한다.
       * 어떤 프로세스도 임계구역에 있지 않거나 나오지 않을 때는 turn의 값은 불변이다.  
       * 순환순서(i, i+1, …, n-1, 0, …, i-1)에서 제일 처음으로 해당되는 프로세스가 임계구역에 들어 간다.  

 

     ③ 제한된 대기(bounded waiting) 요구가 만족됨을 보여야 한다.
       * ③의 성질을 증명하기 위해서 프로세스가 임계구역을 나올 때는 순환순서 내에서 처음의 경쟁자 프로세스를 단일 후계자로 지정하여 임계구역으로의 진입을 기다리는 어떠한 프로세스도 n-1번 이내에 진입하게 한다는 것을 보장함을 보여 준다. 
 
3) N개의 프로세스를 위한 상호배제 2
   ․ 알고리즘은 분산환경을 위해 개발되었습니다. 여기서 중앙 집중적인 환경에 국한시켜 알고리즘을 살펴보기도 합시다.

(2) 알고리즘 6
   ․ 제과점 알고리즘에 대해 알아 봅시다.      
 ○ 임계구역 문제에 대한 새로운 접근은 제과점 알고리즘(bakery algorithm) 이다.  
 ○ 제과점 알고리즘은 제과점, 아이스크림 가게, 정육점, 그리고 이와 유사한 상황에 보편적으로 사용되는 스케줄링 알고리즘에 그 기초를 두고 있다. 
 ○ 제과점 알고리즘은 분산환경을 위해 개발되었다. 

 

   ※ 중앙 집중적인 환경 국한시켜 알고리즘을 살펴봅시다. 
     ① 가게에 들어서자마자 각 고객은 번호를 부여 받는다.
     ② 가장 낮은 번호를 받은 고객이 그 다음 서비스를 받는다.  
     ③ 불행히도 제과점 알고리즘은 2개의 프로세스가 같은 번호를 받지 않게 된다고 보장할 수 없다. 
     ④ 같은 번호인 경우 더 낮은 이름을 가진 프로세스가 먼저 서비스를 받는다.  
     ⑤ Pi와 Pj가 같은 번호를 받고 i<j인 경우 Pi가 먼저 서비스를 받는다.  
  프로세스 이름은 고유하고 전부 순서가 매겨져 있으므로 이 알고리즘은 완전하게 결정적(deterministic)이다.  

    ․ 공통의 자료구조 및 편의를 위한 표기법 정의를 알아 봅시다.     

   ․ 공통의 프로세스 Pi의 구조를 살펴봅시다.     

   ․ 제과점 알고리즘 증명해 봅시다. 
   
 제과점 알고리즘이 옳다는 것을 증명하기 위해서는 
  ○ 첫 번째로 Pi가 임계구역에 있고 Pk(k ≠ i)가 이미 number[k] ≠ 0을 선택했을 때
     (number[i], i) < (number[k], k)가 된다는 것을 보일 필요가 있다.  
  ○ 알고리즘의 주어진 결과로부터 상호배제(mutual exclusion)가 만족됨은 쉽게 알 수 있다.  
  ○ 사실 Pi가 임계구역에 있고, Pk가 임계구역에 들어가려고 한다고 합시다.
     j = i에 대해서 Pk가 두 번째 while 문장을 수행할 때 
  
      * number[k] ≠ 0이고
      * (number[i], i) < (number[k], [k])임을 알 수 있다.  
  
      Pk는 Pi가 임계구역을 벗어날 때까지 while 문장에서 계속 돌게 된다. 
 
   진행요구와 제한된 대기요구가 만족되며 공정성이 유지된다는 것을 보여주기 위해서는 프로세스가 임계구역에 먼저 도착하면 먼저 서비스를 받는다.
   (first-come-first-served)는 사실에 주목함으로써 충분할 것이다.  

 

3. 임계구역의 하드웨어적 해결

 

1) Test-and-set 명령
(1) Test-and-set 명령의 정의  

(2) Test-and-set 명령의 특징
   ․ 하나의 명령 사이클(instruction cycle)내에서 이루어진다.
   ․ 2개의 Test-and-set 명령이 동시에 수행된다고 할 때(서로 다른 CPU에서)이는 어떤 임의적 순서에 의해 순차적으로 수행하게 되는 것이다.

(3) Test-and-set 명령의 수행
   STEP 1
   ․ 기계가 Test-and-Set 명령을 제공한다면, 상호배제는 false로 초기화한 부울 변수(boolean variable) lock을 선언함으로써 다음과 같이 구현된다.    

     STEP 2
   ․ 전역 부울 변수(global boolean variable) lock은 false로 초기화된다. 각 프로세스는 또한 지역 부울 변수(local boolean variable) key를 갖게 된다.

 

2) 모든 요구를 만족시키는 알고리즘 1
   ․ Test-and-set 명령을 사용하여 임계구역에서 필요한 요구를 모두 만족시키는 알고리즘을 살펴봅시다.
(1) 일반적인 자료 구조
  

(2) 프로세서 Pi 구조  

2) 모든 요구를 만족시키는 알고리즘 2
   ․ 프로세스 Pi 가 Test-and-Set 명령을 사용하여 임계구역에서 필요한 요구를 모두 만족시킨다는 것을 증명해 보도록 합시다.

 ○ 상호배제(mutual exclusion) 요구가 성립됨을 증명하기 위해서는 프로세스 Pi가 임계구역에 들어갈 수 있는 조건은 waiting[i] = false이거나 key = false일 때뿐이라는 것을 유의하여야 한다. 
    * Key의 값이 false로 되는 것은 Test-and-Set 명령을 수행함으로써 가능하다. 
    * 맨 처음에 Test-and-Set 명령을 수행하는 프로세스는 key = false인 것을 발견할 것이다. 
    * 다른 프로세스들은 모두 기다리게 된다.
    * waiting[i]는 어떤 다른 프로세스가 임계구역을 벗어났을 경우에만 false로 된다. 
    * 하나의 waiting[i]만이 true일 때 상호배제요구가 성립된다.  

  ○ 진행요구(progress requirement)에 대해서도 상호배제에 사용되는 인자들이 이용될 수 있다. 
    * 임계구역을 벗어나는 프로세스는 lock을 false로 만들거나 또는 waiting[j] = false로 만들어 주기 때문이다. 
    * 이 두 가지 모두는 기다리는 프로세스로 하여금 임계구역에 들어올 수 있도록 허락해 준다.  
  
  ○ 제한된 대기(bounded waiting)조건이 만족함을 보이기 위해서는 프로세스가 임계구역을 벗어날 때( i+1 , i+2 , …, n-1, 0, …, i-1 )의 순환순서로 대기하고 있는 프로세스들의 배열을 조사해야 한다는 점을 생각해야 한다. 
    * 진입구역에 있으면서(waiting[j] = true) 위 순서의 첫 번째에 위치한 프로세스가 다음 번에 임계구역에 들어갈 차례라는 것을 표시한다. 
    * 임계구역에 들어가기 위해 기다리는 모든 프로세스들은 n-1번째 안에 들어갈 수 있다.  
  
  ○ 프로세스 이름은 고유하고 전부 순서가 매겨져 있으므로 이 알고리즘은 완전하게 결정적(deterministic)이다. 

 

4. 세마포어-동기화 도구
   ․ 상호배제(mutual exclusion)의 해결은 좀더 복잡한 문제에서는 일반화 시키기가 어렵습니다. 
    이를 극복하기 위해 세마포어(semaphore)라고 부르는 새로운 동기화(synchronization) 도구가 도입되었습니다.  
    세마포어의 개념과, 이용, 구현에 대해서 살펴보겠습니다. 

 

1) 세마포어의 개념
(1) 표준단위 연산
   ․ wait, signal에 대한 정의   

(2) 세마포어의 개념
   ․ 세마포어 S는 두 표준단위연산(atomic operation) wait와 signal에 의해서만 접근되는 정수변수이다.
   ․ wait, signal 연산 내에서 세마포어의 정수 값의 수정은 개별적으로 수행된다.     

 2) 세마포어의 이용
(1) n개의 프로세스 임계구역(critical section) 문제
   ․ 세마포어(samaphore)는 n개의 프로세스 임계구역(critical section) 문제를 다루는데 사용될 수 있다.   

(2) 여러 가지 동기화(synchromization) 문제
   ․ 세마포어는 여러 가지 동기화(synchronization) 문제
※ 동기화 문제에서의 활용
   ․ 수행중인 2개의 프로세스, 즉 문장 S1을 가진 P1과 문장 S2를 가진 P2를 생각해 봅시다. 
     *  S2는 S1이 끝난 후에만 수행하도록 한다. 
     *  P1과 P2가 0으로 초기화되는 공통 세마포어‘synch'를 공유하게 하고 프로세스 P1에 

 S1 ;
signal(synch) ;         를 삽입하고, 프로세스 P2에 
wait(synch) ;
S2 ; 
        를 삽입함으로써 쉽게 구현될 수 있다. 
       * synch는 0으로 초기화되었기 때문에 P2는 P1이 signal(synch)를 부르고 난 후에 S2를 수행하게 된다. 

 

3) 세마포어의 구현 
   ․ 세마포어 문제
    ◎ 상호배제 해결과 세마포어의 가장 큰 단점은 수행상태대기(busy waiting)를 요구한다는 것이다.
    ◎ 어떤 프로세스가 임계구역 내에 있는 동안, 그 임계구역에 들어가려고 다른 프로세스는 진입 코드(entry code)에서 계속해서 돌게 된다.
    ◎ 이 문제는 하나의 중앙처리장치가 많은 프로세스에 의해서 공유되는 실시간 다중 시스템에서 더욱 심각해진다.
    ◎ 수행상태대기(busy waiting)로 다른 프로세스가 생산적으로 사용할 수 있는 중앙처리장치 시간을 낭비하기 때문이다.
   ․ 세마포어 문제 해결 1
    ◎ 수행상태대기(busy waiting)에 대한 요구를 극복하기 위해서 wait와 signal 세마포어 조작에 정의를 변경시킬 수 있다.
    ◎ 프로세스가 wait조작을 수행하고 세마포어 값이 양이 아님을 발견했을 때 그 프로세스는 대기해야 하나 수행상태대기보다는 프로세스 자체를 봉쇄(block)시킬 수 있다.
    ◎ 제어를 중앙처리장치 스케줄러(CPU scheduler)에게 넘기게되면 중앙처리장치는 중비상태 큐에서 다른 프로세스를 선택하여 수행시킨다.

 

   ․ 세마포어 문제 해결 2
    ◎ 세마포어 S에 의해 봉쇄되거나 대기중인 프로세스는 다른 프로세스에 의한 wait 조작의 수행에 의해 다시 시행된다.
    ◎ 그 프로세스는 wakeup 조작에 으해 다시 수행 되는데, 이는 프로세스의 상태를 봉쇄상태에서 준비상태(ready)로 바꾸고 이를 준비상태 큐에 넣는다. (중앙처리장치는 실행중인 프로세스로부터 새로운 준비사애의 프로세스로 스케줄링 알고리즘에 따라 제어를 옮기거나 옮기지 않을 수 있다.)

 

   ․ 세마포어 구현(레코드로 구현)
    ◎ 세마포어를 구현하기 위해서 세마포어를 다음의 레코드로 구현한다.      

    ◎ 각 세마포어는 정수값과 프로세스의 리스트를 갖고 있다.
    ◎ 어떤 프로세스가 세마포어에 의해 대기중일 때 프로세스의 리스트에 첨가된다. signal조작은 대기중인 프로세스들의 리스트에서 하나를 제거하여 이를 활성화 시킨다.

 

   ․ 세마포어 조작     

(1) 블록(block) 연산과 wakeup(P)연산
   ․ 블록(block) 연산은 이를 호출하는 프로세스를 봉쇄 시킨다.
   ․ wakeup(P)연산은 봉쇄된 프로세스 P의 실행을 재개 시킨다.
    이 두 연산은 운영체제에 의해 기본적인 시스템 호출로 제공된다.

(2) 수행상태대기(busy waiting) 세마포어의 값
   ․ 수행상태대기(busy waiting) 세마포어에서는 그 값이 절대 음수가 될 수 없으나, 여기에 구현된 세마포어의 값은 음수가 될 수 있다.
   ․ 만일 세마포어 값이 음수일 때는 그것의 절대값은 세마포어에서 기다리는 프로세스 개수를 나타낸다. 이 결과는 wait 연산의 구현에 있어 감산과 테스트의 순서를 맞바꿈으로 인해 나타나게 되는 것이다.

 

(3) 프로세스의 리스트
   ․ 프로세스의 리스트는 각 프로세스를 첨가-제거 시키는 가장 간단한 방법은 LIFO(Last-In First-Out)인 스택(stack)일 것이다. 이 방법은 기아상태를 야기시킬 수 있다.
   ․ 이 리스트는 큐로서 좀더 보편적으로 구현할 수 있는데 이때 세마포어는 큐의 head와 tail 부분을 포함한다.
   ․ 일반적으로 이 리스트는 임의의 대기행렬기법(queueing strategy)을 사용할 수 있다.
     (예, FIFO, LIFO, 우선순위, 기타 다른 정책).
   ․ 세마포어의 올바른 사용은 세마포어 리스트에 대한 특정한 대기행렬기법에 좌우되지 않는다.

 

(4) 세마포어의 중요한 특징
   ․ 세마포어의 중요한 특징은 단위적으로 수행된다는 것이다.
   ․ 2개의 프로세스가 동시에 같은 세마포어에 대하여 wait와 signal 조작을 할 수 없게 해야 한다.
※ Wait와 Signal의 조작  

(5) 세마포어의 단위적 수행의 해결방법

단일 프로세스	․ 단일 프로세서(uniprocessor)의 경우에는(즉, 단 하나의 중앙처리장치만 존재) wait와 signal 조작이 수행 중에는 인터럽트를 금지시키면 된다. ․ 이 방법은 일단 인터럽트가 금지되면 다른 프로세스로부터의 명령어의 실행이 중간에 끼어 들지 않으므로 단일 프로세서 환경에서 활용된다.
다중 프로세스	․다중 프로세서(multiprocessor)인 경우에는 인터럽트의 금지가 운용될 수 없다. ․ 다른 프로세스(다른 프로세서에서 수행되는)로부터의 명령어는 어떤 임의의 방법으로서 끼어 들 수 있다. ․ 하드웨어가 어떤 특별한 명령을 제공하지 않으면 임계구역 문제에 대한 정확한 소프트웨어 해결방법(알고리즘 4, 5, 6)을 사용하여야 하는데, 여기서 임계구역은 wait와 signal 프로시저로 구성한다.

5. 동기화 문제(새로 제기된 모든 동기화 방법을 테스트하는 문제를 말함)
   ․ 병행제어 문제의 예가 많기 때문에 중요한 몇 가지 서로 다른 동기화synchronization) 문제를 제시합니다. 동기화 문제들은 새로 제기된 모든 동기화 방법을 테스트하는데 사용됩니다. 여기서의 해결법은 동기화를 위해 세마포어를 사용하는 것입니다.  

 

동기화 문제에 대해서 살펴보겠습니다. 
1) 유한버터 문제
(1) 유한 버퍼 문제의 개념
   ․ 유한 버퍼(bounded buffer) 문제는 동기화 기본연산자(synchronization primitive)의 강력함을 입증하기 위해 보편적으로 사용된다.
   ․ 풀(pool)은 n개의 버퍼로 구성되어 있고 각각은 하나의 항목을 소유할 수 있다고 가정한다.
   ․ ‘mutex' 세마포어 : 버퍼 풀에의 접근을 위한 상호배제를 제공하고 '1'로 초기화되어 있다.
   ․ ‘empty'와 ’full' 세마포어 : 각각 비거나 차 있는 버퍼의 수를 표시하며 각각 'n'과 '0'으로 : 초기화되어 있다.

 

(2) 생산자 프로세스와 소비자 프로세스
   ․  생산자와 소비자의 대칭성을 주목해야 한다. 
   ․  우리는 코드를 보면서 소비자를 위해 꽉 찬 버퍼(full buffer)를 생성해 내는 소비자와 같이 해석할 수 있다.    

2) 판독기/기록기 문제
(1) 판독기/기록기
   ․ 판독기(reader) : 판독하고자 하는 프로세스
   ․ 기록기(writer) : 쓰고자 하는 프로세스 
   ․ 데이터 객체(data object; 파일이나 레코드 같은 것)는 여러 병행 프로세스간에서 공유될 수 있다.
   ․ 프로세스 중의 일부는 공유객체의 내용을 판독하기를 원할 것이고, 반면에 다른 것들은 공유객체를 갱신(즉, 판독과 기록하기)를 원할 수 있다.
   ․ 만약 2개의 판독기가 동시에 공유 데이터 객체에 접근하고자 할 때에는 아무런 문제가 일어나지 않는다.
   ․ 기록기와 또 다른 프로세스(판독기 혹은 기록기)가 동시에 공유객체에 접근한다면 문제가 발행할 수 있다. 이런 병행 접근은 병행성 조건을 침해하게 되기 때문이다.

 

(2) 판독기/기록기 문제
   ․ 병행접근이 병행성 조건을 침해하는 문제가 생기지 않도록 하기 위해서는 기록기(writers)가 공유객체에 대해 배타적 접근을 하도록 해야 합니다. 
   ․ 동기화 문제를 판독기/기록기(reader/writer)문제라고 한다.
   ․ 모든 새로운 동기 기본 연산자(synchronization primitive)를 테스트 하는 데 사용한다.
   ․ 판독기 기록기 문제는 여러 가지 변형이 있으나 모두 우선순위(priority)에 관계된다.

첫번째 판독기/기록기 문제	․ 가장 간단한 형태 ․ 기록기가 이미 공유객체를 사용하도록 허가하지 않았다면 판독기가 대기하지 않는다. ․ 어떠한 판독기도 기록기가 대기중이라는 이유 때문에 다른 판독기가 끝나기를 기다리지 않는다.
두번째 판독기/기록기 문제	․ 기록기가 준비되었다면 기록을 가능한 빨리 수행할 수 있도록 하는 것이다. ․ 기록기가 객체에 접근하기 위해 대기중 일 때에는 어떠한 새로운 판독기도 읽기를 시작할 수 없다.

 

판독기 / 기록기 문제에 대한 모든 해답이 기아상태(starvation)를 낳을 수 있음에 주목해야 한다.
       
        ․ 처음의 경우에서는 기록기가 기아상태일 수 있다.
        ․ 두 번째 경우에서는 판독기가 기아상태일 수 있다. 
        ․ 이런 이유 때문에 문제의 다른 변형이 제기되었다. 

 

  ※ 판독기/기록기 문제에 대한 해결 제시하겠습니다.
     ․ 판독기 프로세스가 공유하는 자료구조
      * 판독기/기록기 문제에 대한 해결에 있어서 판독기 프로세스는 다음의 자료구조를 공유한다.      

     ․ 세마포어 mutex와 wrt
      * 세마포어 mutex와 wrt는 1로 초기화됩니다. readcount는 0으로 초기화된다.  
      * 세마포어 wrt는 판독기와 기록기 모두에게 공통이다. 
      * mutex 세마포어는 변수 readcount가 갱신되는 중에 상호배제를 위해 사용된다. 
      * readcount는 얼마나 많은 프로세스가 현재 객체를 읽고 있는지를 표시한다.  
      * 세마포어 wrt는 기록기를 위한 상호배제 세마포어로서 작용한다.  
      * 이것은 역시 임계구역(critical section)으로 들어가고 나가는 처음과 맨 나중의 판독기에 의해서 사용된다.  
      * 이것은 다른 판독기가 임계구역 내에 있는 동안에는 들어가고 나오는 판독기에는 사용되지 않는다.  
     ․ 판독기 프로세스의 일반적 구조      

     ․ 기록기 프로세스의 일반적 구조     

       * 만약 1개의 기록기가 임계구역에 있고 n개의 판독기가 대기중일 때에는 n-1개의 판독기가 mutex에 대한 큐에 들어 있는 동안 1개의 프로세스는 wrt에 대한 큐에 들어있음을 주목해야한다.
       * 기록기가 signal(wrt)을 수행도중, 대기중인 판독기나 대기중인 하나의 기록기 중에서 실행을 계속시킬 수 있는데, 선택은 스케줄러에 달려 있다.
   
정리하기
1. 프로세스의 병행성은 크게 프로세스 내에서의 병행성과 프로세스들 간의 병행성으로 구분되면 프로세스들 간의 병행에서 어떤 데이터를 공유하는 유기적 순차 프로세스(cooperating sequential process)의 집합이 주어지면 상호배제(mutual exclusion)가 제공되어야 한다.    

 

2. n개의 유기적 프로세스(cooperating process) {P0 , P1, …, Pn-1 }로 구성된 시스템의 경우 각 프로세스는 임계구역(critical section)이라 불리는 코드 세그먼트를 갖는다.

 

3. 시스템의 가장 중요한 특징은 하나의 프로세스가 임계구역에서 수행중일 때 다른 어떠한 프로세스도 이 임계 구역에서 수행될 수 없다는 것이다.

 

4. 임계구역에서 두 개의 프로세스들이 동일한 카운터의 값을 증가시키려는 시도를 한다고 가정할 때 만약 두 프로그램 모두 동시에 변수를 가져와서, 그것의 값을 증가시킨 뒤, 증가된 값을 다시 저장하는 일을 수행한다면, 증가된 값 들 중 하나는 없어지게 될 것이다. 이러한 문제를 방지하기 위한 것이 상호 배제이다.

 

5. 상호배제는 두 개의 프로세스들 간의 상호배제와 n개의 프로세스들 간의 상호배제로 구분될 수 있는데 오늘날 제시되는 상호배제 기법들은 대부분 n 개의 프로세스들 간에 적용될 수 있다. 

 

6. Test-and-Set 는 IBM에 의해 제안된 동기화 문제를 해결하기 위한 기법으로 하드웨어적으로 수행되며 공용변수가 변경되는 동안 인터럽트의 발생을 허용하지 않는다.

 

7. 세마포어(semaphore)는 다양한 동기화(synchronization) 문제를 해결하는 데 사용 되는데 두개의 표준연산자를 사용하며 하나의 프로세스가 세마포어의 값을 수정할 때 다른 어떠한 프로세스가 동시에 같은 세마포어의 값을 수정할 수 없습니다.

 

8. 세마포어 기법은 동기화 문제 해결과 상호배제를 위한 가장 보편적인 기법으로 UNIX 시스템의 프로그래밍에서 운영체제의 자원을 경쟁적으로 사용하는 다중 프로세스에서, 행동을 조정하거나 또는 동기화 시키는 기술로 이용되고 있다.