Chapter06. 프로세스 동기화 : 문제풀이

6.1 경쟁 조건은 ~


6.2 두 개의 프로세스를 위한 임계구역 문제에 대한 최초의 올바른 소프트웨어 해결 방안을 제시한 사람은 Dekker였다. 두 개의 프로세스 P0와 P1은 다음 변수들을 공유한다.
~

프로세스 Pi(i==0 or 1)와 Pj(j==1 of 0)의 구조는 그림6.21과 같다.

이 알고리즘이 임계구역 문제의 세 가지 요건을 모두 충족시킴을 증명하시오.

p.299참고

6.3 ~

2

cf) 임계구역에 대한 세 가지 문제

상호배제 : 프로세스 P가 자신의 임계구역에서 실행된다면, 다른 프로세스들은 그들 자신의 임게구역에서 실행될 수 없다.

진행 : 임계구역이 비어있다면, 나머지 구역에서 실행중이지 않은 프로세스들만 다음에 누가 그 임계구역으로 진입할 수 있는지 결정할 수 있으며, 이 선택은 무한정 연기될 수 없다.

한정된 대기 : 프로세스가 임계구역의 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지, 다른 프로세스들이 임계구역에 진입하는 횟수에 한계가 있어야 한다.

*알고리즘 해석 :

1. 인덱스가 turn과 i 사이에 있는 프로세스는 idle이여야 한다.

2. 그렇다면 flag를 in_cs로 바꾸고, 다른 프로세스 중 이미 flag를 in_cs로 바꾼 것이 있는지 확인한다.

3. 만약 그런 것이 없고, 이번이 process의 turn이라면, 혹은 현재 turn인 process가 idle이라면 임계구역에 진입한다.

1. 상호배제 : 한 프로세스의 flag가 in_cs 로 정해지려면 다른 어떤 프로세스의 flag도 in_cs여서는 안된다. 다른 프로세스들의 상태를 점검하기 전에 프로세스가 자신의 flag를 in_cs로 정하므로 두 개의 프로세스가 동시에 임계구역에 진입할 수 없다.

2. 진행 : 하나의 프로세스(k)만이 flag를 in_cs로 정하고 인덱스가 turn과 k 사이에 있는 그 어떤 프로세스도 flag를 in_cs로 정하지 않는다.

3. 한정된 대기 : 프로세스 k가 임계구역에 진입하기 원하면, k의 flag는 더이상 idle로 바뀌지 않는다. 그러므로, 인덱스가 turn과 k사이에 있지 않은 프로세스는 임계구역에 진입할 수 없다. 그 사이에 인덱스가 turn과 k 사이에 있는 프로세스가 임계구역에 진입하기 원한다면 진입할 것이다. 그리고 turn 값은 k에 가까워질 것이다. 결과적으로, turn이 k가 되거나 인덱스가 turn과 k사이에 있는 프로세스가 없으므로 프로세스 k는 임계구역에 들어가게 된다.

6.4 동기화 프리미티브가 사용자 수준 프로그램에서 사용되는 경우, 단일 처리기 시스템에서 인터럽트 불능을 이용하여 동기화 프리미티브를 구현하는 것이 왜 부적당한지 설명하시오.

5

만약 사용자 수준 프로그램이 인터럽트 불능을 할 수 있다면, 타이머 인터럽트를 불능시키거나 문맥교환을 막을 수 있어서 다른 프로세스가 실행되는 것을 막게 된다.

6.5 다중 처리기 시스템을 위한 동기화 프리미티브를 구현할 때 인터럽트를 사용하는 것이 부적합한 이유를 설명하시오.

6

다중 처리기 상에서 인터럽트의 사용불가능화는 메시지가 모든 처리기에 전달되게 하기 대문에 상당한 시간을 소비한다. 이러한 메시지 전달은 각 임계구역에 진입하는 것을 지연시켜, 시스템 효율을 떨어뜨린다

다중 처리기 시스템에서 인터럽트는 효율적이지 않다.

인터럽트 사용불가화는 다른 프로세스들이 인터럽트가 불가능화된 처리기에서 실행되는 것을 막기 때문이다.

어떤 프로세스가 다른 처리기에서 실행될 수 있는지에는 제한이 없으므로 인터럽트를 불가하게 하는 프로세스는 프로그램 상태에 대한 상호 배제적인 접근을 보장할 수 없다.

6.7 경쟁 조건이 발생할 가능성이 있는 커널 자료구조 2개를 기술하시오. 어떤 경우에 발생할 수 있는지 설명하시오.

시스템의 모든 열린 파일의 리스트를 유지하는 커널 자료구조 - 두 프로세스가 동시에 파일을 열려고 한다면, 리스트에 대한 개별적인 갱신은 경쟁 조건을 일으킬 수 있다.

메모리 할당을 관리하는 자료구조, 프로세스 리스트를 유지하는 자료구조 등

6.8 한정된 대기 요구 조건을 충족하는 상호 배제를 제공하기 위하여 compare_and_swap() 명령이 어떻게 사용될 수 있는지 설명하시오.

cf)상호배제

전역변수 lock을 선언하고 0으로 초기화한다.

compare_and_swap() 명령을 호출한 첫 번째 프로세스(compare_and_swap(&lock, 0, 1)) 는 lock을 1로 지정할 것이다.

lock의 원래 값(0)이 expected의 값(0)과 같으므로 프로세스는 critical section으로 들어간다.

이후의 compare_and_swap() 호출은 lock의 값(1)이 expected 값(0)과 같지 않으므로 성공하지 못한다.

프로세스가 critical section을 빠져나올 때 lock을 0으로 변경하고, 다른 프로세스가 임계구역을 들어갈 수 있게 허용한다.

waiting 배열을 사용하여 한정된 대기 요구조건을 충족시킬 수 있다.

do {
    waiting[i] = TRUE;
    key = TRUE;
    while (waiting[i] && key)
        key = compare_and_swap(&lock, 0, &key);
    waiting[i] = FALSE;
 
    /* critical section */
 
    j = (i+1) % n;
    while ((j != i) && !waiting[j])
        j = (j+1) % n;
    if (j == i)
        lock = FALSE;
    else
        waiting[j] = FALSE;
        
    /* remainder section */
} while (TRUE);

6.15 서버는 개방된 연결의 개수를 제한하도록 설계될 수 있다. ~~~ 동시 연결의 개수를 제한하기 위하여 서버가 세마포를 어떻게 사용할 수 있는지 설명하시오.

8

세마포어는 연결 가능한 소켓의 개수만큼 초기화된다. 소켓이 연결되면 acquire()메소드가 호출되고, 연결이 해제되면 release()메소드가 호출된다. 만약 시스템의 모든 소켓이 연결되면, 현재 연결이 종료되고 release() 메소드가 호출될 때까지 다음 acquire() 호출은 블락된다

6.16 Windows Vista 는 slim reader-writer 락이라고 물리는 새로운 경량 동기화 도구를 제공한다. ~~~ slim reader-writer 락은 어느 쪽도 선호하지 않거나 FIFO 큐를 사용하여 대기 순서를 정하지도 않는다. 이러한 동기화 도구를 제공할 때 어떤 이점이 있는지 설명하시오.

6.17 다중 처리기 환경에서 test_and_set() 명령을 사용하여 wait() 와 signal()세마포 연산을 구현하는 방법을 보이시오. 해결방안은 바쁜 대기를 최소로 실행해야 한다.

10

수도코드

int guard = 0;
int semaphore value = 0;
 
wait()
{
    while (TestAndSet(&guard) == 1);
    if (semaphore value == 0) 
        atomically add process to a queue of processes
        waiting for the semaphore and set guard to 0;
    else 
        semaphore value--;
        guard = 0;
    
}
 
signal()
{
    while (TestAndSet(&guard) == 1);
    if (semaphore value == 0 && there is a process on the wait queue)
        wake up the first process in the queue
        of waiting processes
    else
        semaphore value++;
        guard = 0;
}

6.18 연습문제 4.21 ~~~ 해결 방안을 어떻게 수정해야 하는가?

6.19 동일한 유형의 동기화 문제를 푸는 데 사용될 수 있다는 측면에서 모니터와 세마포가 동등함을 보이시오.

12

monitor semaphore {
    int value = 0;
    condition c;
    semaphore increment() {
        value++;
        c.signal();
    }
    semaphore decrement() {
    while (value == 0)
        c.wait();
        value--;
    }
}

A monitor could be implemented using a semaphore in the following
manner. Each condition variable is represented by a queue of threads
waiting for the condition. Each thread has a semaphore associated with
its queue entry. When a thread performs a wait operation, it creates
a new semaphore (initialized to zero), appends the semaphore to the
queue associated with the condition variable, and performs a blocking
semaphore decrement operation on the newly created semaphore.When
a thread performs a signal on a condition variable, the first process in the
queue is awakened by performing an increment on the corresponding
semaphore.

6.20 유한 버퍼(bounded-buffer) 문제를 위한 모니터 코드를 작성하시오. 단 버퍼들은 모니터 내부에 내장되어 있다.

13

monitor bounded_buffer {
    int items[MAX_ITEMS];
    int numItems = 0;
 
    condition full, empty;
    void produce(int v) {
        while (numItems == MAX_ITEMS)
            full.wait();
        items[numItems++] = v;
        empty.signal();
    }
 
    int consume() {
        int retVal;
        while (numItems == 0)
            empty.wait();
        retVal = items[--numItems];
        full.signal();
        return retVal;
    }
}

6.21 연습문제 6.20의 유한 버퍼용 모니터는 그 안에서 상호 배제를 아주 엄격히 시행하므로 버퍼 개수가 적은 문제들에게만 적합하다.

1. 위의 설명이 과연 타당한 것인지에 대해 논하시오.
2. 보다 많은 개수의 문제를 위한 새로운 기법을 설계하시오.

14

모니터에서 생산자와 소비자의 값을 모니터의 로컬 버퍼로 복사하는데, 버퍼 개수가 많아질수록 메모리를 많이 차지하게 된다. 보다 많은 개수의 버퍼에 대해서는 포인터를 사용하면 된다.

6.22 Readers-writers 문제에서 공평성과 처리량 간의 균형(trade-off)을 논의하시오. 기아 현상을 유발하지 않는 해결책을 제시하시오.

15

Readers-writers 문제에서의 처리량은 한 writer가 단독으로 공유 가치에 접근하는 것을 허락하는 것과는 반대로 여러 reader 를 이롭게 함으로써 증가된다. 반면에 reader는 writer에게 기아를 유발할 수 있다. readers-writers 문제의 기아현상은 대기 프로세스와 관련된 timestamp를 기록함으로써 피할 수 있다. writer가 일을 끝냈을 때, 그것은 가장 오래 기다린 프로세스를 깨울 것이다. reader가 도착하여 다른 reader가 데이터베이스에 접근하고 있음을 알아차리면, 그것은 기다리는 writer가 없는 경우 임계구역에 진입할 것이다. 이러한 제약은 공평성을 보장할 수 있다.

6.23 모니터의 signal() 연산과 세마포에서 정의한 signal()연산이 어떻게 다른지 설명하시오.

16

모니터에서 signal연산 : 만약 시그널이 실행되었고 대기하는 스레드가 없다면, 시그널은 그냥 무시되고 시스템은 시그널이 실행되었다는 것을 기억하지 못한다. 만약 다음으로 wait 연산이 실행된다면 해당하는 스레드는 차단된다.

세마포어에서 signal연산 : 대기하는 스레드가 없어도 모든 시그널 연산이 해당 세마포어값의 증가로 나타난다. 이 증가때문에 다음의 wait 연산은 바로 실행될 것이다.

6.24 모니터에서 signal() 명령어는 오직 모니터 프로시저의 맨 마지막 줄에만 올 수 있다고 가정하자. 이러한 경우 6.7절에서 기술한 구현이 어떻게 간단해질 수 있는지 기술하시오.

17

signal 연산이 마지막에 온다면, signal 연산을 하는 프로세서에서 signal을 수신하는 프로세스로 lock이 전달될 수 있다. 그렇지 않으면, signal 연산을 하는 프로세서는 lock을 release해야 할 것이고, signal을 수신하는 프로세스는 lock을 얻기 위해서 lock을 얻고자 하는 다른 모든 프로세스와 경쟁해야 할 것이다.

6.25 어떤 시스템에는 ~~ . 할당 순서를 결정하는 데 우선순위 번호를 사용하여 세 개의 동일한 프린터를 이들 프로세스들에게 할당하는 모니터를 작성하시오.

18

monitor printers {
    int num_avail = 3;
    int waiting_processes[MAX PROCS];
    int num_waiting;
    condition c;
 
    void request_printer(int proc_number) {
        if (num_avail > 0) {
        num avail--;
        return;
        }
 
        waiting_processes[num_waiting] = proc_number;
        num_waiting++;
        sort(waiting processes);
 
        while (num_avail == 0 && waiting_processes[0] != proc_number)
                c.wait();
        waiting_processes[0] = waiting_processes[num waiting-1];
        num_waiting--;
        sort(waiting_processes);
        num_avail--;
    }
 
    void release_printer() {
    num_avail++;
    c.broadcast();
    }
}

6.28 모니터의 wait()와 signal()연산을 await(B)라는 단일 연산으로 교체하고자 한다. 여기서 B는 일반적인 boolean 수식이며 await(B)를 실행시킨 프로세스를 B가 true가 될 때까지 기다리게 만든다.

~~~

21

a : reader는 임계구역에 진입하기 전, 활성화된 writer와 대기중인 writer가 없다는 것을 체크하기 위해

    await( active writers == 0 && waiting writers == 0 ) 와 같은 구문을 사용할 수 있다.

   writer는 상호 배제를 위해 await( active writers == 0 && active readers == 0 ) 구문을 사용할 수 있다.

시스템은 signal 연산 후에 어떤 대기조건이 만족되는지 체크해서 어떤 대기 스레드가 실행될 것인지 확인해야 한다.