Chapter 6: Synchronization Tools

Background

프로세스들이 concurrently(동시에) 여러 개가 실행될 수 있다.

공동으로 사용하는 데이터가 한꺼번에 접근을 할 수 있다. 변수, 데이터, 파일 등등

자기가 원치 않은 결과값이 나올 수 있다. -> 데이터 값이 변한다.

문제가 생기는 것이다.

 

Producer

Full or not 이것을 체크한다.

Full이면 물건을 받지 못한다.

카운터값이 Buffer 값보다 작아야 한다.

그래야지 while값을 빠져 나온다.

 

Counter 가 0이 아니면

Out위치에 있는 것을 소비하기위해 out값을 증가시키고

소비자 값을 1개 낮춘다

 

consumer

Race Condition

counter++

register1 = counter

register1 = register1 + 1

counter = register1 (저장한다)

 

counter—

register2 = counter
register2 = register2 - 1
counter = register2

 

문제: 카운터 값은 원래 값이 5가 되어야 한다.

S0: producer execute register1 = counter         {register1 = 5}
S1: producer execute register1 = register1 + 1   {register1 = 6}
S2: consumer execute register2 = counter        {register2 = 5}
S3: consumer execute register2 = register2 – 1  {register2 = 4}
S4: producer execute counter = register1         {counter = 6 }
S5: consumer execute counter = register2        {counter = 4}

 

-> 이유는 1개 증가, 1개 감소 시키기 때문에 결국 원래 값인 5가 되어야 한다. 하지만 같이 접근을 했는데, 카운터 값이 4가 되었다. -> 이런 문제를 Race Condition, OS가 이런 문제를 처리해야한다.

 

Critical Section Problem

Critcal Section

동시에 접근 할 수 있는 것

N개의 프로세스들이 있을 때, 각각의 프로세스 등은 같이 사용하는 코드들을 Critical Section이라고 한다.

그로 인해 생기는 문제를 Critical Section problem이다.

 

entry section: critical section 들어가기 전에 해주는 일

 

critical section

 

exit section: critical section을 끝내고 나오는 것

 

remainder section: 나머지 일을 하는 것

 

 

 

 

Algorithm for Process Pi

2개의 process : P1, P2

 

int turn;

P1의 입장 : i = 1, j = 2

P2의 입장 : i = 2, j = 1

 

while (turn == j): entry section

Turn = j: exit section

 

여러가지 프로세스가 들어갈 때, 프로세스들을 기다리게 만드는 것

Entry section에서 해야 하는 일이다.

 

Solution to Critical-Section Problem

(문제를 해결할 수 있는 기준)

 

• Mutual Exclusion(상호 배제)
  • Critical-section에는 딱 1개의 프로세스만 들어간다.
• Progress(진행)
  • 현제 Critical-section 들어갈 게 없으면, 한 프로세스가 Critical-section에 들어가고 싶으면
  • 들어가게 해야 한다.
• Bounded waiting(많은 프로세스)
  • 기다리는 프로세스가 무한대로 기다리면 안된다. 일정한 시간이 되면, 프로세스가 들어가야한다.

Critical-Section Handling in OS

• Preemptive(선점): 다른 프로세스가 이미 실행 중인 프로세스를 제치고 선점할 수 있다.
• Non-preemptive(비선점): 다른 프로세스가 이미 실행 중인 프로세스를 제치지 못한다.

Peterson’s Solution

int turn;

Boolean flag[2]

 

2개만 생각한다

2개의 프로세스가 있다.

Trun은 2개가 사용하는 것

초기값은 false, Critical-Section에 들어가고 싶으면 ture로 바뀐다.

 

P1과 P2가 동시에 수행될 경우

 flag[1], flag[2] 모두 true가 됨 그럴 경우 turn의 값에 따라 critical section에 들어 가는 process가 결정됨.

 못 들어 간 process는 기다리고 있음.

  그러다가 c.s. 에서 나오는 process가 자신의 flag값을 false로 바꿔 놓으면 기다리던 다른 process가 while의 조건이 false가 되므로

   while 문을 빠져 나와서 c.s.로 들어 갈 수 있음.

 

 

만약에 c.s.를 빠져 나오는 process가 자신의 flag을 false로 바꾸는 대신 turn = j를 수행하면 어떻게 될까?

-> 진행 문제가 생긴다. 1만 들어갈 때, 무한대로 기다리게 된다.

 

상호배제 만족

진행 만족

하지만, 여러가지를 할 때 BW(bounded_waiting)문제 발생

 

Solution to Critical-section Problem Using Locks

Locks(열쇠)

여러 개의 프로세스가 있을 때, cs에 들어갈 수 있는 열쇠를 요청한다.

-> 요청 중에서 어떤 운이 좋은 한 프로세스가 열쇠를 받아서 cs에 들어간다

나머지는 열쇠를 받을 때, 까지 요청한다.

Cs에 나온에가 열쇠를 반납해서, 반복한다.

 

 

 

 

 

test_and_set  Instruction

 

boolean test_and_set (boolean *target)

          {

               boolean rv = *target;

               *target = TRUE;

               return rv:

          }

 

매계변수가 들어온다

값을 rv값을 주고

rv값을 return을 한다.

매계변수 값을 true로 만들어 준다.

-> 사용 중이면, 다른 애들은 수행 못한다. -> 비선점

 

Solution using test_and_set()

       do {
          while (test_and_set(&lock)) ;

              /* do nothing */

                 /* critical section */

          lock = false;

                 /* remainder section */

       } while (true);

 

compare_and_swap Instruction

int compare _and_swap(int *value, int expected, int new_value) {

         int temp = *value;

         if (*value == expected)

            *value = new_value;

      return temp;

     }

원자적(더이상 나눠지지 않는다)으로 수행된다

Swap: 보통 2개의 변수의 값을 바꿔주는 값

 

Solution using compare_and_swap

      do {
         while (compare_and_swap(&lock, 0, 1) != 0);

             /* do nothing */

          /* critical section */

       lock = 0;

          /* remainder section */

      } while (true);

 

여러 개는 문제가 생긴다.

-> bounded_waiting(어떤 프로세스가 무한데로 기다린다.)

-> 해결방법 순서를 정한다.

 

 

 

 

Classical Problems of Synchronization

Bounded-Buffer Problem

mutex는 세마코어이다

mutex는 다른 프로세스가 접근 못하게 하는것

 

Full, empty 카운팅 세마코어

Full : 몇 개의 프로세스가 있는 지 나타내는 것

Empty: 프로세스가 어느정도 비어있는 가

 

초기값:

mutex : 1

Full : 0

empty : n

 

Bounded Buffer Problem (producer)

do {

      ...
   /* produce an item in next_produced */

      ...

   wait(empty);

   wait(mutex);

      ...
   /* add next produced to the buffer */

      ...

   signal(mutex);

   signal(full);

} while (true);

 

Bounded Buffer Problem(consumer)

do {

   wait(full);

   wait(mutex);

      ...
   /* remove an item from buffer to next_consumed */

      ...

   signal(mutex);

   signal(empty);

      ...
   /* consume the item in next consumed */

      ...
} while (true);

 

Readers-Writers Problem

reader 프로세스: 읽기만 하는 프로세스 그래서 값을 바꾸는 일을 안한다.

writer 프로세스: 일기도 하고 쓰기도 한다. 데이터를 바꾸을 도 있다.

 

writer는 1개만 접근 가능하다

하지만 reader는 여러 개의 프로세스가 접근 할 수 도 있다.

 

초기값

Rw_mutex = 1

Mutex = 1

Read_count = 0

 

The structure of a writer process

       

do {
   wait(rw_mutex);

      ...
   /* writing is performed */

      ...

     signal(rw_mutex);

} while (true);

 

 

      do {
       wait(mutex);
       read_count++;
       if (read_count == 1)

               wait(rw_mutex);

             signal(mutex);

                       ...
                  /* reading is performed */

                       ...

              wait(mutex);
                  read_count--;
               if (read_count == 0)

                    signal(rw_mutex);

               signal(mutex);

             } while (true);

 

wait(rw_mutex);  -> writer는 들어오지 말라는 것이다.

signal(mutex); -> reader는 들어올 수 있다.

Read_count = 1의 의미-> 가장 먼저 들어가는 read프로세스를 체크해준다.

Read count는 reader 프로세스의 개수

Read_count = 0의 의미-> reader 프로세스가 없다

 

Dining-Philosophers Problem

Dining-Philosophers(식사하는 철학자)

철학자는 생각하거나 식사 2 중 하나를 한다.

조건

1.식사를 하려면, 의자에 앉거 젓가락이 2개가 있어야지 가능해서 왼쪽, 오르쪽 젓가락을 사용할 수 있을 때 식사를 할 수 있다.

 -> 이웃은 식사를 못한다.

chopstick [5] 세마코어

초기값 1

 

The structure of Philosopher i:

do  {

          wait ( chopstick[i] );

     wait ( chopstick[ (i + 1) % 5] );

 

               //  eat

     signal ( chopstick[i] );

     signal (chopstick[ (i + 1) % 5] );

 

                 //  think

} while (TRUE);

 

2개의 젓가락을 사용 가능하면 식사 가능한 것이다.

 

문제

옆에 있는 사람이 식사를 못한다.

생기는 문제 deadlock-> 각각의 프로세스들이 다른 프로세스들이 일을 못하게 막는 것

 

Deadlock 해결법

1. 적어도 4명의 철학자가 동시에 앉을 수 있게한다.

2. 두 개의 젓가락이 모두 사용 가능한 경우에만 젓가락을 집어 들도록 한다.

3. 비대칭 해결: 철학자는 먼저 왼쪽과 오른쪽 젓가락을 집어 든다. 아니면 역순으로 끝나면 다른 사람이 아까 처럼 집는다.

 

Problems with Semaphores

semaphores를 잘못 사용하면 

1. signal이 먼저 오면 계속 critical section에 들어온다

2. wait()가 마지막에 또 들어오면, 계속 기다린다. 

3. 대기와 신호 또는 둘 다 생략한다, -> 상호배제 또는 교착상태에 빠진다.

 

Monitors

객체지향 형태를 사용한다.

class 형태이다

캡슐화가 되어있다.

하나의 통로로만 이용한다.