教材对应的C伪代码.docx
《教材对应的C伪代码.docx》由会员分享，可在线阅读，更多相关《教材对应的C伪代码.docx（52页珍藏版）》请在冰点文库上搜索。
教材对应的C伪代码
/*------------------------------------------------------------------
File:
OScode.cpp《操作系统教程》（第3版）教材对应的C++伪代码
Contents:
OSdescriptioncodefor《操作系统教程》（第三版）
Writtenby:
李贤Jan.2004
Modifiedby:
沈志鹏Jan.2004
Copyright:
Dept.ComputerScience,NanjingUniversity
------------------------------------------------------------------*/
/*------------------------------------------------------------------
本代码写作的出发点为：
方便用C++作为编程语言的同学学习操作系统，使得阅读代码更加容易，理解内容更加方便；同时，本代码并不完全遵循一切C++风格，编写的主旨主要为提高代码的可读性，根据最容易阅读和理解来写出伪代码；最后，代码中的变量名和操作函数名等与原书代码中所取的相同，因此本代码能与书本的相关上下文流畅地衔接。
------------------------------------------------------------------*/
/*----------------------
Chapter3并发进程
----------------------*/
//--------------------------------------------
//Page212例1:
（结果不唯一）购买飞机票问题
//--------------------------------------------
processTi{i=1,2}
{
{按旅客订票要求找到Aj};
intXi=Aj;
if（Xi>=1）
{
Xi--;
Aj=Xi;
{输出一张票};
}
else
{输出信息"票已售完"};
}
//------例1运行情况------
T1:
X1=Aj;X1=m（m>0）
T2:
X2=Aj;X2=m
T2:
X2--;Aj=X2;输出一张票;Aj=m-1
T1:
X1--;Aj=X1;输出一张票;Aj=m-1
//--------------------------------------------
//Page213例2:
（永远等待）内存管理问题
//--------------------------------------------
procedureborrow（intB）
{
if（B>x）
{申请进程进入等待队列等主存资源};
x=x-B;
{修改主存分配表，申请进程获得主存资源};
}
procedurereturn（intB）
{
x=x+B;
{修改主存分配表};
{释放等主存资源的进程};
}
cobegin
{
intx=Memory;//Memory为初始内存容量
repeatborrow（B）;
repeatreturn（B）;
}coend
//--------------------------------------------
//Page2153.2.1互斥和临界区
//--------------------------------------------
//进程T1的临界区为:
X1=Aj;
if（X1>=1）
{
X1--;
Aj=X1;
}
//进程T2的临界区为:
X2=Aj;
if（X2>=1）
{
X2--;
Aj=X2;
}
//--------------------------------------------
//Page216重写的售票管理进程
//--------------------------------------------
sharedAj
processTi{i=1,2}
{
intXi;
{按旅客订票要求找到Aj};
regionAjdo
{
Xi=Aj;
if（Xi>=1）
{
Xi--;
Aj=Xi;
{输出一张票};
}
else
{输出票已售完};
}
}
//--------------------------------------------
//Page2173.2.2临界区管理的尝试
//--------------------------------------------
//尝试1
boolinside1=false;//P1不在其临界区内
boolinside2=false;//P2不在其临界区内
cobegin
{
processP1
{
while（inside2）;//等待
inside1=true;
临界区;
inside1=false;
}
processP2
{
while（inside1）;//等待
inside2=true;
临界区;
inside2=false;
}
}coend
//尝试2
boolinside1=false;//P1不在其临界区内
boolinside2=false;//P2不在其临界区内
cobegin
{
processP1
{
inside1=true;
while（inside2）;//等待
临界区;
inside1=false;
}
processP2
{
inside2=true;
while（inside1）;//等待
临界区;
inside2=false;
}
}coend
//--------------------------------------------
//Page2183.2.3实现临界区管理的软件方法
//--------------------------------------------
//Dekker算法
boolinside[2]={false,false};
intturn=1or2;
cobegin
{
processP1
{
inside[1]=true;
while（inside[2]）
{
if（turn==2）
{
inside[1]=false;
while（turn==2）;
inside[1]=true;
}
}
临界区;
turn=2;
inside[1]=false;
}
processP2
{
inside[2]=true;
while（inside[1]）
{
if（turn==1）
{
inside[2]=false;
while（turn==1）;
inside[2]=true;
}
}
临界区;
turn=1;
inside[2]=false;
}
}coend
//----------Page220Peterson算法---------
boolinside[2]={false,false};
intturn=1or2;
cobegin
{
processP1
{
inside[1]=true;
turn=2;
while（inside[2]&&turn==2）;//等待
临界区;
inside[1]=false;
}
processP2
{
inside[2]=true;
turn=1;
while（inside[1]&&turn==1）;//等待
临界区;
inside[2]=false;
}
}coend
//--------------------------------------------
//Page2223.2.4实现临界区管理的硬件设施
//--------------------------------------------
//-------2.测试并建立指令-------//
//Page221TS指令的处理过程
boolTS（boolx）
{
if（x）
{
x=false;
returntrue;
}
else
returnfalse;
}
//Page222TS指令实现互斥程序
bools=true;
processPi{i=1,2,...,n}
{
boolpi;
do
{
pi=TS（s）;
}while（!
pi）;//上锁
临界区;
s=true;//开锁
}
//-------3.对换指令-------//
//Page222对换指令的处理过程
voidSwap（bool&a,bool&b）
{
booltemp=a;
a=b;
b=temp;
return;
}
//Page222对换指令实现互斥程序
boollock=false;
processPi{i=1,2,...,n}
{
boolpi=true;
do
{
Swap（lock,pi）;
}while（pi）;//上锁
临界区;
lock=false;//开锁
}
//--------------------------------------------
//Page2233.3.1信号量与PV操作
//--------------------------------------------
//生产者-消费者问题
intk;
typedefitemany;//item类型
itembuffer[k];
intin=0,out=0;
intcounter=0;
processproducer
{
while（true）//无限循环
{
{produceaniteminnextp};//生产一个商品
if（counter==k）//缓冲满时，生产者睡眠
sleep（producer）;
buffer[in]=nextp;//将一个产品放入缓冲区
in=（in+1）%k;//指针推进
counter++;//缓冲内产品数加1
if（counter==1）//缓冲为空了，加进一件产品并唤醒消费者
wakeup（consumer）;
}
}
processconsumer
{
while（true）//无限循环
{
if（counter==0）//缓冲区空，消费者睡眠
sleep（consumer）;
nextc=buffer[out];//取一个产品到nextc
out=（out+1）%k;//指针推进
counter--;//取走一个产品，计数减1
if（counter==k-1）//缓冲满了，取走一件产品并唤醒生产者
wakeup（producer）;
{consumetheiteminnextc};//消耗产品
}
}
//--------------------------------------------
//Page2253.3.2记录型信号量与PV操作
//--------------------------------------------
//1.整型信号量
P（s）
{
while（s<=0）;
s--;
}
V（s）
{
s++;
}
//2.记录型信号量Page226
typedefstruct//semaphore结构类型定义
{
intvalue;
listqueue;
}semaphore;
procedureP（semaphores）
{
s.value--;//把信号量减去1
if（s.value<0）//若信号量小于0，则执行P（s）的进程调用W（s.queue）进行
W（s.queue）;//自我封锁，被置成等待信号量s的状态，进入信号量队列queue
}
procedureV（semaphores）
{
s.value++;//把信号量加1
if（s.value<=0）//若信号量小于等于0，则调用R（s.queue）从信号量s队列
R（s.queue）;//queue中释放一个等待信号量s的进程并置成就绪态
}
//3.二元信号量Page227
typedefstruct
{
intvalue;//0or1
listqueue;
}semaphore;
procedureBP（semaphores）
{
if（s.value==1）
s.value=0;
else
W（s.queue）;
}
procedureBV（semaphores）
{
if（s.queueisempty）
s.value=1;
else
R（s.queue）;
}
//--------------------------------------------
//Page2273.3.3用记录型信号量实现互斥
//--------------------------------------------
//一般形式
semaphoremutex;
mutex.value=1;
cobegin
{
...
processPi
{
...
P（mutex）;
临界区;
V（mutex）;
...
}
...
}coend
//记录型信号量和PV操作解决飞机票问题（程序1）
intA[m];
semaphoremutex;
mutex.value=1;
cobegin
{
processPi
{
intXi;
L1:
{按旅客订票要求找到A[j]};
P（mutex）;
Xi=A[j];
if（Xi>=1）
{
Xi--;
A[j]=Xi;
V（mutex）;
{输出一张票};
}
else
{
V（mutex）;
{输出"票已售完"};
}
gotoL1;
}
}coend
//程序2
intA[m];
semaphores[m];
for（intj=0;js[j].value=1;
cobegin
{
processPi
{
intXi;
L1:
{按旅客订票要求找到A[j]};
P（s[j]）;
Xi=A[j];
if（Xi>=1）
{
Xi--;
A[j]=Xi;
V（s[j]）;
{输出一张票};
}
else
{
V（s[j]）;
{输出"票已售完"};
}
gotoL1;
}
}coend
//--------------------------------------------
//Page229哲学家吃通心面问题
//--------------------------------------------
semaphorefork[5];
for（inti=0;i<5;i++）
fork[i]=1;
cobegin
{
processPi//i=0,1,2,3,4
{
L1:
{思考};
P（fork[i]）;
P（fork[i+1]%5）;
{吃通心面};
V（fork[i]）;
V（fork[i+1]%5）;
gotoL1;
}
}coend
//----------------------------------------------------
//Page2303.3.4记录型信号量解决生产者－消费者问题
//----------------------------------------------------
//单生产者－单消费者
intB;
semaphoreempty;//可以使用的空缓冲区数
semaphorefull;//缓冲区内可以使用的产品数
empty.value=1;//缓冲区内允许放入一件产品
full.value=0;//缓冲区内没有产品
cobegin
{
processproducer
{
L1:
{Produceaproduct};
P（empty）;
B=product;
V（full）;
gotoL1;
}
processconsumer
{
L2:
P（full）;
Product=B;
V（empty）;
{Consumeaproduct};
gotoL2;
}
}coend
//m个生产者和n个消费者共享k件产品的缓冲器
itemB[k];
semaphoreempty;empty.value=k;//可以使用的空缓冲区数
semaphorefull;full.value=0;//缓冲区内可以使用的产品数
semaphoremutex;mutex.value=1;//互斥信号量
intin=0;//放入缓冲区指针
intout=0;//取出缓冲区指针
cobegin
{
processproducer_i
{
L1:
{Produceaproduct};
P（empty）;
P（mutex）;
B[in]=product;
in=（in+1）%k;
V（mutex）;
V（full）;
gotoL1;
}
processconsumer_j
{
L2:
P（full）;
P（mutex）;
Product=B[out];
out=（out+1）%k;
V（mutex）;
V（empty）;
{Consumeaproduct};
gotoL2;
}
}coend
//--------------------------------------------
//Page232父母子女苹果桔子消费问题
//--------------------------------------------
intplate;
semaphoresp;//盘子里可以放几个水果
semaphoresg1;//盘子里有桔子
semaphoresg2;//盘子里有苹果
sp.value=1;//盘子里允许放入一个水果
sg1.value=0;//盘子里没有桔子
sg2.value=0;//盘子里没有苹果
cobegin
{
processfather
{
L1:
{削一个苹果};
P（sp）;
{把苹果放入plate};
V（sg2）;
gotoL1;
}
processmother
{
L2:
{剥一个桔子};
P（sp）;
{把桔子放入plate};
V（sg1）;
gotoL2;
}
processson
{
L3:
P（sg1）;
{从plate中取桔子};
V（sp）;
{吃桔子};
gotoL3;
}
processdaughter
{
L4:
P（sg2）;
{从plate中取苹果};
V（sp）;
{吃苹果};
gotoL4;
}
}coend
//-----------------------------------------------
//Page2343.3.5记录型信号量解决读者-写者问题
//-----------------------------------------------
intrc=0;//读进程计数
semaphoreW,mutex;
W.value=1;
mutex.value=1;
procedureread
{
P（mutex）;
rc++;
if（rc==1）
P（W）;
V（mutex）;
读文件;
P（mutex）;
rc--;
if（rc==0）
V（W）;
V（mutex）;
}
procedurewrite
{
P（W）;
写文件;
V（W）;
}
processreader_i
{
read;
}
processwriter_j
{
write;
}
cobegin
{
processreader_i;
processwriter_j;
}coend
//-----------------
升级会员 