OS - 동기화 예시

목차

• 생산자 소비자 문제 (Producer-Consumer)
• 독자-저자 문제 (Reader-Writer)
• 식사하는 철학자 문제(Dining-Philosophers problem)
• 커널 동기화

동기화 예시(Synchronization Examples)

클래식 동기화 문제 3가지

• Bounded Buffer problem = 생산자-소비자문제(Producer-Consumer problem)
• Readers and Writers problem
• Dining-Philosophers problem

 

생산자-소비자 문제(Producer-Consumer, Bounded Buffer problem)

생산자-소비자 문제는 여러 개의 프로세스를 어떻게 동기화할 것인가에 관한 고전적인 문제입니다. 한정 버퍼 문제(Bounded buffer problem)라고도 합니다.

유한한 개수의 물건(데이터)을 임시로 보관하는 보관함(버퍼)에 여러 명의 생산자와 소비자들이 접근합니다.
생산자는 물건이 하나 만들어지면 버퍼에 저장합니다. 소비자는 물건이 필요할 때 버퍼에서 꺼내옵니다.

여기서 생길 수 있는 문제점은 보관함이 꽉 찼는데 물건 넣거나, 보관함에 든 물건이 없는데 물건을 꺼내는 행위가 발생할 수 있습니다.

-예제에 자원(길이 n 버퍼 1개 + 세마포 3개)

• n개의 버퍼가 있고 각각 1개의 데이터를 들고 있을 수 있습니다.
• mutex라는 세마포가 있고 1로 초기화됩니다.
• full이라는 세마포가 있고 0으로 초기화됩니다.
• empty라는 세마포가 있고 n으로 초기화됩니다.

* Counter 변수 없이 mutex만을 사용해서 문제를 해결할 수 없습니다. 카운팅 세마포인 full, empty를 사용하는 것이 효율적입니다.

생산자 프로세스

while(true){
	...
    /* produce an item in next_produced */
    ---
    wait(empty);
    wait(mutex);
    ...
    /* CS : add next produced to the buffer */
    ...
    signal(mutex);
    signal(full);
    }

소비자 프로세스

while(true){
	...
    /* produce an item in next_produced */
    ---
    wait(full);
    wait(mutex);
    ...
    /* CS : add next produced to the buffer */
    ...
    signal(mutex);
    signal(empty);
    }

생산자는 버퍼에 물건이 있다면 꺼내서 사용하고, 없다면 대기합니다. : wait(empty)
만약 물건을 꺼냈다면 상호배타 안에서(mutex lock) 일을 처리합니다. 
그 후 퇴장하면서 물건을 하나 사용했다고 기록합니다 : signal(full)

소비자는 버퍼가 꽉 차지 않았다면 물건을 만듭니다. 꽉 찼다면 대기합니다. : wait(full)
만약 물건을 만들 수 있다면 상호배타 안에서(mutex lock) 일을 처리합니다.
그 후 퇴장하면서 물건을 하나 만들었다고 기록합니다. : signal(empty)

이렇게 서로 만들었다, 사용했다를 해주며 기록해주면서 동기화를 진행합니다.
*이 때, 생산자와 소비자가 별도의 뮤텍스락을 사용하는 것이 더 효율적입니다. 서로 다른 임계구역 느낌.

 

 

독자-저자 문제 (Reader-Writer problem)

독자-저자 문제는 여러 명의 독자와 저자들이 하나의 저장 공간(버퍼)를 공유할 때 발생할 수 있는 문제입니다.
독자는 데이터를 읽을 수만 있습니다. 그반면 저자는 데이터를 읽고 쓸 수 있습니다.
여러명의 독자는 같은 순간에 읽을 수 있지만, 독자와 저자가 같은 순간에 있으면 안됩니다.
저자는 한 순간에 오직 1명의 저자만이 데이터를 수정해야하며 저자는 다른 저자나 독자와 같은 순간에 있으면 안됩니다.

-예제에 자원(저장공간 dataset + 2개의 세마포 + 카운팅용 정수 1개)

• 저장공간 Data set
• rw_mutex 이름의 세마포로 1로 초기화합니다. 독자와 저자의 상호배타용 세마포입니다.(독자와 저자는 공존 X!)
• mutex 이름의 세마포로 1로 초기화합니다.독자가 read_count를 업데이트 하기 위해 사용하는 뮤텍스 세마포입니다.
• read_count 이름의 카운팅용 정수로 0으로 초기화합니다. 현재 진행중인 독자의 수입니다.

저자 프로세스

while(true){
    wait(rw_mutex);
    ...
    /* writing is performed */ 오직 1개의 저자만 들어갈 수 있어야 합니다.
    ...
    signal(rw_mutex);
}

 

독자 프로세스

while(true){
    wait(mutex);
    read_count++;
    if(read_count == 1) //자신이 첫번째 독자라면 저자와 경쟁해야합니다. 아니면 다른 독자 중복허용
    	wait(rw_mutex); //독자가 있다면 저자를 막습니다.
    signal(mutex);
    ...
    /* reading is perforemd */ 독자가 중복해서 들어오는것을 허용해서 뮤택스락 X
    ...
    wait(mutex);
    read_count--;
    if(read_count == 0) //더이상 독자가 없다면 저자를 허용합니다.
    	signal(rw_mutex);
    signal(mutex);
}

이렇게 독자와 저자의 순서를 세마포와 카운팅한 독자의 수로 해결합니다.

위 독자-저자 문제는 3가지 다른 바리에이션이 있습니다.

1. 독자 선호입니다.위 코드와 동일한 경우로 독자가 먼저 들어와있다면 저자를 막습니다. 진행이 막혀 기다리고 있는 저자 이후에 신규독자가 더 들어온다면 기다리던 저자보다 이후 들어온 신규독자가 먼저 일을 합니다.

2. 저자 선호입니다. 독자의 중복을 최대한 허용하지만, 만약 기다리던 저자가 있다면 신규 독자는 기다리던 저자를 앞지르지 못하는 방식입니다. 반대로 늦게 온 저자는 기다리고 있는 독자를 앞지를 수 있습니다.

3. 공정한 독자-저자입니다. 선착순으로 임계구역에 들어가며, 독자의 중복을 최대한 허용하는 방식입니다. 이 방식에서는 늦게온 독자/저자는 기다리고 있는 다른 독자/저자를 앞지르지 못합니다.

* 자세한 내용은 과제 explain.docx에서 확인...

*과제 코드

https://github.com/SniKuz/OS_Lecture/tree/main/ReaderWriter

해당 과제, 스켈레톤 코드 등 권리는 원작자 교수님께 있음을 알려드립니다.

 

 

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

교착상태(데드락)을 설명하기 위해 1965년 에츠허르 다익스트라가 만든 문제입니다. 다익스트라 알고리즘에 그 다익스트라!

문제 설명은 다음과 같습니다.(한국화 버젼)
5명의 철학자가 하나의 원탁에 앉아 식사를 합니다.각각의 철학자들 사이에는 젓가락이 1개씩 있고 식사를 위해서는 젓가락 한 쌍이 필요합니다. 각 철학자는 식사를 하고 있거나, 식사 하지 않을때  일정 시간 생각을 합니다. 철학자 A가 식사하기 위해서는 A의 양 옆 철학자가 모두 식사를 하지 않고 있는 상태여야 합니다.
식사가 끝난 철학자는 젓가락을 각각 원래 위치에 둬야 합니다. 이 때, 어떤 철학자도 굶지 않고 식사할 수 있는 방법은 무엇입니까? 여기서 철학자가 프로세스, 젓가락이 공유자원입니다.

생길 수 있는 문제상황으로 만약 모든 철학자가 자신의 왼쪽 혹은 오른쪽 젓가락을 들게된다면 다른 쪽 젓가락을 들지 못한 상태로 영원히 기다리는 데드락에 빠질 수 있습니다.

데드락을 피하는 3가지 방법

1. 테이블에 최대 4명만 앉고 젓가락이 여유가 있으니 데드락에 빠지지 않습니다.

2. 젓가락을 2개 다 집을 수 있을 때만 집습니다. 가장 일반적인 해결법입니다.

3. 짝수번 철학자는 왼쪽을 집고 오른쪽을, 홀수번 철학자는 오른쪽을 집고 왼쪽을 집는 순서로 집습니다.

모니터로 식사하는 철학자 문제 코드

monitor DiningPhilosophers {
    enum { THINKING; HUNGRY; EATING) state[5];
    condition self[5]; // 배고프지만 젓가락을 집을 수 없을 때 기다리기 위해 사용하는 조건 변수 큐
    
    void pickup(int i){
    	state[i] HUNGRY;
        test(i);
        if(state[i] != EATING) self[i].wait;
    }
    
    void putdown(int i){
    	state[i] = THINKING;
        
        //좌우에 누가 먹기를 기다리고 있으면 깨워줍니다.
        test((i+4)%5); 
        test((i+5)%5);
    }
    
    //i 철학자의 양옆이 모두 식사중이 아닐 때 식사합니다.
    void test(int i){
    	if((state[(i+4)%5] != EATING && state[i] == HUNGRY && (state[(i+5)%5] != EATING)){
        	state[i] = EATING;
            self[i].signal();
        }
    }
    
    initialization_code(){
    	for(int i = 0; i < 5; i++)
        	state[i] = THINKING;
    }
}

위 코드의 경우 데드락이 걸리지 않지만 만약 철학자가 느리다면 젓가락 2개를 모두 확보하는데 시간이 걸려 기아상태일 수 있습니다.

 

 

 커널 동기화(Kernel Synchronization )

윈도우

커널레벨

● 단일코어는 인터럽트 마스크를 통해 인터럽트를 차단합니다.

● 멀티코어 시스템에서는 스핀락을 사용합니다.이때, 스핀락 스레드는 선점하지 않습니다. 그 이유는 효율성 때문이라고 하는데, 예를 들면 스핀락을 가진 스레드가 선점되면 데드락이 발생할 수 있기 때문입니다.
* 멀티코어 시스템에서 스핀락은 효율적일 수 있는데, 그 이유는 락을 오래 들고 있지 않기 때문에 세마포와 같이 Waiting 큐를 관리하지 않기에 더 효율적일 수 있습니다.

유저레벨

● 뮤택스, 세마포, 이벤트, 타이머 등을 사용할 수 있는 디스패처 오브젝트를 제공합니다.
*디스패처 오브젝트마다 Waiting 큐가 있고, 오브젝트가 signaled-state(object available)로 바뀌면 큐에 대기하던 모든 스레드 혹은 일부를 깨웁니다.

● 이벤트 : 어떤 조건을 만족하면 기다리던 스레드에게 notify()합니다.

● 타이머 : 일정 시간이 초과되면 1개 이상의 스레드에게 notify()합니다.

 

리눅스

● 초창기 리눅스(2.6 이전)는 인터럽트 차단으로 했으며 전체 선점형이었습니다.

● 단일 코어 시스템에서 스핀락을 사용하지 않습니다.

● 현재는 리눅스의 스핀락과 뮤택스락은 nonrecursive합니다. 즉 락을 가진 상태에서는 다시 락을 걸 수 없습니다.

● 커널에서 task가 락을 가지고 있다면 이 task는 비선점합니다. 현재 가지고 있는 락의 수를 preempt_count라는 변수에 저장하며, 이 값이 0인경우 선점이 가능합니다.

● 유저레벨에서 POSIX, OpenMP등의 API로 개발 가능합니다.