山东大学大二下学期操作系统实验报告

操作系统实验报告 计算机科学与技术学院 计算机科学与技术专业 2012级X班 目录 一、 进程控制实验 3 1.1 实验目的 3 1.2示例实验 3 1.2.1实验内容 3 1.3独立实验 4 1.3.1实验内容 4 1.3.2实验步骤 4 1.3.3实验演示结果 7 1.3.4实验代码 7 二、进程调度算法实验 9 2.1 实验目的 9 2.2示例实验 10 2.2.1实验内容 10 2.2.2实验演示结果 10 2.3独立实验 11 2.3.1实验内容 11 2.3.2实验步骤 12 2.3.3实验演示结果 14 2.3.4实验代码 14 二、 进程同步实验 16 3.1 实验目的 16 3.2示例实验 16 3.2.1实验内容 16 3.2.2实验演示结果 17 3.3独立实验 17 3.3.1实验内容 17 3.3.2实验步骤 18 3.3.3实验演示结果 21 3.3.4实验代码 21 三、 内存页面置换算法实验 31 4.1 实验目的 31 4.2示例实验 31 4.2.1实验内容 31 4.2.2实验演示结果 32 4.3独立实验 32 4.3.1实验内容 32 4.3.2实验步骤 33 4.3.3实验演示结果 35 4.3.4实验代码 37 四、 磁盘移臂调度算法实验 48 5.1 实验目的 48 5.2示例实验 49 5.2.1实验内容 49 5.2.2实验演示结果 50 5.3独立实验 50 5.3.1实验内容 50 5.3.2实验步骤 51 5.3.3实验演示结果 54 5.3.4实验代码 54 一、 进程控制实验 1.1 实验目的 加深对于进程并发执行概念的理解。实践并发进程的创建和控制方法。观察和体验进程的动态特性。进一步理解进程生命期期间创建、变换、撤销状态变换的过程。掌握进程控制的方法，了解父子进程间的控制和协作关系。练习 Linux 系统中进程创建与控制有关的系统调用的编程和调试技术。

1.2示例实验 1.2.1实验内容 以下实验示例程序应实现一个类似shell 子命令的功能,它可以从执行程序中启动另一个新的子进程并执行一个新的命令和其并发执行。1.2.2实验演示结果 1.3独立实验 1.3.1实验内容 参考以上示例程序中建立并发进程的方法，编写一个父子协作进程，父进程创建一个子进程并控制它每隔 3 秒显示一次当前目录中的文件名列表。

1.3.2实验步骤  1.3.2.1算法设计 通过进程间的通讯，先创建一个父进程一个子进程，父进程沉睡3秒，子进程作为当前父进程再次创建一个他的子进程，当前子进程执行显示当前目录文件列表功能，执行execve()方法后死亡。While(1) 在死循环里无限进行当前操作。即达到父进程创建一个子进程并控制它每隔3秒显示一次当前目录中的文件名列表的要求。

1.3.2.2开发调试过程 打开一终端命令行窗体，新建一个文件夹，在该文件夹中建立名为pctrl.c的C语言程序；

再建立以下名为 pctrl.h 的 C 语言头文件；

建立项目管理文件 Makefile；

输入 make 命令编译连接生成可执行的 pctl 程序；

执行 pctl 程序；

再次执行带有子进程指定执行命令的 pctl 程序。

1.3.2.3思考与分析 1．反映的进程的特征和功能,在真实的操作系统中是怎样实现和反映出教材中讲解的进程的生命期、进程的实体和进程状态控制的。对于进程概念和并发概念有哪些新的理解和认识？子进程是如何创建和执行新程序的？ 答：进程是一个可并发执行的程序在某数据集上的一次运行，是程序的一次运行过程。而程序只是进程的一个组成部分，进程是程序的执行过程。程序是静态的指令集合，而进程是动态的过程实体，是动态的产生、发展和消失。

此外所谓的进程并发执行是在宏观上并发，而在微观上交替执行。每个进程都用一个唯一的整数形式的进程标识符来标识，通过fork()系统调用，可创建新进程。新进程通过复制原来进程的地址空间而成。这种机制允许父子进程方便的进行通信。

系统调用fork(),得到的子进程实际上是父进程的克隆体，要执行不同的新程序要使用系统调用exec(),以用新程序来取代进程的内存空间。其功能是根据参数指定的文件名找到程序文件，把它装入内存，覆盖原来进程的映像，形成一个不同于父进程的子进程。除了进程映像被更换之外，新进程的PID及其他PCB属性均保持不变，实际上是一个新进程“借壳”原来子进程开始运行。父进程可通过系统调用waitpid()来把自己移出就绪队列来等待子进程的终止。

2．信号的机理是什么？怎样利用信号实现进程控制？ 每个信号对应一个正整数常量（为signal number。定义在系统头文件<signal.h>中），代表同一用户的诸进程之间传送事先约定的信息的类型，用于通知某进程发生了某异常事件。每个进程运行时，要通过信号机制来检查是否有信号到达。若有，中断正在执行的程序，转向该信号相对应的处理程序，已完成对事件的处理；
处理结束后再返回到原来的断点继续执行。

1.3.3实验演示结果 1.3.4实验代码 pctl.c文件：
#include “pctl.h“ int main() { int pid_1,pid_2; //存放子进程号 int status_1,status_2; //存放子进程返回状态 while(1){ pid_1=fork() ; if(pid_1<0) // 建立子进程失败? { printf(“Create Process fail!＼n“); exit(EXIT_FAILURE); } if(pid_1 == 0) // 子进程执行代码段 { //报告父子进程进程号 printf(“I am Child-ls process %d＼nMy father is %d＼n“,getpid(),getppid());/*getpid 返回当前进程的进程号，getppid 返回当前进程父进程的进程号*/ pid_2=fork(); if(pid_2<0)// 建立子进程失败? { printf(“Create Process fail!＼n“); exit(EXIT_FAILURE); } if(pid_2==0) // 子进程执行代码段 {//报告父子进程进程号 printf(“I am Child-ps process %d＼nMy father is %d＼n“,getpid(),getppid()); printf(“%d child will Running: ＼n“,getpid()); /*子进程被键盘中断信号唤醒继续执行*/ status_2=execve(“/bin/ps“,NULL,NULL);//装入并执行新的程序 }else{ printf(“wait for the ps-child end%d＼n“,pid_2); waitpid(pid_2,&status_2,0);//等待子进程2结束 //status 用于保留子进程的退出状态 } printf(“%d child will Running: ＼n“,getpid()); //装入并执行新的程序 char *argv[]={“0“,NULL}; status_1 = execve(“/bin/ls“,argv,NULL); } else{ printf(“I am Parent process %d＼n“,getpid()); printf(“wait for the ls-child end %d＼n“,pid_1); waitpid(pid_1,&status_1,0); printf(“child end,sleep...＼n“); sleep(3);// sleep 函数会令调用进程的执行挂起睡眠3秒 } } return EXIT_SUCCESS; } pctl.h文件：
#include <sys/types.h> #include <wait.h> #include <unistd.h> #include <signal.h> #include <stdio.h> #include <stdlib.h> //进程自定义的键盘中断信号处理函数 typedef void (*sighandler_t) (int); void sigcat(){ printf(“%d Process continue＼n“,getpid()); } 二、进程调度算法实验 2.1 实验目的 加深对进程调度概念的理解，体验进程调度机制的功能，了解 Linux 系统中进程调度策略的使用方法。

练习进程调度算法的编程和调试技术。

2.2示例实验 2.2.1实验内容 以下示例实验程序要测试在 linux 系统中不同调度策略和不同优先数的调度效果。

2.2.2实验演示结果 2.3独立实验 2.3.1实验内容 设有两个并发执行的父子进程，不断循环输出各自进程号、优先数和调度策 略。进程初始调度策略均为系统默认策略和默认优先级。当某个进程收到 SIGINT 信号时会自动将其优先数加 1，收到 SIGCSTP 信号时会自动将其优先数减 1。请编 程实现以上功能。

2.3.2实验步骤 2.3.2.1算法设计 建立一个父进程和一个子进程。通过第一章学习的进程控制相互发送信号。当按下 Ctrl+C 时，父进程实现优先级加 1。当按下Ctrl+Z 时，子进程实现优先级减1。

用 signal 系统调用将父进程注册一个本进程处理 SIGINT 的实现优先级加 1 的函数。子进程注册一个本进程处理SIGTSTP 的实现优先级减 1 的函数。当按下 Ctrl+Z 时，子进程做出响应，其优先级减 1；
当按下Ctrl+C 时，父进程做出响应，父进程优先级加 1.然后再输出各自进程号、优先数和调度策略。以上行为通过 for（）语句循环。

2.3.2.2开发调试过程 新建一个文件夹，在该文件夹中建立以下名为 pctl.c 的 C 语言程序。

再建立以下名为pctl.h的 C 语言头文件。

建立项目管理文件 Makefile 。

输入 make 命令编译连接生成可执行的pctl程序 。

执行并调试 pctl程序 2.3.2.3思考与分析 进程调度调度策略和功能如下所示: SCHED_OTHER 默认的分时调度策略(值等于 0) SCHED_FIFO 先进先先出调度策略(值等于 1) SCHED_RR 时间片轮转调度策略(值等于 2) 进程调度本质就是让谁先执行，让谁后执行。在真实的操作系统中，由调度策略和优先级决定谁先执行。Linux 的调度策略有三种，SCHED_OTHER 分时调度，SCHED_FIFO 先进先出，SCHED_RR 时间片轮转。后两种专用于对响应时间有特殊要求的进程，并且会抢先于 SCHED_OTHER 调度策略的进程而执行。通过这个系统调用设置进程调度策略，intsched_setscheduler(pid_t pid,int policy,const struct sched_param *sp); 其中 pid 是进程号，policy 是以上说明的 3 种调度策略之一，sp 调度参数结构指针,调度参数结构主要存有调度优先数。进程优先数(prio)由静态优先级和动态优先级两部分组成。静态优先级与调度策略有关。动态优先级由以下系统调用设置，int setpriority(int which,int who,int prio);which 设置的对象。可以是：
进程 PRIO_PROCESS 进程组 PRIO_PGRP 用户 PRIO_USER who 对应设置对象的进程号或组号或用户号 prio 要设置的进程优先数 2.3.3实验演示结果 2.3.4实验代码 psched.c文件：
#include<stdio.h> #include<stdlib.h> #include<signal.h> #include <sys/resource.h> #define SIGINT 2 #define SIGTSTP 20 void handler_sigint(int signo) { //用于提升优先数 printf(“＼n%d 进程优先数增加 1＼n“,getpid()); setpriority(PRIO_PROCESS, getpid(), getpriority(PRIO_PROCESS,getpid()) + 1); } void handler_sigtstp(int signo) { //用于降低优先数 printf(“＼n%d 进程优先数减小 1＼n“,getpid()); setpriority(PRIO_PROCESS, getpid(), getpriority(PRIO_PROCESS,getpid()) - 1); } int main() { pid_t pid; if((pid = fork()) < 0 ){ perror(“process create error!“); } if(pid > 0) { signal(SIGINT, handler_sigint); //父进程处理 Ctrl+C signal(SIGTSTP, SIG_IGN); //忽略 Ctrl+Z }else{ setpriority(PRIO_PROCESS, getpid(), 10); //设定子进程初始动态优先级为 10,否则看不出效果 signal(SIGTSTP, handler_sigtstp); //子进程处理Ctrl+Z signal(SIGINT, SIG_IGN); //忽略 Ctrl+C } int i=1; while(i<=20) { if(pid > 0) { printf(“I＇m parent process, “); }else{ printf(“I＇m child process, “); } printf(“pid = %d, priority = %d, scheduler = %d＼n“, getpid(), getpriority(PRIO_PROCESS, getpid()),sched_getscheduler(getpid())); sleep(3); i++; } } 其他文件同示例实验。

二、 进程同步实验 3.1 实验目的 加深对并发协作进程同步与互斥概念的理解，观察和体验并发进程同步与互斥操作的效果，分析与研究经典进程同步与互斥问题的实际解决方案。了解 Linux 系统中 IPC 进程同步工具的用法，练习并发协作进程的同步与互斥操作的编程与调试技术。

3.2示例实验 3.2.1实验内容 以下示例实验程序应能模拟多个生产/消费者在有界缓冲上正确的操作。它利用 N 个字节的共享内存作为有界循环缓冲区，利用写一字符模拟放一个产品，利用读一字符模拟消费一个产品。当缓冲区空时消费者应阻塞睡眠，而当缓冲区满时生产者应当阻塞睡眠。一旦缓冲区中有空单元，生产者进程就向空单元中入写字符,并报告写的内容和位置。一旦缓冲区中有未读过的字符，消费者进程就从该单元中读出字符，并报告读取位置。生产者不能向同一单元中连续写两次以上相同的字符，消费者也不能从同一单元中连续读两次以上相同的字符。

3.2.2实验演示结果 3.3独立实验 3.3.1实验内容 抽烟者问题。假设一个系统中有三个抽烟者进程，每个抽烟者不断地卷烟并抽烟。抽烟者卷起并抽掉一颗烟需要有三种材料：烟草、纸和胶水。一个抽烟者有烟草，一个有纸，另一个有胶水。系统中还有两个供应者进程，它们无限地供应所有三种材料，但每次仅轮流提供三种材料中的两种。得到缺失的两种材料的抽烟者在卷起并抽掉一颗烟后会发信号通知供应者，让它继续提供另外的两种材料。这一过程重复进行。

请用以上介绍的 IPC 同步机制编程，实现该问题要求的功能。

3.3.2实验步骤 3.3.2.1问题分析 有两个供应者，有三个消费者。用于存放烟草，纸和胶水的公共缓冲区的大小是 3.存放顺序要指定。分别是烟草，纸和胶水。每一个供应者供应的物品有三种，（烟草+纸）（烟草+胶水）（纸+胶水）
。三个消费者分别需要三个里面的一种。

约束：
（1）某一时刻，只能有一个供应者，放入一对物品。

（2）
某一时刻， 只能有一个消费者， 且要保证这个消费者恰好需要的就是刚刚生产的物品。

（3）所有供应者提供这种物品之后，不论它要生产什么物品，只有等到消费者拿走了物品之后，才能继续生产。

3.3.2.2算法设计 （1）供应者的上下文完全一样，在程序中 fork（）子进程之后，让父进程和子进程并发执行供应者代码即可。

（2）消费者有三个，且每个消费者需要的物品不同，所以不能使用同一个代码段。这样，就需要建立两个子进程和一个父进程同时并发执行。

然后在各自区域执行相似的但不同的代码段。

（3）用信号灯实现同步和互斥约束。

（4）创建公共缓冲区和指向首地址的指针 //获取缓冲区使用的共享内存，buff_ptr 指向缓冲区首地址 buff_ptr = (char *)set_shm(buff_key,buff_num,shm_flg); //获取供应者放产品首位置指针 pput_ptr pput_ptr = (int *)set_shm(pput_key,pput_num,shm_flg); 3.3.2.3开发调试过程 新建一个文件夹，在该文件夹中建立以下名为 ipc.h 的 C 语言头文件。

再建立以下名为 ipc.c 的 C 语言头文件,实现头文件中申明的函数。

再建立以下名为 producer.c 的 C 语言头文件,实现供应者的功能。

再建立以下名为 consumer.c 的 C 语言头文件,实现消费者的功能。

建立项目管理文件 Makefile 。

输入 make 命令编译连接生成可执行的 producer 和 consumer 程序 。

执行并调试 producer 和 consumer 程序。

3.3.2.4思考与分析 进程之间的同步在该实验中是通过信号灯实现的。

进程之间为了同步而使用的信号灯，必须完全相同的在各自进程中创建。这样，这些信号灯就会被这些进程共享。然后通过执行信号灯的 up（）和 down（）操作.使得进程并发执行时保持同步。因为如果信号灯的值小于 0，那么这个进程会阻塞，这就是为什么能够同步。

操作系统中，进程同步可以通过信号量机制实现。在本实验中，信号灯就是信号量 ，down（）操作就是信号量的 wait 操作，up（）操作就是信号量的 signal 操作。

3.3.3实验演示结果 3.3.4实验代码 ipc.h文件：
#include <stdio.h> #include <stdlib.h> #include <sys/types.h> #include <sys/ipc.h> #include <sys/shm.h> #include <sys/sem.h> #include <sys/msg.h> #define BUFSZ 256 //建立或获取 ipc 的一组函数的原型说明 int get_ipc_id(char *proc_file,key_t key); char *set_shm(key_t shm_key,int shm_num,int shm_flag); int set_msq(key_t msq_key,int msq_flag); int set_sem(key_t sem_key,int sem_val,int sem_flag); int down(int sem_id); int up(int sem_id); typedef union semuns { int val; } Sem_uns; typedef struct msgbuf { long mtype; char mtext[1]; } Msg_buf; //生产消费者共享缓冲区即其有关的变量 key_t buff_key; int buff_num; char *buff_ptr; //生产者放产品位置的共享指针 key_t pput_key; int pput_num; int *pput_ptr; //消费者取产品位置的共享指针 key_t cget_key; int cget_num; int *cget_ptr; //生产者有关的信号量 key_t prod_key; key_t pmtx_key; int prod_sem; int pmtx_sem; //消费者有关的信号量 key_t c_PG_key; key_t c_TP_key; key_t c_TG_key; key_t cmtx_key; int c_PG_sem; int c_TP_sem; int c_TG_sem; int cmtx_sem; int sem_val; int sem_flg; int shm_flg; ipc.c文件：
#include “ipc.h“ int get_ipc_id(char *proc_file,key_t key) { FILE *pf; int i,j; char line[BUFSZ],colum[BUFSZ]; if((pf = fopen(proc_file,“r“)) == NULL){ perror(“Proc file not open“); exit(EXIT_FAILURE); } fgets(line, BUFSZ,pf); while(!feof(pf)){ i = j = 0; fgets(line, BUFSZ,pf); while(line[i] == ＇ ＇) i++; while(line[i] !=＇ ＇) colum[j++] = line[i++]; colum[j] = ＇＼0＇; if(atoi(colum) != key) continue; j=0; while(line[i] == ＇ ＇) i++; while(line[i] !=＇ ＇) colum[j++] = line[i++]; colum[j] = ＇＼0＇; i = atoi(colum); fclose(pf); return i; } fclose(pf); return -1; } int down(int sem_id) { struct sembuf buf; buf.sem_op = -1; buf.sem_num = 0; buf.sem_flg = SEM_UNDO; if((semop(sem_id,&buf,1)) <0) { perror(“down error “); exit(EXIT_FAILURE); } return EXIT_SUCCESS; } int up(int sem_id) { struct sembuf buf; buf.sem_op = 1; buf.sem_num = 0; buf.sem_flg = SEM_UNDO; if((semop(sem_id,&buf,1)) <0) { perror(“up error “); exit(EXIT_FAILURE); } return EXIT_SUCCESS; } int set_sem(key_t sem_key,int sem_val,int sem_flg) { int sem_id; Sem_uns sem_arg; //测试由 sem_key 标识的信号灯数组是否已经建立 if((sem_id = get_ipc_id(“/proc/sysvipc/sem“,sem_key)) < 0 ) { //semget 新建一个信号灯,其标号返回到 sem_id if((sem_id = semget(sem_key,1,sem_flg)) < 0) { perror(“semaphore create error“); exit(EXIT_FAILURE); } //设置信号灯的初值 sem_arg.val = sem_val; if(semctl(sem_id,0,SETVAL,sem_arg) <0) { perror(“semaphore set error“); exit(EXIT_FAILURE); } } return sem_id; } char * set_shm(key_t shm_key,int shm_num,int shm_flg) { int i,shm_id; char * shm_buf; //测试由 shm_key 标识的共享内存区是否已经建立 if((shm_id = get_ipc_id(“/proc/sysvipc/shm“,shm_key)) < 0 ) { //shmget 新建 一个长度为 shm_num 字节的共享内存,其标号返回到 shm_id if((shm_id = shmget(shm_key,shm_num,shm_flg)) <0) { perror(“shareMemory set error“); exit(EXIT_FAILURE); } //shmat 将由 shm_id 标识的共享内存附加给指针 shm_buf if((shm_buf = (char *)shmat(shm_id,0,0)) < (char *)0) { perror(“get shareMemory error“); exit(EXIT_FAILURE); } for(i=0; i<shm_num; i++) shm_buf[i] = 0; //初始为 0 } //shm_key 标识的共享内存区已经建立,将由 shm_id 标识的共享内存附加给指针 shm_buf if((shm_buf = (char *)shmat(shm_id,0,0)) < (char *)0) { perror(“get shareMemory error“); exit(EXIT_FAILURE); } return shm_buf; } int set_msq(key_t msq_key,int msq_flg) { int msq_id; //测试由 msq_key 标识的消息队列是否已经建立 if((msq_id = get_ipc_id(“/proc/sysvipc/msg“,msq_key)) < 0 ) { //msgget 新建一个消息队列,其标号返回到 msq_id if((msq_id = msgget(msq_key,msq_flg)) < 0) { perror(“messageQueue set error“); exit(EXIT_FAILURE); } } return msq_id; } producer.c文件：
#include “ipc.h“ int main(int argc,char *argv[]) { int rate; //可在在命令行第一参数指定一个进程睡眠秒数,以调解进程执行速度 if(argv[1] != NULL) rate = atoi(argv[1]); else rate = 3; //不指定为 3 秒 //共享内存使用的变量 buff_key = 101;//缓冲区任给的键值 buff_num = 3;//缓冲区任给的长度 pput_key = 102;//生产者放产品指针的键值 pput_num = 1; //指针数 shm_flg = IPC_CREAT | 0644;//共享内存读写权限 //获取缓冲区使用的共享内存,buff_ptr 指向缓冲区首地址 buff_ptr = (char *)set_shm(buff_key,buff_num,shm_flg); //获取生产者放产品位置指针 pput_ptr pput_ptr = (int *)set_shm(pput_key,pput_num,shm_flg); //信号量使用的变量 prod_key = 201;//生产者同步信号灯键值 pmtx_key = 202;//生产者互斥信号灯键值 c_PG_key = 301;//消费者同步信号灯键值 c_TP_key = 302;//消费者互斥信号灯键值 c_TG_key = 303;//消费者互斥信号灯键值 sem_flg = IPC_CREAT | 0644; //生产者同步信号灯初值设为缓冲区最大可用量 sem_val = 1; //获取生产者同步信号灯,引用标识存 prod_sem prod_sem = set_sem(prod_key,sem_val,sem_flg); //消费者初始无产品可取,同步信号灯初值设为 0 sem_val = 0; //获取消费者同步信号灯,引用标识存 cons_sem c_PG_sem = set_sem(c_PG_key,sem_val,sem_flg); c_TP_sem = set_sem(c_TP_key,sem_val,sem_flg); c_TG_sem = set_sem(c_TG_key,sem_val,sem_flg); //生产者互斥信号灯初值为 1 sem_val = 1; //获取生产者互斥信号灯,引用标识存 pmtx_sem pmtx_sem = set_sem(pmtx_key,sem_val,sem_flg); //循环执行模拟生产者不断放产品 int pid; int i; pid = fork(); if(pid == 0) { while(1){ int r = rand() % 3; if(r == 0) { down(prod_sem); //如果另一生产者正在放产品,本生产者阻塞 down(pmtx_sem); //用写一字符的形式模拟生产者放产品 ,报告本进程号和放入的字符及存放的位置 buff_ptr[*pput_ptr + 1] = ＇P＇; buff_ptr[*pput_ptr + 2] = ＇G＇; sleep(rate); printf(“%d 供 应 商 提 供 : 纸 %c, 胶 水 %c＼n“,getpid(),buff_ptr[*pput_ptr +1] ,buff_ptr[*pput_ptr + 2]); //唤醒阻塞的生产者 up(pmtx_sem); //唤醒阻塞的消费者 up(c_PG_sem); } else if(r == 1) { down(prod_sem); //如果另一生产者正在放产品,本生产者阻塞 down(pmtx_sem); //用写一字符的形式模拟生产者放产品 ,报告本进程号和放入的字符及存放的位置 buff_ptr[*pput_ptr] = ＇T＇; buff_ptr[*pput_ptr + 2] = ＇G＇; sleep(rate); printf(“%d供应商提供:烟草%c,胶水%c＼n“,getpid(),buff_ptr[*pput_ptr] ,buff_ptr[*pput_ptr + 2]); //唤醒阻塞的生产者 up(pmtx_sem); //唤醒阻塞的消费者 up(c_TG_sem); } else if(r == 2) { down(prod_sem); //如果另一生产者正在放产品,本生产者阻塞 down(pmtx_sem); //用写一字符的形式模拟生产者放产品 ,报告本进程号和放入的字符及存放的位置 buff_ptr[*pput_ptr + 1] = ＇P＇; buff_ptr[*pput_ptr] = ＇T＇; sleep(rate); printf(“%d供应商提供:烟草%c,纸%c＼n“,getpid(),buff_ptr[*pput_ptr] ,buff_ptr[*pput_ptr + 1]); //唤醒阻塞的生产者 up(pmtx_sem); //唤醒阻塞的消费者 up(c_TP_sem); } } } else { while(1){ int r = rand() % 3; if(r == 0) { down(prod_sem); //如果另一生产者正在放产品,本生产者阻塞 down(pmtx_sem); //用写一字符的形式模拟生产者放产品 ,报告本进程号和放入的字符及存放的位置 buff_ptr[*pput_ptr + 1] = ＇P＇; buff_ptr[*pput_ptr + 2] = ＇G＇; sleep(rate); printf(“%d 供 应 商 提 供 : 纸 %c, 胶 水 %c＼n“,getpid(),buff_ptr[*pput_ptr + 1] ,buff_ptr[*pput_ptr + 2]); //唤醒阻塞的生产者 up(pmtx_sem); //唤醒阻塞的消费者 up(c_PG_sem); } else if(r == 1) { down(prod_sem); //如果另一生产者正在放产品,本生产者阻塞 down(pmtx_sem); //用写一字符的形式模拟生产者放产品 ,报告本进程号和放入的字符及存放的位置 buff_ptr[*pput_ptr] = ＇T＇; buff_ptr[*pput_ptr + 2] = ＇G＇; sleep(rate); printf(“%d供应商提供:烟草%c,胶水%c＼n“,getpid(),buff_ptr[*pput_ptr] ,buff_ptr[*pput_ptr + 2]); //唤醒阻塞的生产者 up(pmtx_sem); //唤醒阻塞的消费者 up(c_TG_sem); } else if(r == 2) { down(prod_sem); //如果另一生产者正在放产品,本生产者阻塞 down(pmtx_sem); //用写一字符的形式模拟生产者放产品 ,报告本进程号和放入的字符及存放的位置 buff_ptr[*pput_ptr + 1] = ＇P＇; buff_ptr[*pput_ptr] = ＇T＇; sleep(rate); printf(“%d供应商提供:烟草%c,纸%c＼n“,getpid(),buff_ptr[*pput_ptr] ,buff_ptr[*pput_ptr + 1]); //唤醒阻塞的生产者 up(pmtx_sem); //唤醒阻塞的消费者 up(c_TP_sem); } } } return EXIT_SUCCESS; } consumer.c文件：
#include “ipc.h“ int main(int argc,char *argv[]) { int rate; //可在在命令行第一参数指定一个进程睡眠秒数,以调解进程执行速度 if(argv[1] != NULL) rate = atoi(argv[1]); else rate = 3; //不指定为 3 秒 //共享内存 使用的变量 buff_key = 101; //缓冲区任给的键值 buff_num = 3; //缓冲区任给的长度 cget_key = 103; //消费者取产品指针的键值 cget_num = 1; //指针数 shm_flg = IPC_CREAT | 0644; //共享内存读写权限 //获取缓冲区使用的共享内存,buff_ptr 指向缓冲区首地址 buff_ptr = (char *)set_shm(buff_key,buff_num,shm_flg); //获取消费者取产品指针,cget_ptr 指向索引地址 cget_ptr = (int *)set_shm(cget_key,cget_num,shm_flg); //信号量使用的变量 prod_key = 201; //生产者同步信号灯键值 cmtx_key = 203; //生产者互斥信号灯键值 c_PG_key = 301;//消费者同步信号灯键值 c_TP_key = 302;//消费者互斥信号灯键值 c_TG_key = 303;//消费者互斥信号灯键值 sem_flg = IPC_CREAT | 0644; //信号灯操作权限 //生产者同步信号灯初值设为缓冲区最大可用量 sem_val = 1; //获取生产者同步信号灯,引用标识存 prod_sem prod_sem = set_sem(prod_key,sem_val,sem_flg); //消费者初始无产品可取,同步信号灯初值设为 0 sem_val = 0; //获取消费者同步信号灯,引用标识存 cons_sem c_PG_sem = set_sem(c_PG_key,sem_val,sem_flg); c_TP_sem = set_sem(c_TP_key,sem_val,sem_flg); c_TG_sem = set_sem(c_TG_key,sem_val,sem_flg); //消费者互斥信号灯初值为 1 sem_val = 1; //获取消费者互斥信号灯,引用标识存 pmtx_sem cmtx_sem = set_sem(cmtx_key,sem_val,sem_flg); int pid1, pid2; pid1 = fork(); if(pid1 == 0) { //循环执行模拟消费者不断取产品 while(1){ //如果无产品消费者阻塞 down(c_PG_sem); //如果另一消费者正在取产品,本消费者阻塞 down(cmtx_sem); //用读一字符的形式模拟消费者取产品,报告本进程号和获取的字符及读取的位置 sleep(rate); printf(“%d 吸烟者有烟草 T,得到纸%c 和胶水%c,开始吸烟......＼n“, getpid(),buff_ptr[*cget_ptr + 1],buff_ptr[*cget_ptr + 2]); //唤醒阻塞的消费者 up(cmtx_sem); //唤醒阻塞的生产者 up(prod_sem); } } else { pid2 = fork(); if(pid2 == 0) { //循环执行模拟消费者不断取产品 while(1){ //如果无产品消费者阻塞 down(c_TP_sem); //如果另一消费者正在取产品,本消费者阻塞 down(cmtx_sem); //用读一字符的形式模拟消费者取产品 ,报告本进程号和获取的字符及读取的位置 sleep(rate); printf(“%d 吸烟者有胶水 G,得到纸%c 和烟草%c,开始吸烟......＼n“, getpid(),buff_ptr[*cget_ptr + 1],buff_ptr[*cget_ptr]); //唤醒阻塞的消费者 up(cmtx_sem); //唤醒阻塞的生产者 up(prod_sem); } } else { //循环执行模拟消费者不断取产品 while(1){ //如果无产品消费者阻塞 down(c_TG_sem); //如果另一消费者正在取产品,本消费者阻塞 down(cmtx_sem); //用读一字符的形式模拟消费者取产品 ,报告本进程号和获取的字符及读取的位置 sleep(rate); printf(“%d 吸烟者有纸 P,得到胶水%c 和烟草%c,开始吸烟......＼n“, getpid(),buff_ptr[*cget_ptr + 2],buff_ptr[*cget_ptr]); //唤醒阻塞的消费者 up(cmtx_sem); //唤醒阻塞的生产者 up(prod_sem); } } } return EXIT_SUCCESS; } 三、 内存页面置换算法实验 4.1 实验目的 加深对于存储管理的了解，掌握虚拟存储器的实现原理；
观察和了解重要的页面置换算法和置换过程。练习模拟算法的编程技巧，锻炼分析试验数据的能力。

4.2示例实验 4.2.1实验内容 1.示例实验程序中模拟两种置换算法：LRU 算法和 FIFO 算法 2.能对两种算法给定任意序列不同的页面引用串和任意帧实内存块数的组合测试，显示页置换的过程。

3.能统计和报告不同置换算法情况下依次淘汰的页号、缺页次数（页错误数）和缺页率。比较两种置换算法在给定条件下的优劣。

4.为了能方便的扩充页面置换算法，更好的描述置换过程，示例实验程采用了 C++语言用 Replace 类描述了置换算法及其属性。

4.2.2实验演示结果 4.3独立实验 4.3.1实验内容 请在以上示例实验程序中补充“增强二次机会”等置换算法的模拟程序。输入不同的内存页面引用串和实存帧数，观察并分析其页面置换效果和性能，并将其与 LRU和 FIFO 算法进行比较。改进以上示例实验程序，使之能够随机的产生内存页面引用串，以便能动态的观测各种置换算法的性能。

4.3.2实验步骤 4.3.2.1算法设计 Clock（）算法：
FIFO算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：检查最老页面的R位，如果R位为0，那么这个页面既老又没有被使用过，可以立刻被置换掉，如果R位为1，就将R位清0，并将这个页面重新插入链表尾端，然后继续搜索。第二次机会算法是寻找一个最近时间间隔内未被访问过的页面，如果所有的页面都被访问过了，这个算法就是纯粹的FIFO算法。

EClock（）算法：
需将内存中的页面按访问位A和修改位M分为4类: 第一类（A=0，M=0）未被访问，又未被修改，是最佳替换页 第二类（A=0，M=1）未被访问，但被修改过，次佳替换页 第三类（A=1，M=0）被访问过，但未被修改，可能再被访问 第四类（A=1，M=1）以访问且被修改，可能再被访问 程序首先查找第一类页面，如果有则替换，如果没有则查找第二类页面；
置页面的访问位为0，如果有则替换，如果没有则返回重新查找第一类页面；
如果有则替换，如果没有则查找第二类页面，则一定存在。该算法适用于某些页面经常被修改的场合。

LFU（）算法：
即最不经常使用页置换算法，要求在页置换时置换引用计数最小的页，因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多，但以后就不再使用，这类页将会长时间留在内存中，因此可以将引用计数寄存器定时右移一位，形成指数衰减的平均使用次数。

MFU算法：
与LFU算法相反，为最经常使用页置换算法。认为引用次数最小的页以后可能会经常使用。

4.3.2.2开发调试过程 建立vmrp.cc程序，将代码写到程序中；
  再建立名为vmrp.h的C语言头文件；

建立以下项目管理文件Makefile；

输入make命令编译连接生成可执行的vmrp程序；

执行程序。

4.3.2.3思考与分析 4.3.3实验演示结果 4.3.4实验代码 vmrp.cc文件：
#include “vmrp.h“ #include <iostream> #include <cstdlib> using namespace std; Replace::Replace() { int i; //设定总得访问页数,并分配相应的引用页号和淘汰页号记录数组空间 cout << “Please input page numbers :“ ; cin >> PageNumber; ReferencePage = new int[sizeof(int) * PageNumber]; EliminatePage = new int[sizeof(int) * PageNumber]; //输入引用页号序列(页面走向),初始化引用页数组 cout << “Please input reference page string :“; for (i = 0; i < PageNumber; i++) cin >> ReferencePage[i];//引用页暂存引用数组 //设定内存实页数(帧数),并分配相应的实页号记录数组空间(页号栈) cout << “Please input page frames :“; cin >> FrameNumber; PageFrames = new int[sizeof(int) * FrameNumber]; } Replace::~Replace() { } void Replace::InitSpace(char * MethodName) { int i; cout << endl << MethodName << endl; FaultNumber=0; //引用还未开始,-1 表示无引用页 for (i = 0; i < PageNumber; i++) EliminatePage[i] = -1; for(i = 0; i < FrameNumber; i++) PageFrames[i] = -1; } //分析统计选择的算法对于当前输入的页面走向的性能 void Replace::Report(void) { //报告淘汰页顺序 cout << endl << “Eliminate page:“; for(int i=0; EliminatePage[i]!=-1; i++) cout << EliminatePage[i] << “ “; //报告缺页数和缺页率 cout << endl << “Number of page faults = “ << FaultNumber << endl; cout << setw(6) << setprecision(3) ; cout << “Rate of page faults = “ << 100*(float)FaultNumber/(float)PageNumber << “%“ <<endl; } //最近最旧未用置换算法 void Replace::Lru(void) { int i,j,k,l,next; InitSpace(“LRU“); //循环装入引用页 for(k=0,l=0; k < PageNumber; k++) { next=ReferencePage[k]; //检测引用页当前是否已在实存 for (i=0; i<FrameNumber; i++) { if(next == PageFrames[i]) { //引用页已在实存将其调整到页记录栈顶 next= PageFrames[i]; for(j=i;j>0;j--) PageFrames[j] = PageFrames[j-1]; PageFrames[0]=next; break; } } if(PageFrames[0] == next) { //如果引用页已放栈顶,则为不缺页,报告当前内存页号 for(j=0; j<FrameNumber; j++) if(PageFrames[j]>=0) cout << PageFrames[j] << “ “; cout << endl; continue; //继续装入下一页 } else // 如果引用页还未放栈顶,则为缺页,缺页数加 1 FaultNumber++; //栈底页号记入淘汰页数组中 EliminatePage[l] = PageFrames[FrameNumber-1]; //向下压栈 for(j=FrameNumber-1;j>0;j--) PageFrames[j]= PageFrames[j-1]; PageFrames[0]=next; //引用页放栈顶 //报告当前实存中页号 for(j=0; j<FrameNumber; j++) if(PageFrames[j]>=0) cout << PageFrames[j] << “ “; //报告当前淘汰的页号 if(EliminatePage[l]>=0) cout << “->“ << EliminatePage[l++] << endl; else cout << endl; } //分析统计选择的算法对于当前引用的页面走向的性能 Report(); } //先进先出置换算法 void Replace::Fifo(void) { int i,j,k,l,next; InitSpace(“FIFO“); //循环装入引用页 for(k=0,j=l=0; k < PageNumber; k++) { next=ReferencePage[k]; //如果引用页已在实存中,报告实存页号 for (i=0; i<FrameNumber; i++) if(next==PageFrames[i]) break; if (i<FrameNumber) { for(i=0; i<FrameNumber; i++) cout << PageFrames[i] << “ “; cout << endl; continue; // 继续引用下一页 } //引用页不在实存中,缺页数加 1 FaultNumber++; EliminatePage[l]= PageFrames[j]; //最先入页号记入淘汰页数组 PageFrames[j]=next; //引用页号放最先入页号处 j = (j+1)%FrameNumber; //最先入页号循环下移 //报告当前实存页号和淘汰页号 for(i=0; i<FrameNumber; i++) if(PageFrames[i]>=0) cout << PageFrames[i] << “ “; if(EliminatePage[l]>=0) cout << “->“ << EliminatePage[l++] << endl; else cout << endl; } //分析统计选择的算法对于当前引用的页面走向的性能 Report(); } void Replace::Clock(void) { int i,j,k,l,next; InitSpace(“Clock“); //循环装入引用页 int flag[100]; for(i=0;i<FrameNumber;i++) flag[i]=0;//初始位为0 for(k=0,j=l=0;k<PageNumber;k++) { next=ReferencePage[k]; //如果引用页已在实存中,报告实存页号 for(i=0;i<FrameNumber;i++) if(next==PageFrames[i]) break; if(i<FrameNumber) { flag[i]=1; for(i=0;i<FrameNumber;i++) cout<<PageFrames[i]<< “ “; cout<<endl; continue;// 继续引用下一页 } //引用页不在实存中,缺页数加 1 FaultNumber++; int a; for(a=0;a<FrameNumber;a++) if(PageFrames[a]==-1)//还有空余帧，直接放入 { PageFrames[a]=next; break; } if(a!=FrameNumber) { flag[a]=1; for(i=0;i<=a;i++) cout<<PageFrames[i]<<“ “; cout<<endl; continue; } int jj=0; for(j=0;j<FrameNumber;j++) if(flag[j]==0) { jj=j; break; } else { flag[j]=0; } if(j==FrameNumber) jj=0; flag[jj]=1; EliminatePage[l]=PageFrames[jj]; //最先入页号记入淘汰页数组 PageFrames[jj]=next; //引用页号放最先入页号处 //报告当前实存页号和淘汰页号 for(i=0;i<FrameNumber;i++) if(PageFrames[i]>=0) cout << PageFrames[i] << “ “; if(EliminatePage[l]>=0) cout << “->“ << EliminatePage[l++] << endl; else cout << endl; } //分析统计选择的算法对于当前引用的页面走向的性能 Report(); } void Replace::Eclock (void) { int i,j,k,l,next; InitSpace(“Eclock“); //循环装入引用页 int flag[2][100]; for(j=0;j<2;j++) for(i=0;i<FrameNumber;i++) flag[j][i]=0; for(k=0,j=l=0;k<PageNumber;k++) { next=ReferencePage[k]; //如果引用页已在实存中,报告实存页号 for(i=0;i<FrameNumber;i++) if(next==PageFrames[i]) break; if(i<FrameNumber) { flag[0][i]=1;//最近使用访问位 flag[1][i]=0;//修改访问位 for(int kk=0;kk<FrameNumber;kk++) if(kk!=i) { flag[0][i]=0; } for(i=0;i<FrameNumber;i++) cout<<PageFrames[i]<< “ “; cout<<endl; continue;// 继续引用下一页 } //引用页不在实存中,缺页数加 1 FaultNumber++; int a; for(a=0;a<FrameNumber;a++) if(PageFrames[a]==-1) { PageFrames[a]=next; break; } if(a!=FrameNumber) { flag[0][a]=1; flag[0][a]=0; for(i=0;i<=a;i++) cout<<PageFrames[i]<<“ “; cout<<endl; continue; } int jj=0,jjj=0,flagg=0; for(j=0;j<FrameNumber;j++) if((flag[0][j]<jj)||(flag[0][j]==jj&&flag[1][j]<jjj)) { flagg=j; jj=flag[0][j]; jjj=flag[1][j]; } jj=flagg; EliminatePage[l]=PageFrames[jj]; //最先入页号记入淘汰页数组 PageFrames[jj]=next; //引用页号放最先入页号处 //报告当前实存页号和淘汰页号 flag[0][jj]=1; flag[1][jj]=1; for(int kk=0;kk<FrameNumber;kk++) if(kk!=jj) { flag[0][i]=0; } for(i=0;i<FrameNumber;i++) if(PageFrames[i]>=0) cout << PageFrames[i] << “ “; if(EliminatePage[l]>=0) cout << “->“ << EliminatePage[l++] << endl; else cout << endl; } //分析统计选择的算法对于当前引用的页面走向的性能 Report(); } void Replace::Lfu(void) { int i,j,k,l,next; InitSpace(“Lfu“); //循环装入引用页 int flag[100]; for(i=0;i<FrameNumber;i++) flag[i]=0; for(k=0,j=l=0;k<PageNumber;k++) { next=ReferencePage[k]; //如果引用页已在实存中,报告实存页号 for(i=0;i<FrameNumber;i++) if(next==PageFrames[i]) break; if(i<FrameNumber) { flag[i]++; for(i=0;i<FrameNumber;i++) cout<<PageFrames[i]<< “ “; cout<<endl; continue;// 继续引用下一页 } //引用页不在实存中,缺页数加 1 FaultNumber++; int a=20,jj; for(a=0;a<FrameNumber;a++) if(PageFrames[a]==-1) { PageFrames[a]=next; break; } if(a!=FrameNumber) { for(i=0;i<=a;i++) cout<<PageFrames[i]<<“ “; cout<<endl; continue; } a=20; for(j=0;j<FrameNumber;j++) if(flag[j]<a) { a=flag[j]; jj=j; } flag[jj]=1; EliminatePage[l]=PageFrames[jj]; //最先入页号记入淘汰页数组 PageFrames[jj]=next; //引用页号放最先入页号处 //报告当前实存页号和淘汰页号 for(i=0;i<FrameNumber;i++) if(PageFrames[i]>=0) cout << PageFrames[i] << “ “; if(EliminatePage[l]>=0) cout << “->“ << EliminatePage[l++] << endl; else cout << endl; } //分析统计选择的算法对于当前引用的页面走向的性能 Report(); } void Replace::Mfu(void) { int i,j,k,l,next; InitSpace(“Mfu“); //循环装入引用页 int flag[100]; for(i=0;i<FrameNumber;i++) flag[i]=0; for(k=0,j=l=0;k<PageNumber;k++) { next=ReferencePage[k]; //如果引用页已在实存中,报告实存页号 for(i=0;i<FrameNumber;i++) if(next==PageFrames[i]) break; //cout<<“i:“<<i<<“ “<<FrameNumber<<endl; if(i<FrameNumber) { flag[i]++; for(i=0;i<FrameNumber;i++) cout<<PageFrames[i]<< “ “; cout<<endl; continue;// 继续引用下一页 } //引用页不在实存中,缺页数加 1 FaultNumber++; int a=-1,jj; for(a=0;a<FrameNumber;a++) if(PageFrames[a]==-1) { PageFrames[a]=next; break; } if(a!=FrameNumber) { for(i=0;i<=a;i++) cout<<PageFrames[i]<<“ “; cout<<endl; continue; } a=-1; for(j=0;j<FrameNumber;j++) if(flag[j]>a) { a=flag[j]; jj=j; } flag[jj]=1; EliminatePage[l]=PageFrames[jj]; //最先入页号记入淘汰页数组 PageFrames[jj]=next; //引用页号放最先入页号处 //报告当前实存页号和淘汰页号 for(i=0;i<FrameNumber;i++) if(PageFrames[i]>=0) cout << PageFrames[i] << “ “; if(EliminatePage[l]>=0) cout << “->“ << EliminatePage[l++] << endl; else cout << endl; } //分析统计选择的算法对于当前引用的页面走向的性能 Report(); } int main(int argc,char *argv[]) { Replace * vmpr = new Replace(); vmpr->Lru(); vmpr->Fifo(); vmpr->Clock(); vmpr->Eclock(); vmpr->Lfu(); vmpr->Mfu(); return 0; } vmrp.h文件：
#include <iostream> #include <iomanip> #include <malloc.h> class Replace { public: Replace(); ~Replace(); void InitSpace(char * MethodName); //初始化页号记录 void Report(void); // 报告算法执行情况 void Fifo(void); //先进先出算法 void Lru(void); //最近最旧未用算法 void Clock(void); //时钟(二次机会)置换算法 void Eclock(void); //增强二次机会置换算法 void Lfu(void); //最不经常使用置换算法 void Mfu(void); //最经常使用置换算法 private: int * ReferencePage ; //存放要访问到的页号 int * EliminatePage ; //存放淘汰页号 int * PageFrames ; //存放当前正在实存中的页号 int PageNumber; //访问页数 int FrameNumber; //实存帧数 int FaultNumber; //失败页数 }; 四、 磁盘移臂调度算法实验 5.1 实验目的 加深对于操作系统设备管理技术的了解， 体验磁盘移臂调度算法的重要性；
掌握几种重要的磁盘移臂调度算法，练习模拟算法的编程技巧，锻炼研究分析试验数据的能力。

5.2示例实验 5.2.1实验内容 1.示例实验程序中模拟两种磁盘移臂调度算法：SSTF 算法和 SCAN 算法。

2.能对两种算法给定任意序列不同的磁盘请求序列，显示响应磁盘请求的过程。

3.能统计和报告不同算法情况下响应请求的顺序、移臂的总量。比较两种算法在给定条件下的优劣。

4.为了能方便的扩充磁盘移臂调度算法，更好的描述磁盘移臂调度过程，示例实验程序采用了 C++语言用 DiskArm 类描述了磁盘移臂调度算法及其属性。

5.2.2实验演示结果 5.3独立实验 5.3.1实验内容 请在以上示例实验程序中补充 SCAN，C-SCAN，LOOK 磁盘移臂调度算法的模拟程序。输入不同的磁盘柱面请求序列，观察和分析其调度效果和性能，并将其与FCFS 和 SSTF 算法进行比较。改进以上示例实验程序，使之能够随机的产生磁盘柱面请求序列，以便能动态的观测各种调度算法的性能。

5.3.2实验步骤 5.3.2.1算法设计 扫描算法（SCAN）：  磁臂从磁盘的一端向另一端移动，同时当磁头移过每个柱面时，处理位于该柱面上的服务请求。当到达另一端时，磁头改变方向，处理继续。磁头在磁盘上来回扫描。有时被称为电梯算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。

如在本例中，开始时，在53号柱面执行操作的读写磁头的移动臂方向是由里向外，趋向37号柱面的位置，因此，当访问53号柱面的操作结束后，沿臂移动方向最近的柱面是37号柱面。所以应先为37号柱面的访问者服务，然后是为14号柱面访问者服务。在柱面0时，磁头会调转方向，朝磁盘的另一端移动，并处理柱面65、67、98、122、124、183. 循环扫描算法（CSCAN）：
循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。

由于本例中已假定读写的当前位置在53号柱面，从53号柱面继续向外扫描，依次为37、14、0各柱面的访问者服务，此时移动臂已经是最外的柱面，于是立即返回到199号柱面，重新扫描，依次为183、124、122、98、67、65号柱面的访问者服务。

LOOK算法：
LOOK算法是SCAN算法的一种改进。对LOOK算法而言磁头同样在最内圈和最外圈磁道之间往返移动。但LOOK算法发现所移动的方向不再有请求时立即改变移动方向而SCAN算法则需移动到最外圈或最内圈时才改变移动方向。

5.3.2.2开发调试过程 在新建文件夹中建立以下 dask.h 文件；

在新建文件夹中建立以下 dask.cc 文件；

在新建文件夹中建立以下 Makefile 文件；

执行 make 命令编译连接，生成可执行文件 dask；

执行 dask 命令，输入当前道号，当前寻道方向，当前请求寻道数，当前请求寻 道的道号串。

5.3.2.3思考与分析 SCAN和C-SCAN对于磁盘负荷较大的系统会执行的更好，这是因为它不可能产生饿死问题。

SCAN算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。

5.3.3实验演示结果 5.3.4实验代码 dask.cc文件: #include “dask.h“ DiskArm::DiskArm(){ int i; //输入当前道号 cout << “Please input Current cylinder :“ ; cin >> CurrentCylinder; //磁头方向,输入 0 表示向小道号移动,1 表示向大道号移动 cout << “Please input Current Direction (0/1) :“ ; cin >> SeekDirection; //输入磁盘请求数,请求道号 cout << “Please input Request Numbers :“ ; cin >> RequestNumber; cout << “Please input Request cylinder string :“; Request = new int[sizeof(int) * RequestNumber]; Cylinder = new int[sizeof(int) * RequestNumber]; for (i = 0; i < RequestNumber; i++) cin >> Request[i]; } DiskArm::~DiskArm(){ } //初始化道号,寻道记录 void DiskArm::InitSpace(char * MethodName) { int i; cout << endl << MethodName << endl; SeekNumber = 0; SeekChang = 0; for (i = 0; i < RequestNumber; i++) Cylinder[i] = Request[i]; } // 统计报告算法执行情况 void DiskArm::Report(void){ cout << endl; cout << “Seek Number: “ << SeekNumber << endl; cout << “Chang Direction: “ << SeekChang << endl << endl; } //先来先服务算法 void DiskArm::Fcfs(void) { int Current = CurrentCylinder; int Direction = SeekDirection; InitSpace(“FCFS“); cout << Current; for(int i=0; i<RequestNumber; i++){ if(((Cylinder[i] >= Current) && !Direction)||((Cylinder[i] < Current) && Direction)){ //需要调头 SeekChang++; //调头数加 1 Direction = !Direction ; //改变方向标志 //报告当前响应的道号 cout << endl << Current << “ -> “ << Cylinder[i]; } else //不需调头,报告当前响应的道号 cout << “ -> “ << Cylinder[i] ; //累计寻道数,响应过的道号变为当前道号 SeekNumber += abs(Current -Cylinder[i]); Current = Cylinder[i]; } //报告磁盘移臂调度的情况 Report(); } void DiskArm::Sstf(void) { int Shortest; int Distance = 999999 ; int Direction = SeekDirection; int Current = CurrentCylinder; InitSpace(“SSTF“); cout << Current; for(int i=0; i<RequestNumber; i++){ //查找当前最近道号 for(int j=0; j<RequestNumber; j++){ if(Cylinder[j] == -1) continue; //-1 表示已经响应过了 if(Distance > abs(Current-Cylinder[j])){ //到下一道号比当前距离近,下一道号为当前距离 Distance = abs(Current-Cylinder[j]); Shortest = j; } } if((( Cylinder[Shortest] >= Current) && !Direction)||(( Cylinder[Shortest] < CurrentCylinder) && Direction)){ //需要调头 SeekChang++; //调头数加 1 Direction = !Direction ; //改变方向标志 //报告当前响应的道号 cout << endl << Current << “ -> “ << Cylinder[Shortest]; } else //不需调头,报告当前响应的道号 cout << “ -> “ << Cylinder[Shortest] ; //累计寻道数,响应过的道号变为当前道号 SeekNumber += abs(Current -Cylinder[Shortest]); Current = Cylinder[Shortest]; //恢复最近距离,销去响应过的道号 Distance = 999999; Cylinder[Shortest] = -1; } Report(); } //电梯调度算法 void DiskArm::Scan(void){ int Current = CurrentCylinder; int Direction = SeekDirection; InitSpace(“SCAN“); cout << Current; //打印出当前道号 for(int i=0; i<RequestNumber; i++){ int index=-1; int Distance = 999999; for(int j=0;j<RequestNumber;j++){ if(Cylinder[j]==-1) continue; else if((Direction==0&&Cylinder[j]<Current&&(Current-Cylinder[j])<Distance) ||(Direction==1&&Cylinder[j]>Current&&(Cylinder[j]-Current)<Distance)){ index=j; Distance=abs(Current-Cylinder[j]); } } if(Direction==0){ if(index!=-1){ cout<<“->“<<Cylinder[index]; SeekNumber+=Current-Cylinder[index]; Current=Cylinder[index]; Cylinder[index]=-1; }else{ cout<<“->“<<0<<endl; SeekNumber+=Current; Direction=!Direction; //cout<<0; Current=0; SeekChang++; i--; } } else if(Direction==1){ if(index!=-1){ cout<<“->“<<Cylinder[index]; SeekNumber+=Cylinder[index]-Current; Current=Cylinder[index]; Cylinder[index]=-1; }else{ cout<<“->“<<199<<endl; SeekNumber+=199-Current; Direction=!Direction; //cout<<199; Current=199; SeekChang++; i--; } } } //报告磁盘移臂调度的情况 Report(); } //LOOK调度算法 void DiskArm::Look(void){ int Current = CurrentCylinder; int Direction = SeekDirection; InitSpace(“Look“); cout << Current; for(int i=0; i<RequestNumber; i++){ int index=-1; int Distance = 999999; for(int j=0;j<RequestNumber;j++){ if(Cylinder[j]==-1) continue; else if((Direction==0&&Cylinder[j]<Current&&(Current-Cylinder[j])<Distance) ||(Direction==1&&Cylinder[j]>Current&&(Cylinder[j]-Current)<Distance)){ index=j; Distance=abs(Current-Cylinder[j]); } } if(Direction==0){ if(index!=-1){ cout<<“->“<<Cylinder[index]; SeekNumber+=Current-Cylinder[index]; Current=Cylinder[index]; Cylinder[index]=-1; }else{ //cout<<Current<<endl; Direction=!Direction; SeekChang++; i--; } } else if(Direction==1){ if(index!=-1){ cout<<“->“<<Cylinder[index]; SeekNumber+=Cylinder[index]-Current; Current=Cylinder[index]; Cylinder[index]=-1; }else{ //cout<<Current<<endl; Direction=!Direction; SeekChang++; i--; } } } //报告磁盘移臂调度的情况 Report(); } //CScan调度算法 void DiskArm::CScan(void) { int Current = CurrentCylinder; int Direction = SeekDirection; InitSpace(“CScan“); cout << Current; for(int i=0; i<RequestNumber; i++){ int index=-1; int Distance = 999999; for(int j=0;j<RequestNumber;j++){ if(Cylinder[j]==-1) continue; else if((Direction==0&&Cylinder[j]<Current&&(Current-Cylinder[j])<Distance) ||(Direction==1&&Cylinder[j]>Current&&(Cylinder[j]-Current)<Distance)){ index=j; Distance=abs(Current-Cylinder[j]); } } if(Direction==0){ if(index!=-1){ cout<<“->“<<Cylinder[index]; SeekNumber+=Current-Cylinder[index]; Current=Cylinder[index]; Cylinder[index]=-1; }else{ cout<<“->“<<0<<endl; SeekNumber+=Current; Current=199; cout<<“0->199“; SeekChang++; i--; } } else if(Direction==1){ if(index!=-1){ cout<<“->“<<Cylinder[index]; SeekNumber+=Cylinder[index]-Current; Current=Cylinder[index]; Cylinder[index]=-1; }else{ cout<<“->“<<199<<endl; SeekNumber+=199-Current; Current=0; SeekChang++; i--; } } } Report(); } //程序启动入口 int main(int argc,char *argv[]){ //建立磁盘移臂调度类 DiskArm *dask = new DiskArm(); //比较和分析 FCFS 和 SSTF 两种调度算法的性能 dask->Fcfs(); dask->Sstf(); dask->Scan(); dask->CScan(); dask->Look(); } dask.h文件：
#include <iostream> #include <iomanip> #include <malloc.h> #include <cmath> #include <stdlib.h> using namespace std; class DiskArm{ public: DiskArm(); ~DiskArm(); void InitSpace(char * MethodName); //初始化寻道记录 void Report(void); // 报告算法执行情况 void Fcfs(void); //先来先服务算法 void Sstf(void); //最短寻道时间优先算法 void Scan(void); //电梯调度算法 void CScan(void); //均匀电梯调度算法 void Look(void); //LOOK 调度算法 private: int *Request ; //磁盘请求道号 int *Cylinder; //工作柱面道号号 int RequestNumber; //磁盘请求数 int CurrentCylinder; //当前道号 int SeekDirection; //磁头方向 int SeekNumber; //移臂总数 int SeekChang; //磁头调头数 };