6.1 A CPU-scheduling algorithm determines an order for the execution
of its scheduled processes. Given n processes to be scheduled on one
processor, how many different schedules are possible? Give a formula
in terms of n.
처리상태->준비상태 (타이머 인터럽트 등)
처리상태->블록상태 (i/o요청이나 wait() 등)
블록상태->준비상태 (i/o의 완료 등)
프로세스 종료
6.2 Explain the difference between preemptive and nonpreemptive scheduling.
선점형 스케줄링의 경우 프로세스가 끝나지 않더라도 강제적으로 cpu 점유를 뺏어 다른 프로세스에게 할당해주지만 비선점형 스케줄링의 경우 cpu 를 사용하고 있는 프로세스가 끝날 때까지 그 프로세스에게 cpu를 사용하게 해준 후 끝나면 다음 프로세스에게 cpu를 할당해준다.
6.3 Suppose that the following processes arrive for execution at the times
indicated. Each process will run for the amount of time listed. In
answering the questions, use nonpreemptive scheduling, and base all
decisions on the information you have at the time the decision must be
made.
Process Arrival Time Burst Time
P1 0.0 8
P2 0.4 4
P3 1.0 1
a. What is the average turnaround time for these processes with the
FCFS scheduling algorithm?
11
b. What is the average turnaround time for these processes with the
SJF scheduling algorithm?
6.333333333333
c. The SJF algorithm is supposed to improve performance, but notice
that we chose to run process P1 at time 0 because we did not know
that two shorter processes would arrive soon. Compute what the
average turnaround time will be if the CPU is left idle for the first
1 unit and then SJF scheduling is used. Remember that processes
P1 and P2 are waiting during this idle time, so their waiting time
may increase. This algorithm could be called future-knowledge
scheduling.
p3, p2, p1 순으로 들어오면 됨
6.4 What advantage is there in having different time-quantum sizes at
different levels of a multilevel queueing system?
상호작용 프로세스와 같이 높은빈도가 필요한 프로세스는 작은 타임퀀텀의 큐에 있을 수 있고 자주 서비스될 필요가 없는 프로세스는 컨텍스트 스위칭이 덜 요구되는 긴 퀀텀의 큐에 들어가 컴퓨터를 더욱 효율적으로 사용할 수 있게 만들어준다
6.5 Many CPU-scheduling algorithms are parameterized. For example, the
RR algorithm requires a parameter to indicate the time slice. Multilevel
feedback queues require parameters to define the number of queues, the
scheduling algorithm for each queue, the criteria used to move processes
between queues, and so on.
These algorithms are thus really sets of algorithms (for example, the
set of RR algorithms for all time slices, and so on). One set of algorithms
may include another (for example, the FCFS algorithm is the RR algorithm
with an infinite time quantum). What (if any) relation holds between the
following pairs of algorithm sets?
a. Priority and SJF
짧을수록 우선순위가 높다
b. Multilevel feedback queues and FCFS
짧은 프로세스의 경우 FCFS 로 수행되지만 특정 타임퀀텀을 넘긴 프로세스의 경우 우선순위가 낮아져 SJF 와 같은 형태를 띄게 됨
c. Priority and FCFS
들어온 순서대로 우선순위를 가진다
d. RR and SJF
RR 과 SJF에서 완료된 프로세스를 보면 대체로 짧은 프로세스가 먼저 수행되나 SJF 의 경우 starvation이 발생할 수 있다.
6.6 Suppose that a scheduling algorithm (at the level of short-term CPU
scheduling) favors those processes that have used the least processor
time in the recent past. Why will this algorithm favor I/O-bound
programs and yet not permanently starve CPU-bound programs?
IO bound 프로그램은 cpu 사용시간이 짧아 스케줄링에서의 우선순위가 높지만 cpu 사용 이후 IO 를 위해 waiting queue에 들어가있으면 ready 큐에는 cpu-bound 프로그램만 남게 되기에 cpu-bound 프로그램은 starvation 현상을 겪지 않는다.
6.7 Distinguish between PCS and SCS scheduling.
PCS 란 한 프로세스 내에 다른 쓰레드끼리 경쟁하는 범위를 나타냄
scs 란 모든 프로세스 끼리 경쟁하는 범위를 나타냄.
6.8 Assume that an operating system maps user-level threads to the kernel
using the many-to-many model and that the mapping is done through
the use of LWPs. Furthermore, the system allows program developers to
create real-time threads. Is it necessary to bind a real-time thread to an
LWP?
쓰레드 별로 스케줄링 하기 위해선 쓰레드와 같은 개수로 lwp 를 바인딩해주던가 혹은 커널모드를 사용해야할 쓰레드 만이라도 실시간으로 lwp 에 바인딩을 해주어야...(좀더 확실하게 알아 볼 것.)
6.9 The traditional UNIX scheduler enforces an inverse relationship between
priority numbers and priorities: the higher the number, the lower the
priority. The scheduler recalculates process priorities once per second
using the following function:
Priority = (recent CPU usage / 2) + base
where base = 60 and recent CPU usage refers to a value indicating how
often a process has used the CPU since priorities were last recalculated.
Assume that recent CPU usage is 40 for process P1, 18 for process P2,
and 10 for process P3. What will be the new priorities for these three
processes when priorities are recalculated? Based on this information,
does the traditional UNIX scheduler raise or lower the relative priority
of a CPU-bound process?
P1 : 20+60 = 80
P2 : 9+ 60 = 69
P3 : 5+ 60 = 65
6.10 Why is it important for the scheduler to distinguish I/O-bound programs
from CPU-bound programs?
구분하여 잘 섞어 스케줄링 함으로써 cpu 를 효율적으로 사용하기 위해서.
6.11 Discuss how the following pairs of scheduling criteria conflict in certain
settings.
a. CPU utilization and response time
cpu 사용률이 높으려면 컨텍스트 스위치가 일어나지 않고 하나의 프로세스가 계속 cpu를 사용하여야 하지만 컨텍스트 스위치가 자주 일어나지 않으면 반응 시간이 길어진다.
b. Average turnaround time and maximum waiting time
평균 turnaround time 을 줄이기 위해선 짧은 프로세스를 먼저 수행하는 SJF 방법을 이용하여야 하는데 이는 긴 프로세스의 최대 waiting time 이 길어지는 단점을 동반한다.
c. I/O device utilization and CPU utilization
I/O 장치 사용률이 극대화 되려면 io 인터럽트가 발생하거나 io 가 완료되는 시점에서 즉시 컨텍스트 스위치가 되어야 하는데 이는 cpu 사용률의 저하를 동반한다.
6.12 One technique for implementing lottery schedulingworks by assigning
processes lottery tickets, which are used for allocating CPU time.Whenever
a scheduling decision has to be made, a lottery ticket is chosen
at random, and the process holding that ticket gets the CPU. The BTV
operating system implements lottery scheduling by holding a lottery
50 times each second, with each lottery winner getting 20 milliseconds
of CPU time (20 milliseconds × 50 = 1 second). Describe how the BTV
scheduler can ensure that higher-priority threads receive more attention
from the CPU than lower-priority threads.
6.13 In Chapter 5, we discussed possible race conditions on various kernel
data structures. Most scheduling algorithms maintain a run queue,
which lists processes eligible to run on a processor.On multicore systems,
there are two general options: (1) each processing core has its own run
queue, or (2) a single run queue is shared by all processing cores. What
are the advantages and disadvantages of each of these approaches?
전자의 경우 마스터 cpu 만이 커널코드를 실행하고(마스터 cpu만이 시스템 데이터 구조와 공유 데이터 접근 가능), 나머지 cpu들은 유저코드만 실행하며 IO작업이나 커널코드의 실행이 필요하면 마스터cpu 에 시스템 콜을 하기 때문에 critical section problem 이 없어 구현하기 쉽다는 장점을 가지고 있지만 프로그램 실행에 있어서 비효율적이다. 후자의 경우 전자에 비해 프로그램 실행에 효율적이지만 race condition에 따라 critical section problem이 발생하기 때문에 구현시 이를 해결하기 위한 해결방법이 필요하다.
6.14 Consider the exponential average formula used to predict the length of
the next CPU burst. What are the implications of assigning the following
values to the parameters used by the algorithm?
a. = 0 and 0 = 100 milliseconds
b. = 0.99 and 0 = 10 milliseconds
6.15 A variation of the round-robin scheduler is the regressive round-robin
scheduler. This scheduler assigns each process a time quantum and a
priority. The initial value of a time quantum is 50 milliseconds. However,
every time a process has been allocated the CPU and uses its entire time
quantum (does not block for I/O), 10 milliseconds is added to its time
quantum, and its priority level is boosted. (The time quantum for a
process can be increased to a maximum of 100 milliseconds.) When a
process blocks before using its entire time quantum, its time quantum is
reduced by 5 milliseconds, but its priority remains the same. What type
of process (CPU-bound or I/O-bound) does the regressive round-robin
scheduler favor? Explain.
6.16 Consider the following set of processes, with the length of the CPU burst
given in milliseconds:
Process Burst Time Priority
P1 2 2
P2 1 1
P3 8 4
P4 4 2
P5 5 3
The processes are assumed to have arrived in the order P1, P2, P3, P4, P5,
all at time 0.
a. Draw four Gantt charts that illustrate the execution of these
processes using the following scheduling algorithms: FCFS, SJF,
nonpreemptive priority (a larger priority number implies a higher
priority), and RR (quantum = 2).
b. What is the turnaround time of each process for each of the
scheduling algorithms in part a?
c. What is the waiting time of each process for each of these scheduling
algorithms?
d. Which of the algorithms results in the minimum average waiting
time (over all processes)?
6.17 The following processes are being scheduled using a preemptive, roundrobin
scheduling algorithm. Each process is assigned a numerical
priority, with a higher number indicating a higher relative priority.
In addition to the processes listed below, the system also has an idle
task (which consumes no CPU resources and is identified as Pidle ). This
task has priority 0 and is scheduled whenever the system has no other
available processes to run. The length of a time quantum is 10 units.
If a process is preempted by a higher-priority process, the preempted
process is placed at the end of the queue.
Thread Priority Burst Arrival
P1 40 20 0
P2 30 25 25
P3 30 25 30
P4 35 15 60
P5 5 10 100
P6 10 10 105
a. Show the scheduling order of the processes using a Gantt chart.
b. What is the turnaround time for each process?
c. What is the waiting time for each process?
d. What is the CPU utilization rate?
6.18 The nice command is used to set the nice value of a process on Linux,
as well as on other UNIX systems. Explain why some systems may allow
any user to assign a process a nice value >= 0 yet allow only the root
user to assign nice values < 0.
6.19 Which of the following scheduling algorithms could result in starvation?
a. First-come, first-served
b. Shortest job first
c. Round robin
d. Priority
6.20 Consider a variant of the RR scheduling algorithm in which the entries
in the ready queue are pointers to the PCBs.
a. What would be the effect of putting two pointers to the same
process in the ready queue?
b. What would be two major advantages and two disadvantages of
this scheme?
c. How would you modify the basic RR algorithm to achieve the same
effect without the duplicate pointers?
6.21 Consider a system running ten I/O-bound tasks and one CPU-bound
task. Assume that the I/O-bound tasks issue an I/O operation once for
every millisecond of CPU computing and that each I/O operation takes
10 milliseconds to complete. Also assume that the context-switching
overhead is 0.1 millisecond and that all processes are long-running tasks.
Describe the CPU utilization for a round-robin scheduler when:
a. The time quantum is 1 millisecond
b. The time quantum is 10 milliseconds
6.22 Consider a system implementing multilevel queue scheduling. What
strategy can a computer user employ to maximize the amount of CPU
time allocated to the user’s process?
6.23 Consider a preemptive priority scheduling algorithm based on dynamically
changing priorities. Larger priority numbers imply higher priority.
When a process is waiting for the CPU (in the ready queue, but not
running), its priority changes at a rate .When it is running, its priority
changes at a rate . All processes are given a priority of 0 when they
enter the ready queue. The parameters and can be set to give many
different scheduling algorithms.
a. What is the algorithm that results from > > 0?
b. What is the algorithm that results from < < 0?
6.24 Explain the differences in how much the following scheduling algorithms
discriminate in favor of short processes:
a. FCFS
b. RR
c. Multilevel feedback queues
6.25 Using the Windows scheduling algorithm, determine the numeric
priority of each of the following threads.
a. A thread in the REALTIME PRIORITY CLASS with a relative priority
of NORMAL
b. A thread in the ABOVE NORMAL PRIORITY CLASS with a relative
priority of HIGHEST
c. A thread in the BELOW NORMAL PRIORITY CLASS with a relative
priority of ABOVE NORMAL
6.26 Assuming that no threads belong to the REALTIME PRIORITY CLASS and
that none may be assigned a TIME CRITICAL priority, what combination
of priority class and priority corresponds to the highest possible relative
priority inWindows scheduling?
6.27 Consider the scheduling algorithm in the Solaris operating system for
time-sharing threads.
a. What is the time quantum (in milliseconds) for a thread with
priority 15? With priority 40?
b. Assume that a thread with priority 50 has used its entire time
quantum without blocking. What new priority will the scheduler
assign this thread?
c. Assume that a thread with priority 20 blocks for I/O before its time
quantum has expired. What new priority will the scheduler assign
this thread?
6.28 Assume that two tasks Aand B are running on a Linux system. The nice
values of Aand B are−O5 and+5, respectively. Using the CFS scheduler as
a guide, describe how the respective values of vruntime vary between
the two processes given each of the following scenarios:
•Both Aand B are CPU-bound.
•Ais I/O-bound, and B is CPU-bound.
•Ais CPU-bound, and B is I/O-bound.
6.29 Discuss ways in which the priority inversion problem could be
addressed in a real-time system. Also discuss whether the solutions
could be implemented within the context of a proportional share scheduler.
6.30 Under what circumstances is rate-monotonic scheduling inferior to
earliest-deadline-first scheduling in meeting the deadlines associated
with processes?
6.31 Consider two processes, P1 and P2, where p1 = 50, t1 = 25, p2 = 75, and
t2 = 30.
a. Can these two processes be scheduled using rate-monotonic
scheduling? Illustrate your answer using a Gantt chart such as
the ones in Figure 6.16–igure 6.19.
b. Illustrate the scheduling of these two processes using earliestdeadline-
first (EDF) scheduling.
6.32 Explain why interrupt and dispatch latency times must be bounded in
a hard real-time system.
5.1 In Section 5.4, we mentioned that disabling interrupts frequently can
affect the system’s clock. Explain why this can occur and how such
effects can be minimized.
5.2 Explain why Windows, Linux, and Solaris implement multiple locking
mechanisms. Describe the circumstances under which they use spinlocks,
mutex locks, semaphores, adaptive mutex locks, and condition
variables. In each case, explain why the mechanism is needed.
5.3 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.
5.4 Explain why spinlocks are not appropriate for single-processor systems
yet are often used in multiprocessor systems.
5.5 Show that, if the wait() and signal() semaphore operations are not
executed atomically, then mutual exclusion may be violated.
5.6 Illustrate how a binary semaphore can be used to implement mutual
exclusion among n processes.
Exercises
5.7 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.
경쟁 조건은 많은 컴퓨터 시스템에서 발생할 수 있다. deposit(amount) 와 withdraw(amount)의 두 함수를 가진 은행 시스템을 고려하자. 이 두 함수는 은행계좌로 예금되거나 인출될 amount를 전달받는다. 남편과 아내가 공유하는 은행 계좌가 있고 현재 남편은 withdraw()함수를 아내는 deposit() 함수를 동시에 호출한다고 가정하자. 어떻게 경쟁 조건이 발생할 가능성이 있으며 경쟁 조건의 발생을 방지하기 위해 어떤 조치를 취할 수 있는지 기술하시오.
withdraw 함수와 deposit 함수 모두가 같은 계좌에 접근하기 때문에 동시에 접근하게 된다면 결과값이 달라진다. 이는 함수가 접근하는 자원(계좌)을 임계구역으로 설정하여 동시간대에 하나의 함수만이 해당 자원에 접근하게 하면 경쟁조건 발생을 방지할 수 있다.
5.8 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:
boolean flag[2]; /* initially false */
int turn
The structure of process Pi (i == 0 or 1) is shown in Figure 5.21. The
other process is Pj (j == 1 or 0). Prove that the algorithm satisfies all
three requirements for the critical-section problem.
두 개의 프로세스를 위한 임계구역 문제에 대한 최초의 올바른 소프트웨어 해결 방안을 제시한 사람은 dekker였다. 두 개의 프로세스 P0 과 P1은 다음 변수들을 공유한다. 이 알고리즘이 임계구역 문제와 세 가지 요건을 모두 충족시킴을 증명하시오.
P0가 먼저 실행된다면 flag[0] == true 가 되면서 첫 번째 while에서 P1은 기다리게 되고 이는 상호배제를 만족한다. P0가 종료되면 flag[0] == flase 가 되면서 첫 번째 while에서 기다리고 있던 P1이 임계구역에 접근할 수 있게 된다. 이는 progress 를 만족한다. 그 뒤에 다른 프로세스가 임계구역을 접근하려 하면 해당 턴을 가지고있는 실행중인 프로세스가 종료될 때까지 첫 번째 while 문 안의 while에서 spinlock 를 돌다가 실행중인 프로세스가 종료된 후 임계구역에 접근 할 수 있게 되면서 bounded waiting 을 만족시킨다.
5.9 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 andMcGuire. The processes share the following
variables:
enum pstate {idle, want in, in cs}
pstate flag[n];
int turn;
All the elements of flag are initially idle. The initial value of turn is
immaterial (between 0 and n-1). The structure of process Pi is shown in
Figure 5.22. Prove that the algorithm satisfies all three requirements for
the critical-section problem.
5.10 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.
동기화 프리미티브가 사용자 수준 프로그램에서 사용되는 경우, 단일 처리기 시스템에서 인터럽트 불능을 이용하여 동기화 프리미티브를 구현하는 것이 왜 부적당한지 설명하시오.
사용자 수준 프로그램에서 인터럽트 불능을 사용하면 타이머 인터럽트가 작동하지 않고 그에 따른 문맥교환이 일어나지 않아 다른 프로세스와 concurrent 하게 처리되지 못한다.
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;
/* remainder section */
} while (true);
Figure 5.21 The structure of process Pi in Dekker’s algorithm.
5.11 Explain why interrupts are not appropriate for implementing synchronization
primitives in multiprocessor systems.
다중 처리기 시스템을 위한 동기화 프리미티브를 구현할 때 인터럽트를 사용하는 것이 부적합한 이유를 설명하시오.
하나의 처리기에서 인터럽트를 통해 프로세스가 임계구역에 접근하는 것을 방지한다 해도 다른 처리기에서 해당 임계구역에 접근하는 프로세스가 있을 수 있기 때문에 부적합하다.
5.12 The Linux kernel has a policy that a process cannot hold a spinlock while
attempting to acquire a semaphore. Explain why this policy is in place.
리눅스 커널은 정책적으로 세마포를 휙득하려고 시도 중인 프로세스는 스핀락을 가질 수 없게끔 제한한다. 이 정책이 사용되는 이유는 무엇인가?
스핀락은 다른 프로세스가 짧은 시간동안 임계구역에 접근하는 경우에만 사용된다. 세마포의 경우 다른 프로세스가 긴 시간동안 임계구역에 접근하기 때문에 문맥교환을 2번 (다른 프로세스로 갔다가 돌아오는) 하는 시간이 더 짧다고 판단되어 해당 프로세스를 waiting queue 에 넣어놓고 임계구역에 접근하지 않는 다른 프로세스를 수행하는 것이다. 이를 생각해보면 세마포를 휙득하려고 시도 중인 프로세스는 스핀락을 가지게 되면 cpu 시간 낭비가 매우 크기에 제한하는 것이다.
5.13 Describe two kernel data structures in which race conditions are possible.
Be sure to include a description of how a race condition can occur.
경쟁 조건이 발생할 가능성이 있는 커널 자료구조 2개를 기술하시오. 경쟁 조건이 어떤 경우에 발생할 수 있는지에 대한 설명이 반드시 포함되어야 한다.
-메모리 할당을 관리하는 자료 구조
서로다른 프로세스에서 동시에 메모리 할당을 요구하면 같은 주소번지에 메모리를 할당하려해서 경쟁 조건이 발생할 수 있다.
-프로세스 리스트를 유지하는 자료 구조
프로세스가 동시에 생성되는 경우 pid 를 부여할 때 경쟁조건이 발생할 수 있다.
5.14 Describe how the compare and swap() instruction can be used to provide
mutual exclusion that satisfies the bounded-waiting requirement.
5.15 Consider how to implement a mutex lock using an atomic hardware
instruction. Assume that the following structure defining the mutex
lock is available:
typedef struct {
int available;
} lock
(available == 0) indicates that the lock is available, and a value of 1
indicates that the lock is unavailable. Using this struct, illustrate how
the following functions can be implemented using the test and set()
and compare and swap() instructions:
•void acquire(lock *mutex)
•void release(lock *mutex)
Be sure to include any initialization that may be necessary.
do {
while (true) {
flag[i] = want in;
j = turn;
while (j != i) {
if (flag[j] != idle) {
j = turn;
else
j = (j + 1) % n;
}
flag[i] = in cs;
j = 0;
while ( (j < n) && (j == i || flag[j] != in cs))
j++;
if ( (j >= n) && (turn == i || flag[turn] == idle))
break;
}
/* critical section */
j = (turn + 1) % n;
while (flag[j] == idle)
j = (j + 1) % n;
turn = j;
flag[i] = idle;
/* remainder section */
} while (true);
Figure 5.22 The structure of process Pi in Eisenberg and McGuire’s algorithm.
5.16 The implementation of mutex locks provided in Section 5.5 suffers from
busy waiting. Describe what changes would be necessary so that a
process waiting to acquire a mutex lock would be blocked and placed
into a waiting queue until the lock became available.
5.5절의 mutex 락의 구현은 바쁜 대기를 해야만 한다. mutex 락을 휙득하기 위해 기다리는 프로세스가 봉쇄되어 락의 사용이 가능해질 때까지 대기 큐에서 놓이도록 하려면 어떻게 수정해야 하는 지 설명하시오.
바쁜 대기를 위한 코드 while (!available); /* busy wait */ 대신 세마포 절에서 설명된 리스트 사용을 이용하여
acquire()
acquire(mutex *M) {
M->value--;
if (M->value < 0) {
add this process to M->list
block();
}
do{
acquire lock
//critical section
release lock
}
release(mutex *M) {
M->value++;
if (M->value >= 0) {
remove a process P from M->list;
wakeup(P);
}
}
이런 식으로 수정한다면 될 것 같다.
5.17 Assume that a system has multiple processing cores. For each of the
following scenarios, describe which is a better locking mechanism—
spinlock or a mutex lock where waiting processes sleep while waiting
for the lock to become available:
•The lock is to be held for a short duration.
•The lock is to be held for a long duration.
•A thread may be put to sleep while holding the lock.
#define MAX PROCESSES 255
int number of processes = 0;
/* the implementation of fork() calls this function */
int allocate process() {
int new pid;
if (number of processes == MAX PROCESSES)
return -1;
else {
/* allocate necessary process resources */
++number of processes;
return new pid;
}
}
/* the implementation of exit() calls this function */
void release process() {
/* release process resources */
--number of processes;
}
Figure 5.23 Allocating and releasing processes.
5.18 Assume that a context switch takes T time. Suggest an upper bound
(in terms of T) for holding a spinlock. If the spinlock is held for any
longer, a mutex lock (where waiting threads are put to sleep) is a better
alternative.
문맥 교환에 T시간만큼 걸린다고 가정하자. 스핀락을 휙득하기 위해 소요될 수 있는 시간의 상한 값을 T단위로 제시하시오. 스핀락이 이 시간보다 오래 사용된다면 mutex 락(기다리는 스레드가 수면 상태로 들어감)이 더 나은 대체 방안이다.
2T 보다는 작아야 한다. 스핀락을 휙득 하기위해 2T 보다 많은 시간이 필요하다면 해당 프로세스를 mutex 락하고 해당 임계구역에 접근하지 않는 다른 프로세스로 문맥 교환하는 것이 cpu 사용에 더 효율적이다.
5.19 A multithreaded web server wishes to keep track of the number
of requests it services (known as hits). Consider the two following
strategies to prevent a race condition on the variable hits. The first
strategy is to use a basic mutex lock when updating hits:
int hits;
mutex lock hit lock;
hit lock.acquire();
hits++;
hit lock.release();
A second strategy is to use an atomic integer:
atomic t hits;
atomic inc(&hits);
Explain which of these two strategies is more efficient.
5.20 Consider the code example for allocating and releasing processes shown
in Figure 5.23.
a. Identify the race condition(s).
b. Assume you have a mutex lock named mutex with the operations
acquire() and release(). Indicate where the locking needs to
be placed to prevent the race condition(s).
c. Could we replace the integer variable
int number of processes = 0
with the atomic integer
atomic t number of processes = 0
to prevent the race condition(s)?
5.21 Servers can be designed to limit the number of open connections. For
example, a server may wish to have only N socket connections at any
point in time. As soon as N connections are made, the server will
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.
5.22 Windows Vista provides a lightweight synchronization tool called slim
reader–riter locks. Whereas most implementations of reader–riter
locks favor either readers or writers, or perhaps order waiting threads
using a FIFO policy, slim reader–riter locks favor neither readers nor
writers, nor are waiting threads ordered in a FIFO queue. Explain the
benefits of providing such a synchronization tool.
5.23 Show how to implement the wait() and signal() semaphore operations
in multiprocessor environments using the test and set()
instruction. The solution should exhibit minimal busy waiting.
다중처리기 환경에서 test_and_set() 명령을 사용하여 wait()와 signal() 세마포 연산을 구현하는 방법을 보이시오. 해결 방안은 바쁜 대기를 최소로 실행해야 한다.
boolean test and set(boolean *target) {
boolean rv = *target;
*target = true;
return rv;
}
wait(semaphore *S) {
while (!test_and_set(*target)); //busy waiting
S->value--;
if (S->value <= 0) {
add this process to S->list
block();
}
target=false;
}
signal(semaphore *S) {
while (!test_and_set(*target)); //busy waiting
S->value++;
if (S->value > 0) {
remove a process P from S->list;
wakeup(P);
}
target=false;
}
5.24 Exercise 4.26 requires the parent thread to wait for the child thread to
finish its execution before printing out the computed values. If we let the
parent thread access the Fibonacci numbers as soon as they have been
computed by the child thread—ather than waiting for the child thread
to terminate—hat changes would be necessary to the solution for this
exercise? Implement your modified solution.
5.25 Demonstrate that monitors and semaphores are equivalent insofar
as they can be used to implement solutions to the same types of
synchronization problems.
동일한 유형의 동기화 문제를 푸는 데 사용될 수 있다는 측면에서 모니터와 세마포가 동등함을 보이시오.
모니터 내부에서 돌아가는 프로세스들 중 하나만이 활성화 되고 나머지는 프로세스가 종료될때까지 기다리게 되는데 세마포 역시 wait() 과 signal() 을 사용하여 프로세스간의 실행 순서를 설정할 수 있다. 프로세스간 실행 순서를 설정해놓으면 현재 진행중인 프로세스가 끝나기 전에는 다음 프로세스가 수행될 수 없으므로 모니터와 같은 형태로 동기화 문제를 해결할 수 있다.
5.26 Design an algorithm for a bounded-buffer monitor in which the buffers
(portions) are embedded within the monitor itself.
5.27 The strict mutual exclusion within a monitor makes the bounded-buffer
monitor of Exercise 5.26 mainly suitable for small portions.
a. Explain why this is true.
b. Design a new scheme that is suitable for larger portions.
5.28 Discuss the tradeoff between fairness and throughput of operations
in the readers–riters problem. Propose a method for solving the
readers–riters problem without causing starvation.
5.29 How does the signal() operation associated with monitors differ from
the corresponding operation defined for semaphores?
5.30 Suppose the signal() statement can appear only as the last statement
in a monitor function. Suggest how the implementation described in
Section 5.8 can be simplified in this situation.
5.31 Consider a system consisting of processes P1, P2, ..., Pn, each of which has
a unique priority number. Write a monitor that allocates three identical
printers to these processes, using the priority numbers for deciding the
order of allocation.
5.32 A file is to be shared among different processes, each of which has
a unique number. The file can be accessed simultaneously by several
processes, subject to the following constraint: the sum of all unique
numbers associated with all the processes currently accessing the file
must be less than n.Write a monitor to coordinate access to the file.
5.33 Whena signal is performed on a condition inside amonitor, the signaling
process can either continue its execution or transfer control to the process
that is signaled. How would the solution to the preceding exercise differ
with these two different ways in which signaling can be performed?
5.34 Suppose we replace the wait() and signal() operations of monitors
with a single construct await(B), where B is a general Boolean
expression that causes the process executing it to wait until B becomes
true.
a. Write a monitor using this scheme to implement the readers–.
writers problem.
b. Explain why, in general, this construct cannot be implemented
efficiently.
c. What restrictions need to be put on the await statement so that it
can be implemented efficiently? (Hint: Restrict the generality of B
see [Kessels (1977)].)
5.35 Design an algorithm for a monitor that implements an alarm clock that
enables a calling program to delay itself for a specified number of time
units (ticks). You may assume the existence of a real hardware clock that
invokes a function tick() in your monitor at regular intervals.
7.1 List three examples of deadlocks that are not related to a computersystem
environment.
7.2 Suppose that a system is in an unsafe state. Show that it is possible for
the processes to complete their execution without entering a deadlocked
state.
7.3 Consider the following snapshot of a system:
Allocation Max Available
A B C D A B C D A B C D
P0 0 0 1 2 0 0 1 2 1 5 2 0
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 6 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
Answer the following questions using the banker’s algorithm:
a. What is the content of the matrix Need?
b. Is the system in a safe state?
c. If a request from process P1 arrives for (0,4,2,0), can the request be
granted immediately?
7.4 A possible method for preventing deadlocks is to have a single, higherorder
resource that must be requested before any other resource. For
example, if multiple threads attempt to access the synchronization
objects A· · · E, deadlock is possible. (Such synchronization objects may
include mutexes, semaphores, condition variables, and the like.)We can
prevent the deadlock by adding a sixth object F. Whenever a thread
wants to acquire the synchronization lock for any object A· · · E, it must
first acquire the lock for object F. This solution is known as containment:
the locks for objects A· · · E are contained within the lock for object F.
Compare this scheme with the circular-wait scheme of Section 7.4.4.
7.5 Prove that the safety algorithm presented in Section 7.5.3 requires an
order of m × n2 operations.
7.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
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?
7.7 Can a system detect that some of its processes are starving? If you answer
“yes,” explain how it can. If you answer “no,” explain how the system
can deal with the starvation problem.
7.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, thenwe check
any processes that are blocked waiting for resources. If a blocked process
has the desired resources, then these resources are taken away from it
and are given to the requesting process. The vector of resources for which
the blocked process 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 process P0 asks for (2,2,1), it gets
them. If P1 asks for (1,0,1), it gets them. Then, if P0 asks for (0,0,1), it
is blocked (resource not available). If P2 now asks for (2,0,0), it gets the
available one (1,0,0), as well as one that was allocated to P0 (since P0 is
blocked). P0’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.
7.9 Suppose that you have coded the deadlock-avoidance safety algorithm
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 process i is waiting and Allocationi
is as defined in Section 7.5? Explain your answer.
7.10 Is it possible to have a deadlock involving only one single-threaded
process? Explain your answer.
7.11 Consider the traffic deadlock depicted in Figure 7.10.
a. Show that the four necessary conditions for deadlock hold in this
example.
1. 상호 배제 : 도로의 폭은 차가 한 대 밖에 다닐 수 없을 정도로 좁다.
2. Hold & wait : 일정부분의 도로를 점유한 상태에서 다음의 도로를 요구한다.
3. no preemptive : 도로를 점유한 차를 강제적으로 되돌리지 못한다. (도로의 점유를 뺏을 수 없다.)
4. circular wait : 4개의 도로와 맞물려있는 4개의 교차로에서 반시계 방향으로 도로를 요구함으로 차들이 circular wait 한다.
b. State a simple rule for avoiding deadlocks in this system.
교차로에 서있는 차 중 한 대를 빼서 나머지 정체 차량을 다 뺀 후에 다시 집어 넣는다.
7.12 Assume a multithreaded application uses only reader–riter locks for
synchronization. Applying the four necessary conditions for deadlock,
is deadlock still possible if multiple reader–riter locks are used?
1. mutual exclusive : writer lock
2. hold & wait :한 공유 자원에 writer lock 하면서 다른 공유자원에 writer lock 을 시도 할 수 있다.
3. no preemptive : 비선점 스케쥴링이라면 자원을 강제로 반환시킬 수 없다.
4. circular wait : 여러개의 프로세스가 각자 writer lock 를 한 상태로 다른 프로세스의 자원을 원형으로 요구한다면 데드락이 일어날 수 있다.
7.13 The program example shown in Figure 7.4 doesn’t always lead to
deadlock. Describe what role the CPU scheduler plays and how it can
contribute to deadlock in this program.
??
7.14 In Section 7.4.4, we describe a situation in which we prevent deadlock
by ensuring that all locks are acquired in a certain order. However,
we also point out that deadlock is possible in this situation if two
threads simultaneously invoke the transaction() function. Fix the
transaction() function to prevent deadlocks.
7.15 Compare the circular-wait scheme with the various deadlock-avoidance
schemes (like the banker’s algorithm) with respect to the following
issues:
a. Runtime overheads
b. System throughput
7.16 In a real computer system, neither the resources available nor the
demands of processes for resources are consistent over long periods
(months). Resources break or are replaced, new processes come and go,
and new resources are bought and added to the system. If deadlock is
controlled by the banker’s algorithm, which of the following changes
can be made safely (without introducing the possibility of deadlock),
and under what circumstances?
a. Increase Available (new resources added).
아무 문제 없다.
b. Decrease Available (resource permanently removed from system).
safely sequence 의 개수를 줄여 unsafe 상태를 만들 확률이 올라가면서 비례하여 데드락이 발생할 확률도 증가할 것이다.
c. Increase Max for one process (the process needs or wants more
resources than allowed).
safely sequence 의 개수를 줄여 unsafe 상태를 만들 확률이 올라가면서 비례하여 데드락이 발생할 확률도 증가할 것이다.
d. Decrease Max for one process (the process decides it does not need
that many resources).
아무 문제 없다.
e. Increase the number of processes.
새롭게 추가되는 프로세스의 자원 요구량에 따라 비례하여 unsafe 상태가 될 확률이 높아질 것이다.
f. Decrease the number of processes.
프로세스의 개수가 줄면 available 이 증가하는 효과를 낳아 unsafe 상태가 될 확률이 줄어들 것이다.
7.17 Consider a system consisting of four resources of the same type that are
shared by three processes, each of which needs at most two resources.
Show that the system is deadlock free.
7.18 Consider a system consisting of m resources of the same type being
shared by n processes.Aprocess can request or release only one resource
at a time. Show that the system is deadlock free if the following two
conditions hold:
a. The maximum need of each process is between one resource and
m resources.
b. The sum of all maximum needs is less than m + n.
7.19 Consider the version of the dining-philosophers problem in which the
chopsticks are placed at the center of the table and any two of them
can be used by a philosopher. Assume that requests for chopsticks are
made one at a time. Describe a simple rule for determining whether a
particular request can be satisfied without causing deadlock given the
current allocation of chopsticks to philosophers.
7.20 Consider again the setting in the preceding question. Assume now that
each philosopher requires three chopsticks to eat. Resource requests are
still issued one at a time. Describe some simple rules for determining
whether a particular request can be satisfied without causing deadlock
given the current allocation of chopsticks to philosophers.
7.21 We can obtain the banker’s algorithm for a single resource type from
the general banker’s algorithm simply by reducing the dimensionality
of the various arrays by 1. Show through an example that we cannot
implement the multiple-resource-type banker’s scheme by applying the
single-resource-type scheme to each resource type individually.
7.22 Consider the following snapshot of a system:
Allocation Max
A B C D A B C D
P0 3 0 1 4 5 1 1 7
P1 2 2 1 0 3 2 1 1
P2 3 1 2 1 3 3 2 1
P3 0 5 1 0 4 6 1 2
P4 4 2 1 2 6 3 2 5
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 processesmaycomplete. Otherwise, illustratewhythe state is unsafe.
a. Available = (0, 3, 0, 1)
b. Available = (1, 0, 0, 2)
7.23 Consider the following snapshot of a system:
Allocation Max Available
A B C D A B C D A B C D
P0 2 0 0 1 4 2 1 2 3 3 2 1
P1 3 1 2 1 5 2 5 2
P2 2 1 0 3 2 3 1 6
P3 1 3 1 2 1 4 2 4
P4 1 4 3 2 3 6 6 5
Answer the following questions using the banker’s algorithm:
a. Illustrate that the system is in a safe state by demonstrating an
order in which the processes may complete.
b. If a request from process P1 arrives for (1, 1, 0, 0), can the request
be granted immediately?
c. If a request from process P4 arrives for (0, 0, 2, 0), can the request
be granted immediately?
7.24 What is the optimistic assumption made in the deadlock-detection
algorithm? How can this assumption be violated?
7.25 A single-lane bridge connects the two Vermont villages of North
Tunbridge and South Tunbridge. Farmers in the two villages use this
bridge to deliver their produce to the neighboring town. The bridge
can become deadlocked if a northbound and a southbound farmer get
on the bridge at the same time. (Vermont farmers are stubborn and are
unable to back up.) Using semaphores and/or mutex locks, design an
algorithm in pseudocode that prevents deadlock. Initially, do not be
concerned about starvation (the situation in which northbound farmers
prevent southbound farmers from using the bridge, or vice versa).
7.26 Modify your solution to Exercise 7.25 so that it is starvation-free.
댓글
댓글 쓰기