0%

操作系统一复习大纲

Posted on Edited on

第一章 操作系统引论

1.1 操作系统的目标和作用

操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。
目标：方便性，有效性，可扩充性，开放性
作用：用户和硬件间的接口，管理系统资源，抽象计算机资源

1.2 操作系统的发展过程

未配置操作系统的计算机系统：

  • 人工操作方式：用户独占全部资源
  • 脱机IO方式： CPU空闲时间，提升IO效率

单道批处理系统：
内存中始终保持一道作业，IO请求时CPU空闲，小作业内存资源空闲

多道批处理系统：
用户提交作业进入外存，作业调度若干作业进入内存，共享CPU和系统汇总的资源。多道程序交替运行。
优点：资源利用率高，吞吐量大
缺点：平均周转时间长，无交互能力
需要解决的问题：处理机争用，内存分配和保护，IO设备分配，文件组织管理，作业管理，用户与系统接口。

分时系统：侧重用户终端互不干扰，人机交互
引入：人机交互（用户想要独占主机），共享主机。
关键问题：及时接收，及时处理（直接进入内存，RR）

实时系统：侧重多路控制现场的设备、数据互不干扰，程序数据信息交互
能及时响应外部请求，在规定时间内完成对事件的处理，控制实时任务的协调执行。

比较：

  • 多路性：分时为多终端服务；实时周期性控制
  • 独立性：多终端互不干扰；信息采集和对象控制互不干扰
  • 及时性：用户可接受；要求更高
  • 交互性：强；仅对信息查询系统中特定命令
  • 可靠性：较强；非常强

1.3 操作系统的基本特征（四大特征）

  • 并发：多个事件在同一时间段发生。
    引入进程使得并发成为可能。微观上是交替执行。
  • 共享：资源供多个并发执行的进程同时使用。
    分互斥资源共享和同时访问
  • 虚拟：将一个物理实体变为若干逻辑对应物，提升利用率。
    分时分复用和空分复用
  • 异步：进程的执行顺序和时间不确定。

1.4 操作系统的主要功能（五大功能）

  • 处理机管理功能：即对进程的管理
    • 进程控制：创建、撤销、状态迁移
    • 进程同步：临界资源的互斥访问
    • 进程通信：进程的合作
    • 调度：作业调度和进程调度
  • 存储器管理功能：内存分配（动态静态）、内存保护、地址映射、内存扩充
  • 设备管理功能：（管理IO设备）缓冲管理、设备分配、设备处理
  • 文件管理功能：文件存储空间管理、目录管理、文件读写管理保护
  • 操作系统与用户之间的接口：为方便用户使用
    • 用户接口：方便用户直接或间接控制自己的作业
      • 联机用户接口（terminal）：由一组键盘操作命令及解释程序组成
      • 脱机用户接口（.sh）：用作业控制语言写作业说明书
      • 图形用户接口：图标等
    • 程序接口：为用户程序访问系统资源设置，是用户程序取得系统服务的唯一途径
  • 新功能：系统安全、网络功能和服务、支持多媒体

1.5 操作系统的结构设计

系统调用：把应用程序的请求传送至内核，调用相应的内核函数完成所需的处理，将处理返回给应用程序。系统调用是用户程序取得系统服务的唯一途径。
作用：保证系统和资源的安全性；提供统一接口提升编程效率。
用户态 —> 系统调用 —> 内核态
传参方式：指令自带参数；寄存器直接/间接传参；内存堆栈区传参

内核：一组程序控制模块，作为可信软件提供支持进程并发执行的基本功能和操作，驻留内核空间，运行于和心态，具有访问硬件设备和内存的全部权限，可以执行特权指令。

传统操作系统结构：无结构OS、模块化结构OS、分层式结构OS（自底向上设计）

微内核OS结构（对应宏内核OS结构）：
将操作系统划分成两部分（微内核和多个服务器），将操作系统中尽可能多的成分和功能放到服务器中运行，而留下一个尽可能小的内核完成操作系统最核心的功能。

基本概念：

  • 足够小的内核：放入与硬件密切相关的部分、一些基本功能、与服务器的通信
  • 基于客户/服务器模式：客户与服务器之间通过微内核实现信息交互
  • 应用“机制与策略分离”原理：该做什么和怎么做分离
  • 采用面向对象技术：抽象和封装

基本功能：进程（线程）管理、低级存储器管理、中断和陷入处理

优点：

  • 提高系统可扩展性
  • 提高系统可靠性
  • 可移植性强
  • 提供对分布式系统的支持（多个处理机通过通信线路互联而构成的松散耦合的系统）
  • 融入面向对象技术

缺点：频繁的上下文切换，运行效率较早期操作系统有所降低。

第二章 进程的描述和控制

2.1 前趋图和程序执行

前趋图：描述进程执行的先后顺序，DAG

前趋图顺序执行的特征：

  • 顺序性：严格按照顺序执行
  • 封闭性：程序运行时独占全部资源
  • 可再现性：只要初始环境和条件相同，无论执行过程最终结果一定相同。

前趋图并发执行的特征：

  • 间断性：程序之间相互制约
  • 失去封闭性：资源共享
  • 不可再现性：多次执行结果不同

2.2 进程的描述

进程的定义：
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
进程的出现使程序并发执行成为可能。
系统使用进程控制块（PCB）描述进程的基本情况和活动过程，进而控制管理进程。
Main函数参数和系统调用的关系

进程的特征：

  • 动态性：创建产生，调度执行，撤销消亡（程序是静态的）
  • 并发性：多个进程在同一个时间段中并发执行（程序无PCB不能并发）
  • 独立性：进程实体有独立资源能独立运行（程序无PCB不能独立运行）
  • 异步性：进程按各自的不可预知的速度推进

进程和程序的区别：

  • 进程是动态的，程序是静态的
  • 进程是暂时的，程序时永恒的
  • 进程包含程序、数据和PCB
  • 进程可以包含多个程序，同一程序可以对应多个进程

进程的状态和转化：
引入挂起操作的作用：

  • 终端用户的需要：检查、修正错误
  • 父进程的请求：考察和协调子进程
  • 负荷调节的需要：挂起不重要的进程保证系统正常运行
  • 操作系统得出需要：操作系统记账

三态、五态、七态模型：注意图中状态名称和操作名称，要会默写

PCB作用：

  • 作为独立运行基本单位的标志
  • 实现间断性运行的方式
  • 提供进程管理需要的信息
  • 实现与其它进程通信

PCB中的信息：

  • 进程控制符（编号）
  • 处理机状态（寄存器信息，计数器）
  • 进程调度信息（进程状态和优先级）
  • 进程控制信息（资源清单）

PCB组织方式：链式、索引式

操作系统管理数据结构分类：内存表、设备表、文件表、进程表

2.3 进程控制

内核的功能：

  • 支撑功能：中断处理、时钟管理、原语操作
  • 资源管理功能：进程管理、存储器管理、设备管理

引起进程创建的事件：
用户登录、作业调度（从外存进内存）、提供服务（用户请求打印）、应用请求

引起进程终止的事件：
正常结束、异常结束（越界、非法访问、非法指令、特权指令、运行超时、超时等待、算数运算、IO故障）、外界干预（ctrl+c）

引起阻塞和唤醒的事件：
向系统请求共享资源失败、等待操作完成（IO）、新数据未到达（wait）、等待新任务到达（网络进程）

进程创建过程：

  • 申请空白PCB
  • 为新进程分配所需资源（物理+逻辑）
  • 初始化PCB
  • 加入就绪队列

进程终止过程：

  • 根据标识符找到PCB读出进程状态
  • 若正在运行立即终止，指示系统重新调度
  • 终止子孙进程
  • 将进程资源归还父进程或系统
  • 移出PCB等待信息被收集

进程阻塞过程：进程使用阻塞原语block自己
停止运行并进入阻塞队列，调度程序重新调度

进程唤醒过程：由有关进程使用wakeup原语唤醒
将进程从阻塞队列移出，将PCB改为就绪，加入就绪队列。

进程挂起过程：用户或父进程提出，OS利用suspend挂起指定进程
检查进程状态，改为对应的静止状态，复制PCB到指定内存区域以备查看。指引重新调度

进程激活过程：OS利用active激活制定进程
将进程从外村调入内存，检查状态，改为对应就绪/阻塞状态。如果有抢占机制比较是否抢占。

fork、exec系、wait、exit

2.4 进程同步

进程制约关系：间接相互制约（资源互斥共享）、直接相互制约（管道同步）
同步：系统中多个进程发生的事件存在时序关系，需要相互合作完成同一任务
互斥：各进程要求共享资源，而有些资源需要互斥使用，各进程间竞争使用
临界资源：系统中一次只允许一个进程使用的资源
临界区：进程中访问临界资源的代码段

同步机制遵循的规则：（临界区问题）
空闲让进、忙则等待、有限等待、让权等待

硬件同步机制：

  • 关中断：禁止中断发生，不适用于多CPU
  • Test-and-Set指令：疯狂测试lock，如果开门了就锁门后访问
  • Swap指令：疯狂交换key和lock，如果key变true了访问

信号量机制：

  • 整型信号量：P(s)-V(s)/wait(s)-signal(s)
    只要信号量小于等于0就不断进行测试（忙等）
  • 记录型信号量：wait(s)-signal(s)解决了忙等（让权等待）
    S->value≥表示系统中可用资源数
    S->value小于零表示已阻塞进程数
    S->value初始值为1表示互斥信号量
    S->list记录阻塞进程信息
  • AND型信号量：Swait(S1,S2…Sn)、Ssignal
    一次性分配全部资源给进程（要么全部分配，要么一个都不分配），效率较低
    每次一种资源只能分配一个
  • 信号量级：Swait(S1,t1,d1…Sn,tn,dn)
    一次性请求t1个S1，如果成功消耗d1个S1
    Swait(S,d,d)：请求d个S，如果少于d则不分配
    Swait(S,1,1)：退化为记录型信号量(S>1)或互斥信号量(S=1)
    Swait(S,1,0)：S=1时允许多个进程进入，反之不允许进入。相当于可控开关

信号量的应用：互斥和同步P57

管程：定义了一个数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。将共享资源的数据结构和操作过程封装在对象内部，隐藏实现细节。

2.5 经典进程同步问题

  • 生产者-消费者问题P60
  • 哲学家进餐问题P63
  • 读者-写者问题P65

2.6 进程通信

进程通信就是进程之间的信息交换，用于同步和互斥。

进程通信的类型：

  • 共享存储器系统：共享数据结构或存储区
    • 基于共享数据的通信方式（数据结构）
    • 基于共享存储区的通信方式（内存）
  • 管道通信系统：写进程 —> 管道文件 —> 读进程
  • 消息传递系统：以格式化消息为单位
    • 直接通信方式（原语操作）
    • 间接通信方式（通过共享中间实体（邮箱））
  • 客户-服务器系统：
    • 套接字：分基于文件型和基于网络型
    • 远程方法调用和远程文件调用

2.7 线程的基本概念

线程的引入：
为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。

线程和进程的比较：

  • 调度的基本单位：进程独立调度分派；进程调度分派，独立运行
  • 并发性：都可以并发执行
  • 拥有资源：进程是拥有资源的基本单位；线程仅拥有必不可少的独立运行所需的资源
  • 独立性：线程间共享地址空间和资源
  • 系统开销：线程没什么资源，开销小
  • 支持多处理机系统：单进程多线程更加满足多处理机系统

2.8 线程的实现

  • 内核支持线程：内核创建，能够并发，用户切换线程需要陷入
  • 用户级线程：用户创建，切换不需要陷入，但阻塞后无法调度
  • 组合模式：两者结合相互利用

第三章 处理机调度与死锁

3.1 处理机调度的层次和调度算法的目标

处理机调度的层次：

  • 高级调度（作业调度）
  • 中级调度（内存调度）
  • 低级调度（进程调度）

调度算法的目标：

  • 共同目标：资源利用率、公平性、平衡性、策略强制执行
  • 批处理系统目标：平均周转时间短、系统吞吐量高、处理机利用率高
  • 分时系统目标：响应时间快、均衡性
  • 实时系统目标：截止时间的保证、可预测性

周转时间：作业交给系统到完成的时间
平均周转时间 $ \overline{T} = \frac{1}{n}\sum_{i=1}^{n}T_i $
带权平均周转时间 $ W = \frac{1}{n} \sum_{i=1}^{n}\frac{T_i}{T_s} \geq 1 $
$ \text{CPU利用率} = \frac{\text{CPU有效工作时间}}{\text{CPU有效工作时间} + \text{CPU空闲等待时间}} $

3.2 作业和作业调度

进程：程序段+数据+PCB
作业：程序+数据+作业说明书
作业步：完成作业的一个个步骤
作业控制块JCB

作业运行的三个阶段和三种状态：

  • 收容阶段（后备状态）：建立JCB进入后备队列
  • 运行阶段（运行状态）：分配资源、运行
  • 完成阶段（完成状态）：完成

作业调度的主要任务：
根据JCB中的信息检查资源满足情况，再根据调度算法决定将作业放入内存，创建进程分配资源。接纳多少作业、接纳哪些作业
先来先服务算法（FCFS）：等待时间

短作业优先算法（SJF）：作业运行时间
缺点：预制时间、可能饥饿、无人机交互、不考虑紧迫程度

高优先权优先算法（HPF(PSA)）：作业紧迫程度

高响应比优先算法（HRRN(PSA)）：SJF和FCFS的折衷
$ \text{优先权}=\frac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}}= \frac{\text{响应时间}}{\text{要求服务时间}} $

3.3 进程调度

进程调度算法继承作业调度全部算法
任务：保存处理器信息，按算法选取下一个进程，将处理器分配给进程
机制：排队器（事先排队）、分派器（选取进程）、上下文切换器

进程调度方式：

  • 非抢占式：进程执行完毕或无法执行、进程请求IO、通信或同步被block
  • 抢占式：高优先权优先、高响应比优先、时间片原则

最短剩余时间优先算法（SRTF）：抢占式，进程专用
新进程到达时，如果时间少于当前CPU进程剩余时间则产生中断

轮转调度算法（RR）：
根据FCFS排成就绪队列，每隔一个时间片产生中断，将CPU分配给队首进程。进程切换当且仅当时间片完或运行结束。较为可取的时间片大小是略大于典型交互所需要的时间，使交互程序能在一个时间片内完成。

多级反馈队列调度算法（MFQ）：
设置多个就绪队列，每个队列使用不同优先级。能够在不知道进程时长的情况下满足各类型用户的需要（终端、短批处理、长批处理）

  • 第1至第n-1级队列：FCFS
  • 第n级队列：RR
  • 队列间：HPF

3.4 实时调度

按任务性质分类：硬实时调度、软实时调度
按调度方式分类：抢占式、非抢占式（硬实时调度提前预知）
最早截止时间优先EDF：截止越早越优先
最低松弛度优先LLF：截止时间-剩余时间越小越优先

优先级倒置：
一个低优先级进程持有一个高优先级进程所需要的资源，使高优先级进程等待地优先级进程运行。
解决办法：临界区期间低优先级进程继承高优先级进程的优先级。

3.5 死锁概述

死锁：
计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争系统资源而造成的一种互相等待的现象。
若无外力作用，这组进程将永远不能继续执行。

资源：

  • 可重用性资源（数目相对固定）和消耗性资源（生产创建，消费消耗）
  • 可抢占性资源（处理机）和不可抢占性资源（打印机）

死锁的产生：

  • 竞争不可抢占性资源
  • 竞争可消耗性资源
  • 进程间推进顺序不当

死锁定义：如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程就是死锁的。

死锁产生的四个必要条件：

  • 互斥条件：资源独占，进程对分配到的资源进行排他性使用
  • 请求和保持条件：进程已经保持至少一个资源，又提出新请求，如未能满足，不释放已获得资源
  • 不可抢占条件：资源在未被使用完前不能被抢占，只能由进程使用完后自愿释放
  • 循环等待条件：存在进程-资源循环链，环路中的进程形成等待链

死锁处理方法：

  • 预防死锁：破坏死锁产生的必要条件
  • 避免死锁：防止系统进入不安全状态（银行家算法）
  • 检测死锁：通过检测机构及时发现死锁，再采取措施（资源分配图）
  • 解除死锁：当死锁发生，撤销一些进程，回收资源再分配

3.6 预防死锁

破坏请求和保持：一次性申请全部资源（浪费+饥饿）；申请初期资源，运行后释放
破坏不可抢占：新资源得不到满足时主动释放已有资源
破坏循环等待：对资源排序，申请低序号资源必须先释放所有高序号资源

3.7 避免死锁

避免死锁与预防死锁的区别：
预防死锁对进程的资源申请命令施加限制（规定死的）
避免死锁在进程请求分配资源时进行动态检查，并根据检查结果决定分配

安全状态与安全序列：
系统能按某种进程推进顺序为每个进程分配所需资源，直至满足每个进程对资源的最大需求，使每个进程都能顺利完成。
相应序列为安全序列。
若不存在安全序列，则称为不安全状态。

银行家算法中的数据结构：
Max、Allocation、Need、Available

银行家算法过程：两个判断三个调整

  • 检查是否超出需求总量，超出报错
  • 检查是否资源不足，不足等待
  • 试探进行分配
  • 执行安全性检查算法。
  • 如不安全，试探分配作废，进程等待

安全性算法：
Work、Need、Allocation、Work + Allocation、Finish
寻找安全序列。

银行家算法的不足：对资源分配相对保守，计算多，需要预知未来进程变化和资源请求

3.8 检测死锁与解除死锁

资源分配图

死锁定理：
死锁产生充要条件：资源分配图不可完全简化。
不存在环路一定没死锁，存在环路可能不存在死锁。
在一系列简化后，能消去图中所有边，使所有进程节点孤立，则不会产生死锁。

死锁解除的方法：
抢占资源：从一个或多个进程中抢占足够资源分配给死锁进程
终止（撤销）进程：直至打破循环环路，解脱死锁状态

终止进程方法：终止所有死锁进程、逐个终止进程

第九章 操作系统接口

9.1 接口

OS向用户提供的两类接口：用户接口、程序接口

用户接口分类：联机用户接口和脱机用户接口

脱机用户接口：批处理用户接口（作业控制语言JCL、作业控制块JCB）
联机用户接口：字符界面、图形化界面；命令语言（Shell）

9.2 系统调用

系统调用：用户程序取得系统服务的唯一途径
系统调用与一般调用的区别：
运行在内核态、通过软中断进入、返回问题、嵌套调用

9.3 Linux提供的接口

Linux实验有关内容：
常用shell命令：
ls、ps、who、cd、mkdir、cat、kill、wc、link、chmod、chown、data
美元#代表执行所带参数个数、美元1代表第一个参数的值

系统调用命令：
fork、wait、execlp、exit、sleep、signal、kill、getpid、getppid、pipe、pause的应用

进程间的通信：软中断、管道、文件