进程管理模块介绍了进程和线程的相关概念，主要包括：进程的定义、进程的描述、进程控制；线程的定义及实现；进程间通信、信号量；进程调度的基本概念及调度算法；死锁的定义及解决死锁的方法。

After studying this chapter, you should be able to: 
(1) Master(掌握): the difference of process and program; the principal events to create and terminate process; the states of process; race conditions and critical region; semaphore; scheduling algorithm; the definition of deadlock; banker’s algorithm

(2) Understand(理解): the concept of process; PCB; user-level thread and kernel-level thread; CPU-bound and I/O-bound; the relationship and difference of thread and process; four necessary conditions for the deadlock; resource allocation graph

(3) Know(了解): how to implement thread; the relationship and difference of thread and process; scheduling algorithm for various system

Emphasize:

1. creation and termination of process

2. process’s states and their transitions

3. the implementing of process model

4. threads usage

5. the thread model

6. race condition and critical region

7. the value of the semaphore, semaphore’s operations

8. process behaviors and two scheduling ways

9. when to scheduling

10. the goals of different operating systems

11. scheduling algorithm: FCFS, SJF, SRN

12. preemptable and nonpreemptable resource

13. conditions for deadlock

14. deadlock detection and recovery

15. safe and unsafe states

Difficulty:

1. multiprogramming

2. the difference between process and program

3. the difference between process and thread

4. the implementing of user-level thread and kernel-level thread

5. using semaphores to solve producer-consumer problem

6. using semaphores to solve reader-writer problem

7. scheduling algorithm of RR and Priority

8. how to prove one real-time system schedulable or not

9. the banker’s algorithm for multiple resources

10. deadlock prevention

• 1.Process

• To hide the effects of interrupts, operating system provide a conceptual model consisting of sequential processes running in parallel. Processes can be created and terminated dynamically. Each process has its own address space.
  2.Thread

• For some applications it is useful to have multiple threads of control within a single process. These threads are scheduled independently and each one has an own stack, but all the threads in a process share a common address space. Threads can be implemented in user space or in the kernel.
  3.IPC

• Processes can communicate with each other using interprocess communication primitives, such as semaphores, monitors, or messages. These primitives are used to ensure that no two processes are ever in their critical regions at the same time, a situation that leads to chaos. A process can be running, runnable, or blocked and can change state when it of another process executes one of the interprocess communication primitives. Interthread communication is similar.
  4.Semaphore

• Interprocess communication primitives can be used solve such problems as the producer-consumer, dinning philosophers, reader-writer, and sleeping barber. Even with these primitives, care has to be taken to avoid errors and deadlocks.
  5.Scheduling

• Many scheduling algorithms are known. Some of these are primarily used for batch systems, such as shortest job first. Others are common in both batch systems and interactive systems. These include round robin, priority scheduling, multilevel queues, guaranteed scheduling, lottery scheduling, and fair-share scheduling.
  6.Deadlock

• Deadlock is a potential problem in any operating system. It occurs when a group of processes each have been granted exclusive access to some resources, and each one wants yet another resource that belongs to another process in the group. All of them are blocked and none will ever run again. Deadlock can be avoided by keeping track of which states are safe and which are unsafe. A safe state is one in which there exists a sequence of events that guarantee that all processes can finish. An unsafe state has no such guarantee. The banker’s algorithm avoids deadlock by not granting a request if that request will put the system in an unsafe state. Deadlock can be structurally prevented by building the system in such a way that it can never occur by design. Deadlock can also be prevented by numbering all the resources, and making process request them in strictly increasing order.

1. There is a plate in which we can only place one fruit. The father can place an apple or an orange in the plate. The son can eat apple in the plate but he can’t eat orange. The daughter can eat orange in the plate but she can’t eat apple. Please descript the actions of the father, the son and the daughter with UP and DOWN operation. Suppose the plate is empty initially. You should give the initial values of the semaphores and fill in the blanks in the following program.
Solution:
typedef int semaphore;    //semaphores are a special kind of int
Semaphore s1=    1    ;     //counts empty plate
Semaphore s2=    0    ;     //counts orange in the plate
Semaphore s3=    0    ;     //counts apple in the plate
Father ()          //the father process
{    While (true)
    {   Take_up_a_fruit();
        Down(s1);
        if (the fruit is orange)   Up(s2);
        else    Up(s3);   }
}

Daughter ( )       //the daughter process
{    While (true)
    {    Down (s2);
    Take_up_an_orange_and_eat_the_orange ();
    Up (s1);    }
}

Son ( )          //the son process
{    While (true)
    {    Down (s3);
         Take_up_an_apple_and_eat_the_apple();
         Up (s1);    }
}

2. Questions about semaphore. There is one wooden bridge(独木桥), people which in the same direction can cross the bridge one by one. It means that if someone walks from east to west, anyone cannot walk from west to east, and vice versa (反之亦然). Now one people want to walk from east to west, please write out the program with DOWN and UP operations (PV operations) by the semaphores and variables we defined as follows. You should assume the bridge is empty initially.
We define the variable rc to count the number of people which walking from east to west now, its initially value is     0  
We define the semaphore mutex is the resource of access rc, its initially value is     1  
We define the semaphore bridge is the resource of crossing bridge, its initial value is     1     
Please write out the program:
{P(mutex);
rc=rc+1;
if (rc==1)  P(bridge);
V(mutex);
Across the bridge;
P(mutex);
  rc=rc-1;
  if (rc==0)  V(bridge);
V(mutex); }

3. For the following processes

Compute turnaround time of each process and mean turnarounds time using:
(1) First come first served
(2) Shortest job/process first
(3) Shortest remaining time next
(4) Round robin (quantum=2)
(5) Round robin (quantum=1)
(6) Priority (1-high priority, preemptive)
(7) Priority (1-high priority, non-preemptive)
Solution:
(1) A:6B:11C:12D:13Mean turnaround time=(6+11+12+13)/4=42/4=10.5
(2) A:6B:15C:5D:6Mean turnaround time=(6+15+5+6)/4=8
(3) A:10B:15C:2D:3Mean turnaround time=(10+15+2+3)/4=7.5
(4) A:10B:15C:5D:8Mean turnaround time=(10+15+5+8)/4=9.5
(5) A:13B:15C:7D:8Mean turnaround time=(13+15+7+8)/4=8.25
(6) A:13,B:7,C:12,D:13Mean turnaround time=(13+7+12+13)/4=11.25
(7) A:6,B:11,C:12,D:13Mean turnaround time=(6+11+12+13)/4=10.5

4. A soft real-time system has four periodic events with periods of 50, 100, 200, and 250 msec each. Suppose that the four events require 35, 20, 10, and x msec of CPU time, respectively. What is the largest value of x for which the system is schedulable?
Solution:
35/50+20/100+10/200+x/250<=1 max(x)=12.5

5. A system has four processes and three assignable resources. The current allocation and maximum needs are as follows:
Allocated       Maximum  Available
Process A       2  0  1          2  2  1             0  x  0
Process B       1  1  0          5  2  2
Process C       1  0  0          4  0  2
Process D       1  0  2          2  1  2
(1) What is the smallest value of x for which this is a safe state?  x =  2  ;  
(2) If x is the smallest value, please fill in the following blanks:                                      
Process  A  can be satisfied first, when it is over, the available is (2  2  1)
Process  D  can be satisfied next, when it is over, the available is (3  2  3)  
Process  C  can be satisfied next, when it is over, the available is (4  2  3)  
Process  B  can be satisfied next, when it is over, the available is (5  3  3)

1. Through the design process scheduler simulation more than two scheduling algorithm
Solution: (with visual studio)
// processscheduling.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"
#include "iostream"
#include "string.h"
#include "iomanip"
#include <windows.h>+

using namespace std;
bool bProcessCreated();
bool bDisplay();
bool ExecuteRRAlgorithm();
bool ExecutePriorityAlgorithm();
bool Restore();

struct PCB
{     int m_iProcessID;//process id
       char m_strProcessName[10];// process name
       int m_iCPUTime;
       int m_iRemainingTime;
       int m_iState;//0 means ready, 1 means running, don't consider block state now
       int m_iPriority;//a bigger number means a higher priority
       struct PCB *next;  };

struct PCB *pReadyQueue=NULL;
int iProcessID=0;
int _tmain(int argc, _TCHAR* argv[])
{     bProcessCreated();
       bDisplay();
       ExecuteRRAlgorithm();
       Restore();
       ExecutePriorityAlgorithm();
       Sleep(2000000);
       return 0;//return a value   }

bool bProcessCreated()
{
       char strProcessName[10];
       int iCPUTime;
       int iState;
       int iPriority;
       struct PCB *pTemp;
       struct PCB *pCurrentProcess;
       int iProcessNumber;
    cout<<"please input the process number you want to create:";
       cin>>iProcessNumber;
    cout<<endl<<endl;
       for (int i=0;i<iProcessNumber;i++)
       {            try
              {                pTemp=new struct PCB;//requests memory             }
           catch(...)//catch errors for memory allocation
              {   cout<<"the memory is not enough! Creating process failed!";
                  return false;              }
        pTemp->m_iProcessID=iProcessID;//allocates ID for the new process
           iProcessID++;
           cout<<"please input the name of the process:";
           cin>>strProcessName;
        cout<<"please input the CPU time used by the process:";
           cin>>iCPUTime;
        cout<<"please input the priority of the process:";
           cin>>iPriority;
              cout<<endl;
           iState=0;
           pTemp->m_iCPUTime=iCPUTime;
           pTemp->m_iPriority=iPriority;
           pTemp->m_iState=iState;
              pTemp->m_iRemainingTime=iCPUTime;
           strcpy(pTemp->m_strProcessName,strProcessName);
              if(iProcessID==1)
              {     pReadyQueue=pTemp;//ready queue
                     pCurrentProcess=pTemp;
                  pCurrentProcess->next=NULL;           }
              else
              {     pCurrentProcess->next=pTemp;
                     pCurrentProcess=pTemp;
                  pCurrentProcess->next=NULL;           }
       }
       return true;
}

bool bDisplay()
{    struct PCB *pTemp=NULL;
       pTemp=pReadyQueue;
    if(pTemp==NULL)
              cout<<"no process exists!";
       else
       {  cout<<endl;
              cout<<setw(5)<<"PID"<<setw(20)<<"Process-Name"<<setw(15)<<"CPU-Time"<<setw(15)<<"Priority";
              cout<<endl;
              while(pTemp!=NULL)
              {     cout<<setw(5);
                     cout<<pTemp->m_iProcessID;
               cout<<setw(20);
                     cout<<pTemp->m_strProcessName;
               cout<<setw(15);
                     cout<<pTemp->m_iCPUTime;
               cout<<setw(15);
                     cout<<pTemp->m_iPriority;
                     cout<<endl;
                     pTemp=pTemp->next;             }
       }
    cout<<endl;
       return true;
}

bool ExecuteRRAlgorithm()
{     int iQuantum;
       bool bAllRunned=false;
    struct PCB *pTemp=NULL;
       pTemp=pReadyQueue;
    if(pTemp==NULL)
       {     cout<<"no process exists!";
              return false;  }
       cout<<"please input quantum:";
       cin>>iQuantum;
       cout<<endl;
    cout<<"RR scheduling starts......";
       cout<<endl;
       while(!bAllRunned)
       {   bAllRunned=true;
           pTemp=pReadyQueue;
              while(pTemp!=NULL)
              {   if(pTemp->m_iRemainingTime>iQuantum)
                     {   pTemp->m_iRemainingTime=pTemp->m_iRemainingTime-iQuantum;
                         cout<<setw(5);
                            cout<<pTemp->m_iProcessID;
                            cout<<setw(20);
                            cout<<pTemp->m_strProcessName;
                            cout<<setw(1);
                            cout<<":";
                            cout<<setw(5);
                            cout<<iQuantum;
                            cout<<endl;
                pTemp=pTemp->next;
                         bAllRunned=false;
                     }
                  else if(0<pTemp->m_iRemainingTime && pTemp->m_iRemainingTime<=iQuantum)
                     {   cout<<setw(5);
                            cout<<pTemp->m_iProcessID;
                            cout<<setw(20);
                            cout<<pTemp->m_strProcessName;
                            cout<<setw(1);
                            cout<<":";
                            cout<<setw(5);
                            cout<<pTemp->m_iRemainingTime;
                            cout<<endl;
                pTemp->m_iRemainingTime=0;
                pTemp=pTemp->next;
                            bAllRunned=false;
                     }
                  else if(pTemp->m_iRemainingTime==0)
                     {     pTemp=pTemp->next;
                     }
                  else
                     {     ;
                     }
              }
              cout<<endl;
       }
       return true;
}

bool Restore()
{   struct PCB *pTemp=NULL;
       pTemp=pReadyQueue;
       while (pTemp!=NULL)
       {     pTemp->m_iRemainingTime=pTemp->m_iCPUTime;
              pTemp=pTemp->next;      }
       return true;
}

bool ExecutePriorityAlgorithm()
{   struct PCB *pTemp=NULL;
       struct PCB *pFirst=NULL;
       struct PCB *pSecond=NULL;
       struct PCB temp;
       pTemp=pReadyQueue;
    pFirst=pTemp;
       pSecond=pFirst->next;
       while (pFirst!=NULL)
       { while (pSecond!=NULL)
              {  if (pFirst->m_iPriority<pSecond->m_iPriority)
                     {     temp.m_iCPUTime=pSecond->m_iCPUTime;
                            temp.m_iPriority=pSecond->m_iPriority;
                            temp.m_iProcessID=pSecond->m_iProcessID;
                            temp.m_iRemainingTime=pSecond->m_iRemainingTime;
                            temp.m_iState=pSecond->m_iState;
                            strcpy(temp.m_strProcessName,pSecond->m_strProcessName);
                            pSecond->m_iCPUTime=pFirst->m_iCPUTime;
                            pSecond->m_iPriority=pFirst->m_iPriority;
                            pSecond->m_iProcessID=pFirst->m_iProcessID;
                            pSecond->m_iRemainingTime=pFirst->m_iRemainingTime;
                            pSecond->m_iState=pFirst->m_iState;
                            strcpy(pSecond->m_strProcessName,pFirst->m_strProcessName);
                            pFirst->m_iCPUTime=temp.m_iCPUTime;
                            pFirst->m_iPriority=temp.m_iPriority;
                            pFirst->m_iProcessID=temp.m_iProcessID;
                            pFirst->m_iRemainingTime=temp.m_iRemainingTime;
                            pFirst->m_iState=temp.m_iState;
                            strcpy(pFirst->m_strProcessName,temp.m_strProcessName);
                     }
                     pSecond=pSecond->next;
              }
        pFirst=pFirst->next;
              if (pFirst!=NULL)
                     pSecond=pFirst->next;
              else
                     pSecond=NULL;
       }
    cout<<"Prioriy scheduling starts......";
       cout<<endl;
       while(pTemp!=NULL)
       {     cout<<setw(5);
           cout<<pTemp->m_iProcessID;
              cout<<setw(20);
              cout<<pTemp->m_strProcessName;
              cout<<setw(1);
              cout<<":";
              cout<<setw(5);
              cout<<pTemp->m_iRemainingTime;
              cout<<endl;
              pTemp=pTemp->next;
       }
       cout<<endl;
       return true;
}

Program a simulation of the banker’s algorithm. You program should cycle through each of the bank clients asking for a request and evaluating whether it is safe o unsafe. Output a log of requests and decisions to a file.

Solution: (with visual studio)
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>

using namespace std;

//全局变量
int src;
int numProc;
int rqstProc;
int maxSrc[6][16];
int allocation[6][16];
int need[6][16];
int avaliable[6];
int request[6];
int safeSequence[6];
int work[6];
bool finish[6];
bool finishTemp[6];
string printState[] = {"garanted",
"refused(extend the amount of avaliable)",
"refused(extend the amount of need)",
"refused(Deadlock is possible)"};

//函数声明
bool IsSafe(int n);

//主程序
int main(void)
{
ifstream in;
in.open("Input.txt", ios::in);
ofstream out;
out.open("Output.txt", ios::out|ios::app);
//数据初始化
in >> src;
for (int i=0; i<src; ++i)
{
in >> avaliable[i];
}
in >> numProc;
for (int i=0; i<numProc; ++i)
{
for (int j=0; j<src; ++j)
{
in >> maxSrc[i][j];
need[i][j] = maxSrc[i][j];
allocation[i][j] = 0;
}
safeSequence[i] = -1;
finish[i] = false;
}
//输出
cout << "Initial:" << endl << " ";
out << "Initial:" << endl << " ";
for (int i=0; i<src; ++i)
{
cout << " " << char('A'+i);
out << " " << char('A'+i);
}
cout << endl << " ";
out << endl << " ";
for (int i=0; i<src; ++i)
{
cout << " " << avaliable[i];
out << " " << avaliable[i];
}
cout << endl;
out << endl;

//开始银行家算法
bool canFinish;
int inTemp;
while (in >> inTemp)
{
string s;
ostringstream outPrint(s);
rqstProc = inTemp - 1;
int outP = 0;
canFinish = false;

//初步检测是否有足够资源满足需求
for (int i=0; i<src; ++i)
{
in >> inTemp;
request[i] = inTemp;
if (request[i] > avaliable[i])
{
outP = 1;
continue;
}
else if (request[i] > need[rqstProc][i])
{
outP = 2;
continue;
}
}//end of for

//如果需求可以满足，则暂且向其分配资源
if (outP == 0)
{
for (int i=0; i<src; ++i)
{
avaliable[i] -= request[i];
allocation[rqstProc][i] += request[i];
need[rqstProc][i] -= request[i];
work[i] = avaliable[i];
finishTemp[i] = finish[i];
}

//检查分配资源后是否存在安全队列
if (!IsSafe(0))
{
outP = 3;
for (int i=0; i<src; ++i) //如果不存在，回溯
{
avaliable[i] += request[i];
allocation[rqstProc][i] -= request[i];
need[rqstProc][i] += request[i];
}
}
else
{
//如果存在，检查其是否能完成，如果能，回收资源
canFinish = true;
for (int i=0; i<src; ++i)
{
if (need[rqstProc][i] > 0)
{
canFinish = false;
break;
}
}
if (canFinish)
{
for (int i=0; i<src; ++i)
{
avaliable[i] += allocation[rqstProc][i];
}
finish[rqstProc] = true;
}
}
}//end of if

//输出
outPrint << "Process " << rqstProc + 1 
<< " requests(" << request[0];
for (int i=1; i<src; ++i)
{
outPrint << ", " << request[i];
}
outPrint << ") - " << printState[outP] << endl;
s = outPrint.str();
cout << s;
out << s;
if (canFinish)
{
cout << "Process " << rqstProc + 1 << " finishes" << endl;
out << "Process " << rqstProc + 1 << " finishes" << endl;
}
}

in.close();
out.close();
system("pause");
}

bool IsSafe(int n)
{
if (n < numProc) //如果队列未满
{
for (int i=0; i<numProc; ++i)
{
if (!finishTemp[i]) //如果未完成
{
//检查其是否可以完成
finishTemp[i] = true;
for (int j=0; j<src; ++j)
{
if (need[i][j] > work[j])
{
finishTemp[i] = false;
break;
}
}
//如果能完成，回收资源并将其加入安全队列
if (finishTemp[i])
{
for (int k=0; k<src; ++k)
{
work[k] += allocation[i][k];
}
safeSequence[n] = i;
return IsSafe(n+1); //递归实现DFS搜索安全队列
}
}//end of if
}
}
//检查是否存在安全队列
bool safe = true;
for (int i=0; i<numProc; ++i)
{
if (!finishTemp[i])
{
safe = false;
break;
}
}
return safe;
}

1. What’s the biggest advantage of implementing thread in user space? What’s the biggest disadvantage?
Solution: The first advantage is that a user-level package can be implemented on an operating system that does not support threads. The second advantage is that they allow each process to have its own customized scheduling algorithm.
The disadvantage is the problem of how blocking system calls are implemented. Another problem is that if a thread starts running, no other thread in that process will ever run unless the first thread voluntarily gives up the CPU.

2. There is a supper market which permits only 200 peoples to shop at the same time.  The market has one entering gate and one outing gate. Every shopper must enter the market from the entering gate and goes out of the market from the outing gate. And both the entering gate and outing gate can only permit one person to get though. Please fill in the following blanks to describe the shopper problem with Down and Up operating. You should give the initial values of the semaphores and the max value of the semaphore Count.
Solution:
Typedef int semaphore; //semaphores are a special kind of int
Semaphore Count=200; //counts shoppers permitted in
Semaphore In-mutex= 1 ; //counts the entering gate
Semaphore Out-mutex= 1 ; //counts the outing gate
Shopper() //the shopper process
{ 
Down(&Count);
Down(&In-mutex);
Enter_the_market();
Up(&In-mutex);
Shopping();
Down(&Out-mutex);
Go_out_of_the_macket();
Up(&Out-mutex);
Up(&Count);  }
The largest value of Count is _200_.

3. Three peoples date to see the films together. Try to describe synchronization process using DOWN (P), UP (V) primitives.
Solution:
Typedef int semaphore;
Semaphore OneToTwo=0;
Semaphore OneToThree=0;
Semaphore TwoToOne=0;
Semaphore TwoToThree=0;
Semaphore ThreeToOne=0;
Semaphore ThreeToOne=0;
Void Process_One(void)
{  Up (&OneToTwo);
   Up (&OneToThree);
   Down (&TwoToOne);
   Down (&ThreeToOne);
   Go_to_the_cinema();  }

Void Process_Two(void)
{  Up (&TwoToOne);
   Up (&TwoToThree);
   Down (&OneToTwo);
   Down (&ThreeToTwo);
   Go_to_the_cinema();  }

Void Process_Three(void)
{  Up (&ThreeToOne);
   Up (&ThreeToTwo);
   Down (&OneToThree);
   Down (&TwoToThree);
   Go_to_the_cinema();  }

4. Five jobs are waiting to be run. Their expected run times are 9, 6, 3, 5, and X. In what order should they be run to minimize average response time？(Your answer will depend on X.)
Solution:
IF (X<=3): X, 3, 5, 6, 9
IF (X>=3 AND X<=5): 3, X, 5, 6, 9
IF (X>=5 AND X<=6): 3, 5, X, 6, 9
IF (X>=6 AND X<=9): 3, 5, 6, X, 9
IF (X>=9): 3, 5, 6, 9, X

5. Measurements of certain system have shown that the average process runs for a time T before blocking on I/O. A process switch requires a time S, which is effectively wasted (overhead). For round-robin scheduling with quantum Q, give a formula for the CPU efficiency for each of the following: (a) Q=∞ (b) Q>T  (c) S<Q<T    (d) Q=S   (e) Q nearly 0
Solution:
(a) Q=∞         CPU efficiency=T/ (T+S)
(b) Q>T          CPU efficiency= T/ (T+S)
(c) S<Q<T        CPU efficiency=T/ (T+ST/Q)
(d) Q=S          CPU efficiency=50%
(e) Q nearly 0      CPU efficiency is nearly 0

6. For a resource, its usage situation is shown as the following sequence. Process A: has=1; max=10; Process B: has=3; max=4; Process C: has=3; max=7; free=X. What is the smallest value of X for which this is a safe state?
Answer:
  Request (max) for A: 10-1=9, request (max) for B:4-3=1, request (max) for C:7-3=4
  So, B should run first, X>=1
  And when B runs over, free=X+3, then C runs next, X+3>=4, X>=1
  And when C runs over, free=X+3+3=X+6, then A runs, X+6>=9, X>=3
  So, X>=1 AND X>=1 AND X>=3, X>= 3
  So, the smallest value of X is 3

Example:
Cinderella and Prince are getting divorced. To divide their property, they have agreed on the following algorithm. Every morning, each one may send a letter to the other’s lawyer requesting one item of property. Since it takes a day for letters to be delivered, they have agreed that if both discover that they have requested the same item on the same day, the next day they will send a letter canceling the request. Among their property is their dog, Woofer, Woofer’s doghouse, their canary, Tweeter, and Tweeter’s cage. The animals love their house, so it has been agreed that any division of property separating an animal from its house is invalid, requiring the whole division to start over from scratch. Both Cinderella and Prince desperately want Woofer. So they can go on (separate) vacations, each spouse has programmed a personal computer to handle the negotiation. When they come back from vacation, the computers are still negotiating. Why? Is deadlock possible? Is starvation possible?

Solution:
If the two programs are first to apply for Woofer, computer will receive the hunger of endless sequence: request Woofer, request, demand Woofer, cancellation, etc. If one demands dog house, and another demands the dog, it will deadlock, so both sides found and then again, but the next cycle to repeat again. In another case, if two computers programmed first requests the dog or dog house, it will hungry or deadlock. No difference between here. In most of the deadlock problem, hunger does not seem to be a serious problem, simply introduced stochastic delay hunger makes almost impossible. However, the method is not working here.

· The Dining Philosophers Problem

Five philosophers are seated around a circular table. The life of a philosopher consists of alternate periods of eating and thinking. Each philosopher has a plate of spaghetti. The spaghetti is so slippery that a philosopher needs two forks to eat it. Between each pair of plates is one fork. The layout of the table is illustrated as follows.

Solution:
Define N 5
Define LEFT (i+N-1)%N
Define RIGHT (i+1)/N
Define THINKING 0
Define HUNGRY 1
Define EATING 2
Typedef int semaphore;
Int state[N]
Semaphore mutex=1;
Semaphore s[N];

Void philosopher(int i)
{  while (TRUE)
    {   think();
        take-forks(i);
        eat();
        put_forks(); }  }
Void take_forks( int i)
{  down(&mutex);
    state[i]=HUNGRY;
    test(i);
    up(&mutex);
down(&s[i]);   }

Void put_forks( int i)
{  down(&mutex);
    state[i]=TRINKING;
    test(LEFT);
    test(RIGHT);
up(&mutex);  }

Void test(i)
{   if (state[i]==HUNGRY &&state[LEFT]!=EATING &&state[RIGHT]!=EATING)
    {   state[i]=EATING;
        up(&s[i]);     }
}

· The Sleeping Barber Problem

The barbershop consists of a waiting room with n chairs, and the barber room containing the barber chair. If there are no customers to be served the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, the customer leaves the shop. If the barber is busy, then the customer sits in one of the available free chairs. If the barber is asleep, the customer waked the barber up.
Solution:

·  High Response Ratio First (HRRF)

With this algorithm, the scheduler always chooses the process whose Response Ration is the highest. It is nonpreemptive.
Response Ration (RR)= Turnaround time/ Running time
                  = (Running time + Waiting time) / Running time
                  = 1+ Waiting time / Running time

· Example: There are three batch jobs A through C, and their arrival time and running time are as follows. If use FCFS algorithm, what is the scheduling order? Please compute the turnaround time of every job and the mean turnaround time.

Solution:
  Firstly, schedule Job A to run. When Job A finishes, compute the RR of Job B and C
        RRB= 1+ (6-1)/3 = 2.67
        RRC= 1+ (6-3)/2 = 2.5
RRB is higher, so schedule Job B to run. At last, schedule Job C to run. So the scheduling order is: A→B→C
turnaround time: A: 6-0=6;
B: 9-1=8;
C: 11-3=8
  mean turnaround time: (6+8+8)/3=22/3

·  Shortest Process Next

One approach is to make estimates based on past behavior and run the process with the shortest estimated running time. Suppose that the estimated time per command for some terminal is T0. Now suppose its next run is measured to be T1. We could update our estimate by taking a weighted sum of these two numbers, that is, αT0 + (1-α) T1. Through the choice of α we can decide to have the estimation process forget old runs quickly, or remember them for a long time. With α=1/2, we get successive estimates of
T0, T0/2 + T1/2, T0/4 + T1/4 + T2/2 ……
The technique of estimating the next value in a series by taking the weighted average of the current measured value and the previous estimate is sometimes called aging.
Shortest Process Next is to pick the process with minimum running time to run.

·  Guaranteed scheduling:

Make real promises to the user about performance and then live up to them.

· Lottery scheduling:

Give process lottery tickets for various system resources, whenever a scheduling decision has to be made, a lottery ticket is chosen at random, and the process with that ticket gets the resource. More important processes can be given extra tickets.

·  Nonresource Deadlocks

All of our work so far has concentrated on resource deadlocks. One process wants something that another process has and must wait until the first one gives it up. Deadlocks can also occur in other situations, however, including those not involving resources at all.
For example, it can happen that two processes deadlock each waiting for the other one to do something. This often happens with semaphores. In Chap. 4 we saw examples in which a process had to do a down on two semaphores, typically mutex and another one. If these are done in the wrong order, deadlock can result.

· Two-phase Locking

Although both avoidance and prevention are not terribly promising in the general case, for specific applications, many excellent special-purpose algorithms are known, as an example, in many database systems, an operation that occurs frequently is requesting locks on several records and then updating all the locked records. When multiple processes are running at the same time, there is a real danger of deadlock.
The approach often used is called two-phase locking. In the first phase, the process tries to lock all the records it needs, one at a time. If it succeeds, it begins the second phase, performing its updates and releasing the locks. No real work is done in the first phase.
If during the first phase, some record is needed that is already locked, the process just releases all its locks and stars the first phase all over. In a certain sense, this approach is similar to requesting all the resources needed in advance, or at least before anything irreversible is done. In some versions of two-phase locking, there is no release and restart if a lock is encountered during the first phase. In these versions, deadlock can occur.

· Starvation

A problem closely related to deadlock is starvation. In a dynamic system, requests for resources happen all the time. Some policy is needed to make a decision about who gets which resource when. This policy, although seemingly reasonable, may lead to some processes never getting service even though they are not deadlocked.
As an example, consider allocation of the printer. Imagine that the system uses some kind of algorithm to ensure that allocating the printer does not lead to deadlock. Now suppose that several processes all want it at once. Which one should get it?
One possible allocation algorithm is to give it to the process with the smallest file to print (assuming this information is available). This approach maximizes the number of happy customers and seems fair. Now consider what happens in a busy system when one process has a huge file to print. Every time the printer is free, the system will look around and choose the process with the shortest file. If there is constant stream of processes with short files, the process with the huge file will never be allocated the printer. It will simply starve to death (be postponed indefinitely, even though it is not blocked).
Starvation can be avoided by using a first-come, first-sever, resource allocation policy. With this approach, the process waiting the longest gets served next. In due course of time, any given process will eventually become the oldest and thus get the needed resource.