OS_운영체제 카테고리의 PE Series는
2021.10.20 - [학부공부/OS_운영체제] - 00. 운영체제 STUDY 시작
00. 운영체제 STUDY 시작
안녕하세요! 제가 티스토리 페이지를 만든 후 처음으로 작성하는 글입니다... 복학하기 전 개인적인 공부를 정리하자는 취지로 시작하는 글이라 가독성이 떨어지고 부족한 부분이 있을 수 있으
ku320121.tistory.com
포스팅에서 소개한 text book의 연습문제를 풀이한 것을 정리한 것입니다. 해설을 참고하지 않았기 때문에 풀이에 오류가 있을 수 있습니다. 또한 운영체제 교과목 내용을 벗어나는 내용과 사견이 풀이에 포함되어 있을 수 있습니다.
6.2. 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은 trap과 유사하게 CPU Cycle을 사용하면서 Critical section에 진입할 조건이 만족할 때까지 loop를 돌면서 no operation을 수행하는 것이다. 이는 CPU Cycle의 낭비이며 대기 중인 process가 2개 이상일 때 어떤 process가 critical section에 진입할지 예측할 수 없다는 문제가 발생한다. OS에서는 busy waiting과 다른 종류의 waiting도 존재한다. Process state에서 sleep state를 상기해보면 된다. Busy waiting으로 진입한 process를 sleep queue를 이용하여 CPU Cycle을 burn하지 않게 한다면 context switching overhead보다 큰 gain을 얻을 수 있을 것이다. 다시 critical resource를 할당받을 수 있을 때 wake up한다. 따라서 busy waiting은 약간의 performance loss를 허용하는 sleep&wake up 방식으로 해결할 수 있다.
6.4. Show that, if the wait() and signal() semaphore operations are not executed atomically, then mutual exclusion may be violated.
만약 wait()가 atomic하게 실행되지 않아 wait() code에서 while(S <= 0);과 s--;이 분리되어 실행된다면 mutually exclusion을 위반할 수 있게 된다. S = 1이고 P1, P2가 동시에 wait()를 call하는 상황일 때 P1이 while(S <= 0);를 수행하고 P2가 while(S<=0);을 수행한다면 P1과 P2 모두 Critical section으로 진입하게 된다. Critical resource 가용 instance는 1개인데 2개의 process를 할당하는 것은 mutually exclusion위반이다.
6.6. Race conditions are possible in many computer systems. Consider a banking system that maintains an account balance with two functions: deposit(amount) and withdraw(amount). These two functions are passed the amount that is to be deposited or withdrawn from the bank account balance. Assume that a husband and wife share a bank account. Concurrently, the husband calls the withdraw() function, and the wife calls deposit(). Describe how a race condition is possible and what might be done to prevent the race condition from occurring.
계좌를 공유하면서 계좌 잔고에 대한 변수도 process(or thread)들이 공유하는 상황을 고려해 볼 수 있다. 만약잔고변수가 공유되고 concurrent하게 실행되는 경우 execution interleaving은 임의의 order가 될 수 있다. deposit()과with-draw 각각은 sequencing하게 동작하더라도 instruction level에서 실행되는 것을 고려해볼 때 결과를예측할수 없다는 문제가 발생한다(Race condition). 중간 연산 과정에서 해당 내용이 반영되지 않고 덮어써지는 상황이다. Race condition 발생 가능성은 은행 시스템과 같이 무결성이 중요한 시스템에 치명적이다. Race condition 발생을야기하는 resource에 대해 Critical section으로 data에 대한 접근을 관리할 수 있다.
8.6. Consider a computer system that runs 5,000 jobs per month and has no deadlock-prevention or deadlock-avoidance scheme. Deadlocks occur about twice per month, and the operator must terminate and rerun about ten jobs per deadlock. Each job is worth about two dollars (in CPU time), and the jobs terminated tend to be about half done when they are aborted.
A systems programmer has estimated that a deadlock-avoidance algorithm (like the banker’s algorithm) could be installed in the system with an increase of about 10 percent in the average execution time per Practice Exercises 345 job. Since the machine currently has 30 percent idle time, all 5,000 jobs per month could still be run, although turnaround time would increase by about 20 percent on average.
a. What are the arguments for installing the deadlock-avoidance algorithm?
b. What are the arguments against installing the deadlock-avoidance algorithm?
a.
만약 해당 시스템이 10(task)/5000(task) = 0.2%의 deadlock 발생이 치명적이라면 deadlock prevention algorithm의 도입을 적극적으로 주장할 수 있다. 이러한 시스템의 예로는 무기시스템(방공망) 등이 있을 수 있다. Real time service를 제공해야 하는 시스템의 경우 처리시간이 늘어나더라도 deadlock 발생을 원천적으로 차단하여 처리시간을 예측 가능한 boundary에 들어오도록 함과 동시에 반드시 deadline을 준수하도록 만드는 것이 더 중요할 수 있다.
b.
기존 손실 계산
# of task = 5000, Deadlock prevention, avoidance 기법이 없는 시스템일 때 교착 상태
10(task) * 1(회/task) * 2(회/month) * 2(달러/task) * 50% = 20달러 손실
5000(task) * 2(달러/task) = 10000달러
5000개의 task를 수행하는 가치에 비해 deadlock으로 인한 피해액은 0.2%에 불과하다. 만약 deadlock prevention algorithm을 도입하여 작업당 평균 실행 시간이 10% 증가한다면 CPU는 해당 시간동안 dynamic power를 더 소모하게 된다. 데이터센터에서 사용하는 전력소모량을 생각해보았을 때 이는 20달러보다 더 큰 손실을 야기할 수 있다.
8.7. Can a system detect that some of its threads are starving? If you answer “yes,” explain how it can. If you answer “no,” explain how the system can deal with the starvation problem.
감지할 수 있다. Thread에 starvation이 발생한다면 resource를 allocation받기 전까지 control flow가 멈출 것이다. 따라서 HW적으로 시간에 따른 PC(Program counter)변화를 추적할 수 있다. 또는 cache miss ratio 등을 확인해볼 수도 있다.(현실적으로 cache miss ratio가 계속 0인 application은 존재하지 않기 때문이다.) 또는 PCB(or TCB)에 resource management와 관련한 information을 trace하도록 할 때 시간에 대한 정보(request로부터 allocation받은 시간, resource 점유 시간 등)를 함께 저장한다면 starvation을 감지할 수 있다. Starvation은 task에 우선순위를 부여하여 해결할 수 있다. 우선순위가 높은 task가 resource를 빼앗는다면 더 이상 waiting을 하지 않아도 되기 때문이다.(단, task가 system resource를 넘어서는 request를 한 시점에서 계속 발생시킨다면 여전히 starvation이 발생한다.)
8.8. Consider the following resource-allocation policy. Requests for and releases of resources are allowed at any time. If a request for resources cannot be satisfied because the resources are not available, then we check any threads that are blocked waiting for resources. If a blocked thread has the desired resources, then these resources are taken away from it and are given to the requesting thread. The vector of resources for which the blocked thread is waiting is increased to include the resources that were taken away.
For example, a system has three resource types, and the vector Available is initialized to (4,2,2). If thread T0 asks for (2,2,1), it gets them. If T1 asks for (1,0,1), it gets them. Then, if T0 asks for (0,0,1), it is blocked (resource not available). If T2 now asks for (2,0,0), it gets the available one (1,0,0), as well as one that was allocated to T0 (since T0 is blocked). T0’s Allocation vector goes down to (1,2,1), and its Need vector goes up to (1,0,1).
a. Can deadlock occur? If you answer “yes,” give an example. If you answer “no,” specify which necessary condition cannot occur.
b. Can indefinite blocking occur? Explain your answer.
a.
Deadlock은 발생할 수 없다. Deadlock이 발생할 수 있는 4가지 조건 중 no preemption조건을 위배하므로 deadlock은 발생하지 않는다. 다만 뺏어오지 못하는 resource가 존재한다면 이러한 해결책이 완전한 해결책이 될 수 없다.
(T0의 가용 자원을 뺏어와도 T1의 Need vector에 비해 부족할 경우 T1도 봉쇄 상태에 빠져든다. 결국 T0, T1만이 실행되고 있는 thread였다면 모든 thread가 봉쇄 상태에 빠질 수는 있지만 이는 system의 resource 자체가 부족한 것이므로 deadlock은 아니다.)
B.
a.에서 언급한 경우가 deadlock은 아니지만 무한 봉쇄에 빠지는 case이다. 또는 다른 thread에 의해 계속 선점되는 경우 T0, T1은 무한 봉쇄에 빠질 수 있다.
8.9. Consider the following snapshot of a system:
Using the banker’s algorithm, determine whether or not each of the following states is unsafe. If the state is safe, illustrate the order in which the threads may complete. Otherwise, illustrate why the state is unsafe.
a. Available = (0, 3, 0, 1)
b. Available = (1, 0, 0, 2)
a.
Loop 반복해도 T0, T4가 resource를 allocation 받지 못한다 : Not safe
b.
Safe state <T1, T2, T3, T4, T0>
8.10. Suppose that you have coded the deadlock-avoidance safety algorithm that determines if a system is in a safe state or not, and now have been asked to implement the deadlock-detection algorithm. Can you do so by simply using the safety algorithm code and redefining Maxi = Waitingi + Allocationi, where Waitingi is a vector specifying the resources for which thread i is waiting and Allocationi is as defined in Section 8.6?
Explain your answer.
8.11. Is it possible to have a deadlock involving only one single-threaded process? Explain your answer.
불가능하다. 직관적인 근거는 Resource allocation graph에서 Cycle이 만들어 질 수 없기 때문이다. dEADLOCK이 발생하기 위한 최소한의 조건인 4가지 conditions에 대해 떠올려보면 우선 mutual exclusion이 발생하지 않는다. 또한 thread가 최소한 하나의 resource를 점유한 채, 다른 thread에 의해 점유된 resource를 추가로 얻기 위해 반드시 wait해야 된다는 Hold&wait condition도 만족하지 않는다. Hold*wait condition이 만족하지 않으므로 당연히 circular wiat condition도 만족할 수 없다.
댓글