[운영체제] 운영체제 공룡책 연습문제 풀이 7장

목차

7.1 What is the meaning of the term busy waiting? What other kinds of waiting are there in an operating system? Can busy waiting be avoided altogether? Explain your answer.

7.2 Explain why spinlocks are not appropriate for uniprocessor systems yet may be suitable for multiprocessor systems.


7.3 Prove that, in the bakery algorithm (Setion 7.2.2), the following property holds :
If Pi is in its critical section and Pk (k≠i) has already chosen its number[k≠i] has already chosen its number[k]≠0, then (number[i], I) < (number[k], k).

7.4 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 following variables:

7.5 The first known correct software solution to the critical-section problem for n processes with
a lower bound on waiting of n-1 turns was presented by Eisenberg and McGuire.
The processes share the following variables :
.......

본문내용

7.1 What is the meaning of the term busy waiting? What other kinds of waiting are there in an operating system? Can busy waiting be avoided altogether? Explain your answer.

busy waiting이란 하나의 프로세스가 C.S에 들어가면 Critical Section에 들어가려고 하는 다른 프로세스가 Entry Section의 코드를 루프를 계속 돌며 대기하는 프로세스가 많을 때를 지칭한다. 한 프로세스가 임계 구역에 있으면, 이 임계 구역에 진입하려는 다른 프로세스들은 진입부에서 계속 반복해야 한다. 바쁘게 대기하는 것은 다른 프로세스들이 생산적으로 사용할 수 있는 CPU 시간을 낭비하게 하여 하나의 CPU가 여러 프로세스에 공유되는 다중 프로그래밍 시스템에는 치명적이다. 그러나, 프로세스가 lock을 기다릴 때 문맥 교환(context switch)이 불필요하여 lock이 매우 짧은 시간만 적용될 때는 매우 유용하다. 다중 프로세스 시스템에서 busy waiting를 극복하기 위하여 wait와 signal 연산을 수정한다.
-진입에 실패하고 대기할 필요가 있는 프로세스를 대기 큐로 보냄
-대기 큐에서 기다리는 프로세스들은 신호를 받아 실행 가능한 상태로 변화
즉 busy waiting을 해결하는 방법은 현재 하나의 Process가 C.S.에서 작업을 할 때 들어오는 다른 Process를 Block해서 waiting 상태로 만들고, 현재 C.S.에서 작업하던 Process가 끝나서 Exit Section을 나오면 하나의 Process를 wakeup 해준다.

7.2 Explain why spinlocks are not appropriate for uniprocessor systems yet may be suitable for multiprocessor systems.

uniprocessor : wait와 signal 수행시 인터럽트를 금지시키면 다른 프로세스가 끼어들지 않으므로 끝까지 수행가능
multiprrocessor : 인터럽트 효과가 없으므로 소프트웨어적으로 해결가능 turn+flag algo
즉 단일 프로세서에서는 바쁜 대기 상태는 다른 프로세스들이 생산적으로 사용할 수 있는 중앙처리장치 시간을 낭비하게 된다. 그러나 다중 프로세서 환경에서의 Spinlock은 유용하게 사용된다. Spinlock의 장점은 프로세스가 록에서 대기할 때 문맥교환이 불필요하다는 점이다. 그러므로, 록이 매우 짧은 시간만 적용될 때는 Spinlock이 매우 유용하다.

참고 자료

없음