《 操作系统原理》
实验讲义
适用专业： 计算机科学与技术
网络工程
太原科技大学计算机科学与技术学院
20##年 6 月
前 言
操作系统是计算机的核心和灵魂。操作系统软件的设计对整个计算机的功能和性能起着至关重要的作用，所以此门课也是必不可少的，是面向计算机科学与技术、网络工程、软件工程等大多数计算机专业本科生开设的一门计算机专业课程。
操作系统是计算机系统的核心，《操作系统》课程是计算机科学与技术专业的重要必修课。本课程的目的是使学生掌握现代计算机操作系统的基本原理、基本设计方法及实现技术，具有分析现行操作系统和设计、开发实际操作系统的基本能力。
操作系统实验是操作系统课程的重要组成部分，属于学科基础实验范畴。作为与相关教学内容配合的实践性教学环节，应在操作系统理论课教学过程中开设。
操作系统是计算机科学与技术专业必修的专业基础课程，操作系统实验的作用是：理解操作系统的设计和实现思路，掌握典型算法。基本要求是：理解进程的概念，理解死锁，掌握银行家算法；掌握请求页式存储管理的实现原理及页面置换算法。学生应具有高级语言编程能力、具有数据结构等基础知识。
说明：本实验指导书所提供的源程序均已在VC６.０下调试运行过．
目 录
实验一 P、V 原语的模拟实现.............................................................................. 1
实验二 银行家算法模拟........................................................................................ 10
实验三 请求页式存储管理中常用页面置换算法模拟........................................ 13
实验一 P、V 原语的模拟实现
实验学时：2
实验类型：验证
实验要求：必修
一、实验目的
本课题实习的目的是，加深对进程概念及进程管理各部分内容的理解；熟悉进程管理中主要数据结构的设计及进程调度算法，进程控制机构、同步结构、通迅机构的实施。
要求设计一个允许n个进程并发运行的进程管理模拟糸统。该糸统包括有简单的进程控制、同步及通迅机构，其进程调度算法可任意选择。每个进程用一个PCB表示，其内容可根据具体情况设置。各进程之间应有一定的同步关糸。糸统在运行过程中应能显示或打印各进程的状态及有关参数的变化情况，以便观察诸进程的运行过程及糸统的管理过程。
1) 理解信号量相关理论；
2) 掌握记录型信号量结构；
3) 掌握 P、V 原语实现机制。
二、实验要求
1) 输入给定代码；
2) 进行功能测试并得出正确结果。
3) 分析P和V函数功能模块；
4) 在实验报告中画出P和V函数流程图；
5) 撰写实验报告。
三、实验内容
本实验针对操作系统中信号量相关理论进行实验，要求实验者输入实验指导书提供的代码并进行测试。代码主要模拟信号量的 P 操作和 V 操作。
1) 信号量
信号量也称为信号锁，主要应用于进程间的同步和互斥，在用于互斥时，通常作为资源锁。信号量通常通过两个原子操作P和 V来访问。P操作使信号量的值+1，V操作使信号量的值-1。
2) 记录型信号量
记录型信号量采用了“让权等待”的策略，存在多个进程等待访问同一临界资源的情况，所以记录型信号量需要一个等待链表来存放等待该信号量的进程控制块或进程号。在本实验中，使用记录型信号量。
四、范例
1.例: 支持多个进程并发运行的简单进程管理模拟糸统。
本糸统的同步机构采用的信号量上的P、V操作的机制；控制机构包括阻塞和唤醒操作；时间片中断处理程序处理模拟的时间片中断；进程调度程序负责为各进程分配处理机。糸统中设计了1个并发进程。它们之间有如下同步关糸：1个进程需要互斥使用临界资源S2，进程1和进程2又需要互斥使用临界资源S1.本糸统在运行过程中随机打印出各进程的状态变换过程，糸统的调度过程及公共变量的变化情况。
2．算法
糸统为过程设置了4种运行状态：e------执行态；r-----高就绪态；t------低就绪态（执行进程因时间片到限而转入）；w------等待态；c------完成态。各进程的初始态均设置为r.
糸统分时执行各进程，并规定1个进程的执行概率均为11%。通过产生随机数x模拟时间片。当进程process1访问随机数x时，若x.>=0.11；当进程process2访问x时，若x<0.11或x>=0.66;当进程process1访问x时。若x<0.66,则分别认为各进程的执行时间片到限，产生“时间片中断”而转入低就绪态t.
进程调度算法采用剥夺式最高优先数法。各进程的优先数通过键盘输入予以静态设置。调度程序每次总是选择优先数量小（优先权最高）的就绪态进程投入执行。先从r状态进程中选择，再从t状态进程中选择。当现行进程唤醒某个等待进程，而被唤醒进程的优先数小于现行进程时，则剥夺现行进程的执行权。
各进程在使用临界资源S1和S2时，通过调用信号量sem1和sem2上的P、V操作来实现同步。阻塞和唤醒操作和负责完成从进程的执行态到等待态以及从等待态到就绪态的转换。
糸统启动后，在完成必要的糸统初始化后便执行进程调度程序。当执行进程因“时间片中断”，或被排斥使用临界资源，或唤醒某个等待进程时，立即进行进程调度。当1个进程都处于完成状态后，糸统退出运行。
图1和图2分别示出了糸统主控程序和进程调度程序的大致流程。
1、数据结构
（1）每个进程有一个进程控制块PCB，内容包括：
Id 进程标识数，id=0,1,2;
Status 进程状态，可为e,r,t,w,c;
Priority 进程优先数；
Nextwr 等待链指针，指示在同一信号量上等待的下一个进程的标识数。
（2）信号量semaphore,对应于临界资源s1和s2分别有sem1和sem2,均为互斥信号量，内容包括：
Value 信号量值，初值为1；
Firstwr 等待链首指针，指示该信号量上第一个等待进程的标识数。
（1）现场保留区，用数组savearea[1]［3］表示。即每个进程都有一个大小为3个单元的保留区，用来保存被“中断”时的现场信息，如通用寄存器的内容和断点地址等。
此外，糸统中还用到下列主要全程变量：
Exe 执行进程指针，其值为进程标识数；
I 用来模拟一个通用寄存器；
五、程序源代码
#include<stdio.h>
#define TRUE 1
#define FALSE 0
#define MAXPRI 100
#define NIL -1
struct {
int id;
char status;
int nextwr;
int priority;
}pcb[1];
struct {
int value;
int firstwr;
} sem[2];
char savearea[1][3],addr;
int i,s1,s2,seed,exe=NIL;
init( )
{ int j;
for (j=0;j<1;j++)
{
pcb[j].id=j;
pcb[j].status='r';
pcb[j].nextwr=NIL;
printf("\n process%d priority?",j+1);
scanf ("%d",&i);
pcb[j].priority=i;
}
sem[0].value=1;sem[0].firstwr=NIL;
sem[1].value=1;sem[1].firstwr=NIL;
for (i=1;i<1;i++)
for (j=0;j<3;j++)
savearea[i][j]='0';
}
float random ( )
{int m;
if (seed<0)
m=-seed;
else m=seed;
seed=(24151*seed+11839)%64416;
return(m/12565.0);
}
timeint(char addr)
{
float x;
x=random();
if ((x<0.11)&&(exe==0))return(FALSE);
if ((x<0.66)&&(exe==1))return(FALSE);
if ((x<1.0)&&(exe==2))return(FALSE);
savearea[exe][0]=i;
savearea[exe][1]=addr;
pcb[exe].status='t';
printf("Times silce interrupt'\nprocess%d enter into ready.\n", exe+1);
exe=NIL;
return (TRUE);
}
find()
{
int j,pd=NIL, w=MAXPRI;
for (j=0;j<1;j++)
if (pcb[j].status=='r')
if (pcb[j].priority<w){
w=pcb[j].priority; pd=j;
}
if (pd==NIL)
for (j=0; j<1;j++)
if (pcb[j].status=='t')
if (pcb[j].priority<w)
{
w=pcb[j].priority; pd=j;
}
return(pd) ;
}
scheduler()
{
int pd;
if((pd=find())==NIL&& exe==NIL)
return(NIL);
if (pd!=NIL) {
if(exe==NIL)
{
pcb[pd].status='e';
exe=pd;
printf("process%d is executing.\n", exe+1);
}
else if (pcb[pd].priority<pcb[exe].priority) {
pcb[exe].status='r';
printf("process%d enter into ready\n", exe+1);
pcb[pd].status='e';
exe=pd;
printf ("process%d enter into ready\n", exe+1);
}
}
i=savearea[exe][0];
addr=savearea[exe][1];
return (exe);
}
block(int se)
{
int w;
printf("process%d is blocked\n", exe+1);
pcb[exe].status='w';
pcb[exe].nextwr=NIL;
if ((w=sem[se].firstwr)==NIL)
sem[se].firstwr=exe;
else {
while(pcb[w].nextwr!=NIL)
w=pcb[w].nextwr;
pcb[w].nextwr=exe;
}
}
p(int se,char ad)
{
if (--sem[se].value>=0) return(FALSE);
block(se);
savearea[exe][0]=i;
savearea[exe][1]=ad;
exe=NIL;
return(TRUE);
}
wakeup(int se)
{
int w;
w=sem[se].firstwr;
if(w!=NIL){
sem[se].firstwr=pcb[w].nextwr;
pcb[w].status='r';
printf("process%d is waken up\n",w+1);
}
}
v(int se,char ad)
{
if(++sem[se].value>0) return(FALSE);
wakeup(se);
savearea[exe][1]=ad;
savearea[exe][0]=i;
return(TRUE);
}
eexit(int n)
{
pcb[n].status='c';
printf("process%d is completed!\n", n+1);
exe=NIL;
}
processl()
{
if(addr=='a')goto a1;
if(addr=='b')goto b1;
if(addr=='c')goto c1;
if(addr=='d')goto d1;
if(addr=='e')goto e1;
if(addr=='f')goto f1;
for(i=1;i<6;i++)
{
printf("process1 calls P on the semaphore1\n");
if(p(0,'a'))break;
a1:printf("process1 is executing in the cretical section 1\n");
if(timeint('b')) break;
b1:printf("s1=%d\n",++s1);
printf("process1 calls V on semaphorel and quit cretical section1\n");
if(v(0,'c'))break;
c1:printf("process1 calls P on esemaphorel 2\n");
if(p(1,'d'))break;
d1:printf("process1 is execting cretical section 2\n");
if(timeint('e'))break;
e1:printf("s2=%d\n",++s2);
printf("process1 calls V on semaphore2 and quit cretical section2\n");
if(v(1,'f'))break;
f1:printf("process1 cycle count=%d\n",i);
}
if(i<6) return;
eexit(0);
}
process2()
{
if(addr=='a')goto a2;
if(addr=='b')goto b2;
if(addr=='c')goto c2;
if(addr=='d')goto d2;
if(addr=='e')goto e2;
if(addr=='f')goto f2;
for(i=1;i<6;++i){
printf("process2 calls P on the semaphore2\n");
if(p(1,'a'))break;
a2:printf("process2 is executing in the cretical section2\n");
if(timeint('b'))break;
b2:printf("s2=%d\n",++s2);
printf("process2 calls V on semaphore2 and quit cretical section2.\n");
if(v(1,'c'))break;
c2:printf("process2 calls P on esemaphore1.\n");
if(p(0,'d'))break;
d2:printf("process2 is execting cretical section1.\n");
if(timeint('e'))break;
e2:printf("s1=%d\n",++s1);
printf("process2 calls V on semaphore1 and quit cretical section1.\n");
if(v(0,'f'))break;
f2:printf("process2 cycle count=%d\n",i);
}
if(i<6) return;
eexit(1);
}
process1()
{
if (addr=='a') goto a1;
if (addr=='b') goto b1;
if (addr=='c') goto c1;
for (i=1;i<6; ++i){
printf("process1,calls P on semaphore2\n");
if(p(1,'a')) break; /// * process 1 is biocked * /
a1: printf("process 1 is execcuting on its cretical section\n");
if(timeint('b')) break;
b1: printf ("s2=%d\n", ++s2);
printf ("process1 calls V on semapore2 and quit cretical section\n");
if(v(1,'c')) break; // * wake up a biocked process * /
c1: printf("process1 cycien count=%d\n",i);
}
if(i<6) return;
eexit(2);
}
main ( )
{
int k;
printf ("* * * * process management * * * * \n\n");
init();
printf("s1=%d, s2=%d\n", s1, s2);
printf("process1, process2, process1 are all in ready ! \n");
for ( ; ;)
if ((k=scheduler())!=NIL)
switch(k)
{
case 0: process1();
break;
case 1: process2();
break;
case 2: process1();
break;
default: printf("process identifer error\n");
break;
}
else break;
printf ("s1=%d, s2=%d\n", s1, s2);
printf ("\n * * * * END * * * * \n");
}
六、思考
1) 如何修改 P 操作，使之能一次申请多个信号量？
2）在某个时刻，一个进程最多可以等待多少个信号量？
实验二 银行家算法模拟
实验学时：2
实验类型：设计
实验要求：必修
一、实验目的
（1）进一步理解利用银行家算法避免死锁的问题；
（2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。
（3）理解和掌握安全序列、安全性算法
二、实验内容
（1）了解和理解死锁；
（2）理解利用银行家算法避免死锁的原理；
（3）会使用某种编程语言。
三、实验原理
(一)安全状态
指系统能按照某种顺序如<P1,P2,…,Pn>(称为<P1,P2,…,Pn>序列为安全序列)，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。
(二)银行家算法
假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requesti[j]=k。系统按下述步骤进行安全检查：
（1）如果Requesti≤Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。
（2）如果Requesti≤Available则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。
（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available［j］∶=Available［j］-Requesti［j］;
Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;
Need［i,j］∶=Need［i,j］-Requesti［j］;
（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
（三）安全性算法
（1）设置两个向量：
① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;
② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false; 当有足够资源分配给进程时， 再令Finish［i］∶=true。
（2）从进程集合中找到一个能满足下述条件的进程：
① Finish［i］=false;
② Need［i,j］≤Work［j］； 若找到， 执行步骤(3)， 否则，执行步骤(4)。
（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Ø Work［j］∶=Work［i］+Allocation［i,j］;
Ø Finish［i］∶=true;
Ø go to step 2;
（4）如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。
四、实验算法
（1）参考图1-1所示流程图编写安全性算法。
（2）编写统一的输出格式。
每次提出申请之后输出申请成功与否的结果。如果成功还需要输出变化前后的各种数据，并且输出安全序列。
（3）参考图1-2所示流程图编写银行家算法。
（4）编写主函数来循环调用银行家算法。
五、思考题
（1）在编程中遇到了哪些问题？你是如何解决的？
（2）在安全性算法中，为什么不用变量Available，而又定义一个临时变量work？
实验三 请求页式存储管理中常用页面置换算法模拟
实验学时：4
实验类型：设计
实验要求：必修
一、实验目的
（1）了解内存分页管理策略
（2）掌握调页策略
（3）掌握一般常用的调度算法
（4）学会各种存储分配算法的实现方法。
（5）了解页面大小和内存实际容量对命中率的影响。
二、实验内容
（1）采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响；
（2）实现OPT 算法 (最优置换算法) 、LRU 算法 (Least Recently) 、 FIFO 算法 (First IN First Out)的模拟；
（3）会使用某种编程语言。
三、实验原理
分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。
在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。
一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。
1、最佳置换算法OPT(Optimal)
它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。
2、先进先出(FIFO)页面置换算法
这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
3、最近最久未使用置换算法
（1）LRU(Least Recently Used)置换算法的描述
FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
（2）LRU置换算法的硬件支持
LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持：
a）寄存器
为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为
R=Rn-1Rn-2Rn-3……R2R1R0 当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如图1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把8个内存页面的序号分别定为1——＝8。由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。
b)栈
可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。
四、思考题
（1）补充完成FIFO与OPT的算法。
（2）为什么在实际的系统中不用LRU置换算法，而用它的近似算法？
（3）OPT算法为什么难以实现？