T (A) the Ready Queue Contains All the Processes That Are Ready to Execute and Waiting

Midterm Exam: 컴퓨터 시스템 및 실습

2008년 4월 23일 수요일 (총 100점)

학번: 이름:

1. 다음 질문에 True or False로 답하시오. [맞으면 2점, 틀리면 -0.5점] (총 16점)

[ T ] (a) The ready queue contains all the processes that are ready to execute and waiting for the CPU.

[ T ] (b) Each process is represented in the operating system by its own process-control block (PCB).

[ T ] (c) In general, user-level threads are faster to create and manage than are kernel-level threads.

[ F ] (d) Upcalls are used in kernel threads.

[ F ] (e) Priority inversion is a process scheduling technique.

[ F ] (f) All unsafe states are deadlocks. That is, an unsafe state must lead to a deadlock.

[ F ] (g) Major problem of RR scheduling is to predict the length of the next CPU bursts.

[ T ] (h) FCFS is non-preemptive, RR is preemptive, SJF Priority may be preemptive and non-preemptive.

2. Thread 생성시 어떤 자원이 사용되는가? 이들 자원은 프로세스가 생성시 사용되는 자원과 어떻게 다른가? (5점)

è Because a thread is smaller than a process, thread creation typically uses fewer resources than process creation. Creating a process requires allocating a process control block (PCB), a rather large data structure. The PCB includes a memory map, list of open files, and environment variables. Allocating and managing the memory map is typically the most time-consuming activity. Creating either a user or kernel thread involves allocating a small data structure to hold a register set, stack, and priority.

3. 멀티 프로세스보다 스레드를 사용하는 두 가지 장점은 무엇인가?

è CPU switching among peer threads and the creation of threads inexpensive compared with context switches among processes. (processing time aspects à more efficient)

Also, one multi-threaded process uses fewer resources than multiple redundant processes including memory, open filed and CPU scheduling. (resource usage aspects à more efficient)

스레드가 지닌 중요한 단점은 무엇인가?

è Because all threads can access every address in the task, a thread can read or write over any other thread’s stacks. That is, thread mechanism does not provide protection between threads.

스레드 사용이 장점이 되는 응용과 그렇지 않은 응용의 예를 제시하라. (8점)

è A Web server that services each request in a separate thread

Any kind of sequential program is not a good candidate to be threaded. An example of this is a program that calculates an individual tax return.

4. 경쟁 조건(race condition)이란 무엇인가? (4점)

è Several processes access and manipulate the same data concurrently, and the outcome of the execution depends on the particular order in which the access takes place.

5. Process Synchronization을 보장하는 방법으로 semaphore와 monitor 방법이 있다. 각각에 대해서 설명하고, semaphore의 어떤 단점을 해결하기 위해 monitor 방법이 사용되는지 설명하시오. (6점)

è Semaphore is integer variables with atomic operations down() and up() and synchronization tool that does not require busy waiting. Semaphore is initialized to the number of resources available and N processes share a semaphore, mutex. To use a resource, a process performs down() and to release a resource, a process perform up(). When the semaphore is 0, all resources are being used. So, the process blocks itself instead of busy waiting and up() operation wakes up a waiting process.

Monitor is a high-level abstraction that provides a convenient and effective mechanism for process synchronization. Monitor is defined as an abstract data type like class in object-oriented language (C++, Java). A monitor instance is shared among multiple processes and only one process may be active within the monitor at a time. Condition variables provides a method by which a monitor procedure can block its execution until it is signaled to continue

Although semaphores provide a convenient and effective mechanism for process synchronization, using them incorrectly can result in timing errors that are difficult to detect, since these errors happen only if some particular execution sequences take place and these sequences do not always occur. To make it easier to write correct programs, researchers proposed a higher-level synchronization primitive called a monitor

6. Readers-writers 문제의 동작에 있어서 fairness(공평성)과 throughput(처리량) 간의 tradeoff를 설명하시오. Readers-writers 문제에 있어서 starvation(기아)가 발생하는 것을 해결하는 방법을 제안하시오. (6점)

è Throughput in the readers-writers problem is increased by favoring multiple readers as opposed to allowing a single writer to exclusively access the shared values. On the other hand, favoring readers could result in starvation for writers. The starvation in the readers-writers problem could be avoided by keeping timestamps associated with waiting processes. When a writer is finished with its task, it would wake up the process that has been waiting for the longest duration. When a reader arrives and notices that another reader is accessing the database, then it would enter the critical section only if there are no waiting writers. These restrictions would guarantee fairness.

7. Deadlock을 처리하는 4가지 방법에 대해서 설명하시오. (5점)

A. just ignore the problem altogether

i. Ignore the problem and pretend that deadlocks never occur in the system;

1. used by most operating systems, including UNIX and Windows

2. It is then up to the application developer to write programs that handle deadlocks

B. detection and recovery

i. Allow the system to enter a deadlock state and then recover

1. deadlock detection, deadlock recovery

C. dynamic avoidance

i. careful resource allocation

D. prevention

i. negating one of the four necessary conditions

ii. ensure that the system will never enter a deadlock state

1. Use a protocol to prevent or avoid deadlocks

8. 아래 그림 1은 교통의 교착 상태를 보여준다. 다음 질문에 답하시오. (총 8점)

(a) 교착 상태가 발생하는 네 가지 조건에 대해서 적고 간단히 설명하시오. (2점)

è The four necessary conditions for a deadlock are

1. Mutual exclusion condition: each resource assigned to 1 process or is available

2. Hold and wait condition: process holding resources can request additional

3. No preemption condition: previously granted resources cannot forcibly taken away

4. Circular wait condition: must be a circular chain of 2 or more processes & each is waiting for resource held by next member of the chain

(b) 그림 1의 실례에 적용된 교착 상태를 위한 네 가지 필요 조건을 설명하시오. (4점)

è The mutual exclusion condition holds as only one car can occupy a space in the roadway. Hold-and-wait occurs where a car holds onto their place in the roadway while they wait to advance in the roadway. A car cannot be removed (i.e. preempted) from its position in the roadway. Lastly, there is indeed a circular wait as each car is waiting for a subsequent car to advance. The circular wait condition is also easily observed from the graphic.

è A simple rule that would avoid this traffic deadlock is that a car may not advance into an intersection if it is clear they will not be able to immediately clear the intersection.

그림 1. 교통의 교착 상태

9. 교착 상태 방지나 방지 기법이 없이 1개월에 5,000개의 작업을 실행하는 시스템을 생각해 보자. 1개월에 두 번 정도 교착 상태가 발생하며 그 때마다 운영원이 약 10개의 작업을 종료시키고 재실행시킨다. 각 작업은 중앙처리 장치 시간으로 약 2달러의 가치가 있으며, 종료된 작업들은 실행이 취소될 때 약 50% 정도 실행되었다.

시스템 프로그래머는 다음과 같이 추정하기를 교착 상태 방지 알고리즘(은행가 알고리즘 같은 것)을 사용하면 각 작업마나 평균 10%의 실행 시간이 증가한다고 하였다. 컴퓨터가 현재 약 30% 정도의 유휴 시간을 갖고 있으므로, 반환 시간(turnaround time)이 약 20% 정도 증가하더라도 1개월에 5,000개의 작업은 모두 실행 시킬 수 있다. (총 12점)

(a) 실행 시간과 비용 측면에서 교착상태 방지 알고리즘을 적용하는 것이 이로운가? 이롭지 않은가? (계산을 정확히 하여 비교할 것) (8점)

è done in the course class

(b) 교착 상태 방지 알고리즘을 이용하면 어떤 장점이 있는가? (5점)

è A deadlock-avoidance scheme tends to increase the runtime overheads due to the cost of keep track of the current resource allocation. However, a deadlock-avoidance scheme allows for more concurrent use of resources than schemes that statically prevent the formation of deadlock. Also, deadlock-avoidance scheme supports the system stability. Some important systems need to be guaranteed to process (operate) without stopping (falling into deadlock). So, we need to support the deadlock-avoidance scheme to prevent a deadlock.

10. 많은 수의 중앙처리장치 스케줄링 알고리즘들은 매개변수를 사용하고 있다. 예를 들면, 라운드로빈(RR) 알고리즘은 시간 할당량(quantum)을 표시하는 매개변수를 필요로 한다. 다단계 피드백 큐(Multi-level Feedback Queue)는 큐의 수, 각 큐에 대한 스케줄링 알고리즘, 큐 사이에 프로세스를 이동시키는 기준 등을 정의하기 위해 매개변수를 필요로 한다.

그러므로 이들 알고리즘은 실제로 알고리즘들의 집합이다. (예를 들면, 선입선처리(FCFS) 알고리즘은 무한한 시간 할당량을 가진 라운드로비(RR) 알고리즘이다.) 다음 알고리즘들의 각 쌍 사이에는 무슨 관계가 있는가? (아무 관계도 없으면 관계 없음이라고 명시하시오) (총 6점)

(a) 다단계 피드백 큐(Multi-level Feedback Queue)와 FCFS

è The lowest level of MLFQ is FCFS.

(b) 우선순위(Priority)와 FCFS

è FCFS gives the highest priority to the job having been in existence the longest.

è None

11. 다음의 스케줄링 알고리즘들이 짧은 프로세스들을 어떻게 차등해 처리하는지 설명하시오. (6점)

(a) FCFS

è discriminates against short jobs since any short jobs arriving after long jobs will have a longer waiting time.

(b) SJF

è processes the shortest job first.

è treats all jobs equally (giving them equal bursts of CPU time) so short jobs will be able to leave the system faster since they will finish first.

12. Batch system과 Interactive system에서의 process 스케줄링 알고리즘을 적용하여 얻으려는 최종 goal은 무엇인가? (scheduling criteria 측면에서 적으시오.) (5점)

è Batch system

- Throughput: maximize jobs per hour

- Turnaround time: minimize time between submission and termination

- CPU utilization: keep the CPU busy all the time

Interactive system

- Response time: respond to requests quickly

- Proportionality: meet users’ expectations

13. 다음 프로세스들의 집합을 생각해 보자. 중앙처리장치 버스트 (CPU burst) 시간 단위는 millisecond이다. (총 12점)

Process CPU Burst Time Priority

P1 10 3

P2 1 1

P3 2 3

P4 1 4

P5 5 2

프로세스들은 시간 0에 P1, P2, P3, P4, P5 순으로 도착된다고 가정한다.

(a) SJF, Non-preemptive Priority (작은 우선순위 번호가 높은 우선순위를 의미), RR(quantum=2)을 이용해 프로세스들의 실행을 설명하는 Gantt 차트를 그리시오. (6점)

(b) 각 스케줄링 알고리즘에 대한 반환 시간(turnaround time)은 얼마인가? (3점)