操作系统 - 应试笔记 · 陈驰水-个人博客

本博客为 吉林大学软件学院操作系统课程 复习笔记。

本文内容基本只包括 简答题 的复习。

名词解释题，网上已经有很多学长学姐的笔记，推荐 gonghr 学长。

如果想 系统学习操作系统，本文也能起到一定的梳理作用。

考试范围来自 2022级

考试范围
#

第一章绪论
#

操作系统（名词解释）：操作系统是位于硬件层(HAL)之上，所有其它软件层之下的一个系统软件，是管理系统中各种软硬件资源，方便用户使用计算机系统的程序集合。

类别与发展（考过至少写出六种类别）

第二章进程管理
#

多道程序设计
#

吞吐量 = 作业道数 / 全部处理时间

利用率 = CPU使用时间 / 运行总时间

CPU利用率越高，说明系统效率越高对不对？

不对，比如程序中出现死循环使得 CPU 利用率解决百分之百，无法处理其他请求，系统效率极低。
单道程序设计资源利用率低
Multiprogramming（多道程序设计）：多道程序设计是指在一台处理机上同时并发运行多个程序，即在一台处理机上有多个程序同时进入主存并发运行，宏观上并行，微观上串行交替运行。

思考：内存中的程序数量是否越多越好

道数过少，系统资源利用率低

道数过多，系统开销(system overhead)增大，程序响应速度下降

进程
#

1.重中之重

4. 操作系统为什么提出“作业、进程、线程”的概念？

PPT小结：

作业与进程

作业进入内存后变为进程

一个作业通常与多个进程相对应

进程与线程

一个进程一般包含多个线程，至少包含一个线程

不支持多线程的系统，可视为单线程进程

**作业：**用户在一次解题或一个事物处理过程中要求计算机系统所做工作的集合。它包括用户程序、所需要的数据及控制指令等。作业是由一系列有序的步骤组成的。

进程：

进程是程序的一次执行

进程是可以参与并发执行的程序

进程是程序和数据一道通过处理器执行时所发生的活动

进程是具有一定独立功能的程序关于一个数据集合的一次运行活动

程序和进程

程序静态，进程动态。这是进程和程序的本质差异

程序可长期保存，进程有生存期

一个程序可对应多个进程，一个进程只能执行一个程序

并发：可与其它进程同时执行

宏观同时，“交替执行”，不要求多个CPU

**线程：**线程是进程中的一个实体，是被系统独立调度和执行的基本单位。

作业是在早期的多道批处理系统中提出的，在现代操作系统中基本没有概念及应用。

引入进程的目的是更好地使多道程序并发执行，提高资源利用率和系统吞吐量

引入线程地目的使减小程序在并发执行时所付出地时空开销（上下文切换），提高操作系统地并发性能。

进程状态转化

进程创建时是什么状态

就绪态

当进程已分配到除处理器(CPU)以外的所有必要资源后，只要再获得处理器就可以执行的状态称为就绪状态。在一个系统里,可以有多个进程同时处于就绪状态，通常把这些就绪进程排成一个或多个队列，称为就绪队列。

进程结束时是什么状态

终止态

当一个进程已经正常结束或异常结束，操作系统已将其从系统队列中移出，但是，尚未撤消，这时称为终止状态。

下图为考试原题

进程控制块PCB 标志进程存在的数据结构，其中保存系统管理进程所需的全部信息：pid、进程状态、现场信息、调度参数、所属用户(uid)……

当调度某进程执行时，需要从该进程的PCB中查询其状态及优先级等参数

当调度到某进程后，根据PCB中的现场信息恢复现场，并根据PCB中的程序和数据的内存地址找到程序和数据

进程执行过程中，当需要与其它进程通信时，也要访问PCB

当进程发生进程切换时，需要将现场信息从系统栈弹出，保存于PCB中

系统建立进程时建立PCB，撤销进程时撤销PCB.

进程上下文：PCB + 程序

系统开销：运行操作系统程序完成系统管理工作所花费的时间和空间

UNIX中分为 P区（proc）和U区（user）

P区有Pid Uid 进程状态等需要常驻内存

U区是有进程被使用的时候才用的不需要常驻
进程切换时需要保存的现场信息

16. 进程的现场信息包括什么，可能存放的位置

a 地址寄存器

保存当前CPU所访问的内存单元的地址

b 通用寄存器

用于传送和暂存数据，也可参与算术逻辑运算，并保存运算结果

c 浮点寄存器

用于存储浮点数字，它决定着计算机的计算精度。

d. SP(系统栈指针)

e. PSW(程序状态字)

f. PC(指令计数器)

g. 打开文件表

存放位置：进程栈（不是系统栈）
进程的特征

§并发性 §动态性 §独立性 §交互性 §异步性 §结构性
进程的创建与撤销

进程创建 §向系统申请一个空闲PCB，并指定唯一的进程标识

§为新进程分配资源

§初始化新进程的PCB

§加载程序

§将PCB入就绪队列.

考试原题！！考了两次

引起进程创建的事件

用户登录作业调度提供服务应用请求

进程撤销 exit()

从系统PCB表中找到被撤销进程的PCB

检查被撤销进程的状态是否为执行状态。若是，则立即停止该进程的执行

设置重新调度标志，以便在该进程撤销后将处理器分配给其它进程

检查被撤销进程是否有子孙进程，若有子孙进程还应撤销该进程的子孙进程

回收该进程占有的全部资源并回收其PCB

进程等待

停止当前进程的执行，由于该进程正处于执行状态，故应停止该进程的执行

保存该进程的现场信息。为了使进程以后能够重新调度运行，应将进程的现场信息送入其PCB中保存

将进程状态改为等待.

进程唤醒(事件发生)

将被唤醒进程从相应的等待队列中移除

将进程状态改为就绪，并将该进程插入就绪队列.

思考：父进程创建子进程与主程序调用子程序区别?

父进程创建子进程后，父进程与子进程可同时执行

主程序调用子程序后，主程序暂停在调用点，子程序开始执行，直到子程序执行完毕返回，主程序才开始执行

思考

若系统中没有运行进程，是否一定没有就绪进程？

a：不一定比如死锁

若系统中即没有运行进程，也没有就绪进程，系统中是否就没有进程？

a：可能有等待状态的进程

在采用优先级进行调度时，运行进程是否一定是系统中优先级最高的进程？

a：就绪队列中的最高优先级进程

某进程被唤醒后立即投入运行，就说这个系统采用的是剥夺式调度方法？

a：不是，若当前CPU空闲，则非剥夺

线程
#

**线程是进程中一个相对独立的执行流。**一个进程可以包含多个线程，这些线程执行同一程序中的相同代码段或不同代码段，共享数据区和堆。一般认为，进程是资源的分配单位，线程是CPU的调度单位。

多线程优点：

§切换速度快（地址空间不变，避免了上下文切换（PCB+程序））

§系统开销小

§通讯容易（共享数据空间）

线程控制块TCB(Thread control block)

标志线程存在的数据结构，其中包含对线程管理需要的全部信息

内容：线程标志线程状态调度参数现场(通用寄存器,PC,SP) 链接指针

存放位置：

用户级线程：目态空间（用户空间）

核心级线程：系统空间

！考试原题：用户级线程与系统级的线程的区别（优缺点）

用户级线程：

§若同一进程中的多个线程至少有一个处于运行态，则该进程的状态为运行态

§若同一进程中的多个线程均不处于运行态，但至少有一个线程处于就绪态，则该进程的状态为就绪态

§若同一进程中的多个线程均处于等待态，则该进程的状态为等待态

优点
- 不依赖于操作系统，调度灵活
  
  同一进程中多线程切换速度快(不需进入操作系统)
- 调度算法可以是进程专用的，不同的进程可以根据需要，对自己的线程选择不同的调度算法。
- 用户级线程的实现于操作系统平台无关，对线程管理的代码是属于用户程序的一部分。
缺点
- 当线程执行一个系统调用时，不仅该线程被阻塞，而且进程内的所有线程都被阻塞。
- 不能发挥多处理机的优势，内核每次分配给进程仅有一个 CPU，因此进程中仅有一个线程能执行。

内核级线程

优点
- 能充分发挥多处理机优势，内核能同时调度同一进程中多个线程并行执行。
- 如果进程中一个线程被阻塞，内核可以调度该进程中的其他线程占用处理机，也可以运行其他进程中的线程。
- 非新版本：内核支持线程具有很小的数据结构和堆栈，线程切换比较快、开销小。
- 非新版本：内核本身也可以采用多线程技术，可以提高系统的执行速度和效率。
缺点
- 同一进程中的线程切换，需要从用户态到核心态进行，系统开销大。
- 非新版本：线程的创建、撤销、调度在操作系统核心态，占用系统资源，增加系统开销。

具体区别

核心级别线程操作系统可见；用户级别线程操作系统不可见
用户级别线程的创建、撤销和调度不需要操作系统的支持，且是在（程序）语言这一级处理的。核心级别线程的创建、撤销和调度都需要操作系统内核的支持
用户级别线程执行系统调用命令将导致其所属进程被中断，核心级别线程执行系统调用命令将导致线程被中断
在仅有用户线程的系统内，CPU调度以进程为单位。在有核心级别线程的系统内，CPU调度以线程为单位
用户级别线程的实体是运行在用户态下的程序，而核心级别线程的实体则是可以运行在任何状态下的程序

第三章中断和调度
#

中断
#

定义：处理器在运行过程中，出现了某一事件，必须中止正在运行的程序，转去处理这个事件，然后再返回原来运行的程序

引入中断的目的

实现并发活动
实现实时处理
故障自动处理

中断类型：

自愿性主要的是系统调用、访管指令

强迫性是硬件故障、程序性中断、外部中断、IO中断

中断嵌套与中断屏蔽 计组学的

中断屏蔽（关中断）-> 保护现场->开中断（开放高优先级）->中断处理->关中断->恢复现场（用PCB）->开中断->中断返回

中断相当于一种特殊的子程序调用，发生时刻具有不确定性

§思考1：中断现场保存在什么地方？进程现场保存在什么地方？

中断现场主要保护PC PSW（中断向量），一般在系统栈中保存。

进程以PCB进程控制块的形式保存在所有进程共享的内核空间中。

§思考2：为什么说PCB保存的是核心级别现场？用户级别现场保存在什么地方？

PCB保存在内核空间中，可以供操作系统内核以及其他进程访问。

用户级现场保存在用户堆栈中，指的是线程级别的上下文信息，存储在目态空间。

使用临界区的四个必要条件 ①空闲让进：临界区空闲时应该允许一个进程访问； ②忙则等待：临界区被访问时，其余想访问他的进程必须等待； ③有限等待：等待的进程在外等待的时间必须是有限的； ④让权等待：若等待进程一直等待，迟迟进不到临界区时，应该让出cpu，防止忙等待。

第五章死锁
#

死锁：一组进程中的每一个进程，均无限期地等待此组进程中其它进程所占有的，因而永远无法得到的资源，这种现象称为进程死锁
类型：竞争资源引起的死锁（可以竞争相同或不同的资源）、进程通讯引起的死锁、其他
饥饿(starvation)

当等待时间给进程推进和响应带来明显影响时,称发生了进程饥饿

饥饿到一定程度的进程所赋予的使命即使完成也不再具有实际意义时称该进程被饿死

§饥饿 vs 死锁

§死锁进程处于等待状态，忙式等待的进程并非处于等待状态, 但却可能被饿死

§死锁进程等待永远不会释放的资源, 饿死进程等待可能被释放,但却不会分给自己的资源,其等待时间没有上界

§死锁一定发生了循环等待,饿死不然

§死锁至少涉及两个进程, 饿死进程可能只有一个

第六章主存
#

动态异长分区的分配

空闲区域表

最先适应 (First Fit)

从低地址到高地址

次适应法(Next Fit)

从低地址到高地址，从上次的地址开始继续找

最佳适应 (Best Fit)

从小到大排序，会出碎片

最坏适应 (Worst Fit)

从大到小排序，大进程无处可用

碎片

动态异常分区存储分配可能形成很小的空闲区域，称为碎片(fragment)

如果碎片很多，将造成严重的存储资源浪费

解决方法-紧凑(compaction)

移动所有的占有区域，以使所有的空闲区域连成一片。缺点：开销大

内存管理方式

§界地址管理方式（一维地址）

§页式管理方式（一维地址）

§段式管理方式（二维地址）

§段页式管理方式（二维地址）
页式管理方式：具体和计组一样多加了快表、页表

页表对应逻辑页号->页框号（存在多级页表）

传统页表面向进程空间

每个进程逻辑页面有一表项

当进程空间很大时，页表很大

反置页表面向内存空间

对每个内存页框设置一个表项，表项的序号为物理页框号f，表项的内容为进程标识pid与逻辑页号p的有序对

反置页表大小固定

整个系统一个反置页表，为所有进程所共用

快表相同，是更快的页表，但空间小

段的共享（标记当前多少进程正在使用，归零后才能写入）

段的保护->

对于保存共享代码的段，任何进程都不能修改它
对于具有保密要求的段，某些进程不能读取它
对于属于系统数据的段，某些进程不能修改等

考试原题

分段和分页的区别和优缺点

页的大小是固定的，由操作系统决定，而段的大小不固定，取决于我们当前运行的程序。

分页仅仅是为了满足操作系统内存管理的需求，而段是逻辑信息的单位，它含有一组其意义相对完整的信息，在程序中可以体现为代码段，数据段，是为了满足用户的需要。

段一般比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。

分页对用户是透明的，分段对用户是可见的　　　　

第八章文件
#

物理结构（顺序、链接、索引、倒排、散列）

文件块：逻辑块号 + 块内地址（和页面一个道理）

fcb：类似pcb 存储首地址，长度等信息

顺序：整块的内存，用长度判越界
链接：fcb存储块数，用指针形成链表
索引：多加一个索引表，fcb存储索引表号和数量

学习通简答题
#

作业、进程、线程（what，why）
#

见上述表达

忙式等待与排队等待
#

忙等待：当某进程正在使用临界区，其他试图进入临界区的进程都必须在进入区内连续空循环，会持续调用CPU查询临界区状态。

排队等待：当某进程正在使用临界区，其他试图进入临界区的进程按顺序加入排队队列，当该临界区进入空闲时，给队首信号，让其进入临界区。在等待过程中不需要持续占用CPU。

区分进程间的互斥与同步
#

两者都属于进程的竞态，其都有多个进程竞争使用不能被同时使用的只有，使得其一定要出现时间上的先后处理。

互斥指的是当一个进程进入临界区时，其他程序一定要等待，当其退出临界区后，另一个进程才能访问该临界资源，其临界资源的使用是互斥的，在宏观上是串行的。

同步指的是进程间具有前后执行顺序要求的，具有某种合作关系。

面包店思路
#

说明一下面包店算法的思想? 如何实现的互斥与公平性问题?

将每个线程想象成面包店的顾客，其想获得临界资源的操作为进入面包店，面包店每次只能进入一个人即临界资源只能同时被一个线程使用。想获取临界资源的线程获取一个号码，该号码逐次加一。但是当多个线程同时取号时，number修改前都进行了max，则他们会取到相同的number，但在执行时按照字典序进行。按照签到号码从小到大获取临界资源，完成后号码归零。

A[i]=true;  
number[i]=max{number[0],…,number[n-1]}+1;
A[i]=false;

For (j=0; j< n; j++) {  // 遍历 n 个进程  
    While (A[j]);       // 当有线程 j 正在获取号码，阻塞
    While ((number[j]!=0) && (number[j],j)<(number[i],i)); // 如果找到线程 j 比 i 小，则等待 j 线程结束
}

i 进入临界区……
// 清空 i 的号码
number[i] = 0;