操作系统经典算法

1．什么是操作系统？它在计算机中的地位如何？其功能有哪些？ 参考答案：操作系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。

操作系统是计算机系统中最靠近硬件的一层软件，它支持和管理硬件，与具体的应用领域无关，在计算机系统的所有软件中，操作系统是基础，其它软件只有在操作系统的支持下，才能发挥作用。它是计算机硬件和其它软件以及计算机用户之间的联系纽带，如果没有操作系统，用户几乎无法使用计算机系统。

从资源管理的观点看，操作系统具有五个方面的功能：处理器管理、存储器管理、设备管理、文件管理和提供用户接口。这五大部分相互配合，协调工作，实现计算机系统的资源管理、控制程序的执行、并为用户提供方便的使用接口。

2．操作系统有哪几种类型？各有什么特点？ 参考答案：操作系统是随着计算机硬件技术的不断发展和用户的使用要求的提高而从无到有不断完善起来的，其主要类型及其特点如下：

（1） 批处理操作系统：具有很高的资源利用率和系统吞吐量，但作业的平均周转时

间较长，也没有交互性。

（2） 分时操作系统：具有多路性、独立性、及时性和交互性特征，而交互性是其最

重要的特征之一。

（3） 实时操作系统：实时操作系统

操作系统经典问题介绍

一 生产者-消费者问题扩展 1.扩展一

设有一个可以装A、B两种物品的仓库,其容量无限大，但要求仓库中A、B两种物品的数量满足下述不等式：-M≤（A物品数量－B物品数量）≤N其中M和N为正整数。试用信号量和PV操作描述A、B两种物品的入库过程。

问题分析：

若只放入A，而不放入B，则A产品最多可放入N次便被阻塞；若只放入B，而不放入A，则B产品最多可放入M次便被阻塞；每放入一次A，放入产品B的机会也多一次；同理，每放入一次B，放入产品A的机会也多一次。

The P,V code Using Pascal

Semaphore mutex=1，sa=N，sb=M; cobegin

procedure A: procedure B: while(TURE) while(TURE) begin begin p(sa); p(sb); p(mutex);

实验六磁盘调度算法

1、实验目的

通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。

2、试验内容

问题描述：

设计程序模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN 和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。

3、程序要求：

1）利用先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法模拟磁道访问过程。

2）模拟四种算法的磁道访问过程，给出每个磁道访问的磁头移动距离。

3）输入：磁道个数n和磁道访问序列，开始磁道号m和磁头移动方向（对SCAN 和循环SCAN算法有效），算法选择1-FCFS，2-SSTF，3-SCAN，4-循环SCAN。

4）输出：每种算法的平均寻道长度。

4、需求分析

(1) 输入的形式和输入值的范围

算法选择

要访问的磁道数

磁道

当前磁道号

输入当前移动臂的移动的方向（第三个算法）

(2) 输出的形式

每种算法的平均寻道长度

(3)测试用例

先来先服务FCFS

最短寻道时间优先

习题：

1. 进程同步，信号量机制实现

设有6个程序s1,?, s6，它们在并发系统中执行时如图所示的制约关系，试用wait和signal原语来实现它们之间的同步。（10分）

S5 S2 S3 S4 S1

Var a, b, c, d, e, f, g, h; semaphore:= 0, 0, 0, 0, 0, 0, 0; begin

parbegin

begin S1; signal(a); signal(b);signal(c); end; begin wait(a); S2; signal(d); end; begin wait(b); S3; signal(f); end; begin wait(c); S4; signal(g); end;

begin wait(d); S5; signal(e); end;

begin wait(e); wait(f); wait(g); S6; end;

parend end

S6 2. 进程同步，信号量机制实现。详见上课讲的例题 3. 有如下进程，后一个依次比前

v1.0 可编辑可修改

1、设有两个优先级相同的进程P1，P2如下所示。令信号量S1，S2的初值为0，试问P1，P2并发运行结束后，x= ,y= ,z=

进程P1 进程P2

y:=1; x:=1;

y:=y+2; x:=x+1;

V(S1); P(S1);

z:=y+1; x:=x+y;

P(S2); V(S2);

y:=x+y z:=x+z

X=5, y＝8， Z＝ 9.

2、在生产者-消费者问题中，假定在生产者和消费者之间的公用缓冲池中有n 个缓冲区，可利用互斥信号量mutexP使生产者进程实现对缓冲池的互斥使用，利用互斥信号量mutexC使消费者进程实现对缓冲池的互斥使用；利用资源信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将产品送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个产品。试用记录型信号量正确实现生产者和消费者的同步。

Semapho

实验七 操作系统页面调度算法

一、实验项目名称：

操作系统页面调度算法

二、实验目的和要求：

目的：对操作系统中使用的页面调度算法进行设计。

要求：对教材中所讲述的几种页面调度算法进行深入的分析，通过请求页式存储管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法。

三、实验内容

1、设计两个程序模拟实现一个作业在内存中执行的页面置换，并计算缺页中断次数。

3、编制两种页面置换算法：1）FIFO页面置换算法；2）LRU页面置换算法 四、实验原理：

1、FIFO页面置换算法：总是选择在内存中驻留时间最长的一页将其淘汰。 2、LRU页面置换算法：选择最近一段时间内最长时间没有被访问过的页面予以淘汰。

五、参考程序：（提供代码，未改动）

1、FIFO页面置换算法：

#define M 4 /*m为系统分配给作业的主存中的页面数*/ #define N 15 #include void main() {

int a[M];/*定义内存页面数*/ int b[N];/*定义总页面数*/

int c[N];/*定义被淘汰的页面号*/ int i,k,flag,count,m=0;

实验名称 同组人姓名 实验日期 教师评价： 实验预习□ 实验操作□ 实验结果□ 实验报告□ 其它□ 2010-5-17 内存分配与回收算法实现 实验性质 实验成绩 □ 基本操作 ●验证性 □ 综合性 □设计性 教师签名： 一、实验目的及要求 1） 掌握为实现多道程序并发执行，操作系统是如何通过作业调度选择作业进入内存 2） 系统如何为进入内存的作业分配内存空间，实现多道作业同时驻留内存，就绪进程队列中的多个进程是如何以分式方式共享CPU，作业运行完成离开系统时，系统如何进行内存回收，计算进程周转时间。 3） 掌握各种调度算法，以及实现所需的各种数据结构。 二、实验内容 根据给定的动态分区分配算法流程图，用你熟悉的计算机编程语言编写一程序，该程序实现内存的合理分配后回收。 三、主要设备及软件 PC、Windows2000操作系统、Linux操作系统 四、实验流程、操作步骤或核心代码、算法片段 1、分配算法流程出 无法 修改有关数据结构 进行紧筹形成连续空闲区 分配返空闲分区总和>=u.size

《计算机操作系统》

课程设计报告

题 目： 银行家算法设计与实现 专 业： 软件工程 班 级： 09级（2）班 姓 名： XXX 学 号： XXX 指导老师： XXX 完成时间： 2012年2月20日

目录

一、课设题目要求 二、算法设计思路 三、主要数据结构及其说明 四、程序流程图 五、源程序代码 六、结果及数据分析 七、实验心得 八、参考资料

一、课设题目要求

模拟一个银行家算法，要求如下： 输入：

1.系统中各类资源表

2.每个进程需要各类资源总数 系统分配给各个进程各类资源数 输出：

1.判断T0时刻的安全性

2.如果系统是安全的，任意给出某个进程的一个资源请求方式并判断系统能否接受此请求，如果可以接受，其输出全部安全序列，反之，不予分配。

二、算法设计思路

银行家算法是一种最

共享资源分配与银行家算法

一、问题描述

本题主要内容是模拟实现资源分配。银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

二、基本要求

具体用银行家算法实现资源分配。要求如下：

(1) 设计一个P（例如P=3）个并发进程共享J（例如J=4）类不同资源的系统，进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。

(2) 设计用银行家算法 ，实现资源分配，应具有显示或打印各进程依次要求申请的资源数以及依次分配资源的情况。

(3) 确定一组各进程依次申请资源数的序列，输出运行结果。

三、方案设计及开发过程

1、银行家分配算法 银行家分配算法，顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行加资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，每个进程都无法继续执行下去的死锁现象。

操作系统实验二 银行家算法

实验二 银行家算法

一、实验目的:

运用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地避免死锁的发生，以加深对课堂上所讲授的知识的理解。

二、实验内容：

完成银行家算法的模拟实现：设计有m个进程共享n个系统资源的系统，进程可动态的申请和释放资源。系统按各进程的申请动态的分配资源时，采用银行家算法有效地避免死锁的发生。

三、实验准备：

1.相关理论知识： （1）银行家算法的思路

对进程的资源请求进行合法性检查；若请求合法，则进行试分配。试分配后，调用安全性检查算法进行安全性检查。若安全，则满足该进程请求，分配资源；若不安全，则拒绝该进程申请，不分配资源，并恢复系统试分配前的资源状态。

（2）银行家算法中用到的主要数据结构

可利用资源向量 int Available[j] // j为资源的种类。 最大需求矩阵 int Max[i][j] // i为进程的数量。 分配矩阵 int Allocation[i][j]

需求矩阵 int Need[i][j]= Max[i][j]- Allocation[i]