6강. 연습문제

6.1 The first known correct software solution to the critical-section problem for two processes was developed by Dekker. The two processes, P0 and P1, share the follwing variables:

boolean flag[2]; / initially false /

int turn;

The structure of process Pi(i==0 or 1) is shown in Figure 6.27; the other process is Pj(j == 1 or 0). Prove that the algorithm satisfies all three requirements for the critical-section problem.

do {
	flag[i] = TRUE;
	while (flag[j)){
		if (turn == j) {
			flag[i] = FALSE;
			while (turn == j) ; // do nothing
			flag[i] = TRUE;
		}
	}

//critical section

turn = j;
flag[i] = FALSE;

}while (TRUE);

---

Solution이 만족해야하는 세가지 조건

1. Mutual Exclusion : 한번에 하나의 Process만 Critical Section에 접근이 가능해야한다.
2. Progress : Critical Section에 들어가고 싶은 Process들 중 Process를 선택하는 작업이 무한히 연기되어서는 안된다. -> Critical Section이 비어있으면 들어갈 수 있어야 한다.
3. Bounded Waiting : Critical Section에 들어가고 싶은 Process가 언젠가는 Critical Section에 들어갈 수 있어야 한다.
4. flag와 turn 변수에 의해 Mutual Exclusion이 보장된다. 하나의 프로세스가 Critical Section에 들어가 있다면, flag[j]는 TRUE이고 turn이 j이기 때문에 while문에 의해 기다리게 된다.
5. flag와 turn 변수에 의해 Progress가 보장된다. Critical section이 비어있다면 turn이 자신 프로세스를 가리키고 있고, while문에 의해 기다리지 않고 Critical section으로 들어갈 수 있다.
6. turn에 의해 Bounded Waiting이 보장된다. 두 프로세스가 Critical Section에 들어가길 원해 flag[i]와 flag[j]가 TRUE가 되어도 turn에 의해 기다리게 되고, 한 프로세스가 Critical Section에서 나올 때 turn을 변경해줌으로써 기다리고 있던 프로세스가 바로 Critical Section에 들어갈 수 있다.

6.2 Explain why spinlocks are not appropriate for single-processor systems yet are often used in multiprocessor systems

---

Spinlock 방식은 Critical Section에 있는 프로세스가 Exit하기 위해서는 다른 프로세스가 실행되어야 한다. 프로세서를 차지하고 있는 프로세스가 Critical Section에 있다면 다른 프로세스가 프로세서를 할당받지 못해 프로세스가 Critical Section으로 들어갈 수 없다.

6.3 Explain why implementing synchronization primitives by disabling interrupts is not appropriate in a single-processor system if the synchronization primitives are to be used in user-level programs

---

User-level Program이 Interrupt를 허용하지 않도록 하는 Synchronization Primitives 방식을 사용하게 된다면 Timer Interrupt를 Disable하여 Context Switching이 일어나지 않을 수 있고 하나의 프로세스만 계속 실행되게 되어 적절하지 않다.

6.4 Describe how the Swap() instruction can be used to provide mutual exclusion that satisfies the bounded-waiting requirement.

---

Exit Section에서 한 프로세스가 Lock을 False로 바꾸면서 Critical Section을 빠져나가게 되면, 기다리고 있던 다른 프로세스는 Key와 Lock을 Swap()을 하여 Key가 False가 되게 되고 반복문을 탈출하면서 Critical Section에 진입하게 된다. 이를 통해서 Critical Section에는 하나의 프로세스만 진입할 수 있는 Mutual Exclustion조건을 만족하고, 무제한으로 프로세스가 기다리지 않도록 하는 Bounded-Waiting 조건도 만족하게 된다.

6.5 Servers can be designed to limit the number of open connections. For examples, a server may wish to have only N socket connections at any point in time. As soon as N connections are made, the server wiill not accept another incoming connection until an existing connection is released. Explain how semaphores can be used by a server to limit the number of concurrent connections.

---

Semaphore는 공유된 자원의 수를 가리키는 변수이다. Exisiting Connection이 Released될 때 Semaphore의 수를 증가시기는 Signal()을 호출하게 되면, Wait()함수를 호출한 다른 Socket Connection은 Semaphore의 수를 감소시키고 Connection을 하게 된다. Semaphore = N으로 설정하여 Connection의 수를 제한할 수 있다.