200 ～200 学年 学期 级 数学与计算机科学学院
Allocation Need Available 进 程 A B C D A B C D A B C D P0 P1 P2 P3 P4 0 0 3 2 1 0 0 0 2 5 7 6 0 3 3 2 0 0 1 4 0 0 1 2 0 4 0 0 1 7 5 0 1 1 3 4 0 6 5 2 0 6 5 6 再利用安全性算法检查系统是否安全,可用资源Available (0,4,0,0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不能将资源分配给P2。
3、假设页的大小为1K，指令LOAD 1,2500的虚地址为100。请详细说明在请求分页系统中该指令的地址变换过程。假定某时刻页表中已调入内存的页面的页号和物理块号的对照表如下： 页号 0 1 2 块号 2 3 8 解：（1）指令地址100转换
并由虚地址100可知，指令LOAD 1,2500在第0页的100单元中。由于第0页在主存的第二块中，因此，该指令在主存的地址为2048+100=2148。
（2）指令地址2500转换
当CPU执行到第2148单元的指令时，地址变换机构首先将2500转换为页号与页内地址两部分，即P=2,W=452。由页表，可知第二页所对应的主存快为8。将块号8与页内地址452相连，得到待访问的主存物理地址为8644。
4、某商店有两种食品A和B，最大数量各为m个。该商店将A、B两种食品搭配出售，每次各取一个。为避免食品变质，遵循先到食品先出售的原则。有两个食品公司分别不断地供应A、B两种食品（每次一个）。为保证正常销售，当某种食品的数量比另一种的数量超过K（K （1）共需设置几个进程？ （2）用P、V操作解决上述问题中的同步和互斥关系。 题 （ 6 ） 一、 名词解析（每题4分，共20分） 16 200 ～200 学年 学期 级 数学与计算机科学学院 1. 进程 进程是程序在一个数据集合上的运行过程。 2. 地址重定位 地址重定位是将逻辑地址转换成绝对地址。可分为静态重定位，动态重定位两种 3. 文件系统 操作系统提供的管理文件的机构。 4. 虚拟存储器 虚拟存储器就是统一管理内外存，使得用户作业或进程运行空间的大小不受内存容量的限制，从而展现在用户面前的是一个比实际内存大得多的存储器，并将其称为虚拟存储器，相应的地址空间称为虚拟地址空间。 5. 中断 二、 填空（每空1分，共20分） 1. 2. 3. 4. 5. 操作系统，通常包括处理机管理、存储管理、设备管理、文件管理、作业管理和用户接口等。 处理机管理是OS的核心程序。其中，系统调用是在管态下执行的程序。 计算机系统由软件和硬件系统组成，操作系统属于前者。硬件系统由CPU、存储器、I/O控制系统和各种外围设备组成。 存储管理的功能主要包括：内存分配、地址分配、主存空间的共享和保护、空间的扩充。 页式管理需要硬件的支持，块是主存空间分配的物理单位，页面大小决定了主存储器分块的大小。页表一般存放在主存中。页块的大小是512B~8KB。 6. 系统出现死锁的根本原因是竞争资源和进程间推进顺序都不得当造成。 7. 8. 9. 要确定磁盘上一个物理块所在的位置，需给出柱面号、磁道号和扇区号。 虚拟存储器的容量是由计算机的地址机构和可用的辅助存储器容量的大小决定的。 文件按用途分：系统文件、库文件、用户文件，按保护级分：只执行文件、只读文件、读写文件。 10. SPOOLING系统由预输入程序、井管理程序、缓输出程序组成。 三、 简述题（每小题6分，共30分） 1. 2. 3. 4. 5. 为了使并发进程能正确地执行，对临界区的管理有哪些必须遵循的原则？ 简述解决死锁问题的三种方法。 选择进程调度算法的准则是什么？ 有哪几个主要因素影响缺页中断率？ 什么是线程？多线程技术具有哪些优越性？ 四、 应用题（每小题10分，共20分） 1. 在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是：115，228， 120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题： （1）按FIFO调度算法将产生 次缺页中断，依次淘汰的页号为？缺页中断率为多少？ （2）按LRU调度算法将产生 次缺页中断，依次淘汰的页号为？ 缺页中断率为多少？ 答:页大小为100K则字地址所在的页为 1，2，1，0，4，1，3，4，2，1 (1)按FIFO调度算法将产生5次缺页中断依次淘汰的页号为：0，1，2;缺页中断率为：5/10=50% FIFO 1 1 0 1 2 2 1 0 1 1 0 4 4 2 1 1 1 3 3 4 2 1 4 2 1 1 3 4 1 缺页 6/10=60% (2)按LRU调度算法将产生6次缺页中断(2分);依次淘汰的页号为：2，0，1，3;缺页中断率为： 17 200 ～200 学年 学期 级 数学与计算机科学学院 LRU 1 1 0 1 2 2 1 0 1 1 0 4 4 1 0 1 1 3 3 1 4 1 4 2 2 4 3 1 1 1 2 4 1 缺页 2. 用PV操作解决读者写者问题的正确程序如下： begin S, Sr: Semaphore; rc: integer; S:=1; Sr:=1; rc:=0; cobegin PROCESS Reader i ( i=1,2…) begin P(Sr) rc:=rc+1; if rc=1 then P(S); V(Sr); read file; P(Sr); rc:=rc-1 if rc=0 thenV(S); V(Sr); end ; PROCESS Writer j (j=1,2…) begin P(S); Write file; V(S) end; coend ; end; 请回答： （1） 信号量 Sr的作用； （2） 程序中什么语句用于读写互斥，写写互斥； （3） 若规定仅允许5个进程同时读，怎样修改程序？ 答:(1)Sr用于读者计数rc的互斥信号量; (2)if rc=1 then P(S)中的P(S)用于读写互斥，写者进程中的P(S)用于写写互斥，读写互斥。 (3)程序中增加一个信号量S5，初值为5，P(S5)语句加在读者进程P(Sr)之前，V(S5)语句加在读者进程第2个V(Sr)之后。 题 （ 7） 五、 名词解析（每题4分，共20分） 1. 多道程序设计系统 2. 进程的同步 3. 管态和目态 4. 文件结构 5. 线程 六、 填空（每空1分，共20分） 1. 采用多道程序设计的好处：a________， b充分利用外围设备， c发挥了CPU与外围及外围设备 之间的__________________________________________。 18 200 ～200 学年 学期 级 数学与计算机科学学院 2. 操作系统，通常包括：处理机管理、作业管理、存储器管理、用户接口，设备管理和文件管理。 3. 中央处理器的两种工作方式：管态和目态。操作系统在管态下工作，用户程序在目态下工作。 4. 进程是一个程序在一个数据集上的一次执行。程序是静态的，而进程是动态的。进程通过一个进 程控制块pcb来被系统所指挥，它是进程存在的唯一标志 。 5. 对于多个可变分区的管理，常用的主存分配算法有：最先适应算法、最优适应算法、最坏适应算 法。处理器要设置重定位寄存器、限长寄存器两个。 6. 按组织结构，文件可以包括逻辑文件和物理文件。其中，逻辑结构组织可采用流式文件和记录式 文件，物理结构组织分为顺序文件、链接文件和索引文件。 7. 死锁的必要条件：互斥条件、请求与保持条件、不可抢夺资源、循环等待资源。 8. 设备，可分为块设备，比如：磁盘，字符设备如交互式终端，打印机。 9. 在单处理机环境下，进程间有几种通信方式：a. 共享存储器系统通信方式；b. 消息传递系统通 信方式c.管道通信方式。 10. 文件目录是用来检索文件的。文件目录由若干目录项组成，它记录文件的有关信息。文件目录的 结构包括：一级目录结构、二级目录结构和多级目录结构。 七、 简述题（每小题6分，共30分） 1. 2. 3. 4. 5. 试比较单道与多道批处理系统的特点及优缺点。 内存管理有哪些主要功能?它们的主要任务是什么? 试从动态性，并发性和独立性上比较进程和程序? 何谓死锁?产生死锁的原因是？产生死锁必要条件是什么? 分页和分段有何区别? 八、 应用题（每小题10分，共20分） 1. 在一个请求分页系统中，采用LRU 页面置换算法时，假如一个作业的页面走向为4，3，2，1， 4，3，5，4，3，2，1，5，当分配给该作业的物理块数M 分别为3 和4 时，试计算访问过程中所发生的缺页次数和缺页率?比较所得结果? 答:M=3时LRU 4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 2 2 3 3 3 3 5 4 3 3 4 4 4 4 1 1 4 1 1 1 5 2 2 2 + + + + + + + + + + 所以，缺页中断率f=10/12=83.3% M=4时LRU 4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 1 1 2 2 2 4 3 2 5 5 1 1 4 3 3 3 3 3 4 4 4 4 5 + + + + + + + + 所以，缺页中断率f=8/12=66.7% 2. 假设为某临界区设置一把锁W，当W=1 时，表示关锁；W=0 时，表示锁已打开.试写出开锁原 语和关锁原语，并利用它们去实现互斥。 19 200 ～200 学年 学期 级 数学与计算机科学学院 答: 开锁原语: unlock(W): W=0; 关锁原语: lock(W); if(W==1) do no_op; W=1; 利用开关锁原语实现互斥: var W: semaphore:=0; begin parbegin process : begin repeat lock(W); critical section unlock(W); remainder section until false; end parend 题 （ 8 ） 填空 1. 一般的，进程有三种基本状态：就绪、执行和阻塞。其中，不需要组成队列的是执行。 2. 访问磁盘时间由三部分组成，即数据传输时间、寻道时间和旋转延迟时间，其中寻道时间约占大部 分访问磁盘的时间。 3. 按地址递增管理存储区时，分区管理中采用最先适应法时，应将空闲区按地址递增次序排列，而使 用最佳适应法时空闲区应按容量从小到大次序排列，使用最坏适应法时空闲区按容量从大到小次序排列。 4. 在单处理机环境下，进程间有：共享存储器系统通信方式、消息传递系统通信方式、管道通信方式。 5. 存储管理中，常用交换，覆盖和虚拟性方式来突破主存容量的限制。 6. 在利用信号量实现进程互斥时，应将临界区置于P操作和V操作之间。 7. 对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。其中，破坏循环等待条件是属于 死锁预防，有名的银行家算法是属于死锁避免，而剥夺资源是死锁解除的基本方法。 单项选择题 1．（ D ）不是基本的操作系统。 A、批处理操作系统 B、分时操作系统 C、实时操作系统 D、网络操作系统 2．不是分时系统的基本特征（C）。 A、同时性 B、独立性 C、实时性 D、交互性 3．处理器执行的指令被分成两类，其中有一类称为特权指令，它只允许（C ）使用。 A、操作员 B、联机用户 C、操作系统 D、目标程序 4．当用户程序执行访管指令时，中断装置将使中央处理器（B ）工作。 A、维持在目态 B、从目态转换到管态 C、维持在管态 D、从管态转换到目态 5．进程所请求的一次打印输出结束后，将使进程状态从（D ） 20