OPERATING SYSTEM Important
Test-and-set. compare-and-swap. atomic reads and writes. Other atomic operations. enabling
and disabling interrupts.
_______________________________________________________________
What is the difference between a process and a thread?
Every process has its own address space, but multiple threads inside a process share part of
the memory with their parent process. There is less context switching overhead to switch
among threads when compared to switching among threads.
_______________________________________________________________
What is the difference between deadlock and starvation?
In a deadlock situation, none of the involved processes can possibly make progress. In a
starvation situation, a process is ready to execute, but it is not being allowed to execute.
_______________________________________________________________
Suppose our computer system is running five processes (P1,P2,P3,--,P5 ) and has four
separate types of resources (A,B,C,D). We want to see if the system is in a safe state
using the Banker's algorithm. Using the following information about the state of the
system, determine if the state is safe: (11 points)
Total
AB C D
4 5 4 3
Available
AB C D
0 1 0 0
Maximum
A B C D
P1 1 3 3 0
P2 2 2 1 3
P3 1 1 0 1
P4 1 4 1 0
P5 3 1 2 1
Used
A B C D
P1 0 1 2 0
P2 2 0 1 1
P3 1 0 0 1
P4 0 3 1 0
P5 1 0 0 1
A B C D
Total 4 5 4 3
A B C D
Available 0 1 0 0
Total gives the number of instances of each resource in the system; Available gives the
number of unallocated instances of each resource; Maximum refers to the maximum
number of instances of each resource required by each process; Used refers to how many instances of each resource each process currently holds.
Answer:
The Need matrix is as follows:
Need
A B C D
P1 1 2 1 0
P2 0 2 0 2
P3 0 1 0 0
P4 1 1 0 0
P5 2 1 2 0
The state of the system is unsafe. Executing the Banker's algorithm terminates with P2
and P5 unable to complete. We give a possible sequence of execution with "Work" P3 runs (1, 1, 0, 1), P4 runs (1, 4, 1, 1),P1 runs (1, 5, 3, 1). Now neither P2
nor P5 can release its resources because each holds resources the other needs.
------------------------------------------------------------------------------------------------
2. A computer system has m resources of the same type and n processes share these
resources. Prove or disprove the following statement for the system:
This system is deadlock free if sum of all maximum needs of processes is less than m+n.
3. There are four processes which are going to share nine tape drives. Their current and
maximum number of allocation numbers are as follows :
process current maximum
p1 3 6
p2 1 2
p3 4 9
p4 0 2
a. Is the system in a safe state? Why or why not?
b. Is the system deadlocked? Why or why not?
A Process Using Mutual Exclusion:
int me;
while (1) {
/* non critical section code */
enter(me); /* also called entry code */
/* critical section code */
leave(me); /* also called exit code */
}
We assume each process has access to its process ID, which we're calling me in this example. The process can pass its ID into the enter() and leave() functions.
First try: use a lock.
shared int lock = 0;
void enter(int me)
{
while (lock == 1) /* do nothing */;
lock = 1;
}
void leave(int me)
{
lock = 0;
}
Problem: Process 0 can check that the lock is available, and then get preempted. Process 1 can now check the the lock is available, and enter the critical section. While in the critical section, it can be swapped out, and Process 0 restarted. Since Process 0 has already checked the availability of the lock, it can also enter the critical section. This "solution" fails to provide mutual exclusion.
Second try: take turns
shared int turn = 0;
void enter(int me)
{
while (turn != me);
}
void leave(int me)
{
turn = 1 - me;
}
Problem: If process 0 never attempts to enter the critical section, process 1 is never allowed to enter it (and, if 0 has entered once, it can never enter again until 1 endters). This "solution" fails to guarantee progress. Can you convince yourself it does in fact provide mutual exclusion (so it does meet some of the criteria, but not all)?
Third try: Keep track of whether the other guy wants in
shared int flag[2];
void enter(int me)
{
flag[me] = 1;
while (flag[1-me]);
}
void leave(int me)
flag[me] = 0;
}
Problem: Doesn't satisfy the progress condition. Both processes can get stuck in the entry code and wait there forever, in other words "deadlocked".
Fourth and last try: (Peterson's Algorithm): combine second and third
The basic approach here is that we're going to keep track of both whether the other process wants in, and also whose turn it is. If the other process wants to get in, we'll let it in if it's its turn. But if it doesn't want in, we'll take its place.
shared int flag[2];
shared int turn;
void enter(int me)
{
flag[me] = 1;
turn = 1-me;
while (flag[1-me] && (turn == (1-me)));
}
void leave(int me)
{
flag[me] = 0;
}
CRITICAL SECTION
// functions to enter/leave the // critical section void critical_section_enter_t0() { while (turn != T0) continue; } void critical_section_leave_t0() { turn = T1; } | // functions void critical_section_enter_t1() { while (turn != T1) continue; } void critical_section_leave_t1() { turn = T0; } |
i. Does this proposal provide mutual exclusion for the critical
section? Justify your answer!
Yes, it does. The variable ‘turn’ is either T0 or T1, and if it is T0, then
only thread T0 can progress past ‘critical_section_enter_t0’, and vice
versa.
ii. Is this proposal a satisfactory solution to the critical section
problem? Justify your answer!
No, it is not. It does not guarantee progress. In particular, thread T0
cannot reenter the critical section after it has left it unless thread T1
entered and left the critical section in the interim since critical_section_leave_t0() sets turn = T1. Only critical_section_leave_t1() can change it back to T0 again.
Consider:
critical_section_enter_t0();
critical_section_leave_t0();
// may block even though t1 is not in the critical section
critical_section_enter_t0();
critical_section_leave_t0();
