文章目录

专题四 设备管理一. 名词解释二. I/O的控制方式三. 缓冲技术四. SPOOLing系统五. 磁盘调度算法附：参考文献

专题四 设备管理

一. 名词解释

---

（一）设备按照工作特性分类

---

存储设备： 计算机用来存储信息的设备； 输入输出设备： 计算机用来接收来自外部世界信息的设备；

---

（二）设备按照使用性质来分类

---

独占设备： 在一段时间内，仅允许一个进程独占的设备； 共享设备： 由若干进程同时共用的设备； 虚拟设备： 利用某种技术把独占设备改造成由多个进程共用的设备；

---

（三）设备按照数据传输的方式来分类

---

串行设备： 指数据按二进制位一位一位地顺序传送的设备； 并行设备： 指数据按二进制同时通过并行线进行传送的设备；

---

（四）设备标识

---

设备（类型）号： 操作系统为每类设备规定了一个编号； 设备绝对地址： 系统按照某一种规则位每台设备分配一个唯一的号码，用作设备控制器区分和识别设备的代号； 缓冲技术： 目的是缓和设备之间数据传输速度不匹配问题的技术；

---

二. I/O的控制方式

程序查询方式 工作原理： – 通过程序不断循环检测设备的状态； （1）在程序执行的过程中，在进行数据输入/输出之前先查询设备的状态。 （2）若设备已准备好，则传送数据；反之程序继续查询。

（二）中断查询方式 工作原理： （1）CPU向设备控制器发出一条I/O命令之后，CPU立即返回继续执行原来的任务； （2）设备控制器便控制I/O设备进行输入/输出； （3）当设备完成一个字节数据的I/O时，设备控制器产生一个中断信号； （4）CPU检测到中断信号之后，进行相应的处理； （三）直接存储器（DMA）访问方式 工作原理： （1）CPU将DMA命令块写入内存，CPU 将命令块地址写入DMA控制器的寄存器中，随后CPU向磁盘控制器发送一个命令，磁盘控制器将数据读到内部缓冲区； （2）DMA控制器通过总线发送请求至磁盘控制器，磁盘控制器根据请求将数据以字为单位通过总线传送到指定的内存位置，当把数据字写入内存之后，磁盘控制器通过总线向DMA控制器发送一个回答信号； （3）DMA相应回答信号做内存地址增加1，减少字节计数；若计数等于0，DMA控制器中断CPU，传送完成，若计数大于0，则重复（1）（2）；

---

三. 缓冲技术

引入目的： (1) 缓解CPU与I/O设备间速度不匹配的问题; (2) 提高并行性 (3) 减少CPU的中断频率.放宽CPU的响应时间;

缓冲技术的类型及使用原则： 单缓冲: 若数据的到达率与离去率相差很大时,则使用单缓冲; 双缓冲: 信息的输入和输出速率相近,则使用双缓冲; 多缓冲: 若为阵发性的输入输出,则使用多缓冲;

---

四. SPOOLing系统

SPOOLing的定义 : 多道程序中的一道程序模拟脱机输入时的外围控制机的功能,另一道程序模拟脱机输出时外围控制机的功能（又称外围联机操作或假脱机操作）; SPOOLing的功能： 是用于将一台独占设备改造成共享设备的一种虚拟技术; 基本组成： （1）输入井与输出井 （2）输入缓冲区与输出缓冲区 （3）输入进程与输出进程

SPOOLing系统的基本原理： （1）执行任务之前：预先将程序和数据输入到输入井中; （2）任务运行时：使用数据时，从输入井中取出/任务运行时：输出数据时，把数据写入输出井; （3）任务运行完：外设空闲时输出全部数据和信息；

典型例子：SPOOLing技术如何使一台打印机虚拟成多台打印机 （1）由输出进程在输出井申请一个磁盘块区，并将要打印的数据送入其中 （2）输出进程再为用户申请一张空白的用户请求打印表，并将用户的打印请求填入表中依次形成打印请求队列中;

---

五. 磁盘调度算法

模拟实验环境： Ubuntu 20.04 visual studio code

FCFS 算法

– 算法设计思想： 磁盘驱动程序每次接受一个请求，并按照请求的顺序依次进行

– 模拟实验源代码：

#include<stdio.h> #include<unistd.h> #include<sys/types.h> #include<stdlib.h> int abs(int value) { if(value>=0) return value; else return -value; } /*磁道个数*/ int n; /* 起始位置 */ int begin; /* 磁道 */ struct Disk { int num;//磁道序列 struct Disk* next; }; struct Quene { struct Disk* head; struct Disk* tail; }; struct Quene q; int IsEmpty() { if(q.head == NULL) return 1; else return 0; } void EnQuene(struct Disk* d) { if(q.head == NULL) { q.head = d; q.tail = d; } else { struct Disk* p = q.tail; p->next = d; q.tail = d; } } struct Disk* DeQuene() { struct Disk* p = q.head; q.head = p->next; p->next = NULL; return p; } void Init() { n = rand()%1000; printf("磁道个数: %d\n",n); for(int i = 0;i<n;i++) { struct Disk* pnew = (struct Disk*)malloc(sizeof(struct Disk)); pnew -> num = rand()%1000; EnQuene(pnew); printf("***************** No.= 已入队 *****************\n",pnew->num); } printf("\n"); } double FCFS(int* begin1) { begin = *begin1; double result = 0; while(!IsEmpty()) { struct Disk* p = DeQuene(); printf("= --> = 移动的距离: =\n",begin,p->num,abs(p->num - begin)); result = result + (double)(abs(p->num - begin)); begin = p->num; } return result; } int main() { Init(); int b; printf("Begin = "); scanf("%d",&b); printf("\n"); double result = FCFS(&b); printf("平均寻道时间 = O\n",result/n); return 0; }

– 模拟实验（部分）初始值：

– 模拟实验（部分）过程展示：

– 初始位置与模拟实验结果：

SSTF 算法

– 算法设计思想： 下一次总是处理与磁头最近的请求，力求使寻道时间最小化;

– 模拟实验源代码：

#include<stdio.h> #include<unistd.h> #include<sys/types.h> #include<stdlib.h> #define INFINITE 1000 int abs(int value) { if(value>=0) return value; else return -value; } /*磁道个数*/ int n; /* 起始位置 */ int begin; /* 磁道 */ struct Disk { int num;//磁道序列 struct Disk* next; }; struct Disk d; int IsEmpty() { if(d.next == NULL) return 1; else return 0; } /* 入"队"操作 */ void Insert(int num) { struct Disk* p; struct Disk* pnew = (struct Disk*)malloc(sizeof(struct Disk)); pnew -> num = num; pnew -> next = NULL; for(p = &d;p->next;p = p -> next); p -> next = pnew; } /* 删除指定的元素，在本次实验中经常会与MIN函数连用*/ struct Disk* Delete(struct Disk* d,struct Disk* pos) { struct Disk* p1 = d; struct Disk* p; for(p = d->next;p;p = p->next,p1 = p1->next) { if(p == pos) { p1 -> next = p->next; p -> next = NULL; return p; } } } /* 在上升过程中距离最近的磁道的位置 */ struct Disk* MIN() { int temp = INFINITE; struct Disk* pos; for(struct Disk* p = d.next;p;p = p->next)//寻找当前位置距离最近的磁道 { if(abs(p->num - begin) <= temp) { temp = abs(p->num - begin); pos = p; } } return pos; } /* 初始化 */ void Init() { n = rand()%1000; printf("磁道个数: %d\n",n); for(int i = 0;i<n;i++) { int num = rand()%1000; Insert(num); printf("***************** No.= 已入队 *****************\n",num); } printf("\n"); } /* 最短寻道时间优先法 */ double SSTF(int* begin1) { begin = *begin1; double result = 0; while(!IsEmpty()) { struct Disk* p = Delete(&d,MIN()); printf("############### = F --> = F 移动的距离: = ###############\n",begin,p->num,abs(begin - p->num)); result = result + (double)(abs(p->num - begin)); begin = p->num; } return result; } int main() { Init(); int b; printf("Begin = "); scanf("%d",&b); printf("\n"); double result = SSTF(&b); printf("平均寻道时间 = O\n",result/n); return 0; }

– 模拟实验初始值： – 模拟实验过程展示： – 初始位置与模拟实验结果

SCAN 算法

#include<stdio.h> #include<unistd.h> #include<sys/types.h> #include<stdlib.h> #define INFINITE 1000 /*磁道个数*/ int n; /* 起始位置 */ int begin; /* 磁道 */ struct Disk { int num;//磁道序列 struct Disk* next; }; /* 下降组 */ struct Disk* Down; /* 上升组 */ struct Disk* Up; /* 插入函数，分组依据，判断与起始位置的大小 */ void Insert(struct Disk* d,int num) { struct Disk* p = (struct Disk*)malloc(sizeof(struct Disk)); p-> num = num; p->next = d->next; d->next = p; } /* 在上升过程中距离最近的磁道的位置 */ struct Disk* MIN() { int temp = INFINITE; struct Disk* pos; for(struct Disk* p = Up->next;p;p = p->next) { if(p->num < temp) { temp = p->num; pos = p; } } return pos; } /* 在下降过程中距离最近的磁道的位置 */ struct Disk* MAX() { int temp = -1; struct Disk* pos; for(struct Disk* p = Down->next;p;p = p->next) { if(p->num > temp) { temp = p->num; pos = p; } } return pos; } /* 删除指定的元素，在本次实验中经常会与MIN，MAX函数连用*/ struct Disk* Delete(struct Disk* d,struct Disk* pos) { struct Disk* p1 = d; struct Disk* p; for(p = d->next;p;p = p->next,p1 = p1->next) { if(p == pos) { p1 -> next = p->next; p -> next = NULL; return p; } } } /* 请求访问磁道队列 */ struct Quene { struct Disk* head; struct Disk* tail; }; struct Quene q; /* 判断磁道队列是否为空 */ int IsEmpty() { if(q.head == NULL) return 1; else return 0; } /* 入队操作 */ void EnQuene(struct Disk* d) { if(q.head == NULL) { q.head = d; q.tail = d; } else { struct Disk* p = q.tail; p->next = d; q.tail = d; } } /* 初始化 */ void Init() { Down = (struct Disk*)malloc(sizeof(struct Disk)); Up = (struct Disk*)malloc(sizeof(struct Disk)); n = rand()%1000; printf("磁道个数: %d\n",n); for(int i = 0;i<n;i++) { struct Disk* pnew = (struct Disk*)malloc(sizeof(struct Disk)); pnew -> num = rand()%1000; EnQuene(pnew); printf("***************** No.= 已入队 *****************\n",pnew->num); } printf("\n"); } /* 判断磁道组是否为空 */ int IsEmptyLink(struct Disk* d) { if(d->next == NULL) return 1; else return 0; } /* 电梯扫描算法 */ double SCAN(int* begin1) { begin = *begin1; double result = 0; /* 将磁道队列进行分组*/ for(struct Disk* p1 = q.head;p1;p1 = p1->next) { if(p1-> num >= begin) //如果比起始位置要大选择上升组 Insert(Up,p1->num); else //如果比起始位置要小选择下降组 Insert(Down,p1->num); } /* 判断是上升优先还是下降优先，判断的依据是：队头的磁道与起始位置的大小关系 */ if(begin >= q.head->num)//队头的磁道不大于起始位置 { printf("Go Down!\n"); while(!IsEmptyLink(Down)) { struct Disk* p = Delete(Down,MAX()); printf("***************** = -> = F 移动的距离: = *****************\n",begin,p->num,begin - p->num); result = result + (double)(begin - p->num); begin = p->num; //free(p); } if(!IsEmptyLink(Up)) { printf("Go Up!\n"); printf("= ---> = 移动的距离: =\n",begin,MIN()->num,MIN()->num - begin); result = result + (double)(MIN()->num - begin); begin = MIN()->num; } while(!IsEmptyLink(Up)) { struct Disk* p = Delete(Up,MIN()); printf("***************** = -> = F 移动的距离: = *****************\n",begin,p->num,p->num - begin); result = result + (double)(p->num - begin); begin = p->num; //free(p); } } else //队头的磁道小于起始位置 { printf("Go Up!\n"); while(!IsEmptyLink(Up)) { struct Disk* p = Delete(Up,MIN()); printf("***************** = -> = 移动的距离: = *****************\n",begin,p->num,p->num - begin); result = result + (double)(p->num - begin); begin = p->num; //free(p); } if(!IsEmptyLink(Down)) { printf("Go Down!\n"); printf("= ---> =F 移动的距离: = \n",begin,MAX()->num,begin - MAX()->num); result = result + (double)(begin - MAX()->num); begin = MAX()->num; } while(!IsEmptyLink(Down)) { struct Disk* p = Delete(Down,MAX()); printf("***************** = -> = 移动的距离: = *****************\n",begin,p->num,begin - p->num); result = result + (double)(begin - p->num); begin = p->num; //free(p); } } return result; } int main() { Init(); int b ; printf("Begin = "); scanf("%d",&b); printf("\n"); double result = SCAN(&b); printf("平均寻道时间： = O\n",result/n); return 0; }

– 模拟实验初始值： – 模拟实验过程展示 下降过程： – 初始位置与模拟实验结果: 初始

附：参考文献

[1] 操作系统原理 机械工业出版社 第二版 孟庆昌 张志华 [2] 参考慕课：操作系统 西安交通大学 软件学院 田丽华（副教授） [3] 参考慕课：操作系统原理 华中科技大学 软件学院 苏曙光（副教授）