OPERATING SYSTEM

What are two types of low-level operations that higher-level synchronization operations(e.g., semaphores and monitors) can be built upon?
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;
}