08. CPU-Synchronization(2)

Bounded-Buffer Problem

• 한정된 양의 버퍼가 있고 이 버퍼에 대해 생산자와 소비자가 버퍼에 아이템을 넣는 동작, 꺼내오는 동작을 하는 모델.
• 하나의 생산자 or 소비자가 버퍼에 접근하려고 할때 다른 생산자 소비자는 접근하면 안된다. 한 순간에 한번만.
• 버퍼가 가득 차있을때는 producer가 접근 불가하고 버퍼가 비어있을때는 consumer이 접근 불가능하다.
  버퍼는 bool형 1차원 배열로 선언하고 not used로 초기화해준다.
• 생산자는 not used인 index를 used로 바꾼다.
• 소비자는 used인 index를 not used로 바꾼다.
• 문제 해결을 위한 세마포어
  Empty(버퍼 내에 저장할 공간이 있음을 표시 / not used인 엔트리가 n개 있다는 뜻으로 n으로 초기화) 
  Full(버퍼내에 소비할 아이템이 있음을 표시 / 0으로 초기화 / Full=0이면 버퍼내에 소비할 아이템이 없다는뜻)
  Mutex(바이너리 세마포어 / 버퍼에 대한 접근을 관리 / 한번에 한명만 들어올 수 있으니까 1로 초기화) 

Do { //생산자 프로세스

         //생산자가 생산한 것을 넣으려고 한다
       wait(empty);
       wait(mutex); //뮤텍스 검사
       **
       signal(mutex); //뮤텍스를 다시 1로 변경

       signal(full);
   } while(true);
     생산자는 empty를 wait하면서 들어가고 full을 signal하면서 나옴. full+1 → 소비자가 소비할 수 있어짐

 

Do{ //소비자 프로세스

   wait(full); //생산자가 full+1 해줬으므로 소비를 할 수 있음

   wait(mutex);

    //버퍼에 있는 것을 삭제하려고 한다

   signal(mutex);

   signal(empty); //empty+1 

   **
  } while(true);

 

• Readers-Writers Problem
  여러 readers와 writers가 하나의 공유 데이터를 읽거나 쓰기 위해 접근
• Readers) 공유 데이터를 읽는다. 데이터에 변화를 주지 않으므로 여러 readers는 동시에 데이터를 읽을 수 있다.
• Writers) 공유 데이터에 쓴다. writer가 데이터를 수정하기 위해 reader이나 다른 writer은 작업을 하지 말아야한다.
• 문제 해결을 위한 세마포어
  Int Readcount: 버퍼에 현재 몇개의 reader이 접근중인지 표시
  Semaphore Wrt: writers 사이의 동기화 관리
  Semaphore Mutex: Readcount와 Wrt을 관리하는 세마포어
  mutex, wrt, readcount는 각각 1,1,0으로 초기화된다. (mutex, wrt는 한번에 한명만 들어올 수 있고 readcount는 현재 아무것도 없으니까)

Solution1
Writer 프로세스

do{

     wait(wrt); //entry section. wrt 세마포어를 잡은 프로세스만 writing 진행가능

       /* writing */

     signal(wrt); //exit section

} while(true);

 

Reader 프로세스

do{

     wait(mutex); //공유 자원에 접근하기 위해 mutex 기다림

         readcount++;
         if(readcount==1)
                wait(wrt); // 많은 reader중에 내가 처음 들어가는 reader라는 뜻. reader++했는데 1이 된것이므로

     signal(mutex);
     //처음 들어가는거니까 버퍼에 writer이 작업하고 있을수도 있다. writer이 작업중인지 아닌지 기다림. writer이 없으면 리더가 wrt 세마포어를 잡고 들어감. read counter이 1일때 wrt를 잡고있으니까 다른 리더들은 wait(mutex)에 접근을 못해서 reader count를 올릴 수 없어 밖에서 기다림. 첫번째 리더가 wrt를 잡고 뮤텍스를 푸는 순간 다른 리더들은 우르르 들어올 수 있음. 뮤텍스를 잡고 read count를 올리면 if(readcount==1) 검사를 안 하므로.
     /* reading */

    wait(mutex);

       readcount--;

       if(readcount==0)  //마지막으로 나오는 리더
              signal(wrt);  // wrt 세마포어를 건내주고 나옴. wrt+1. (리더들이 있는 동안은 계속 wrt를 잡고 있음)

} while(true);

 

-> 위 코드들의 문제점: 리더들이 계속 들어와서 readcount==0까지 안오면? Writer은 단순히 wrt만 기다리면서 통과하는 코드이기 때문에 만약 한 프로세스가 wrt를 잡고 다른 프로세스들을 다 통과시켜버리면 리더들이 다 지나갈때 까지 writer을 들어갈 수 없다.

   -> 해결방안: writer이 wrt를 요청하려고하면 reader들의 진입을 막는다. reader 진입으로 인한 writer의 starvation 문제가 해결됨. 이미 진입한 reader들이 빠져나가면 writer의 수행이 시작됨.

 

문제 해결을 위한 세마포어)

Readcount: 버퍼에 몇개의 reader가 접근중인지 표시

Writercount: 버퍼에 몇개의 writer이 접근중인지 표시

Wrt: Writers 사이의 동기화 관리

Read: Reader드르이 진입을 제어하기 위한 세마포어

Rmutex: Readcount와 wrt을 관리하는 세마포어

Wmutex: Writecount와 read를 관리하는 세마포어

rmutex, wmutex, wrt, read=1 //각 세마포어는 한 프로세스만 들어갈 수 있도록 설정

readcount, writecount=0

 

Solution2
Writer process entry section

wait(wmutex);
    writecount++;

    if(writecount==1) //한명이라도 대기하는 wmute가 있으면 read를 잡음

          wait(read);

signal(wmutex);

wait(wrt); //빠져나온 후 writer의 세마포어를 기다림

/* writing */

//wait(read)를 수행하여 reader들이 계속해서 진입하는걸 막고 진입한 reader들이 수행을 끝내면 writer이 수행됨
  한 writer만 writing할 수 있도록 제어

 

 

Writer process exit section

/* writing */

signal(wrt);  //wait(wrt)에서 기다리던 writer들이 수행됨

wait(wmutex);

     writecount--;

     if(writecount==0)  //마지막 writer라면 read를 호출함. read 세마포어를 놓아줌.

              signal(read);

signal(wmutex);

//signal(read)를 수행함으로써 reader들이 다시 진입할 수 있게한다. 여기서 만약 writecount가 0으로 내려가지 않고 계속해서 writer가 쓰기 작업을 하려한다면 reader들은 starvation상태가 된다.

 

Reader process entry section

wait(read); //1->0

signal(read);  //0->1

wait(rmutex);

      readcount++;

      if(readcount==1)

               wait(wrt);

signal(rmutex);

/* reading */

//첫 부분에서 wait(read), signal(read)가 번갈아 수행되므로 여러개의 reader가 읽을 수 있다. 그런데 여기서 writer이 wait(read)를 수행하면 더 이상 signal(read)가 수행되지 않으므로 reader은 진입하지 않는다.

 

Reader process exit section

/* reading */

wait(rmutex);

      readcount--;

      if(readcount==0)

               signal(wrt);  //writer이 이걸 호출할때까지 리더들은 위에서 계속 기다림. writer이 다 나간후에야 reader들이 통과

signal(rmutex);

//reader이 더 이상 진입을 하지 않아 readcount가 0이 되면 writer도 없다는게 보장된다. 따라서 signal(wrt)를 통해 writer이 진입할 수 있도록 한다.

 

reader은 wait(read)에서 대기중인데 signal(read)가 보내지는 경우는 다음과 같다.

• 처음 read가 1로 초기화된 경우
• 수행하려고 대기중인 writer이 하나도 없는 경우
• 이미 진입한 reader이 하나 있을 경우 하나의 signal(read)가 수행되고 이로 인해 진입한 reader이 다시 signal(read)를 수행하여 연쇄적으로 reader들이 진입할 수 있음.
• 두번째 코드에서는 반대로 reader starvation이 일어날 수 있다.

 

Solution3

reader, writer을 분리하여 어떤 작업이 수행중일때도 다른 reader, writer들이 대기할 수 있다. 대기중인 작업이 있으면 그 작업을 수행하도록 하여 starvation 상태를 방지한다.

writer의 동작) writer은 어떤 작업이 수행되고 있거나 대기중인 reader, writer이 있다면 쓰기 작업이 허가될때까지 대기.                    대기중인게 없으면 쓰기를 수행한다.
                  writer이 수행하고 나면 대기하던 reader들을 모두 수행되게한다. reader가 아니고 writer이 남아있으면 쓰                    기수행

reader의 동작) reader은 writer이 기다리고 있거나 쓰기 작업이 수행중이면 대기. reader들이 모두 수행되면 대기하고 있던 writer을 하나 수행한다. 즉, writer이 쭉 지나가고 나면 무조건 reader에게 기회를 한번 주는것. 그 반대도 마찬가지.

문제 해결을 위한 세마포어)

rc: Critical Section내에 작업중인 reader count

wc: Critical Section내에 작업중인 writer count

rwc: Reader waiting count, 수행을 기다리고 있는 reader의 수

wwc: Writer waiting count, 수행을 기다리고 있는 writer의 수

Wrt: Writers 사이의 동기화 관리

Read: Readers 사이의 동기화 관리

mutex: 위 데이터와 세마포어를 관리하는 세마포어

rc, wc, rwc, wwc=0 / wrt, read=0 /mutex=1 로 초기화

 

 

너무 힘들다.... 나머지는 다음에