标签：入门调度并发线程进程 2.1 408 操作系统

操作系统

1.1 操作系统的概念、特征、功能、目标

1.1.1 操作系统的概念

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

1.1.2 操作系统的特征

操作系统的基本特征包括并发、共享、虚拟和异步。

并发

并发和并行的区别：

并发是指两个或多个事件在同一时间间隔内发生。宏观上有多道程序在同时执行，微观上还是分时交替执行（对于单处理机）。操作系统的并发性是通过分时得以实现的。

并行真正实现同时刻执行多个任务。

共享

资源共享即共享，指系统中的资源可供内存中多个并发执行的进程共同使用。

共享有两种资源共享的方式：

互斥共享方式：当进程A访问某资源时，必须先提出请求，如果此时该资源空闲，系统便可将之分配给进程A使用，此后若再有其他进程也要访问该资源时（只要A未用完）则必须等待。仅当进程A访问完并释放该资源后，才允许另一进程对该资源进行访问。例如打印机、磁带机。
同时共享方式：允许在一段时间内由多个进程“同时”对它们进行访问。这里所谓的“同时”往往是宏观上的，而在微观上，这些进程可能是交替地对该资源进行访问，即“分时共享”。

并发和共享的关系

并发和共享是操作系统两个最基本的特征，这两者之间互为存在条件：

资源共享是以程序的并发为条件，若程序不允许程序并发执行，则自然不存在资源共享问题。
若系统不能对资源共享实施有效的管理，也必将影响程序的并发执行，甚至根本无法并发执行。

虚拟

虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。

例如：

虚拟处理器技术：通过多道程序设计技术让多道程序并发执行方法，来分时使用一个处理器。把一个物理上的CPU虚拟为多个逻辑上的CPU。使用时分复用技术。
虚拟存储器：将一台机器的物理存储器变为虚拟存储器，以便从逻辑上来扩充存储器容量。使用空分复用技术，把CPU抽象成进程，把磁盘抽象成文件，把内存抽象成地址空间。

异步

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

1.1.3 操作系统的目标和功能

操作系统作为计算机系统资源的管理者

操作系统作为用户与计算机硬件系统之间的接口

操作系统提供的接口主要分为两类：

命令接口：联机命令接口又称交互式命令接口，适用于分时或者实时系统的接口。

脱机命令又称批处理命令接口，适用于批处理系统。

程序接口：由一组系统调用命令组成，用户通过在程序中使用这些系统命令来请求操作系统为其提供服务。操作系统不允许用户直接操作各种硬件资源，因此用户程序只能通过系统调用的方式来请求内核来为其服务，间接的使用各种资源。
GUI：通过调用程序接口实现，严格地说GUI图形接口不属于操作系统的一部分，但图形接口所调用的系统调用命令属于操作系统的一部分。

1.2 操作系统的发展与分类（了解）

1.3 操作系统的运行机制和体系结构

1.3.1 中断和异常

中断也称外中断，指来自CPU执行以外的事件的发生，如设备发出的I/O结束中断。

异常也称内中断，指来自CPU执行指令内部的事件，如地址越界、算术溢出。

1.3.2 系统调用

注意

陷入指令是唯一一个只能在用户态执行，而不可以在核心态执行的指令。

系统调用就是用户程序要求操作系统的服务。

1.3.3 操作系统的体系结构

2.1 进程与线程

2.1.1 进程的概念和特征

概念

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立的单位。

组成

PCB（程序控制块）、程序段、数据段。

注意

PCB是进程存在的唯一标志

2.1.2 进程的状态与转换

2.1.3 进程控制

2.1.4 进程的组织

2.1.5 进程通信

2.1.6 线程和多线程模型

线程的基本概念

引入进程的目的是为了更好地让多道程序并发执行，以提高资源利用率和系统吞吐量，增加并发程度。

而引入线程是为了减小程序在并发执行时所付出的时空开销，提高操作系统地并发性能。也叫轻量级进程。

线程是一个CPU执行单元，也是程序执行流的最小单元，由线程ID、程序计数器、寄存器集合和堆栈组成。

线程是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只用有一点在运行中必不可少的资源，但它可以与同属于一个进程的其它进程的其他线程共享进程所拥有的全部资源。

线程也有就绪、阻塞和运行三种基本状态。

由于一个进程内部有多个线程，如果线程的切换发生在同一个进程内部，则只需要很少的时空开销。

线程与进程的比较

调度。在传统的操作系统中，拥有资源和独立调度的基本单位都是进程。在引入线程的操作系统中，线程是独立调度的基本单位，进程仍是资源的基本单位。
拥有资源。（前面已经叙述）
并发性。在引入线程的操作系统中，不仅进程之间可以并发执行，而且多个线程之间也可以并发执行，从而使操作系统有更好的并发性，提高系统的吞吐量。
系统开销。由于创建和撤销进程时，系统都要为之分配或者回收资源，如内存空间、IO设备等。而且，进行进程切换时，涉及当前执行进程CPU环境的保存及新调度到进程CPU环境的设置，而进程切换时只需要保存和设置少量的寄存器内容，开销很小。此外，线程之间共享进程的地址空间，所以线程之间的同步与通信非常容易实现。
地址空间和其他资源。进程的地址空间之间相互独立，同一进程的各线程共享进程的资源。
通信。进程间的通信需要进程同步和互斥手段的辅助，而线程可以直接读或写进程数据段。

线程的实现方式

多线程模型

2.1.7 处理机调度的概念、层次

高级调度

中级调度

低级调度

2.1.8 进程调度的时机、切换与过程、方式

进程调度的时机

进程调度的方式

进程的切换和过程

2.1.9 调度算法的评价指标

CPU利用率
系统吞吐量
周转时间
带权周转时间
平均带权周转时间
等待时间
响应时间

2.1.10 FCFS、SJF、HRRN调度算法

FCFS（先来先服务）、SJF（短作业优先）、HRRN（高响应比优先）

FCFS(先来先服务)

SJF(短作业优先)非抢占

SJF(短作业优先)抢占

HRRN(高响应比优先)

2.1.11 时间片轮转、优先级、多级反馈队列

时间片轮转调度算法

注意

在时间片轮转调度算法中，时间片的大小对系统性能的影响很大。

如果时间片足够大，以至于所有进程都能在一个时间片内执行完毕，则时间片轮转调度算法就退化为先来先服务调度算法。
如果时间片很小，那么处理机将在进程间过于频繁切换，使处理机的开销增大，而真正用于运行用户进程的时间将减少。

优先级调度算法(非抢占)

优先级调度算法(抢占)

多级反馈队列调度算法

被抢占处理机的进程会重新放回原队列的队尾

2.1.12 进程同步、互斥

进程同步

进程互斥

2.1.12.1 实现临界区互斥的基本方法

单标志法

双标志先检查法

双标志后检查法

Peterson算法

2.1.13 信号量

整型信号量

记录型信号量

信号量机制实现

2.1.14 经典同步问题（难点）

生产者-消费者问题

多生产者-多消费者问题

吸烟者问题

读者-写者问题

哲学家问题

2.1.15 管程

管程的定义

管程是代表共享资源的数据结构和对该共享数据结构实施操作的一组过程所组成的资源管理程序，这组操作能初始化并改变管程中的数据和同步进程。

生活化的语言介绍管程

管程实质上是一个抽象类，这个抽象类有好几个成员变量，系统中任何设备都可以通过这几个成员变量进行区分和描述，管程中还有对这些成员变量进行操作的一组成员函数，例如，对外设的操作中，会有read，write这些函数。如果进程p0要使用一台打印机，于是管程这个抽象类就会利用初始值语句对自身的几个成员变量赋初始值（这个行为不需要程序员关注），特定的几个初值可以让管程表示成一台打印机，进程p0进入管程后，通过调用管程中的成员函数对这台打印机进行操作。每次进入这个管程只能是一个进程。

2.1.16 死锁

死锁的定义

在多道程序系统中，由于多个进程的并发执行竞争资源而互相等待。例如，某计算机系统中只有一台打印机和一台输入设备进程p1正占用输入设备，同时又提出使用打印机的请求，但此时打印机正在被进程p2所占用，而p2在未释放打印机之前，又提出请求使用正被p1占用着的输入设备。这样两个进程相互无休止地等待下去，均无法继续执行，此时两个进程陷入死锁状态。

死锁的处理策略

为使系统不发生死锁，必须设法破坏产生死锁的四个必要条件之一，或者允许死锁发生，但当死锁发生时能检测出死锁，并有能力实现恢复。

3.1 内存管理

3.1.1 内存管理的概念

内存管理的概念

内存管理的概念就是对内存进行划分和动态分配。

内存管理的功能

内存空间的分配和回收：由操作系统完成主存储器空间的分配和管理，使程序员摆脱存储分配的麻烦，提高编程效率。
地址转换：在多道程序环境下，程序中的逻辑地址与内存中的物理地址不可能一致，因此存储管理必须提供地址变换功能，把逻辑地址转换成相应的物理地址。
内存空间的扩充：利用虚拟存储技术或者自动覆盖技术从逻辑上扩充内存。
存储保护：保证各道作业在各自的存储空间内运行，互不干扰。

3.1.2 覆盖与交换

覆盖与交换技术是在多道程序环境下用来扩充内存的两种方法

覆盖的基本思想

由于程序运行时并非任何时候都要访问程序的各个部分（尤其大程序），因此可以把用户空间分成一个固定区和若干个覆盖区。将经常活跃的部分放在固定区，其余部分按调用关系分段。首先将那些即将要访问的段放入覆盖区，其它段放在外存中，在需要调用前，系统再将其调入覆盖区，替换覆盖区中原有的段。

交换的基本思想

把处于等待状态（或在CPU调度原则下被剥夺运行权利）的程序从内存移到辅存，把内存空间腾出来，这一过程又叫换出；把准备好竞争CPU运行的程序从辅存移到内存，这一过程又称为换入。

现在

交换技术主要是在不同进程（或作业）之间进行，而覆盖则用于同一个程序或者进程中。由于覆盖技术要求给出程序段之间的覆盖结构，使得其对用户和程序员不透明，所以对于主存无法存放用户程序的矛盾，现代操作系统是通过虚拟内存技术来解决的，覆盖技术则已成为历史，而交换技术在现代操作系统中仍具有较强的生命力。

3.1.3 连续分配管理方式

单一连续分配

固定分区分配

动态分区分配

注意

在算法实现时，分配操作中最佳适应法和最大适应法需要对可用块进行排序或遍历查找，而首次适应法和邻近适应法只需要简单的查找。在回收操作中，当回收的块与原来的空闲块相邻时需要将这些块合并。在算法实现时，使用数组或链表进行管理，除了内存的利用率，这里的算法开销也是操作系统设计需要考虑的一个因素。

3.1.4 基本分页存储管理的基本概念

区别

连续分配：为用户进程分配的必须是一个连续的内存空间。

非连续分配：为用户进程分配的可以是一些分散的内存空间。

地址的转换

要算出逻辑地址对应的页号
要知道该页号对应页面在内存中的起始地址
要算出逻辑地址在页面内的偏移量
物理地址=页面地址+页面偏移量

页号=逻辑地址/页面长度（取除法的整数部分）

页面偏移量=逻辑地址%页面长度（取除法的余数部分）

页面在内存中的起始位置：操作系统需要用某种数据结构记录进程各个页面的起始位置。

3.1.5 基本地址变换机构

3.1.6 具有快表的地址变换机构

对比

由上面介绍的地址变换过程可知，若页表全部放在内存中，则存取一个数据或一条指令至少需要访问两次内存。一次是访问页表，确定所存取的数据或者指令的物理地址，第二次才根据该地址存取数据或者指令。为此，在地址变换机构增设了一个具有并行查找能力的高速缓冲存储器——快表，又称联想存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，主存中的页表常称为慢表。

3.1.7 两级页表

3.1.8 基本分段存储管理方式

分页和分段对比

3.1.9 段页式管理方式

3.1.10 虚拟内存的基本概念

3.1.11 请求分页管理方式

3.1.12 页面置换算法

最佳置换算法理想化

最佳置换算法可以保证最低的缺页率，但实际上只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

3.1.13 页面分配策略

系统有足够的对换区空间

系统缺少足够的对换区空间

UNIX方式

4.1 文件

4.1.1 初识文件管理

4.1.2 文件的逻辑结构

按逻辑结构分类

无结构文件（流式文件）如.txt文件
有结构文件（记录式文件）:

顺序文件
索引文件
索引顺序文件
直接文件或散列文件

4.1.3 文件目录

文件控制块

文件控制块（FCB）是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。
FCB主要包含以下信息：基本信息，如文件名、文件的物理位置、文件的逻辑位置、文件的物理结构等。存取控制信息，如文件存取权限等。使用信息，如文件建立时间、修改时间等。