实验二：处理机调度
一、实验目的：
1、了解Linux下Emacs编辑器的使用方法，掌握各种常用的键盘操作命令；
2、理解并掌握处理机调度算法。
二、实验内容及要求：
在采用多道系统的设计程序中，往往有若干进程同时处于就绪状态。当就绪状态进程数大于处理机数时，就必须按照某种策略来决定哪些进程优先占用处理机。本实验模拟在单处理机情况下处理机调度。
1、优先调度算法实现处理机的调度：
设计思路：
1)每个进程用一个进程控制块PCB来代表，进程控制块包括进程名(进程的标识)、指针(按优先数的大小把进程连成队列，用指针指出下一个进程的进程控制块首地址，最后一个进程中的指针为"0")、要求运行时间、优先数、状态(就绪、结束)；
2)每次运行处理机调度程序前，为每个进程确定它的"优先数"和"要求运行时间"；
3)把给定的进程按优先数的大小连成队列，用一单元指出队首进程；
4)每模拟执行一次进程，优先数减一，要求运行时间减一；
5)如果要求运行的时间>=0，再将它加入队列（按优先数的大小插入，重置队首标志）；如果要求运行的时间=0，那么把它的状态修改为结束，且推出队列；
6)若就绪队列不为空，重复上述，直到所有的进程都结束；
7)程序有显示和打印语句，每次运行后显示变化。
2、按时间片轮转法实现处理机调度：
设计思路：
1)每个进程用一个进程控制块PCB来代表，进程控制块包括进程名(进程的标识)、指针(把进程连成循环队列，用指针指出下一个进程的进程控制块首地址，最后一个进程中的指针指出第一个进程的进程控制块首地址)、已运行时间、状态(就绪、结束)；
2)每次运行处理机调度程序前，为每个进程确定它的"要求运行时间"；
3)用指针把给定的进程按顺序排成循环队列，用另一标志单元记录轮到的进程；
4)每模拟运行一次进程，已运行时间加一；
5)进程运行一次后，把该进程控制块的指针值送到标志单元，以指示下一个轮到的进程。若该进程要求运行时间≠已运行时间，未执行结束，待到下一轮再执行；若要求运行时间=已运行时间，状态改为结束，退出队列；
6)若就绪队列不为空，重复步骤四和五；
7)程序有显示和打印语句，每次运行后显示变化。
三、程序设计：
1、优先数调度算法：
/*我的思路：先主函数输入要进行调度的进程数，然后调用函数create(),把进程的信息输入，再调用函数insert(),把输入的函数按照优先数的大小排成链表，然后调用函数prio()实现优先数调度*/
#include
#include
#include
typedef struct node
{ char name[10]; /*进程名*/
int prio; /*优先数*/
int cputime; /*占用cpu时间*/
int needtime; /*要求运行时间*/
char state; /*状态*/
struct node *next; /*指针*/
}PCB;
PCB *ready,*run,*finish; /*就绪执行结束指针*/
int N;
void prt() /*输出函数，可以方便看到进程执行的演示*/
{
PCB *p;
printf(" NAME CPUTIME NEEDTIME PRIORITY STATUS\n");
if(run!=NULL)
printf(" %-10s%-10d%-10d%-10d %c\n",run->name,run->cputime,run->needtime,r un->prio,run->state); /*输出执行的进程的信息*/
p=ready;
while(p!=NULL)
{ printf(" %-10s%-10d%-10d%-10d %c\n",p->name,p->cputime,p->needtime,p-> prio,p->state); /*输出就绪进程的信息*/
p=p->next; }
p=finish;
while(p!=NULL)
{ printf(" %-10s%-10d%-10d%-10d %c\n",p->name,p->cputime,p->needtime,p-> prio,p->state); /*输出结束队列的信息*/
p=p->next; }
getchar(); } /*使用getchar()函数可以让输出时停留画面，等待人按回车继续*/
void insert(PCB *q) /*插入新进程，把进程按优先数大小排序*/
{ PCB *p1,*s,*r;
int b;
s=q; /*指针s指向新要插入的进程*/
p1=ready; /*指针p1指向原来的进程队列的队首*/
r=p1; /*使用指针r是指向p1前面的进程*/
b=1;
while((p1!=NULL)&&b)
if(p1->prio>=s->prio) { r=p1; p1=p1->next; } /*新进程的优先数小，则p1 else b=0; 指向下一个进程继续比*/ if(r!=p1) { r->next=s; s->next=p1; } /*新进程找到位置，插在r和p1之间*/ else { s->next=p1; ready=s; } } /*新进程的优先数最大，插在队首，并void create() 修改就绪队首ready指针*/ { PCB *p;
int i;
ready=NULL; run=NULL; finish=NULL;
printf("Please enter the name and time and priority of PCB:\n");
/*输入进程名、和*/
for(i=0;i { p=malloc(sizeof(PCB)); /*为新进程开辟空间*/ scanf("%s",p->name); /*输入进程名*/ scanf("%d",&p->needtime); /*输入进程要求运行时间*/ scanf("%d",&p->prio); /*输入进程优先数*/ p->cputime=0; p->state='W'; /*表示就绪队列中未在队首先执行，但也是就绪状态*/ if (ready!=NULL) insert(p); /*就绪队首不为NULL，插入新进程*/ else { p->next=ready; ready=p; } } /*否则先插在NULL前*/ printf(" Display is going to start: \n"); printf("***********************************************\n"); prt(); run=ready; /*队列排好，run指向就绪队列队首*/ ready=ready->next; /*ready指向下一个进程，这样当进程执行时如果优先数小于其他的进程，应该先进行优先数最大的进程*/ run->state='R'; } /*队首进程的状态为就绪*/ void prio() { while(run!=NULL) { run->cputime=run->cputime+1; /*运行一次cpu占用时间加一*/ run->needtime=run->needtime-1; /*运行一次要求运行时间减一*/ run->prio=run->prio-1; /*运行一次优先数减一*/ if(run->needtime==0) /*若要求运行时间为0时*/ { run->next=finish; /*退出队列*/ finish=run; /*finish为结束进程的队列*/ run->state='E'; /*修改状态为结束*/ run=NULL; /*释放run指针*/ if (ready!=NULL) /*创建新就绪队列的头指针*/ { run=ready; run->state='R'; ready=ready->next; } } else if((ready!=NULL)&&(run->prio /*队首进程的优先数比它下一个小，且下一个进程不为NULL时执行*/ { run->state='W'; run->next=NULL; /*队首进程退出进程队列*/ insert(run); /*在进程队列中重新插入原来的队首进程*/ run=ready; /*重新置就绪队列的头指针*/ run->state='R'; ready=ready->next; } prt(); } } void main() { printf("Please enter the total number of PCB:\n"); scanf("%d",&N); create(); /*模拟创建进程，并输入相关信息*/ prio(); } /*优先数调度算法*/ 2、时间片轮转法： #include #include #include typedef struct node { char name[10]; /*进程名*/ int count; /*计数器，判断是否=时间片的大小*/ int cputime; /*占用cpu时间*/ int needtime; /*要求运行时间*/ char state; /*状态*/ struct node *next; /*指针*/ }PCB; PCB *ready,*run,*finish,*tail; /*就绪执行结束尾指针*/ int N，round; void prt() /*输出函数，可以方便看到进程执行的演示*/ { /*略同优先数法*/ } void insert(PCB *q) /*在队尾插入新的进程*/ { tail->next=q; tail=q; q->next=NULL; } void create() { PCB *p; int i; ready=NULL; run=NULL; finish=NULL; printf("Please enter the name and time of PCB:\n"); /*输入进程名、和*/ for(i=0;i { p=malloc(sizeof(PCB)); /*为新进程开辟空间*/ scanf("%s",p->name); /*输入进程名*/ scanf("%d",&p->needtime); /*输入进程要求运行时间*/ p->cputime=0; p->state='W'; /*表示就绪队列中未在队首先执行，但也是就绪状态*/ if (ready!=NULL) insert(p); /*就绪队首不为NULL，插入新进程*/ else {p->next=ready; ready=p; tail=p; } } printf(" Display is going to start: \n"); printf("***********************************************\n"); prt(); run=ready; /*队列排好，run指向就绪队列队首*/ ready=ready->next; /*ready指向下一个进程*/ run->state='R'; } /*队首进程的状态为就绪*/ void count() { while(run!=NULL) { run->cputime=run->cputime+1; /*运行一次cpu占用时间加一*/ run->needtime=run->needtime-1; /*运行一次要求运行时间减一*/ run->count=run->count+1; /*运行一次计数器加一*/ if(run->needtime==0) /*若要求运行时间为0时*/ { run->next=finish; /*退出队列*/ finish=run; /*finish为结束进程的队列*/ run->state='E'; /*修改状态为结束*/ run=NULL; /*释放run指针*/ if (ready!=NULL) /*创建新就绪队列的头指针*/ { run=ready; run->state='R'; ready=ready->next; } } else if(run->count==round) /*如果时间片到*/ { run->count=0; /*计数器置0*/ if(ready!=NULL) /*如就绪队列不空*/ { run->state='W'; insert(run); /*在进程队列中重新插入原来的队首进程*/ run=ready; /*重新置就绪队列的头指针*/ run->state='R'; ready=ready->next; } prt(); } } void main() { printf("Please enter the total number of PCB:\n"); scanf("%d",&N); printf("Please enter the timeround(don't be too big,1 or 2 is best):\n"); scanf("%d",&round); /*输入时间片的大小，不应太大*/ create(); /*模拟创建进程，并输入相关信息*/ count(); } /*优先数调度算法*/ 四、程序运行的初值及执行结果： 1、优先数调度算法： 以下是输出的结果（符合优先数调度）： 2、时间片轮转法调度算法： 以下是输出结果（符合时间片轮转法调度）： 五、结果分析： 在优先数调度中，程序首先输出各个进程的初始值，按回车之后，由于进程p1的优先数最大，排在就绪队列的队首，首先执行，执行一次后优先数减一，要求运行时间减一，cpu占用时间加一，再和其他的进程比较优先数，还是最大，继续执行，再执行一次后优先数小于进程p3，所以下一个执行的是p3，按这样的顺序，在就绪队列队首的进程状态为"R"，不在队首的就绪进程状态为"W"，结束的进程状态为"E"，一直执行，直到所有进程状态都为"E"，调度完成。 在时间片轮转法调度中，先设置了时间片的大小为1，然后各个进程按循环队列依次执行，每执行一次，要求运行时间减一，若等于0了，则状态改为"E"， 退出队列，直到所有进程的状态为"E"，调度完成。 六、实验小结： 本次实验虽然为模拟在单处理机情况下处理机的调度，但深深帮我理解了处理机调度的工作，也对进程的几种状态就绪、结束等有了明确的认识。优先数调度的思考度更强点，在编写C程序的时候，对于其中的进程插入和优先数调度两个函数思考了蛮久，每执行一次进程后，优先数的改变将又要重新排就绪队列，这也是实验的难点所在，自己原来学C的时候对于队列不是很熟，也借本次实验又巩固了原来的知识。也许是有了优先数调度的基础，时间片轮转法调度的编写来得相对轻松，它的insert()函数比较简单，不用根据优先数来排队，而是直接插在队尾即可。另外，通过本次实验，我对函数的分模块书写的优点感受颇深，方便了移植和修改，减轻了下次编写的负担，这也是我们以后面向程序设计的要求所在。 泉州师范学院 软件学院 《计算机操作系统》 课程设计 题目：处理机调度 班级： 10软件工程(2)班 学号： 姓名： 指导教师： 2012 年12 月25 日 目录 第一章概述 (2) 1.1需求分析 (2) 1.2背景设计 (2) 第二章概要设计 (1) 第三章详细设计 (2) 3.1高响应比调度算法 (2) 3.2时间片轮转法 (3) 3.3短进程优先法 (4) 第四章调试分析与测试结果 (5) 第五章总结 (7) 第六章参考文献 (8) 第一章概述 1.1需求分析 进程是操作系统最重要的概念之一，进程调度是操作系统内核的重要功能，本实验要求用C语言编写一个进程调度模拟程序，使用短作业优先调度算法，高响应比调度算法，时间片轮转调度算法实现进程调度。可以手动阻塞与唤醒。并用MFC实现图形界面。本实验可加深对进程调度算法的理解。 1.2背景设计 在OS中，调度的实质是一种资源分配，调度算法即指：根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法，如在批处理系统中，为照顾为数众多的短作业，采用短作业有限调度算法；在分时系统中，为保证系统具有合理的响应时间，采用轮转法进行调度。采用算法时，则要考虑多方面因素，以便达到最佳效果。 第二章概要设计 设计一个有多个进程共行的进程调度程序。 进程调度算法：短作业优先调度算法，高响应比调度算法，时间片轮转调度算法 每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、服务时间、进程状态等等。 struct progress { CString Name; //进程名称 CString Start; //创建时间 int ServiceT; //服务时间 int RunningT; //消逝时间 int RemainT;//剩余时间 int id;//进程标识符 CProgressCtrl* pro; //指向进度条的指针 int Rp;//进程成为就绪进程的时间 1.有两个程序，程序A依次使用CPU计10s，使用设备甲计5s，使用CPU计5s，使用设 备乙计10s，使用CPU计10s。程序B依次使用设备甲计10s，使用CPU计10s，使用设备乙计5s，使用CPU计5s，使用设备乙计10s。在单道程序环境下先执行程序A再执行程序B，计算CPU的利用率是多少？在多道程序环境下，CPU的利用率是多少？ 解答： 单道环境下，CPU运行时间为（10+5+10）s+(10+5)s=40s,两个程序运行总时间为40s+40s=80s,故利用率是40/80=50% 多道环境下，运行情况如下图所示，CPU运行时间为40s，两个程序总时间为45s，故利用率为40/45=88.9% 2.设某计算机系统有一个CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪 状态，且进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。进程B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试画出它们的时序关系图（可以用甘特图），并说明： （1）开始运行后，CPU有无空闲等待？若有，在哪些时间内等待？计算CPU的利用率。 （2）进程A运行时有无等待现象？若有，在什么时候发生等待现象？ （3）进程B运行时有无等待现象？若有，在什么时候发生等待现象？ 进程运行情况如下： 1）CPU在100-150ms时间段内空闲，利用率为250/300=83.3% 2）进程A为无等待现象 3）进程B为有等待现象，0-50ms，180-200ms 3.设内存中有3道程序A、B、C，它们按A、B、C的优先次序执行。它们的计算和I/O操 作的时间见表1-1。假设3道程序使用相同设备进行I/O操作，即程序以串行方式使用设备，试画出单道运行和多道运行的时间关系图（调度程序的执行时间忽略不计）。在两种情况下，完成3道程序分别需要多长时间（多道运行时采用抢占式调度策略）。 中国地质大学江城学院 LINUX操作系统实验报告 姓名 班级学号 指导教师冯春华 2012 年月日 实验一在LINUX下获取帮助、Shell实用功能 实验目的： 1、掌握字符界面下关机及重启的命令。 2、掌握LINUX下获取帮助信息的命令：man、help。 3、掌握LINUX中Shell的实用功能，命令行自动补全，命令历史记录，命令的排列、替 换与别名，管道及输入输出重定向。 实验内容： 1、使用shutdown命令设定在30分钟之后关闭计算机。 2、使用命令“cat /etc/named.conf”设置为别名named，然后再取消别名。 3、使用echo命令和输出重定向创建文本文件/root/nn，内容是hello，然后再使用追加重定向输入内容为word。 4、使用管道方式分页显示/var目录下的内容。 5、使用cat显示文件/etc/passwd和/etc/shadow，只有正确显示第一个文件时才显示第二个文件。 实验步骤及结果： 1、 2、 3、 4、 5、 实验二文件和目录操作命令 实验目的： 1、掌握LINUX下文件和目录的操作命令，如pwd、cd、ls、touch、mkdir、rmdir、cp、 mv、rm等。 2、掌握LINUX下建立链接文件的方法。 实验内容： 1、使用命令切换到/etc目录，并显示当前工作目录路径。 2、使用命令显示/root目录下所有文件目录的详细信息，包括隐藏文件。 3、使用命令创建空文件/root/ab，并将该文件的时间记录更改为8月8日8点8分。 4、使用命令创建具有默认权限为744的目录/root/ak，然后将/etc/named.conf文件复制到该目录中，最后将该目录及其目录下的文件一起删除。 5、统计文件/etc/named.conf的行数、字符数和单词数。 6、使用命令创建/root/a文件的硬链接文件/root/b和软链接文件/root/c。 实验步骤及结果： 一、先来先服务算法 1．程序简介 先来先服务算法按照作业进入系统后备作业队列的先后次序挑选作业,先进入系统的作业将优先被挑选进入主存,创建用户进程,分配所需资源,然后,移入就绪队列.这是一种非剥夺式调度算法,易于实现,但效率不高.只顾及作业的等候时间,未考虑作业要求服务时间的长短,不利于短作业而优待长作业,不利于I/O繁忙型作业而有利于CPU繁忙型作业.有时为了等待场作业执行结束,短作业的周转时间和带全周转时间将变得很大,从而若干作业的平均周转时间和平均带权周转时间也变得很大。 2．分析 1．先定义一个数组代表各作业运行的时间，再定义一个数组代表各作业到达系统的时间，注意到达系统的时间以第一个作业为0基础（注意：若各程序都同时到达系统，则到达系统时间都为0）。 2．输入作业数。 3．然后运用循环结构累积作业周转时间和带权周转时间。 4．最后，作业周转时间和带权周转时间分别除以作业数即可得到平均作业周转时间和平均带权周转时间。 3．详细设计 源程序如下： #include Linux操作系统实验教程 第1章Linux系统概述 一、Linux系统结构 从操作系统的角度来分析Linux,它的体系结构总体上属于层次结构如下图所示： 从内到外包括三层：最内层是系统核心，中间是Shell、编译编辑实用程序、库函数等，最外层是用户程序，包括许多应用软件。 从操作系统的功能角度来看，它的核心有五大部分组成：进程管理、存储管理、文件管理、设备管理、网络管理。各子系统实现其主要功能，同时相互之间是合作、依赖的关系。进程会管理是操作系统最核心的内容，它控制了整个系统的进程调度和进程之间的通信，是整个系统合理高效运行的关键； 存储管理为其他子系统提供内存管理支持，同时其他子系统又为内存管理提供了实现支持，例如要通过文件管理和设备管理实现虚拟存储器和内外存的统一管理。 二、配置一个双引导系统 如果计算机中已经安装了其他操作系统，并想创建一个引导系统以便兼用Red Hat Linux和另外的操作系统，需要使用双引导。机器启动时，可以选择其中之一，但不能同时使用两者。每个操作系统都从自己的硬盘驱动器或硬盘分区中引导，并使用自己的硬盘驱动器或硬盘分区。 如果计算机上还没有安装任何操作系统，可以使用专门的分区及格式化软件给Windows创建指定大小的分区，Windows的文件系统为FAT,再为Linux系统创建所需要大小的分区(4G或更大)，另外再给Linux留100MB 左右的交换分区，Linux的文件系统为ext2。然后就可以安装系统了。应首先安装Windows,然后再安装Red Hat Linux。如果只进行了分区而没有格式化各分区，在安装时可以使用Windows自带的格式化程序和Linux自带的格式化程序进行各自分区的格式化。 当Windows已经被安装，而且已为Linux准备了足够的磁盘空间，就可以安装Linux了。Red Hat Linux安装程序通常会检测到Windows并自动配置引导程序来引导Windows或Red Hat Linux。 《计算机操作系统》练习题 第一部分：处理机管理 1. 什么是进程控制块？试从进程管理、进程通信、中断处理、文件管理、存储管理、设备管理的角度设计进程控制块应包含的项目。 2. 在创建和撤销一个进程时所要完成的主要工作分别是什么？当进程A由于所分配的时间片到，由运行状态转入就绪状态；而进程B被调度程序选中由就绪态转为运行状态时，系统所要做的主要工作是什么？ 3. 某系统采用以下措施对资源进行管理：进程在使用资源时提出资源申请，当一个已经保持了某些资源的进程再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再提出申请。问这种措施为什么能够预防死锁？它有什么不足之处？ 4. 理发师问题描述如下：理发店包含一间接待室和一间工作室，接待室内有n（n>0）把椅子，而工作室只有1把椅子。如果没有顾客，理发师就去睡觉；如果顾客到来时所有椅子都有人，那么顾客离去；如果理发师在忙而接待室有空闲的椅子，那么顾客会坐在其中一把椅子上等待；如果理发师在睡觉，则顾客会唤醒他。请采用信号量机制解决该位理发师问题（用代码描述） 5. 在一个批处理系统中，有两个作业进程。有一作业序列，其到达时间及估计运行时间列表如表所示。 作业到达时间估计运行时间 1 10：00 35 2 10：10 30 3 10：15 45 4 10：20 20 5 10：30 30 系统采用最高相应比优先的作业调度算法（相应比=等待时间/估计运行时间）。作业进程的调度采用短作业优先的抢占式调度算法。 （1）列出各作业的执行时间（即列出每个作业运行的时间片段，例如作业i的运行时间序列为10：00~10：40，11：00~11：20，11：30~11：50（结束））。 （2）计算这批作业的平均周转时间。 6. 假设一个CPU算法会优先考虑在近期占用CPU时间最少的进程，分析为什么这样的调度算法有利于受I/O约束的进程，但又不会使受CPU约束的进程饥饿。 7. 某系统如此定义P、V操作： P(S) S=S-1: 课程设计报告 设计名称：模拟实现一种处理机调度算法 学生姓名： xxx 专业：计算机科学与技术 班别： xxxxxxxx 学号： xxxxxx 指导老师： xxxxx 日期： 2014 年 6 月 20 日 初始条件： 1．预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。 2．实践准备：掌握一种计算机高级语言的使用。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1．模拟进程调度，能够处理以下的情形： ⑴能够选择不同的调度算法（要求中给出的调度算法）； ⑵能够输入进程的基本信息，如进程名、优先级、到达 时间和运行时间等； ⑶根据选择的调度算法显示进程调度队列； ⑷根据选择的调度算法计算平均周转时间和平均带权周 转时间。 2．设计报告内容应说明： ⑴需求分析； ⑵功能设计（数据结构及模块说明）； ⑶开发平台及源程序的主要部分； ⑷测试用例，运行结果与运行情况分析； ⑸自我评价与总结： i）你认为你完成的设计哪些地方做得比较好或比较出 色； ii）什么地方做得不太好，以后如何改正； iii）从本设计得到的收获（在编写，调试，执行过程中 的经验和教训）； iv）完成本题是否有其他方法（如果有，简要说明该方 法）； 进程调度模拟设计——先来先服务、优先级法1、背景： 当计算机系统是多道程序设计系统时，通常会有多个进程或线程同时竞争CPU。只要有两个或更多的进程处于就绪状态，这种情形就会发生。如果只有一个CPU可用，那么就必须选择下一个要运行的进程。在操作系统中，完成选择工作的这一部分称为调度程序，该程序使用的算法成为调度算法。 进程调度的核心问题是采用什么样的算法把处理机分配给进程，好的算法将提高资源利用率，减少处理机的空闲时间，避免有些作业长期得不到相应的情况发生等，从而设计出受欢迎的操作系统。较常见的几种进程调度算法有：先来先服务调度算法；短作业优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先算法和多级反馈队列调度算法等。 2.1设计目的 无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机 第四章处理机调度 4.3 习题 4.3.1 选择最合适的答案 1．某系统采用了银行家算法，则下列叙述正确的是（）。 A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁 C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁 2．银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项正确的是（）。 A.Max[i,j]=Allocation[i,j]+Need[i,j] B.Need[i,j]= Allocation[i,j]+ Max[i,j] C.Max[i,j]= Available[i,j]+Need[i,j] D.Need[i,j]= Available[i,j]+ Max[i,j] 3．下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。 A.非抢占式静态优先权法 B.抢占式静态优先权法 C.时间片轮转调度算法 D.非抢占式动态优先权法 4．在下列选项中，属于预防死锁的方法是（）。 A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法 5．在下列选项中，属于检测死锁的方法是（）。 A.银行家算法 B.消进程法 C.资源静态分配法 D.资源分配图简化法 6．在下列选项中，属于解除死锁的方法是（）。 A．剥夺资源法 B.资源分配图简化法 C．银行家算法 D.资源静态分配法 7．为了照顾紧迫型作业，应采用（）。 A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法 8．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则 第四章存储器管理 1．在存储管理中，采用覆盖和交换技术的目的是 A．节省内存空间B．物理上扩充内存容量C．提高CPU效率D．实现内存共享 2．采用不会产生内部碎片 A．分页式存储管理B．分段式存储管理 C．固定分区式存储管理D．段页式存储管理 3．某虚拟存储器系统采用页式内存管理，使用LRU页面替换算法，考虑下面的页面地址访问流： 1，8，1，7，8，2，7，2，1，8，3，8，2，1，3，1，7，1，3 假定内存容量为4个页面，开始时是空的，则缺页中断的次数A．4 B．5 C．6 D．7 4．最佳适应算法的空闲块链表是 A．按大小递减顺序连在一起B．按大小递增顺序连在一起C．按地址由小到大排列D．按地址由大到小排列5．在可变分区存储管理中的紧凑技术可以 A．集中空闲区B．增加内存容量 C．缩短访问周期D．加速地址转换 6．在固定分区分配中，每个分区的大小是 A．相同B．随作业长度变化 C．可以不同但预先固定D．可以不同但根据作业长度固定7．实现虚拟存储管理的目的是 A．实现存储保护B．实现程序浮动 C．扩充辅存容量D．扩充内存容量 8．采用分段存储管理的系统中，若地址是24位表示，其中8位表示段号，则允许每段的最大长度是 A．224B．216C．28 D．232 9．把作业地址空间使用的逻辑地址变成内存的物理地址称为A．加载B．重定位C．物理化D．逻辑化10．在段页式存储管理系统中，内存等分成程序按逻辑模块划分成若干 A．块B．基址C．分区D．段E．页号F．段长11．虚拟存储管理系统的基础是程序的理论 A．局部性B．全局性C．动态性D．虚拟性12．以下存储管理方式中，不适用于多道程序设计系统的是A．单用户连续分配B．固定式分区分配 C．可变式分区分配D．页式存储管理 13．在可变分区分配方案中，某一道作业完成后，系统收回其在内存空间并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数减1的情况是 A．无上邻空闲区也无下邻空闲区 B．有上邻空闲区但无下邻空闲区 C．无上邻空闲区但有下邻空闲区 D．有上邻空闲区也有下邻空闲区 处理器调度习题 处理器调度 选择题 ?当CPU执行操作系统代码时，则处理机处于( )。 ?A．执行态 B．目态 C．管态 D．就绪态 ?( )是机器指令的扩充，是硬件的首次延伸，是加在硬件上的第一层软件。 ?A．系统调用 B．操作系统 C．内核 D．特权指令 ?操作系统提供给程序员的接口是( )。 ?A．进程 B．系统调用 C．库函数 D．B和C ?用户程序向系统提出使用外设的请求方式是( )。 ?A．作业申请 B．原语 C．系统调用 D．I／O指令 ?当作业正常完成进入完成状态时，操作系统( )。 ?A．将输出该作业的结果并删除内存中的作业 ?B．将收回该作业的所占资源并输出结果 ?C．将收回该作业的所占资源及输出结果，并删除该作业 ?D．将收回该作业的所占资源及输出结果，并将它的控制块从当前的队列中删除 ?下列选项是关于作业和进程关系的描述，其中哪一个是不正确的( )。 ?A．作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的OS中。 ?B．作业是比进程低一级的概念。 ?C．一个作业至少由一个进程组成。 ?D．作业是用户向计算机提交任务的实体，而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 ?作业从后备作业到被调度程序选中的时间称为( )。 ?周转时间B．响应时间C．等待调度时间D．运行时间 ?设有三个作业J1，J2，J3，它们同时到达，运行时间分别为T1，T2，T3，且T1≤T2≤T3，若它们在一台处理机上按单道运行，采用短作业优先算法，则平均周转时间为( )。 ?A．T1+T2+T3 B．1／3(T1+T2+T3) ?C．T1+2／3T2+1／3T3 D．T1+1／3T2+2／3T3 ?从作业提交给系统到作业完成的时间间隔称为作业的( )。 ?A．中断时间 B．等待时间 C．周转时间 D．响应时间 ?设有四个作业同时到达，每个作业执行时间均为2 h，它们在一台处理机上按单道方式运行，则平均周转时间为( )。 ?A．1 h B．5 h C．2．5 h D．8 h ?FCFS调度算法有利于( )。 ?A．长作业和CPU繁忙型作业 B．长作业和I／O繁忙型作业 ?C．短作业和CPU繁忙型作业 D．短作业和I／O繁忙型作业 ?下列哪种说法不是SJ(P)F调度算法的缺点( )。 ?A．对于长作业(进程)不利 ?B．未考虑作业(进程)的紧迫程度 ?C．不能有效降低作业(进程)的平均等待时间 ?D．由于根据的是用户提供的估计执行时间，因此不一定真正做到短而优先。 ?选择排队进程中等待时间最长的进程被优先调度，该调度算法是( )。 ?A．先来先服务调度算法B．短进程优先调度算法 ?C．优先权调度算法D．高响应比优先调度算法 ?在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和( )相同。 ?A．先来先服务调度算法B．短进程优先调度算法 多处理机系统介绍 随着用户计算需求的增长，多处理系统能够提供一个自然地、不断提高的升级途径。只要核心的用户程序能够提供线程级并行，给系统添加处理器，或者将较小的系统替换为较大的、包含更多处理器的系统，都能给用户提供一个直接增加计算能力的途径。其次，多处理机系统使系统供应商能够将单个微处理器的设计代价分摊到多种设计方案中，这些设计方案能够提供不同层次的性能和扩展能力。最后，使用一致共享存储器的多处理机系统能够提供与分时共享的但处理机兼容的编程模式，便于用户使用以前已经存在的应用程序，也便于开发新的应用程序。在这些系统中，硬件和操作系统软件综合起来提供给用户和程序员的功能界面，实际上是基于以下4点多处理机理想假设: 完全共享存储器即系统中所有处理机对所有物理存储器的访问都是平等的。 单位延迟即所有的访存请求都能在一个周期内满足。 无竞争即一个处理机的访存不会受到另一个处理机访存的影响。 写的瞬间船舶即某个处理机写存储器导致的更新立刻对所有的处理机可见。 系统及处理机的设计者必须努力使系统尽量接近这些理想假设，从而满足用户对于性能和正确性的要求。显然，在实现这些目标时，诸如造价以及可扩展性等因素起着重要作用，但是一个优秀的系统必须很好的满足这些假设。 完全共享存储器，单位延迟以及无竞争 诸如图9.4所示，大多数提供一致存储器访问（UMA，Uniform Memory Access）的传统共享存储器多处理机系统使用一种“dancehall”的组织结构，一组存储器模块或者存储体通过交叉开关互联网络与另一组处理机连接起来，并且每个处理机通过交叉开关访问存储器的延迟是相通的。这种方法的弊端在于交叉开关的价格，该价格会随着处理机和存储器的总数按平方增长，同时每次访存都必须穿过交叉开关，另一种方法是非一致存储访问(NUMA,Nonuniform Memory Access),许多系统供应商现在都按照这种方法构造系统，在这种方法中，处理机仍然通过一个交叉开关互联网络连接在一起，但是每个处理机有一个本地的存储器，它的访问延迟要低得多，在NUMA结构中，只有对远程存储器的访问才存在穿越交叉开关的延迟开销。 在UMA和NUMA系统中，与单处理机系统一样，都是通过cache来近似满足单位延迟的理想假设，cache能够同时满足对本地和远程存储器（NUMA）的访问，类似的，可以使用cache 对访存流量进行过滤减轻存储体之间的竞争。因此，对于在单处理机系统中不可缺少的cache， 1.下表给出作业1、2、3到达时间和运行时间。采用短作业优先调度算法和先来先 服务调度算法，试问平均周转时间各为多少？是否还有更好的调度策略存在？（时间单位：小时，以十进制进行计算。） 2.假设有四个作业,它们提交、运行时间如下表所示。若采用响应比高者优先调度算 法，试问平均周转时间和带权周转时间为多少？（时间单位：小时，以十进制进行计算。） a、 b、c，且满足a＜b＜c，试证明采用短作业优先调度算法能获得最小平均周转时间。 4.在单CPU和两台输入/输出设备(I1,I2)的多道程序设计环境下,同时投入三个作业 Job1、Job2、Job3运行。这三个作业对CPU和输入/输出设备的使用顺序和时间如下所示： Job1: I2(30ms);CPU(10ms);I1(30ms);CPU(10ms);I2(20ms|) Job2: I1(20ms);CPU(20ms); I2(40ms|) Job3: CPU(30ms);I1(20ms);CPU(10ms);I1(10ms|) 假定CPU 、I1、I2都能并行工作，Job1优先级最高，Job2次之，Job3优先级最低，优先级高的作业可以抢占优先级低的作业的CPU但不抢占I1和I2。试求： （1）三个作业投入到完成分别需要的时间。 （2）从投入到完成的CPU利用率。 （3）I/O设备利用率 1.对下面的5个非周期性实时任务,按最早开始截止时间优先权调度算法应如何进行 A要求每20ms执行一次,执行时间为10ms;任务B要求50ms执行一次,执行时间为10ms;任务C要求 50ms执行一次,执行时间为15ms,应如何按最低松弛度优先算法对它们进行 CPU调度? 5.某系统有R1、R2和R3共3种资源，在T0时刻P1、P2、P3和P4 这4 个进程对资源的占用和需求情况见下表，此时系统的可用资源向量为（2，1， 2），问题： ①将系统中各种资源总数和此刻各进程对各资源的需求数目用向量或矩阵 表示出来； ②如果此时P1和P2均发出资源请求向量Request(1,0,1),为了保证系统的安 全性，应该如何分配资源给这两个进程，说明你所采用策略的原因。 6假定某计算机系统有R1(2)、R2(1)两类可再使用资源,它们被进程P1、P2所共享,两个进程均以下列顺序使用资源: ?申请R1?申请R2?申请R1?释放R1?释放R2?释放R1 ? 试求出系统可能到达的死锁点，并画出死锁点的资源分配图。 实验报告 学院（系）名称：计算机与通信工程学院 姓名学号专业计算机科学与技术班级2009级3班实验项目实验一：处理机调度算法的实现 课程名称操作系统课程代码0668036 实验时间2011 年11月17日第3、4节 2011 年11月21日第7、8节 2011 年11月24日第3、4节 实验地点软件实验室7-216 批改意见成绩 教师签字： 实验内容： 1．设定系统中有五个进程，每一个进程用一个进程控制块表示。 2．输入每个进程的“优先数”和“要求运行时间”。 3．为了调度方便，将五个进程按给定的优先数从大到小连成就绪队列。用一单元指出队列首进程，用指针指出队列的连接情况。 4．处理机调度总是选队首进程运行。采用动态优先数算法，进程每运行一次优先数就减“1”，同时将运行时间减“1”。 5．若某进程运行时间为零，则将其状态置为“结束”,且退出队列。 6．运行所设计程序，显示或打印逐次被选中进程的进程名，以及进程控制块的动态变化过程。 实验要求： 1．详细描述实验设计思想、程序结构及各模块设计思路； 2．详细描述程序所用数据结构及算法； 3．明确给出测试用例和实验结果； 4．为增加程序可读性，在程序中进行适当注释说明； 5．认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等； 6．实验报告撰写要求结构清晰、描述准确逻辑性强； 7．实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。 【实验过程记录（源程序、测试用例、测试结果及心得体会等）】 程序运行代码如下： #include 多处理机操作系统 【摘要】本文通过对操作系统的发展对引入多操作系统的原因和采用多处理机操作系统的优点进行了阐述。分别对多处理机操作系统的三种模式类型分别就其工作原理和特点进行了详细说明。随后对多处理机操作系统的共享公用存储器的实现方法进行了阐述，即处理机和存储器的几种连接方式的优缺点和实现原理进行了说明。 【summary】In this paper, the development of the operating system into multiple operating systems on the causes and the use of the advantages of multiprocessor operating system has been described. Multiprocessor operating systems, respectively, for the three model types in respect of its working principle and characteristics are described in detail. Then the multi-processor operating system share a common memory implementation are described,The processor and memory advantages and disadvantages of several connections and implementation principles described 【关键词】多处理机操作系统、主从式(master-slave)、 独立监督式(separate supervisor) 浮动监督式(floating superviso)、公用存储器、 操作系统经过上个世纪60、70年代的发展，到了本世纪80年代已趋于成熟，随着VLSI和计算机体系结构的发展，操作系统随之发展，形成了多处理机操作系统、微机操作系统、网络操作系统、分布式操作系统和嵌入式操作系统等。 从广义上说，多处理机操作系统，就是由多台计算机协同工作来完成所要求的任务的计算机系统操作系统。而传统的侠义上，多处理机系统的作用是利用系统内的多个CPU来并行执行用户的多个指令。这样做的优点有三。 第一、利用多个处理机提供在发生故障的情况下的冗余性，建立高度可靠的系统。 第二、将程序可以分成几个能作为进程独立执行的部分，减少程序执行的时间。 第三、通过并行执行多个用户程序，增加系统的吞吐量。 多个CPU在物理位置上处于同一机壳中，有一个单一的系统物理地址空间和每一个CPU均可访问系统内的所有存储器是其显著的特点。 引入多处理机系统的原因有以下三点： 1、增加系统的吞吐量 2、节省投资 3、提高系统的可靠性 多处理机操作系统的模式类型可分为三种： 1、主从式(master-slave)主从式操作系统即由一台主处理机记录、控制 其它从处理机的状态，并分配任务给从处理机。操作系统在主处理机 上运行，从处理机的请求通过陷入传送给主处理机，然后主处理机回 答并执行相应的服务操作。主从式操作系统的特点有如下几个特点： 1）：由于只有一个处理机访问执行表，所以不存在管理表格存取冲突 和访问阻塞问题。 2）：操作系统程序只在一台处理机上运行。 《Linux系统管理与维护》实验指导书 实验一初识Linux操作系统 一实验名称 初识Linux操作系统 二实验目的与要求 掌握Linux的启动、登录与注销。 三实验内容 1.以root用户和普通用户两种不同身份登录Linux，说出其登录后得差异。 2.图形模式下的注销、重启与关机。 3.学会在虚拟机上登录和注销Linux。 四操作步骤与结果分析 五问题与建议 实验二Linux的桌面应用 一实验名称 Linux的桌面应用 二实验目的与要求 熟悉Linux操作系统桌面环境 熟悉Linux文件系统及常用的操作 掌握Linux下使用外部存储设备、网络设备 掌握Linux下安装应用程序 三实验内容 1.查看GNOME提供的“应用程序”、“位置”或者“系统”菜单，运行其中的应用程 序和工具。 2.查看Linux文件目录结构，学会常用的文件目录操作，如复制、粘贴、移动、删 除、更名、创建文档、创建文件夹等。 3.练习在Linux下使用光盘和U盘。 4.学会网络配置，使计算机能够进行网络浏览等操作。 5.学会在Linux下安装新的应用软件。 四操作步骤与结果分析 五问题与建议 实验三Linux操作系统的安装 一实验名称 Linux操作系统的安装 二实验目的与要求 掌握安装Linux操作系统 三实验内容 1.通过学习《项目五Linux操作系统的安装及远程服务》的内容，学会如何安装Linux。 环境：windows 系统、vmware虚拟机、Redhat Linux镜像光盘。 通过安装向导将安装分为两步：1、基本安装，2、配置及具体安装。 在第一阶段重点如何分区，在第二阶段重点掌握如何设置密码及安装桌面环境。四操作步骤与结果分析 五问题与建议 《操作系统》复习提纲与要求 一、《操作系统》试题类型 二、《操作系统》重点和难点 三、《操作系统》各章节复习 一、《操作系统》试题类型 计算机专业： 1.填空题 2.选择题 3 判断题 4.简答题 5应用题 二、《操作系统》重点和难点 第1章操作系统引论 内容概要： 1. 操作系统的目标 2. 操作系统的发展过程 3. 操作系统的特征和服务 4. 操作系统的功能 5. 操作系统的进一步发展 重点： 1. 操作系统的目标 2. 操作系统的特征和服务第2章进程管理 内容概要： 1.前趋图和程序执行 2.进程的描述 3.进程的控制 4.线程的基本概念 重点： 1.进程的描述 2.进程的控制 3.线程的基本概念 进程的同步与通信 内容概述： 1.进程同步的基本概念 2.信号量机制 3.经典进程同步问题 4 .进程通信 重点： 1.进程同步的基本概念 2.信号量机制 3.经典进程同步问题 4.进程通信 第2章处理机调度和死锁 内容概要： 1.调度的类型和模型 2.调度算法 3.死锁的基本概念 4.死锁的预防和避免 5.死锁的检测和解除 重点： 1.调度的类型和模型 2.调度算法 3.死锁的基本概念 4.死锁的预防和避免 5.死锁的检测和解除 第3章存储器管理 内容概要： 1.程序的装入和链接 2.连续分配存储管理方式 3.分页存储管理方式 4.分段存储管理方式 重点： 1.连续分配存储管理方式 2.分页、分段存储管理方式 第3章虚拟存储器 内容概要： 1.虚拟存储器的基本概念 2.请求分页式存储管理方式 3.页面置换算法 4.请求分段存储管理方式 重点： 1. 虚拟存储器的基本概念 2.请求分页式存储管理方式 3.页面置换算法 4磁盘存储器管理 第4章文件管理 内容概要: 1.文件和文件系统 2.文件逻辑结构 3.目录管理 4.文件共享 5.文件保护 重点： 1.文件和文件系统有关概念 2.文件逻辑结构的类型和文件的检索 实验2 处理机调度 一、实验要求 ●了解引起处理机调度的原因 ●分析先来先服务算法，给出代码注释 二、实验内容 进程调度算法的数据结构主要有：进程函数定义，建立进程函数，进程调度函数。示例： #include "stdio.h" #include p=(pcb*)malloc(sizeof(pcb)); p->name=ID; p->ax=a; p->bx=b; p->cx=c; p->dx=d; p->pc=m; p->psw=n; p->precendence=pre; p->status=aready; if(head==NULL) head=p; else q->next=p; q=p; printf("\ninput the next pcb: "); scanf("\n%c",&ID); scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&m,&n); } if(q!=NULL) q->next=NULL; q=head; while(q) { printf("\n peocess name. status.ax. bx. cx. dx. pc. psw.\n "); printf("%10c%5d%8d%5d%5d%5d%5d%5d%5d",q->name,q->status,q->precende nce,q->ax,q->bx,q->cx,q->dx,q->pc,q->psw); q=q->next; } return head;/*createprocess end*/ } void processfifo(pcb *head) { pcb *p; p=head; printf("\n the process use fifo method.\n"); printf("running the frist process:\n"); while(p!=NULL) { p->status=running; printf("\nprocess name status. ax. bx. cx. dx. pc. psw."); printf("\n%10c%5d%8d%5d%5d%5d%5d%5d",p->name,p->status,p->ax,p->bx, p->cx,p->dx,p->pc,p->psw); /*check process running status */ 第四章处理机调度 一. 选择最合适的答案 1．某系统采用了银行家算法，则下列叙述正确的是（）。 A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁 C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁 2．银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项正确的是（）。 **[i,j]=Allocation[i,j]+Need[i,j] **[i,j]= Allocation[i,j]+ Max[i,j] **[i,j]= Available[i,j]+Need[i,j] **[i,j]= Available[i,j]+ Max[i,j] 3．下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。 A.非抢占式静态优先权法 B.抢占式静态优先权法 C.时间片轮转调度算法 D.非抢占式动态优先权法 4．在下列选项中，属于预防死锁的方法是（）。 A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法 5．在下列选项中，属于检测死锁的方法是（）。 A.银行家算法 B.消进程法 C.资源静态分配法 D.资源分配图简化法 6．在下列选项中，属于解除死锁的方法是（）。 A．剥夺资源法 B.资源分配图简化法 C．银行家算法 D.资源静态分配法 7．为了照顾紧迫型作业，应采用（）。 A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法 8．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和（）相同。 A.先来先服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.长作业优先调度算法 实验5 文件系统：Linux文件管理 1．实验目的 （1）掌握Linux提供的文件系统调用的使用方法； （2）熟悉文件和目录操作的系统调用用户接口； （3）了解操作系统文件系统的工作原理和工作方式。 2．实验内容 （1）利用Linux有关系统调用函数编写一个文件工具filetools，要求具有下列功能：*********** 0. 退出 1. 创建新文件 2. 写文件 3. 读文件 4. 复制文件 5. 修改文件权限 6. 查看文件权限 7. 创建子目录 8. 删除子目录 9. 改变当前目录到指定目录 10. 链接操作 *********** 代码： #include menu(); scanf("%d",&choose); while(choose!=0) { switch(choose) { case 1:openfile();break; case 2:writefile();break; case 3:readfile();break; case 4:copyfile();break; case 5:chmd();break; case 6:ckqx();break; case 7:cjml();break; case 8:scml();break; case 9:ggml();break; case 10:ylj();break; } menu(); scanf("%d",&choose); } return 0; } void menu(void) { printf("文件系统\n"); printf("1.创建新文件\n"); printf("2.写文件\n"); printf("3.读文件\n"); printf("4.复制文件\n"); printf("5.修改文件权限\n"); printf("6.查看文件权限\n"); printf("7.创建子目录\n"); printf("8.删除子目录\n"); printf("9.改变目前目录到指定目录\n"); printf("10.链接操作\n"); printf("0.退出\n"); printf("请输入您的选择...\n"); } void openfile(void) { int fd; if((fd=open("/tmp/hello.c",O_CREAT|O_TRUNC|O_RDWR,0666))<0) perror("open");操作系统_ 处理机调度
操作系统 多处理机习题
LINUX操作系统实验报告
操作系统处理器调度算法C++程序
Linux操作系统实验教程
处理机管理复习_1
模拟一种处理机调度算法讲解
操作系统原理第四章 处理机调度习题
操作系统课后习题答案第四章存储器管理习题.doc
处理器调度习题教学内容
多处理机系统介绍(翻译)
操作系统处理机调度练习题
操作系统实验一处理机调度算法的实现
多处理机操作系统论文
Linux操作系统实验指导书
操作系统复习提纲与要点
操作系统 之 处理机调度
操作系统原理-第四章处理机调度习题
操作系统实验5文件系统：Linux文件管理
相关主题
文本预览