操作系统期末速成（一）

操作系统的功能及特征概念操作系统是指控制和管理整个计算机系统的硬件和软件资源并且合理地组织调度计算机的工作和资源的分配提供给用户和其他软件比较便的接口和环境是计算机系统中最基本的系统软件基本特征并发两个或多个事件在同一时间间隔内发生宏观上看是同时发生的, 微观上是交替发生的并行在同一时刻有两个或多个事件同时进行共享系统中的资源可供内存中多个并发执行的进程共同使用分为以下两种资源共享方式互斥共享方式同时共享方式并发和共享是操作系统两个最基本的特征虚拟一个物理意义上的实体变为若干个逻辑上的对应物, 物理实体是真实存在的, 逻辑上的对应物是用户自己感受到的异步在多道程序环境下, 允许多个程序并发执行, 但由于资源有限, 进程的执行不是一贯到底的, 而是走走停停, 以不可预知的速度向前推进, 这就是进程的异步性操作系统功能主要功能内存管理中断处理CPU调度操作系统作为计算机系统资源的管理者处理机管理存储器管理文件管理设备管理操作系统作为用户与计算机硬件系统之间的接口用户接口分为两类命令接口 (按照作业控制方式的不同)联机命令接口 (交互式命令接口)适用于分时或者实时系统的接口脱机命令接口适用于批处理系统, 它由一组作业控制命令组成程序接口(系统调用)由一组系统调用组成当前最为流行的是图形用户界面 (GUI)OS提供给应用程序的接口操作系统的分类单道批处理系统特点单路性独占性自动性封闭性顺序性缺点系统的资源得不到充分的利用多道批处理系统特点多路性共享性自动性封闭性无序性调度性好处提高CPU的利用率提高内存和 I/O 设备的利用率, 增加系统吞吐量缺点平均周转时间长, 无交互能力分时系统主要特征多路性交互性独立性及时性在一台主机上连接了多个配有显示器和键盘的终端, 该系统允许多个用户同时通过自己的终端, 以交互方式使用计算机, 共享主机资源采用时间片轮转的处理机调度策略实时系统系统能及时响应外部事件的请求, 在规定时间内完成对该事件的处理, 并控制所有实时任务协调一致地运行例题某单CPU系统中有输入设备和输出设备各1台现有3个并发执行的作业每个作业的输入、计算和输出时间分别为2ms、3ms和4ms且都按输入、计算和输出的顺序执行则执行完这3个作业需要的时间最少是多少?因 CPU、输入设备和输出设备都只有一个因此各操作步骤不能重叠即执行完3个作业所需要的时间最少是17ms操作系统的运行机制用户态及内核态CPU执行两种不同性质的程序操作系统内核程序应用程序操作系统划分用户态用户自编的程序命令解释程序属于命令接口核心态操作系统内核程序运行进程调度内核计算机最底层的软件, 是计算机功能的延伸时钟管理操作系统通过时钟管理向用户提供准确的时间, 通过时钟中断的管理, 可实现进程的切换中断机制引入中断机制的初衷是提高多道程序环境中 CPU 的利用率原语计算机底层的一些可被调用的公用小程序, 它们各自完成一个规定的操作, 是不可划分的单位系统控制其数据结构及处理linux是一个多道分时操作系统中断, 异常中断本质发生中断就意味着需要操作系统介入开展管理工作中断可以使 CPU 从用户态切换到核心态, 使操作系统获得计算机的控制权, 有了中断, 才能实现多道程序并发执行用户态 -- 核心态是通过中断实现的, 并且中断是唯一途径核心态 -- 用户态是通过执行一个特权指令, 将程序状态字 (PSW) 的标志位设置为 “用户态”例如缺页处理程序时钟中断处理程序异常信号的来源CPU内部, 与当前执行的指令有关资源中断 -- 指令中断系统调用时使用的访管指令 (又称陷入指令, trap指令)强迫中断主要有硬件故障 (如: 缺页) 或 软件中断 (如: 整数除0)进程管理进程的状态与转换进程的概念进程是程序的一次执行进程是一个程序及其数据在处理机上顺序执行时所发生的活动进程是具有独立功能的程序在一个数据集合上云霄的过程, 它是系统进行系统分配和调度的一个独立单位进程的分类用户进程系统进程进程的组成程序控制块 (PCB)应该包含操作系统对其进行管理所需的各种信息, 如进程描述信息, 进程控制和管理信息, 资源分配清单和处理机相关信息程序段程序代码存放的位置数据段程序运行时使用, 产生的运算数据, 如全局变量, 局部变量, 宏定义的常量就存放在数据段内进程的特征动态性进程的最基本的特征, 进程是程序的一次执行过程, 是动态的产生, 变化和消亡的并发性内存中有多个进程实体, 各进程可并发执行独立性进程是能独立运行, 独立获取资源, 独立接受调度的基本单位异步性各个进程按各自独立的, 不可预知的速度向前推进, 操作系统要提供进程同步机制来解决异步问题结构性每个进程都会配置一个PCB, 结构上看, 进程由程序段, 数据段和PCB组成进程的状态定义一个进程的生命周期可以划分为一组状态, 这些状态刻画了整个进程, 进程状态体现一个进程的生命状态就绪状态 (基本状态)进程已经具备运行条件, 但由于未分配CPU无法运行的状态运行状态 (基本状态)进程占用CPU, 并在CPU上运行的状态阻塞状态 (基本状态)进程因等待某个事件发生而暂时不能运行的状态创建状态进程在创建时需要申请一个空白PCB, 向其中填写控制和管理进程的信息完成资源分配终止状态进程结束, 或出现错误, 或被系统终止, 进入终止状态状态的转换运行状态 -- 就绪状态时间片用完被调度程序调离被高优先级进程抢占进程通信概念进程之间的信息交换低级通信PV操作高级通信 (是以较高的效率传输大量数据的通信方式)共享通信基于共享数据结构的通信方式 (例如生产者与消费者), 基于共享存储区的通信方式消息传递是以格式化的消息为单位, 利用原语传递消息, 分为直接通信和间接通信管道通信是消息传递的一种特殊方式, 是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件, 又称 pipe 文件处理机调度处理机调度概述基本准则不同调度算法具有不同的特性, 在选择调度算法时, 必须考虑算法的特性, 为了比较处理机调度算法的性能, 人民提出了很多评价准则, 下面介绍几种常见的CPU利用率CPU是计算机系统中最重要和昂贵的资源之一, 所以应尽可能使保持忙的状态, 使这一资源利用率最高系统吞吐量表示单位时间内CPU完成作业的数量长作业需要消耗较长的处理机时间, 因此会降低系统的吞吐量短作业需要消耗的处理机时间较短, 因此能提高系统的吞吐量调度算法和方式不同, 也会对系统的吞吐量产生较大的影响周转时间周转时间是指从作业提交到作业完成所经历的时间, 是作业等待, 在就绪队列中排队, 在处理机上运行及进行输入 / 输出操作所花费的时间的总和等待时间等待时间指进程处于等待处理机状态的时间之和, 等待时间越长, 用户满意度越低响应时间响应时间指从用户提交请求到系统首次产生响应所用的时间公式作业的周转时间可用公式表示如下周转时间 作业完成时间 - 作业提交作业平均周转时间是指多个作业周转时间的平均值平均周转时间 (作业1的周转时间 … 作业n的周转时间) / n带权周转时间是指作业周转时间与作业实际运行时间的比值带权周转时间 作业周转时间 / 作业实际运行时间平均带权周转时间是指多个作业带权周转时间的平均值平均带权周转时间 (作业1的带权周转时间 … 作业n的带权周转时间) / n进程调度方式当某个进程正在处理机上执行时, 若有某个更为重要或者紧迫的进程需要处理, 即优先权更高的进程进入就绪队列, 此时应如何分配处理机的方式非剥夺调度方式 (非抢占方式)指的是当一个进程正在处理机上执行时, 即使有某个更为重要或者紧迫的进程进入就绪队列, 仍然让正在执行的进程继续执行, 直到该进程完成或发生某种事件而进入阻塞态时, 才把处理机分配给更重要或更紧迫的进程剥夺调度方式 (抢占方式)采用剥夺式的调度, 对提高系统吞吐率和响应效率都有明显好处, 但剥夺不是一种任意性行为, 必须遵循一定的原则, 主要有优先权, 短进程优先和时间片原则等调度例题正在执行的进程在时间片用完后进入就绪态, 系统会调入一个新的进程来为其分配处理机并执行正在执行的进程提出 I/O 请求后进入等待态, 系统会调入一个新的进程来为其分配处理机并执行有新的用户登录系统会创建新的进程, 若处理机空闲, 则分配处理机并执行等待硬盘读取数据的进程获得了所需的数据后, 若处理机空闲, 则可进行进程调度调度算法FCFS算法 (first come first server)算法规则按照作业 / 进程到达的先后顺序来进行调度适用情况可用于作业调度也可用于进程调度优缺点算法实现简单对长作业有利, 对短作业不利SJF算法 (short job first)算法规则以作业的长短来计算优先级, 作业越短, 其优先级越高适用情况可用于作业调度及进程调度优缺点最短的平均等待时间及平均周转时间必须先知道作业的运行时间对长作业不利, 会出现饥饿现象没有考虑作业的紧迫程度优先级算法算法规则基于进程 (作业) 的紧迫程度, 由外部赋予进程相应的优先级, 根据优先级进行调度适用情况可用于作业调度 (宏观调度) 也可用于进程调度 (微观调度) 甚至说 I/O 调度类型抢占式优先级调度算法只需出现另一个优先级更高的进程, 调度就会发生变化非抢占式优先级调度算法主动放弃优先级类型静态优先级在创建进程时确定, 其在进程的整个运行期间不变动态优先级在创建进程之初, 先赋予进程一个优先级, 然后动态的调整优先级优缺点用优先级区分紧急程度, 运行时实时OS可能导致饥饿 (低优先级进程的饥饿)时间片轮转算法 (RR)算法思想公平的, 轮流的为各个进程服务, 让每个进程在一定时间间隔内都可以得到响应算法规则按照各进程到达就绪队列的顺序, 轮流让各个进程执行一个时间片, 若进程未到一个时间片内执行完, 则剥夺处理机, 将进程重新放到就绪队列队尾重新排队适用情况可用于进程调度是否抢占属于抢占式算法由时钟装置发出时钟中断来通知CPU时间片已到优缺点公平, 响应快, 适用于分时操作系统不能区分任务的紧急程度, 需要进程切换, 消耗较大例题作业执行顺序如图高响应比优先算法 (HRRN)算法思想综合考虑作业或者进程的等待时间和要求服务的时间算法规则在每次调度前先计算各个作业或者进程的响应比 (优先级), 选择响应比最高的作业或者进程为其服务响应比 (等待时间 要求服务时间) / 要求服务时间 响应时间 / 要求服务时间适用情况可用于作业调度及进程调度优缺点综合考虑了等待时间和运行时间, 较好地实现了折中每次调度前都要计算响应比, 会增加系统的开销不会导致饥饿现象例题多级反馈队列调度算法算法思想对其他调度算法的折中权衡算法规则设置多个就绪队列各级队列优先级从高到低, 时间片从小到大每个队列都采用 FCFS 调度算法按队列优先级调度只有当第 1 ~ i - 1 队列均空时, 才会调度第 i 队列中的进程适用情况可用于进程调度类型属于抢占式的算法优缺点用优先级区分紧急程度, 运用于实时OS可能导致饥饿 (低优先级进程的饥饿)死锁必要条件互斥非剥夺部分分配循环等待进程同步进程同步与互斥基本概念临界资源是一次仅允许一个进程使用的共享资源各个进程采取互斥的方式, 实现共享的资源称为临界资源属于临界资源的硬件打印机磁带机属于临界资源的软件消息队列变量数组缓冲区临界区每个进程中访问临界资源的那段代码称为临界区每次只允许一个进程进入临界区, 进入后, 不允许其他进程进入临界资源的访问过程分为4个部分进入区负责检查是否可以进入临界区, 设置正在访问临界资源的标志临界区访问临界资源的那段代码退出区负责解除正在访问临界资源的标志剩余区做其他处理为禁止两个进程同时进入临界区, 同步机制应遵循以下准则空闲让进临界区空闲时, 可以允许一个请求进入临界区的进程立即进入临界区忙则等待当已有进程进入临界区时, 其他试图进入临界区的进程必须等待有限等待对请求访问的进程, 应保持能在有限时间内进入临界区让权等待当进程不能进入临界区时, 应立即释放处理器, 防止进程忙等待进程同步直接制约关系, 它指的是多个进程一起完成某个任务, 这些进程因为合作需要在某些位置上协调他们的工作次序而产生了某些制约关系进程互斥间接制约关系, 当某个进程A在访问临界区使用临界资源时, 另一个B进程必须等待, 直到A进程访问结束并释放临界资源后, B进程才能去访问信号量机制概念是一种功能较强的机制, 可用来解决互斥和同步问题, 它只能被两个标准的原语 wait(S) 和 signal(S) 访问, 也可记为 “P操作” 和 “V操作”整型信号量被定义为一个用于表示资源数目的整型量S该机制并未遵循让权等待的准则, 而是使进程处于忙等的状态记录型信号量记录型信号量是不存在忙等现象的进程同步机制, 除需要一个用于代表资源数目的整型变量 value 外, 再增加一个进程链表 L, 用于链接所有等待该资源的进程信号量的基本应用实现多个进程的互斥互斥信号量 mutex, 初值为 1每个进程将临界区代码置于 P(mutex) 和 V(mutex) 原语之间必须成对使用 P 和 V 原语 (在同一进程中), 不能次序错误, 重复或遗漏遗漏 P 原语则不能保证互斥访问遗漏 V 原语则不能在使用临界资源之后将其释放实现同步分析什么地方需要实现同步关系 (必须保证一前一后执行的两个操作)设置同步信号量S, 初始化为0在前操作之后执行V(S)在后操作之后执行P(S)信号量题目做题的一般方法分析问题, 找出同步, 互斥关系根据资源设置信号量变量写出代码过程, 并注意 P, V 操作的位置检查代码, 模拟机器运行, 体验信号量的变化和程序运行过程是否正确例题信号量表示相关资源的当前可用数量, 当信号量 k 0 时, 表示还有 k 个相关资源可用. 当信号量 k 0 时, 表示有 |k| 个进程在等待该资源信号量 mutex -1时, 其绝对值等于等待进入临界区的进程数, 表示有一个进程进入临界区, 另一个进程等待进入生产者-消费者问题问题描述系统中有一组生产者进程和一组消费者进程, 生产者进程每一次生产一个产品放入缓冲区, 消费者进程每次从缓冲区中取出一个一个产品并使用 (注意: 这里的产品理解为某种数据)生产者, 消费者共享一个初始为空, 大小为n的缓冲区只有缓冲区没满时, 生产者才能把产品放入缓冲区, 否则必须等待只有缓冲区不空时, 消费者才能从中取出产品, 否则必须等待缓冲区是临界资源, 各进程必须互斥地访问问题分析该问题中出现的主要两种关系生产者 - 消费者之间的同步关系: 一旦缓冲池中所有缓冲区均装满产品时, 生产者必须等待消费者提供空缓冲区; 一旦缓冲池中所有缓冲区全为空时, 消费者必须等待生产者提供满缓冲区生产者 - 消费者之间的互斥关系: 由于缓冲池是临界资源, 所以任何进程在对缓冲区进行存取操作时都必须和其他进程互斥进行PV操作题目分析的步骤关系分析找出题目中描述的各个进程, 分析它们之间的同步, 互斥关系整理思路根据各进程的操作流程确定操作的大致顺序设置信号量设置需要的信号量, 并根据题目条件确定信号量的初始值如何实现互斥的实现是在同一个进程中进行一对 PV操作同步的实现是在两个进程中进行, 在一个进程中执行 P操作, 在另一个进程中执行 V操作注意实现互斥的 P 操作一定要放在实现同步的 P 操作之后