操作系统期末复习资料(1)

版本 V3 4 概念题概念题 理解进程的定义 进程的组成 对进程的管理和控制使用的是什么 理解进程的定义 进程的组成 对进程的管理和控制使用的是什么 进程是指在系统中能独立运行并作为资源分配的基本单位 它是由一组机器指令 数据和堆栈等组成的 是 一个能独立运行的活动实体 进程控制一般是由 OS 的内核中的原语来实现的 原语原语 原语 Primitive 是由若干条指令组成的 用于完成一定功能的一个过程 具有不可分割性 即原语的执 行必须是连续的 在执行过程中不允许被中断 管程管程 代表共享资源的数据结构 以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序 共 同构成了一个操作系统的资源管理模块 我们称之为管程 死锁死锁 所谓死锁 是指多个进程在运行过程中因争夺资源而造成的一种僵局 当进程处于这种僵局状态是 若无外力作用 它们都将无法再向前推进 死锁四个条件死锁四个条件 互斥条件 请求和保持条件 不剥夺条件 环路等待条件 临界资源临界资源 把在一段时间内只允许一个进程访问的资源称为临界资源或独占资源 每个进程中访问临界资源 的那段代码称为临界区 临界区 属于临界资源的硬件有打印机 磁带机等 软件有消息缓冲队列 变量 数组 缓冲 区等 诸进程间应采取互斥方式 实现对这种资源的共享 SPOOLing 是关于慢速字符设备如何与计算机主机交换信息的一种技术 通常称为 假脱机技术 虚拟存储器虚拟存储器 所谓虚拟存储器 是指具有请求调入功能和置换功能 能从逻辑上对内存容量加以扩充的一种 存储器系统 事事务务 事务是用于访问和修改各种数据项的一个程序单位 事务也可以被看做是一系列相关读和写操作 操作系统的基本类型操作系统的基本类型 批处理操作系统 分时操作系统 实时操作系统 操作系统的基本特性操作系统的基本特性 并发性 共享性 虚拟技术和异步性 用户与操作系统之间的接口用户与操作系统之间的接口 用户接口和程序接口 进程同步的主要任务进程同步的主要任务是为多个进程 含线程 的运行进行协调 两种协调方式 两种协调方式 进程互斥方式和进程同步方式 进程的三种基本状态转换进程的三种基本状态转换 就绪状态 执行状态 阻塞状态 线程与进程的区别 线程与进程的区别 调度调度 在传统的操作系统中 作为拥有资源的基本单位和独立调度 分派的基本单位都是进程 而在引 入线程的操作系统中 则把线程作为调度和分派的基本单位 而进程作为资源拥有的基本单位 把传统 进程的两个属性分开 从而可显著地提高系统的并发程度 在同一进程中 线程的切换不会引起进程的 切换 但从一个进程中的线程切换到另一个进程中的线程时 将会引起进程的切换 就绪 阻塞执行 时间片完 进程调度I O完成 I O请求 版本 V3 4 并发性并发性 在引入线程的操作系统中 不仅进程之间可以并发执行 而且在一个进程中的多个线程之间亦 可并发执行 使得操作系统具有更好的并发性 从而能更加有效地提高系统资源的利用率和系统的吞吐 量 拥有资源拥有资源 不论是传统的操作系统 还是引入了线程的操作系统 进程都可以拥有资源 是系统中拥有 资源的一个基本单位 一般而言 线程自己不拥有系统资源 但它可以访问其隶属进程的资源 系统开销系统开销 在创建或撤消进程时 系统都要为之创建和回收进程控制块 分配或回收资源 操作系统所 付出的开销明显大于线程创建或撤消时的开销 类似地 在进程切换时 涉及到当前进程 CPU 环境的保 存及新被调度运行进程的 CPU 环境的设置 而线程的切换则仅需保存和设置少量寄存器内容 不涉及存 储器管理方面的操作 所以就切换代价而言 进程也是远高于线程的 此外 在同步和通信的实现方面 线程也比进程容易 处理机调度的处理机调度的 3 种调度是什么及其调度对象分别为什么种调度是什么及其调度对象分别为什么 填空题 选择题 高级调度是作业 低级调度是进程 或内核级线程 中级调度是外存中暂时不能运行而被挂起的进程 了解基本的作业调度和进程调度算法了解基本的作业调度和进程调度算法 先来先服务算法 FCFS 最短作业优先算法 SJF 高优先权优先调度算 法和基于时间片轮转算法 填空题 选择题 P91 操作系统的定义操作系统的定义 是配置在计算机硬件上的第一层软件 是对硬件系统的首次扩充 它在计算机系统中占据了 特别重要的地位 操作系统的主要功能 从资源管理的角度 操作系统的主要功能 从资源管理的角度 处理机管理 存储器管理 设备管理和文件管理 理解并发进程的特征 与顺序程序设计相比 理解并发进程的特征 与顺序程序设计相比 在多道程序环境下 程序的执行属于并发执行 此时它们将 失去其封闭性 并具有间断性间断性及不可再现性不可再现性的特征 在多道程序设计系统中 并发进程之间可能存在的两种制约关系在多道程序设计系统中 并发进程之间可能存在的两种制约关系 间接相互制约关系和直接相互制约关系 间接相互制约关系 同处于一个系统中的进程 通常都共享着某种系统资源 如共享 CPU 共享 I O 设 备等 所谓间接相互制约即源于这种资源共享 例如 有两个进程 A 和 B 如果在 A 进程提出打印请求 时 系统已将惟一的一台打印机分配给了进程 B 则此时进程 A 只能阻塞 一旦进程 B 将打印机释放 则 A 进程才能由阻塞改为就绪状态 直接相互制约关系 这种制约主要源于进程间的合作 例如 有一输入进程 A 通过单缓冲向进程 B 提供 数据 当该缓冲空时 计算进程因不能获得所需数据而阻塞 而当进程 A 把数据输入缓冲区后 便将进 程 B 唤醒 反之 当缓冲区已满时 进程 A 因不能再向缓冲区投放数据而阻塞 当进程 B 将缓冲区数据 取走后便可唤醒 A 同步机制应遵循基本准则 临界区调度原则 同步机制应遵循基本准则 临界区调度原则 空闲让进 忙则等待 有限等待 让权等待 信号量信号量 1 一种是用于实现进程互斥的信号量 初值一般为 1 2 另一种是用于解决进程同步的信号量 初值表示资源的数量 填空题 选择题 例 对于两个并发进程都想进入临界区 设互斥信号量为 S 若某时 S 0 表示有 1 个进程进入了临界区 4 种常用的种常用的 I O 控制方式控制方式 程序 I O 方式 中断驱动 I O 方式 直接存储器访问 I O 方式 I O 通道控制方式 版本 V3 4 通道通道 通道是通过执行通道程序 并与设备控制器共同实现对 I O 设备的控制的 了解常用的缓冲技术的作用 了解常用的缓冲技术的作用 1 缓和 CPU 与 I O 设备间速度不匹配的矛盾 2 减少对 CPU 的中断频率 放宽对 CPU 中断响应时间的限制 3 提高 CPU 和 I O 设备之间的并行性 文件系统的主要功能 文件系统的主要功能 文件系统的管理功能 是通过把它所管理的程序和数据组织成一系列文件的方法来 实现的 文件目录的作用 文件目录的作用 文件目录是一种数据结构 用于标识系统中的文件及其物理地址 供检索时使用 6 重定位的定义 重定位就是把程序的逻辑地址空间变换成内存中的实际物理地址空间的过程 也就是说在装 入时对目标程序中指令和数据的修改过程 7 重定位的方式有哪两种 比较它们的不同 重定位有静态和动态两种情况 所谓静态重定位是在装入一个作业的时候 把作业中的指令地址和数据地址全部一次性 地转换成绝对地址 所谓动态重定位是由软件和硬件相配合来实现的 地址重定位不再是装入的时候一次完 成了 而是设置一个基址寄存器 装入作业的时候 将作业在主存区域的首地址放入到基址 寄存器中 作业执行的时候 由硬件的地址转换机构动态地对地址进行转换 执行指令的时 候 只要将逻辑地址加上基址寄存器的内容 就得到了绝对地址 静态重定位和动态重定位的不同在于 静态重定位是在作业装入的时候一次完成 动 态重定位是在作业执行时再实现的 静态重定位是软件支持的 动态重定位是硬件和软件 合作实现的 静态重定位不能实现主存的移动 而动态重定位可以 动态重定位还可能 提供虚拟存储空间 版本 V3 4 算法题算法题 生产者与消费者问题生产者与消费者问题 P58 利用记录型信号量解决生产者 消费者问题 Var mutex empty full semaphore 1 n 0 buffer array 0 1 n 1 of item in out integer 0 0 begin parbegin producer begin repeat producer an item in nextp wait empty wait mutex buffer in nextp in in 1 mod n signal mutex signal full until false end consumer begin repeat wait full wait mutex nextc buffer out 版本 V3 4 out out 1 mod n signal mutex signal empty consumer the item in nextc until false end parend end 利用 and 信号量解决生产者 消费者问题 Var mutex empty full semaphore 1 n 0 buffer array 0 1 n 1 of item in out integer 0 0 begin parbegin producer begin repeat produce an item in nextp Swait empty mutex buffer in nextp in in 1 mod n Ssignal mutex full until false end consumer begin 版本 V3 4 repeat Swait full mutex Nextc buffer out Out out 1 mod n Ssignal mutex empty consumer the item in nextc until false end parend end 银行家算法银行家算法 P115 在银行家算法中 若出现下述资源分配情况 ProcessAllocationNeedAvailable P0003200121622 P110001750 P213542356 P303320652 P400140656 1 该状态是否安全 2 若进程 P2 提出请求 Request 1 2 2 2 后 系统能否将资源分配给它 解 1 该状态是安全的 因为存在一个安全序列 安全列表 资源情况进程WorkNeedAllocationWork AllocationFinsh P01622001200321654true P31654065203321986true P41986065600141 9 9 10true P11 9 9 10175010002 9 9 10true 版本 V3 4 P22 9 9 10235613543 12 14 14true 2 不能 若分配进程 P2 系统还剩的资源情况为 0 4 0 0 此时系统中的资源将无法满足任何一个进程的资 源请求 从而导致系统进入不安全状态 容易引起死锁发生 逻辑地址变换为物理地址的过程逻辑地址变换为物理地址的过程 P132 1 分页地址变换机构会将有效地址分为页号和页内地址 再以页号为索引去检索页表 2 如果页号大于或等于页表长度就产生地址越界中断 3 表项在页表中的位置 页表始址 页号 页表项长度 读出物理块号装入物理地址寄存器 4 将页内地址送入物理地址寄存器的块内地址字段中 最佳最佳 Optimal 先进先出先进先出 FIFO 页面置换算法页面置换算法 P151 假定系统为某进程分配了三个物理块 并考虑有以下的页面号引用串 7 7 0 0 1 1 2 2 0 0 3 3 0 0 4 4 2 2 3 3 0 0 3 3 2 2 1 1 2 2 0 0 1 1 7 7 0 0 1 1 进程运行时 先将 7 0 1 三个页面装入内存 以后 当进程要访问页面 2 时 将会产生缺页中断 此时 OS 根据最佳置换算法 将选择页面 7 予以淘汰 这是因为页面 0 将作为第 5 个被访问的页面 页面 1 是第 14 个被访 问的页面 而页面 7 则要在第 18 次页面访问时才需调入 下次访问页面 0 时 因它已在内存而不必产生缺页中断 当进程访问页面 3 时 又将引起页面 1 被淘汰 因为 它在现有的 1 2 0 三个页面中 将是以后最晚才被访问 的 图 4 26 示出了采用最佳置换算法时的置换图 采用最佳置换算法发生了 6 次页面置换 版本 V3 4 采用 FIFO 算法进行页面置换 当进程第一次访问页面 2 时 将把第 7 页换出 因为它是最先被调入内存的 在第一次访问页面 3 时 又将把第 0 页换出 因为它在现有的 2 0 1 三个页面中是最老的页 利用 FIFO 算法 进行了 12 次页面置换 比最佳置换算法多一倍 PV 操作 综合题 操作 综合题 例如 进程之间的关系如下图所示 使用 P V 操作描述它们之间的同步 如图 S1 S2 S3 S6是最简单的程序段 为使各程序段能正常执行 应设置若干个初始值为 0 的信 号量 为保证 S1 S2 S1S3的前驱关系 应分别设置信号量 a b 为了保证 S2S4 S2S5 S3S6S4S6S5S6 应分别设置信