操作系统rr算法例题

操作系统例题讲解

一、调度算法

对如下表所示的5个进程：

进程 P1 P2 P3 P4 P5 到达时间（ms） 2 0 4 0 5 优先级 3 1 4 2 5 CPU阵发时间（ms） 3 2 3 4 2 采用可剥夺的静态最高优先数算法进行调度（不考虑系统开销）。 问 题： ⑴ 画出对上述5个进程调度结果的Gantt图；

⑵ 计算5个进程的平均周转时间、平均带权周转时间。

解： ⑴ 调度结果的Gantt图如下： 0

P4 2

P1 4 P3 5 P5 7

P3 9 P1 10

P4 12

P2 14

(2) 时间计算： 进程 P1 P2 P3 P4 P5 到达时间 （ms） 2 0 4 0 5 优先级 3 1 4 2 5 运行时间 （ms） 3 2 3 4 2 开始时间 （ms） 2 12 4 0 5 完成时间 （ms） 10 14 9 12 7 周转时间（ms） 8 14 5 12 2 带权周转时间（ms） 8/3 7 5/3 3 1 平均周转时间=(8+14+5+12+2)/5=41/5=8.2 (ms) 平均带权周转时间=(8/3+7+5/3+3+1)/5=46/15≈3.07(ms)

二、存储管理

某系统采用虚拟页式存储管理方式

中山纪念中学信息学奥林匹克算法设计题选

算法设计题选

（一）、算法设计：

一、筛选法

1：求1—100间的所有素数。

分析：用筛选法，先把2—100的数存到一个数组中，然后先把2的所有倍数删除掉（即让此数变为0），再删3的倍数，继续往上就是5的倍数，7的倍数??，最后，剩下的数(即数组中不为0的数)就是素数。 Var n:array[2..100] of integer; I,j,k:integer; Begin For I:=2 to 100 do n[I]:=I; I:=2; Repeat J:=1; Repeat J:=j+1; K:=I*j; if n[k]>0 then N[k]:=0; Until (j+1)*i>100; Repeat i:=i+1; until (n[i]>0) or (i>50); Until i>50; for i:=2 to 100 do if n[i]>0 then write(n[i]:4); end. 另外，该题也可利用集合来做，同样用筛选法： var

一、选择题

1．当（ ）时，进程从执行状态转变为就绪状态。 A．进程被调度程序选中 B。时间片到 C．等待某一事件 D。等待的事件发生 2．操作系统中，wait、signal操作是一种（ ） A．机器指令 B．系统调用命令 C．作业控制命令 D．低级进程通信原语 3. 下面对进程的描述中，错误的是（ ）。

A.进程是动态的概念 B.进程执行需要处理机 C.进程是有生命期的 D.进程是指令的集合

4. 下列各项工作步骤中，（ ）不是创建进程所必需的步骤。 A.建立一个PCB B.作业调度程序为进程分配CPU C.为进程分配内存等资源 D. 将PCB链入进程就绪队列 5. 下列关于进程的叙述中，正确的是（ ）。 A.进程通过进程调度程序而获得CPU。

B.优先级是进行进程调度的重要依据，一旦确定不能改变。 C.在单CPU系统中，任一时刻都有1个进程处于运行状态。 D.进程申请CPU得不到满足时，其状态变为等待状态。 6. 有m个进程共享同一临界资源，若使用信号量

1．2例题精选

例1.1如何理解虚拟机的概念？

解:一台仅靠由硬件组成的计算机一般被称为裸机，不易使用。操作系统为用户使用计算机提供了许多服务，从而把一台难于使用的裸机改造成了功能更强大、使用更方便的计算机系统，这种计算机系统称为虚拟机。所谓虚拟，是指把一个物理上的实体变为若干个逻辑上的对应物。前者是实际存在的，而后者是虚的，只是用户的一种感觉。在单CPU的计算机系统中能同时运行多道程序，好像每个程序都独享一个CPU，这就是虚拟。在构造操作系统时，把操作系统分成若干层，每层完成特定的功能，从而形成一个虚拟机。下层的虚拟机为上层的虚拟机提供服务，这样逐次扩充以完成操作系统的功能。

讨论 “虚拟”的概念体现在操作系统的方方面面。例如，虚拟存储器，使一台只有4MB内存的计算机可以运行总容量远远超过4 MB的程序；虚拟外设，能够使多个用户同时访问该外设等。

例1.2什么是多道程序设计，它的主要优点是什么？

解: 所谓多道程序设计是指把一个以上的程序存放在内存中，并且同时处于运行状态，这些程序共享CPU和其他计算机资源。其主要优点是：

（1）CPU的利用率高：在单道程序环境下，程序独占计算机资源，当程序

一、选择题

1．当（ ）时，进程从执行状态转变为就绪状态。 A．进程被调度程序选中 B。时间片到 C．等待某一事件 D。等待的事件发生 2．操作系统中，wait、signal操作是一种（ ） A．机器指令 B．系统调用命令 C．作业控制命令 D．低级进程通信原语 3. 下面对进程的描述中，错误的是（ ）。

A.进程是动态的概念 B.进程执行需要处理机 C.进程是有生命期的 D.进程是指令的集合

4. 下列各项工作步骤中，（ ）不是创建进程所必需的步骤。 A.建立一个PCB B.作业调度程序为进程分配CPU C.为进程分配内存等资源 D. 将PCB链入进程就绪队列 5. 下列关于进程的叙述中，正确的是（ ）。 A.进程通过进程调度程序而获得CPU。

B.优先级是进行进程调度的重要依据，一旦确定不能改变。 C.在单CPU系统中，任一时刻都有1个进程处于运行状态。 D.进程申请CPU得不到满足时，其状态变为等待状态。 6. 有m个进程共享同一临界资源，若使用信号量

1．2例题精选

例1.1如何理解虚拟机的概念？

解:一台仅靠由硬件组成的计算机一般被称为裸机，不易使用。操作系统为用户使用计算机提供了许多服务，从而把一台难于使用的裸机改造成了功能更强大、使用更方便的计算机系统，这种计算机系统称为虚拟机。所谓虚拟，是指把一个物理上的实体变为若干个逻辑上的对应物。前者是实际存在的，而后者是虚的，只是用户的一种感觉。在单CPU的计算机系统中能同时运行多道程序，好像每个程序都独享一个CPU，这就是虚拟。在构造操作系统时，把操作系统分成若干层，每层完成特定的功能，从而形成一个虚拟机。下层的虚拟机为上层的虚拟机提供服务，这样逐次扩充以完成操作系统的功能。

讨论 “虚拟”的概念体现在操作系统的方方面面。例如，虚拟存储器，使一台只有4MB内存的计算机可以运行总容量远远超过4 MB的程序；虚拟外设，能够使多个用户同时访问该外设等。

例1.2什么是多道程序设计，它的主要优点是什么？

解: 所谓多道程序设计是指把一个以上的程序存放在内存中，并且同时处于运行状态，这些程序共享CPU和其他计算机资源。其主要优点是：

（1）CPU的利用率高：在单道程序环境下，程序独占计算机资源，当程序

1操作系统引论

1、什么是操作系统，它的主要功能是什么？

关于操作系统，至今沿无严格的统一的定义，对操作系统的定义有各种说法，不同的说法反映了人们从不同的角度所揭示的操作系统的本质特征。

（1）从资源管理的角度，操作系统是控制和管理计算的软、硬件资源，合理地组织计算机的工作流程以及方便用户的程序集合。

（2）从硬件扩充的角度，操作系统是控制和管理计算机裸机之上的第一层软件，是对计算机硬件功能的一次扩充。

操作系统的主要功能有处理机管理、内存管理、设备管理文件管理等功能，以及用户接口。

2、什么是多道程序设计技术？多道程序设计技术的主要特点是什么？ 多道程序设计技术就是把多个程序同时放入内存，它们共享系统中的各种资源，并发地在处理机上运行。 特点如下：

（1）多道，即计算机内存中同时存入多道相互独立的程序。

（2）宏观上并行，是指同时进入系统的多道程序都处于运行过程中。

（3）微观上串行，是指在单处理机环境下，内存中的多道程序轮流地占有CPU，交替执行。

3、批处理系统是怎样的一种操作系统？它的特点是什么？

批处理系统是一种基本的操作系统类型。在该系统中，用户的作业（包括程序、数据及程序的处理步骤）被成批地输入到计算机中，然后在操作系统的控制下

1操作系统引论

1、什么是操作系统，它的主要功能是什么？

关于操作系统，至今沿无严格的统一的定义，对操作系统的定义有各种说法，不同的说法反映了人们从不同的角度所揭示的操作系统的本质特征。

（1）从资源管理的角度，操作系统是控制和管理计算的软、硬件资源，合理地组织计算机的工作流程以及方便用户的程序集合。

（2）从硬件扩充的角度，操作系统是控制和管理计算机裸机之上的第一层软件，是对计算机硬件功能的一次扩充。

操作系统的主要功能有处理机管理、内存管理、设备管理文件管理等功能，以及用户接口。

2、什么是多道程序设计技术？多道程序设计技术的主要特点是什么？ 多道程序设计技术就是把多个程序同时放入内存，它们共享系统中的各种资源，并发地在处理机上运行。 特点如下：

（1）多道，即计算机内存中同时存入多道相互独立的程序。

（2）宏观上并行，是指同时进入系统的多道程序都处于运行过程中。

（3）微观上串行，是指在单处理机环境下，内存中的多道程序轮流地占有CPU，交替执行。

3、批处理系统是怎样的一种操作系统？它的特点是什么？

批处理系统是一种基本的操作系统类型。在该系统中，用户的作业（包括程序、数据及程序的处理步骤）被成批地输入到计算机中，然后在操作系统的控制下

1操作系统引论

1、什么是操作系统，它的主要功能是什么？

关于操作系统，至今沿无严格的统一的定义，对操作系统的定义有各种说法，不同的说法反映了人们从不同的角度所揭示的操作系统的本质特征。

（1）从资源管理的角度，操作系统是控制和管理计算的软、硬件资源，合理地组织计算机的工作流程以及方便用户的程序集合。

（2）从硬件扩充的角度，操作系统是控制和管理计算机裸机之上的第一层软件，是对计算机硬件功能的一次扩充。

操作系统的主要功能有处理机管理、内存管理、设备管理文件管理等功能，以及用户接口。 2、什么是多道程序设计技术？多道程序设计技术的主要特点是什么？

多道程序设计技术就是把多个程序同时放入内存，它们共享系统中的各种资源，并发地在处理机上运行。 特点如下：

（1）多道，即计算机内存中同时存入多道相互独立的程序。

（2）宏观上并行，是指同时进入系统的多道程序都处于运行过程中。

（3）微观上串行，是指在单处理机环境下，内存中的多道程序轮流地占有CPU，交替执行。 3、批处理系统是怎样的一种操作系统？它的特点是什么？

批处理系统是一种基本的操作系统类型。在该系统中，用户的作业（包括程序、数据及程序的处理步骤）被成批地输入到计算机中，然后在操作系统的控制下

问题1 一个司机与售票员的例子

在公共汽车上，为保证乘客的安全，司机和售票员应协调工作：

停车后才能开门，关车门后才能行车。用PV操作来实现他们之间的协调。 S1：是否允许司机启动汽车的变量 S2：是否允许售票员开门的变量 driver()//司机进程 {

while (1)//不停地循环 {

P(S1);//请求启动汽车 启动汽车; 正常行车； 到站停车；

V(S2); //释放开门变量，相当于通知售票员可以开门 } }

busman()//售票员进程 {

while(1) {

关车门;

V(S1)；//释放开车变量，相当于通知司机可以开车 售票

P(S2)；//请求开门 开车门； 上下乘客； } }

注意：busman() driver() 两个不停循环的函数

问题2 图书馆有100个座位，每位进入图书馆的读者要在登记表上登记，退出时要在登记表上注销。要几个程序？有多少个进程？（答：一个程序；为每个读者设一个进程）

（1） 当图书馆中没有座位时，后到的读者在图书馆为等待（阻塞） （2） 当图