OS arrangement for test - Cooperating process and Synchronization (1)

It is just my opinion, so don't you attack me. please!

But if this posting has some incorrect informations, you comment about that

Please!!

Cooperating process and Synchronization

• 결정성
  · 프로세스들이 순차적으로 실행 되는 것이 이야기합니다. 즉 비결정성을 띈다면 동기화를 통해 데이터의 무결성을 유지해야하겠죠.
  
  · 비간섭 관계의 정의
  1.프로세스 시스템에서 한 프로세스가 다른 프로세스를 선행할 때 이들이 서로 독립적
  2.한 프로세스의 출력 장소가 다른 프로세스의 입력 장소나 출력 장소가 아닐 때, 이 프로세스들은 비간섭 관계에 있다고 정의함.
  모든 쌍의 프로세스가 비간섭 → 시스템은 비간섭 <시스템에서 비간섭은 결정성과 필요 충분 조건>
  또한 공유 변수간의 간섭이 없어야 결정성을 만족합니다.

• Critical section(임계 영역)
  · 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원(임계자원(Critical Resource))에 대해 접근하고 실행하는 프로그램내의 코드 부분이다. 프로세스가 공유자료를 변경하는 영역이고, 하나의 프로세스만 공유 데이터에 접근하고 나머지 프로세스들은 공유 데이터에 접근할 필요가 있더라도 기다려야 합니다.
  임계구역은 가능한 한 빨리 수행되어야만 하며, 프로세스가 임계구역에 들어간 후 프로세스가 블록 상태로 되어서는 안 됩니다.
  
  · Critical section에 대한 요구사항 3가지
  1.상호 배제 (다른 어떤 프로세스도 C.S를 실행할 수 없다.)
  2.진행(비어있는 C.S에 두 P가 동시 접근한다면 적절한 결정기법(pipe)이 있어야 함.)
  3.제한된 대기 (진입 요청 후부터 수락까지 사이에 다른 P가 C.S에 실행할 수 있는 횟수에 제한이 있어야함.)

• 상호 배제의 구현

function mutex() {
 var turn;
 function p0() {
   while(true) {
    while(turn == 1);
    criticalSection();
    turn = 1;
   }
  }

   function p1() {
    while(true) {
     while(turn == 0);
     criticalSection();
     turn = 0;
    }
   }

  turn = 0;  
  p0();
  p1();
}

• 이 경우 발생할 수 있는 문제점
  · 첫 번째 진입은 P0만 가능함.
  · 교대로 1번씩만 접근할 수 있음.
  
  · 첫 진입이 고정되어있는 것입니다. 이는 C.S가 비어있을 때, 진입을 원하는 프로세스를 방해해서는 안된다는 원칙을 위배합니다.
  · 무조건 교대로 1번씩만 C.S에 들어갈 수 있는 상황입니다. 이는 누구든 C.S가 비어있으면 들어갈 수 있는 법칙을 위배합니다.

function mutex(lock)  {       
  lock = false;
}

function enterMutex(lock) {        
  while(lock);
  lock = true;
}

• 이 경우 발생할 수 있는 문제점
  · while(lock);과 lock = true; 사이에서 context-switching이 일어난다면 C.S에 두 개의 프로세스가 들어가게 됨. 이는 상호배제를 위배합니다.

function mutex(lock)  {       
  lock = false;
}

function enterMutex(lock) {         
  lock = true;
  while(lock);
}

• 이 경우 발생할 수 있는 문제점
  · lock = true;와 while(lock); 사이에서 context-switching이 일어난다면 C.S에 두 프로세스 모두 들어갈 수 없는 상태가 될 수 있습니다. 이는 교착상태에 빠지게 됩니다.

• 올바른 상호 배제 구현 (Peterson's Solution)

function enterMutex(lock) {    
  flag[i] = 1;
  turn = j; //1
  while(flag[j] == 1 
         && turn == j);//3
}

function enterMutex(lock) {    
  flag[j] = 1;
  turn = i; //2
  while(flag[i] == 1 
         && turn == i);//4
}

· 1이 2보다 먼저 수행되었을 경우 3과 4의 while문 중 어느것이 걸국 먼저 유일하게 빠져나갈까요? 3
이유는 4가 3보다 먼저 수행되었어도, 결국 문맥 교화에 의해 언젠가는 3이 수행되어 들어감
· 즉, 먼저 양보한 사람이 들어가게 되어있는 구조입니다.