操作系统的功能及特征

• 概念

  • 操作系统是指控制和管理整个计算机系统的硬件和软件资源，并且合理地组织调度计算机的工作和资源的分配，提供给用户和其他软件比较便的接口和环境，是计算机系统中最基本的系统软件

• 基本特征

  • 并发

    • 两个或多个事件在同一时间间隔内发生

    • 宏观上看是同时发生的, 微观上是交替发生的

    • 并行

      • 在同一时刻有两个或多个事件同时进行

  • 共享

    • 系统中的资源可供内存中多个并发执行的进程共同使用

    • 分为以下两种资源共享方式

      • 互斥共享方式

      • 同时共享方式

    • 并发和共享是操作系统两个最基本的特征

  • 虚拟

    • 一个物理意义上的实体变为若干个逻辑上的对应物, 物理实体是真实存在的, 逻辑上的对应物是用户自己感受到的

  • 异步

    • 在多道程序环境下, 允许多个程序并发执行, 但由于资源有限, 进程的执行不是一贯到底的, 而是走走停停, 以不可预知的速度向前推进, 这就是进程的异步性

• 操作系统功能

  • 主要功能

    • 内存管理

    • 中断处理

    • 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 操作之后