[운영체제]chapter 07. Synchronization Examples_#01

동기화 예제 #1 동시성 제어의 고전적 문제들

동시성 제어 문제들의 고전적인 예제들

• 유한 버퍼 문제 (Bounded-Buffer Problem)
  • 생산자-소비자 (Producer-Consumer Problem)
• 독자-저자 문제 (Readers-Writers Provlem)
• 식사하는 철학자 문제(Dining-Philosophers Problem)

 

1. 유한 버퍼 문제 bounded-Buffer Problem

• 생산자-소비자 문제로도 불림
• 각각에 하나의 아이템을 저장할 수 있는 n개의 버퍼로 구성
• 생산자의 목적은 소비자를 위해 버퍼를 가득 채우는 것이 목표
• 소비자의 목표는 아이템을 소비하여 버퍼를 비우는 것이 목표

공유 데이터 구조

• Mutex: 이진 세마 포어
  • 버퍼 공간에 접근하는 동안 다른 프로세스가 접근하지 못하게 상호 배제를 제공
  • mutex = 1 초기화, mutex = 0: 접근 불가능, mutex = 1: 접근 가능 함
• Empty : 비어있는 버퍼의 개수를 의미하는 세마 포어
  • Empty = 0 : 버퍼가 가득 찼다는 의미
  • Empty = n : 버퍼가 비어있다는 의미
• Full : 차있는 버퍼의 개수를 의미하는 세마포어
  • full = 0 : 버퍼가 비어있다는 의미
  • full = n : 버퍼가 가득 찼다는 의미

int n;
semaphore mutex = 1;
semaphore empty = n;
semaphore full =0

 

 

생산자 프로세스의 구조

while(true){
		...
    // produce an item in next producer
    ...
    wait(empty);
    wait(empty);
    ...
    // add next producer to buffer
    ...
    signal(mutext);
    signal(full);
   
}

• empty의 lock은 여러 생산자 프로세스가 가질 수 있음
• 그러나 mutex lock은 이진 세마포어이기 때문에 버퍼에 접근할 수 있는 프로세스는 단 하나 
• empty = 0: 버퍼가 가득찼다는 의미이므로 생산자 프로세스는 대기해야 함

소비자 프로세스의 구조

while(true){
	wait(full);
    wait(mutex);
    	...
    // remove an item from buffer to mext consumer
    ...
    signal(mutex);
    sigmal(empty);
    ...
    // comsume the item in mext consumer
    ...
}

 

• full lock을 가질수 있는 프로세스는 여러개
• 그러나 mutex lock은 이진 세마포어이기 때문에 버퍼를 접근할 수 있는 프로세스는 단하나
• full =0: 버퍼가 비어있다는 의미이므로 소비자 프로세스는 대기

2. 독자-저자 문제 (Readers-Writers Problem)

• 여러개의 프로세스들이 동시에 수행됨
• Readers 프로세스들은 공유 데이터를 읽기만 함
• Writers 프로세스들은 공유 데이터를 읽기/쓰기를 수행 함
  • 예를 들어 데이터 베이스는 여러개의 프로세스들에 의해서 공유 됨
  • 어떤 프로세스는 select만 수행하는 프로세스가 있을 수 있다. 이러한 프로세스는 reader프로세스로 간주
  • 어떤 프로세스는 update만 수행하는 프로세스가 있을 수 있다. 이러한 프로세스는 writer 프로세스로 간주
• 두개 이상의 프로세스가 접근하는 경우는 다음과 같이 나뉠 수 있다.
  • Case1: 두개 이상 reader 프로세스들이 동시에 공유 데이터에 접근한다면 문제는 발생하지 않음
  • Case2: 만약 1개의 Writer 프로세스와 또다른 프로세스 (Reader 또는 Writer 프로세스)가 동시에 데이터 베이스에 접근한다면 데이터 불일치가 발생함 

Reader-Writer Problem의 문제 유형

• 모든 문제들은 우선순위와 관련이 있다
• 첫번째 Reader-Writers Problem
  • Reader 프로세스가 임계영역에서 데이터를 읽는 상태에서 Writer프로세스가 대기하고 있다고 해서 Reader 프로세스가 대기해야할 필요는 없다.
  • 즉, Reader 프로세스든, Writer 프로세스든 기회는 공정히 가져야한다는 의미
• 두번째 Reader-Writers Problem
  • 만약 Writer 프로세스가 임계 영역에서 데이터에 접근 중인 상태라면 새로운 Reader프로세스들은 접근 해서는 안됨
• 2가지 변형 모두 기아 (Starvation)현상이 발생할 수 있음
  • 첫번째 케이스는 공유 자원에 접근하고자 하는 Reader 프로세스가 100만개가 존재하고 Writer 프로세스가 1개라면 reader프로세스들은 Writer 프로세스를 위해 대기를 안해도 되므로 Writer프로세스는 후순위로 밀리게 됨
  • 두번째 케이스는 반대로 Writer 프로세스가 100만개가 존재하고 소수의 Reader 프로세스들은 계속 대기만 해야 함

Reader-Writer 문제의 해결안

Reader 프로세스 자료 구조

semaphore rw_mutex = 1; // 이진 세마포어
semaphore mutex = 1; // 이진 세마포어
int read_count = 0;

 

• mutex: read_count를 갱신할 때 다른 Reader 프로세스의 접근을 막기 위한 상호 배제에 사용되는 lock
• rw_mutex: 다른 writer의 접근을 막기 위한 상호 배제에 사용됨
  • Reader 프로세스와 Writer 프로세스가 둘다 참조 한다
• read_count: 현재 몇 개의 reader 프로세스들이 객체를 읽고 있는지 알려줌
  • read_count = 0: 공유 자원을 읽고 있는 Reader프로세스들이 없어지므로 Writer프로세스가 진입해도 된다는 의미

Writer 프로세스의 구조

while(true){
	wait(rw_mutex);
    ...
    // writing is performed
    ...
    signal(rw_mutex);
}

 

Reader 프로세스의 구조

While(true){
	wait(mutex); // 다른 Reader 프로세스들과 lock을 얻기 위해 경쟁
    read_count++; // 현재 읽고 있는 Reader 프로세스 숫자 증가 (임계 영역 공유 자원)
    
    // 만약 현재 읽으려고 하는 reader 프로세스가 첫번째라면
    // rw_mutex의 lock을 얻는다. 그러면 다른 Writer 프로세스는 대기
    if(readcount ==1)
    	watit(rw_mutex);
    signal(mutex);
	...
    // reading is performed
    ...
    wait(mutex);
    readcount--; // 현재 일고있는 reader 프로세스 숫자 감소 (임계 영역 공유자원)
    if(readcount==0) // 더이상 읽는 Reader 프로세스가 없으면 rw_mutex lock 반환
    	signal(rw_mutex);
    signal(mutex);
}

 

reader-writer문제의 해결안 특징

• Writer 프로세스가 임계 영역에서 작업중이면 n개의 reader 프로세스는 대기중이다
  • n개의 Reader 중에서 1개의 Reader 프로세스는 rw_mutex의 큐에 있다
    • 1개의 Reader 프로세스는 제일  첫번째로 읽으려고 하는 Reader 프로세스이다.
  • n개의 Reader중에서 n-1개의 Reader 프로세스는 mutex의 큐에 있다
• Writer 프로세스가 sigmal(rw_mutex)를 실행하는 경우
  • 대기중인 Reader 프로세스들 또는 단일 대기중인 Writer 프로세스가 실행을 재개할 것이다
  • 누구를 선택할 것인지는 스케줄러에 달려있다

Reader-Writer Locks

• Reader-Writer Problem과 해결안은 Reader-Writer Locks가 제공하여 일반화 되어있다.
• Reader-Writer Lock을 획득할 때 lock의 모드를 명세하는 것을 요구한다 (읽기 모드 / 쓰기 모드)
• 여러개의 프로세스들은 읽기 모드에서 Reader-Writer lock을 얻을 수 있다.
• 그러나 오직 하나의 프로세스만이 Writer 프로세스들을 위해 요구되는 배타적인 접근으로써 쓰기에 대한 lock을 얻을 수 있다.

Reader-Writer 예제

class ReaderWriter{
	public static void main(String[] args){
    	Thread[] readers = new Thread[2];
        Thread[] writers = new Thread[1];
        SharedDB db = new SharedDB();
        
        // create thread of Reader
        for(int i =0; i < writers.length; i++){
        	writers[i] = new Thread(new Writer(db));
            writers[i].start();
        }
    }
}

class Reader implemnets Runnable{
	SharedDB sharedDB;
	
    public Reader(ShardDB shardDB){
    	this.sharedDB = sharedDB;
    }
    @Override
    public void run(){
    	while(true){
        	try{
            	Thread.sleep(1000);
                sharedDB.acquiredReadLock();
                shardDB.read();
                shardDB.releaseReadLock();
            } catch (InterruptedException e){
            	throw new RuntimeException(e);
            }
            }
        }
    }
}
class Writer implements Runnable{
	SharedDB sharedDB;
    public Writer(SharedDB sharedDB){
    	this.sharedDB = SharedDB;
    }
    @Override
    public void run(){
    	while(true){
        	try{
            Thread.sleep(1000);
            sharedDB.acquireWriteLock();
            sharedDB.write();
            sharedDB.releaseWriteLock();
          } catch (InterruptedException e){
          		throw new RuntimeException(e);
          }
        }
    }
}
class SharedDB{
	private int readerCount = 0;
    private boolean isWriting = false;
    
    public void read(){
    	// read from the database here
        System.out.println('현재 데이터 베이스를 읽고있습니다.');
    }
    public void write(){
    	// write into the database here
        System.out.println("현재 데이터 베이스를 작성하고 있습니다");
    }
    synchronized public void acquireReadLock(){
    	while(isWriing){
        	try{
            	wait();
            } catch (InterruptedExeption e){
            	throw new RuntimeException(e);
            }
        }
        readerCount++;
    }
    synchronized public void releaseReadLock(){
    	readerCount--;
        if(readerCount == 0 ){
        	notify();
        }
    }
    synchronized public void acquireWriteLock(){
    	while(readerCount > 0 || isWriting){
        	try{
            	wait();
            } catch (InterruptedException e){
            	throw new RuntimeException(e);
            }
        }
        isWriting = true;
    }
    synchronized public void releaseWriteLock(){
    	isWriting = false;
        notify();
    }
}

 

 

참고: https://yonghwankim-dev.tistory.com/272

[운영체제][프로세스관리] 동기화 예제 #1 동시성 제어의 고전적 문제들