操作系统试验参考指导书.doc

《 操作系统原理》
实验指引书

羊四清 编 写

合用专业： 计算机科学与技术
网络工程

湖南人文科技学院计算机科学技术系
8 月

前 言

操作系统是计算机核心和灵魂。操作系统软件设计对整个计算机功能和性能起着至关重要作用，因此此门课也是必不可少，是面向计算机科学与技术、网络工程、软件工程等大多数计算机专业本科生开设一门计算机专业课程。
操作系统是计算机系统核心，《操作系统》课程是计算机科学与技术专业重要必修课。本课程目是使学生掌握当代计算机操作系统基本原理、基本设计办法及实现技术，具备分析现行操作系统和设计、开发实际操作系统基本能力。
操作系统实验是操作系统课程重要构成某些，属于学科基本实验范畴。作为与有关教学内容配合实践性教学环节，应在操作系统理论课教学过程中开设。
操作系统是计算机科学与技术专业必修专业基本课程，操作系统实验作用是：理解操作系统设计和实现思路，掌握典型算法。基本规定是：理解进程概念，理解死锁，掌握银行家算法；掌握祈求页式存储管理实现原理及页面置换算法。学生应具备高档语言编程能力、具备数据构造等基本知识。
阐明：本实验指引书所提供源程序均已在VC６.０下调试运营过．
目录

实验一 进程创立模仿 1
实验二 进程撤销模仿 9
实验三 P、V 原语模仿实现 10
实验四 带优先级时间片轮换进程调度算法实现 16
实验五 银行家算法模仿 26
实验六 持续动态内存管理模仿实现 29
实验七 祈求页式存储管理中惯用页面置换算法模仿 31
实验八 SCAN 磁盘调度模仿实现 36
实验九 UNIX基本操作 37

实验一 进程创立模仿
实验学时：2
实验类型：验证
实验规定：必修
一、实验目
1） 理解进程创立有关理论；
2） 掌握进程创立办法；
3） 掌握进程有关数据构造。
二、实验内容
本实验针对操作系统中进程创立有关理论进行实验。规定实验者输入实验指引书提供代码并进行测试。代码简化了进程创立各种环节和内容。进程树形构造采用广义二叉树方式进行存储。
三、实验原理
1）进程控制块
为了描述和控制进程运营，系统为每个进程定义了一种进程控制块（PCB），它是进程实体一某些，是操作系统管理进程最重要数据构造。其重要包括四类信息：
(1) 进程标记符
它唯一地标记一种进程。普通涉及进程号 pid，父进程号 ppid 和顾客号 uid。
(2) 解决机状态
解决器状态普通由解决机各种寄存器中内容构成。PCB 存储中断（阻塞，挂起）时各寄存器值，当该进程重新执行时，可以从断点处恢复。重要涉及：
a) 通用寄存器；
b) 指令计数器；
c) 程序状态字 PSW；
d) 顾客栈指针。
(3) 进程调度信息
a) 进程状态；
b) 进程优先级（用于描述优先使用 cpu 级别一种整数，高优先级进程先得到cpu，普通状况下，优先值越小优先级越高）；
c) 其他信息（等待时间、总执行时间等）；
d) 事件（等待因素）。
(4) 进程控制信息
a) 程序和数据地址（程序在内存和外存中首址）；
b) 进程同步和通信机制；
c) 资源列表（进程除 CPU 以外所有资源）；
d) 链接指针（进程队列中指向下一种进程 PCB 首址）。
2) 进程创立流程
(1) 申请空白 PCB
为新进程申请获得唯一数字标记符，并从 PCB 集合中索取一种空白 PCB。如果无空白PCB，可以创立一种新 PCB。在本实验中，每次动态创立 PCB。
(2) 为新进程分派资源
为新进程分派内存空间和栈空间。
(3) 初始化进程控制块
a) 初始化标记信息；
b) 初始化解决机状态信息；
c) 初始化解决机控制信息。
(4) 将新进程插入就绪队列
P1
P2
P3
P4
P5
P6
P7
P8
P9
P10
P11
P12
3) 进程树

图 1-1 进程树
进程树用于描述进程家族关系，如图 1-1 中可以看出，进程 P1 创立了进程 P2、P3、P4、P5，而 P2 又创立了 P6、P7、P8 …… 。在进程创立过程中，需要对每一种新增长进程加入到进程树中，有了清晰父子关系，可以使资源继承或进程删除等操作变得很以便。
4) 进程总链
它是一种 PCB 链表，每一种新创立进程必要把其 PCB 放入总链中，该总链可以对破坏进程树进行修复，也以便 PCB 查找。
四、程序清单
1.basic.h 文献
#ifndef basic_h
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define basic_h
char *errormsg[256];
//process control block
struct pcb
{
int pid;//process id
int ppid;//parent process id
int prio;//priority
int state;//state
int lasttime;//last execute time
int tottime；//totle execute time
};
//process node
struct pnode
{
pcb *node;
pnode *sub;
pnode *brother;
pnode *next;
};
//信号量
struct semphore{
char name[5]；//名称
int count;//计数值
int curpid;//当迈进程 id
pnode *wlist；//等待链表
};
#define geterror(eno) printf("%s\n",errormsg[eno])

void initerror()
{
errormsg[0] = (char *)malloc(20);
errormsg[0]="error command!";
errormsg[1] = (char *)malloc(20);
errormsg[1]="error parameter!";
}
//get a substring in string s
char * substr(char *s,int start,int end)
{
char *s1;
int len = strlen(s);
if(start<0 || end>=len || start>end)
return NULL;
s1=(char *)malloc(end-start+2);
for(int i=0;i<=end-start;i++)
s1[i] = s[i+start];
s1[i]='\0';
return s1;
}
//find the location of c in string s
int instr(char *s,char c)
{
unsigned i;
for(i=0;i<strlen(s);i++)
if(s[i]==c)
return i;
return -1;
}
//change the string to array data
int * strtoarray(char *s)
{
int *a,count,x1;
unsigned int i;
char c，*s1,*s2;
if(!s)
{
printf("string can't be null!\n");
return NULL;
}
count=0;
s1=s;
for(i=0;i<strlen(s1);i++)
if(s1[i]==',')
count++;
count++;
a = (int *)malloc(count);
c=',';
for(i=0;i<count;i++)
{
x1 = instr(s1,c);
if(x1>=0)
s2=substr(s1,0,x1-1);
else
s2=s1;
a[i]=atoi(s2);
if(c==',')
s1=substr(s1,x1+1,strlen(s1)-1);
}
return a;
}
#endif

2、源程序
#include "basic.h"
pnode *proot;//system process tree root
pnode *plink;//system process link head
//create process
int createpc(int *para)
{
//add your code here
pnode *p,*p1,*pp;
int pflag;
pflag=0;
for(p=plink;p;p=p->next)
{
if(p->node->pid == para[0]) //check if this pid is already exist
{
printf("pid %d is already exist!\n",para[0]);
return -1;
}
if(p->node->pid == para[1]) //find parent pcb
{
pflag=1;
pp = p;
}
}
if(!pflag)
{
printf("parent id %d is not exist!\n",para[1]);
return -2;
}
//init new pcb
p1 = new pnode;
p1->node=new pcb;
p1->node->pid = para[0];
p1->node->ppid = para[1];
p1->node->prio = para[2];
p1->sub=NULL;
p1->next=NULL;
p1->brother=NULL;
//add to process tree
if(!pp->sub)
pp->sub=p1;
else
{
for(p=pp->sub;p->brother;p=p->brother);
p->brother=p1;
}
// add to process link
for(p=plink;p->next;p=p->next);
p->next=p1;
return 0;
}
//show process detail
void showdetail()
{
//add your code here
pnode *p,*p1;
p=plink;
for(;p;) //print all pcb info
{
printf("%d(prio %d):",p->node->pid,p->node->prio);
p1 = p->sub;
for(;p1;) //print sub pcb
{
printf("%d(prio %d)",p1->node->pid,p1->node->prio);
p1 = p1->brother;
}
printf("\n");
p = p->next;
}
printf("\n");
}
//don't change
void main()
{
initerror();
short cflag,pflag;
char cmdstr[32];
proot = new pnode;
proot->node=new pcb;
proot->node->pid=0;
proot->node->ppid=-1;
proot->node->prio=0;
proot->next=NULL;
proot->sub=NULL;
proot->brother=NULL;
plink=proot;
for(;;)
{
cflag=0;
pflag=0;
printf("cmd:");
scanf("%s",cmdstr);
if(!strcmp(cmdstr,"exit")) //exit the program
break;
if(!strcmp(cmdstr,"showdetail"))
{
cflag = 1;
pflag = 1;
showdetail();
}
else
{
int *para;
char *s,*s1;
s = strstr(cmdstr,"createpc")；//create process
if(s)
{
cflag=1;
para = (int *)malloc(3);
//getparameter
s1 = substr(s,instr(s,'(')+1,strlen(s)-2)；//get param string
para=strtoarray(s1);//get parameter
createpc(para)；//create process
pflag=1;
}
}
if(!cflag)
geterror(0);
else
if(!pflag)
geterror(1);
}
}
五、实验环节
输入实验提供代码后，可以输入 createpc 命令创立进程，输入 showdetail 显示每个进程及其子进程信息，测试命令解释如下：
1) createpc 创立进程命令。
参数： 1、pid（进程 id） 2 、ppid（父进程 id）3、prio（优先级）。
示例：createpc(1,0,1) 。创立一种进程，其进程号为 1，父进程号为 0，优先级为 1.
createpc(2,1,2) 。创立一种进程，其进程号为 2，父进程号为 1，优先级为 2。
2) showdetail 显示进程信息命令。
3) exit退出命令行。
六、思考题
1) 进程创立核心内容是什么？
2) 该设计和实际操作系统进程创立相比，缺少了哪些环节？
实验二 进程撤销模仿
实验学时：2
实验类型：验证
实验规定：必修
一、实验目
1) 理解进程撤销有关理论；
2) 掌握进程撤销流程。
二、实验内容
本实验针对操作系统中进程撤销有关理论进行实验。规定实验者设计一种程序，该程序可模仿撤销各种进程及其子孙进程。
1) 采用动态或静态办法生成一颗进程树（进程数目≥20）；
2) 设计进程撤销算法；
3) 实现进程撤销函数，采用级联方式撤销；
4) 可动态撤销进程；
5) 可动态观测进程树状况；
6) 测试程序并得到对的成果。
三、实验原理
1)进程创立流程
(1) 从 PCB 链中找到该进程 PCB，从中读出该进程状态；
(2) 如果该进程处在执行状态，则终结该进程并置调度标志为真；
(3) 若该进程有子孙进程，需要撤销其子孙进程；
(4) 释放该进程占有资源；
(5) 从 PCB 链中移出该进程 PCB。
2） 进程子树删除
对于已经创立进程树（可以参照实验 1 创立进程），在删除时候，一方面需要考虑把该进程及其子孙从整棵树中脱离出来，这样才不会破坏整棵树完整性。
3） 进程总链元素删除
对于进程树种撤销所有进程，必要在进程总链中进行删除。
四、思考题
1） 进程撤销核心内容是什么？
2） 进程总链在进程撤销过程中有什么作用？

实验三 P、V 原语模仿实现
实验学时：2
实验类型：验证
实验规定：必修
一、实验目
1) 理解信号量有关理论；
2) 掌握记录型信号量构造；
3) 掌握 P、V 原语实现机制。
二、实验内容
本实验针对操作系统中信号量有关理论进行实验，规定实验者输入实验指引书提供代码并进行测试。代码重要模仿信号量 P 操作（down）和 V 操作（up）。
1) 信号量
信号量也称为信号锁，重要应用于进程间同步和互斥，在用于互斥时，普通作为资源锁。信号量普通通过两个原子操作 dwon(P)和 up(V)来访问。dwon 操作使信号量值+1，up 操作使信号量值-1。
2) 记录型信号量
记录型信号量采用了“让权等待”方略，存在各种进程等待访问同一临界资源状况，因此记录型信号量需要一种等待链表来存储等待该信号量进程控制块或进程号。在本实验中，使用记录型信号量。

三、实验规定
1) 输入给定代码；
2) 进行功能测试并得出对的成果。
3) 分析 dwon 和 up 函数功能模块；
4) 在实验报告中画出 dwon 和 up 函数流程图；
5) 撰写实验报告。
四、程序清单
#include "basic.h"

semphore sem[5]；//deinfe 5 semphores
pnode * pr[20]；//define 0-19 total 20 process
//down operation

void down(char * sname,int pid)
{
int fflag,pflag；
pnode *p,*p1；
semphore *s；
fflag=0；
pflag=0；
for(int i=0;i<5;i++)
if(!strcmp(sem[i].name,sname))//find semaphore by name
{
s=&sem[i]；
fflag=1；
break；
}
for(i=0;i<20;i++) //find pcb by pid
if(pr[i]->node->pid == pid)
{
p1 = pr[i]；
pflag=1；
break；
}
if(!fflag) //semaphore is not exist
{
printf("the semphore '%s' is not exist!\n",sname)；
return；
}
if(!pflag) //pid is not exist
{
printf("the process '%d' is not exist!\n",pid)；
return；
}
s->count--； //semaphore！s value -1
if(s->count>=0) //this pcb get the semaphore
s->curpid = p1->node->pid；
else
{
if(s->wlist) //the link is not NULL，add the pcb to the last
{
for(p=s->wlist;p->next;p=p->next)；
p->next=p1；
}
else //this pcb is the first pcb be added to the down list
s->wlist=p1；
}
}

//up operation
void up(char *sname)
{
int fflag=0；
for(int i=0;i<5;i++)
if(!strcmp(sem[i].name,sname)) //find the semaphore by name
{
fflag=1；
break；
}
if(fflag) //find it
{
sem[i].count++；
if(sem[i].wlist) //there are processes in the down list
{
sem[i].curpid = sem[i].wlist->node->pid；
sem[i].wlist = sem[i].wlist->next；
}
}
else
printf("the semphore '%s' is not exist!\n",sname)；
}

//show semphore infomation
void showdetail()
{
int i；
pnode *p；
printf("\n")；
for(i=0;i<5;i++)
{
if(sem[i].count<=0)
{
printf("%s (current_process %d)： ",sem[i].name,sem[i].curpid)；
p=sem[i].wlist；
while(p)
{
printf("%5d",p->node->pid)；
p=p->next；
}
}
else
printf("%s ： ",sem[i].name)；
printf("\n")；
}
}

/***************************************************************/
void init()
{
//init semaphore
strcat(sem[0].name,"s0")；
strcat(sem[1].name,"s1")；
strcat(sem[2].name,"s2")；
strcat(sem[3].name,"s3")；
strcat(sem[4].name,"s4")；
for(int i=0;i<5;i++)
{
sem[i].wlist=NULL；
sem[i].count=1；
}
//init process
for(i=0;i<20;i++)
{
pr[i] = new pnode；
pr[i]->node=new pcb；
pr[i]->node->pid=i；
pr[i]->brother=NULL；
pr[i]->next=NULL；
pr[i]->sub=NULL；
}
}

void main()
{
short cflag,pflag；
char cmdstr[32]；
char *s,*s1,*s2；

initerror()；
init()；

for(;;)
{
cflag=0；
pflag=0；
printf("cmd:")；
scanf("%s",cmdstr)；
if(!strcmp(cmdstr,"exit")) //exit the program
break；
if(!strcmp(cmdstr,"showdetail"))
{
cflag = 1；
pflag = 1；
showdetail()；
}
else
{
s = strstr(cmdstr,"down")；//create process
if(s)
{
cflag=1；
//getparameter
s1 = substr(s,instr(s,'(')+1,instr(s,',')-1)；
s2 = substr(s,instr(s,',')+1,instr(s,')')-1)；
if(s1 && s2)
{
down(s1,atoi(s2))；
pflag=1；
}
}
else
{
s=strstr(cmdstr,"up");//delete process
if(s)
{
cflag=1；
s1 = substr(s,instr(s,'(')+1,instr(s,')')-1)；
if(s1)
{
up(s1)；
pflag=1；
}
}
}
}
if(!cflag)
geterror(0)；
else if(!pflag)
geterror(1)；
}
}
/*******************************************************************/
五、测试规定
1） 至少进行 10 次以上 wait 和 signal 操作；
2） 规定 wait 操作浮现进程等待队列；
3） 对有等待队列信号量进行 signal 操作。
六、实验指引
实验中提供了 5 个信号量（s0-s4）和 20 个进程（pid 0-19）。在程序运营过程中可以键入 down up 命令和 showdetail 命令显示每个信号量状态。详细输入解释如下：
1) dwon 获取信号量操作（P 操作）。
参数： 1 sname 2 pid 。
示例：down(s1,2) 。进程号为 2 进程申请名字为 s1 信号量。
2) up 释放信号量操作（V 操作）。
参数 1 sname。
示例：up(s1)。释放信号量名字为 s1 信号量。
3) showdetail 显示各信号量状态及其等待队列。
4) exit退出命令行。
七、实验思考
1) 如何修改 dwon 操作，使之能一次申请各种信号量？
2）在某个时刻，一种进程最多可以等待多少个信号量？
实验四 带优先级时间片轮换进程调度算法实现
实验学时：4
实验类型：设计
实验规定：必修
一、实验目
（1）掌握进程状态转换过程
（2）掌握时间片轮转进程调度算法；
（3）掌握带优先级进程调度算法；
二、实验内容
（1）自定义PCB数据构造；
（2）使用带优先级时间片轮转法调度进程，每运营一种时间片，优先级减半。
（3）命令集
A）create 随机创立进程，进程优先级与所需要时间片随机决定；
B）round 执行1次时间片轮转操作，其办法为运营高优先级队列第1个，再减少其优先级，插入到相应队列中。
C）ps 查看当迈进程状态
D）sleep 命令将进程挂起
E）awake 命令唤醒1个被挂起进程
F）kill 命令杀死进程
G）quit命令退出
（4）选用面向对象编程办法。
三、实验原理或算法
本实验结合了进程状态转换、优先级调度、时间片轮转调度三方面内容，依照进程状态转换图，设立SLEEP命令，将1个进程挂起，AWAKE命令唤醒1个被挂起进程（从阻塞状态到就绪状态）。
1) 优先级
优先级体现了进程重要限度或急迫限度，在大多数当代操作系统中，都采用了优先级调度方略。优先级从小到大（如 0-127） 优先级最高，127 最低。在本实验中按数值大小决定优先级，数值大优先级高。
2) 基于时间片调度
将所有就绪进程按照先来先服务原则，排成一种队列，每次调度时，将 cpu 分派给队首进程，并令其执行一种时间片。当时间片用完时，由一种计时器发出时钟中断祈求，调度程序把此进程终结，把该进程放到队尾。
在该实验中，时间片以 100ms 为单位（实际要小得多）。在调度过程中，需要通过时间函数检测进程执行时间，当该进程执行时间≥时间片大小时，进行调度。
3) 高优先级调度
优先级高进程优先得到 cpu，等该进程执行完毕后，此外进程才干执行。
4) 基于时间片高优先级调度
在调度算法中，只有处在就绪状态进程才干被调度，调度算法结合了优先级调度和时间片轮转调度算法，商定：从最高优先级队列取第1个就绪状态进程进行调度，时间片到后减少其优先级（减少一半），然后插入到低优先级队列尾部，每次调度后，显示进程状态。

四、程序清单
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
//#include <dos.h>
#include <string.h>

//定义进程数
#define LEN 10
//定义最高优先级
#define MAXPIOR 3
// 定义时间片
#define QUANTUM 2
#define PCB sizeof(struct pcb)

struct pcb //PCB
{int ident;//标记符
int state;//状态 0-就绪，1－运营，2－堵塞
int pior;//优先级,MAXPIOR为最高优先级*/
int life;//生命期*/
struct pcb *next;/*指针*/
} *array[MAXPIOR];

static int idlist[LEN];/*标记符表*/
int life=0;/*总生命期初始化为0*/
char str[20];
char command[7][10];
int killtest=0;
void init();
int create();
void kill(int x);
void process();
void routine();
void ps();

void init()
{
int i=0;
for (i=0;i<MAXPIOR;i++)
array[i]=NULL;
sprintf(command[0],"quit");
sprintf(command[1],"ps");
sprintf(command[2],"create");
sprintf(command[3],"kill");
sprintf(command[4],"round");
sprintf(command[5],"sleep")；
sprintf(command[6],"awake");
}

int create()
{
int i=0,pior=0;
struct pcb *p,*q,*s;
while (idlist[i]!=0&&i<=LEN-1)
i++;
if (i==LEN) return -1;
idlist[i]=1;
srand((unsigned)time(NULL))；
pior=rand()%MAXPIOR； //最大优先级设定为0－2整数
//printf("pior=%d\n",pior);
s=(struct pcb *)malloc(PCB);//create a node to keep the process messege
s->ident=i;
s->state=0;
s->pior=pior;
s->life=1+rand()%20;//进程有生命期假设为1－20
s->next=NULL;
life=life+(s->life);

p=array[pior];//建立同优先级队列（链表）
if (p==NULL)
array[pior]=s;
else
{
while(p!=NULL)
{
q=p;
p=p->next;
}
q->next=s;
}
printf("success create process id=%d，current process state disp below:\n",s->ident);
ps();
//printf("end display\n");
return 1;
}

void ps()
{int i=0;
struct pcb *p;
for (i=0;i<MAXPIOR;i++)
{p=array[i];
whil