13180-操作系统

江苏省高等教育自学考试【13180-操作系统】学习笔记

课程代号	课程名称	教材代号	教材名称	作者	出版社	版次
13180	操作系统	131801	操作系统(附大纲)	陈向群、孙卫真	机械工业出版社	2023 年

操作系统的概念

计算机系统的组成

计算机系统包括硬件(子)系统和软件(子)系统。

计算机系统的资源包括两大类：硬件资源和软件资源。

软件系统（程序、数据）
- 应用软件：文字处理、图形图像处理、科学计算、MIS等
- 支撑软件：数据库、网络、多媒体等
- 系统软件：操作系统、编译程序等
硬件系统
- 中央处理器（CPU）
- 内存
- 外存储器（磁盘、磁带等）
- 输入输出设备（键盘、鼠标、显示器、打印机等）

在计算机系统中，集中了资源管理功能和控制程序执行功能的一种软件称为操作系统。

操作系统的定义

操作系统是计算机系统中的一个系统软件，能有效地组织和管理计算机系统中的硬件及软件资源，合理地组织计算机工作流程，控制程序的执行，并向用户提供各种服务功能，使得用户能够灵活、方便、有效地使用计算机，并使整个计算机系统高效运行。

操作系统的任务：

组织和管理计算机系统中的硬件及软件资源。
向用户提供各种服务功能。

操作系统在计算机系统中的地位和作用

并发性、共享性、虚拟性和异步性是操作系统的特征

并发性。并发性是指在计算机系统中同时存在若干正在运行的程序，从宏观上来看，这些程序在同时向前推进。从微观上来看，在单处理器的环境下，这些同时运行着的程序是交替在CPU上运行的。
共享性。共享性是指操作系统程序与多个用户程序共用系统中的各种资源。在计算机系统中，对资源的共享一般有两种形式：互斥共享和同时共享。
虚拟性。把物理上的一个实体变成逻辑上的多个对应物，或把物理上的多个实体变成逻辑上的一个对应物的技术。
异步性。操作系统必须随时对以不可预测的次序发生的事件进行响应。

操作系统的发展

多道批处理操作系统

允许多个程序同时存在于内存之中，由中央处理器以切换方式为之服务，使得多个程序可以同时执行。

分时与实时操作系统

分时系统是指多个用户通过终端设备与计算机交互作用来运行自己的作业，并且共享一个计算机系统而互不干扰，就好像自己有一台计算机。

通用操作系统

个人计算机操作系统

[非考点] 现代操作系统的两大发展方向—宏观应用与微观应用

操作系统分类

批处理操作系统

用户将作业交给系统操作员，系统操作员在收到作业后，并不立即将作业输入计算机，而是在收到一定数量的用户作业之后，组成一批作业，再把这批作业输入计算机中。

操作员将作业“成批”地输入到计算机中，由监督程序识别一个作业，进行处理后再取下一个作业。这种自动定序的处理方式称为批处理方式。

分时操作系统

实时操作系统

实时操作系统是指使计算机能在规定的时间内，及时响应外部事件的请求，同时完成对该事件的处理，并能够控制所有实时设备和实时任务协调一致地开展工作。

实时操作系统为了能够实现硬实时或软实时的要求，除了具有多道程序系统的基本能力以外，还需要有以下几方面的能力： 实时时钟管理、过载防护、 高可靠性。

个人计算机操作系统

个人计算机操作系统是一种单用户的操作系统。

个人计算机操作系统的主要特点是：计算机在某一时间内为单个用户服务；采用图形界面人机交互的工作方式，界面友好；使用方便，用户无须具备专门知识，也能熟练地操纵系统。

网络操作系统

为计算机网络配置的操作系统称为网络操作系统。

分布式操作系统

将大量的计算机通过网络联结在一起，可以获得极高的运算能力及实现广泛的数据共享。这样一种系统称为分布式系统。

嵌入式操作系统

其他类型操作系统

操作系统设计

操作系统设计的复杂度

在操作系统设计的过程中，主要的困难有设计复杂程度高、正确性难以保证、研发周期长。

操作系统的设计过程

功能设计
算法设计
结构设计。结构设计是指按照系统的功能和特性要求，选择合适的结构，使用相应结构设计方法将系统逐步分解、抽象和综合，使操作系统结构清晰、简明、可靠、易读、易修改，而且使用方便，适应性强。

操作系统的设计目标

一个高质量的操作系统应具有可靠性、高效性、易维护性、可移植性、安全性等特征。

操作系统的结构设计

操作系统的体系结构：整体式结构、层次式结构、客户/服务器（微内核）结构、外核结构

整体式结构

首先确定操作系统的总体功能，然后将总体功能分解为若干个子功能，实现每个子功能的程序称为模块。分解为最基本的模块为止。

层次式结构

把操作系统的所有功能模块，按功能流图的调用次序，分别排列成若干层，各层之间的模块只能是单向依赖或单向调用（如只允许上层或外层模块调用下层或内层模块）关系。

客户/服务器（微内核）结构

将操作系统分成用于实现操作系统最基本功能的内核和提供各种服务的服务进程两个部分，这样的操作系统结构是微内核结构。

外核结构

操作系统启动

操作系统的引导方式

BIOS引导
UEFI引导

操作系统的引导过程

将存放在硬盘上的静态的系统装载到内存中，并开始执行操作系统的过程。

操作系统的启动机制

启动过程分为四个部分：BIOS自检、系统引导、启动内核、初始化系统。

当计算机开机时，BIOS自检会进行自检并检测出第一个能够引导系统的设备，比如硬盘或光驱。

计算机系统的层次结构

在计算机系统的层次结构中，所有子系统都可以包括在硬件（子）系统和软件（子）系统这两个层次中。


硬件系统	`中央处理器`、`存储系统`、`中断机制`、`I/O技术`、 `时钟`
软件系统	`系统软件`、`支撑软件`、`应用软件`

系统软件


`操作系统`	软件系统的最下层，邻接底层硬件。主要功能是实现资源的管理和控制程序的运行。常用的操作系统有 Windows、UNIX 和 Linux 等
`编译系统`	把由高级语言编写的程序翻译为计算机可以直接执行的目标代码。目前常见的高级语言编译系统有 C/C++、VB 语言的编译系统等。
`数据库`	对大量数据的管理功能，包括对数据的分类、存储、加工、删除以及检索等操作。常见的大型数据库管理系统有 SQL Server、Oracle、Sybase 和 IBM DB 等。

支撑软件


网络通信程序	实现计算机网络通信的功能。
多媒体支持软件	协助计算机系统实现对图形、图像、语音和视频等多媒体信息的处理。
硬件接口程序	提供与各种计算机外部设备的连接支持。
实用软件工具	提供了多种系统维护和操作的手段，如磁盘整理工具、文件修复工具等。
软件开发工具	为程序设计人员编写代码提供了友好、便捷的环境。

应用软件的种类和用途极其广泛。

CPU的构成与基本工作方式

CPU的结构

CPU一般由运算器、控制器、一系列的寄存器以及高速缓存构成。

运算器。实现指令中的算术和逻辑运算，是计算机的计算核心。
控制器。负责控制程序的运行流程，包括取指令、维护CPU状态、CPU与内存的交互等。
寄存器。一种暂时存储器，用于在CPU执行指令过程中暂存数据、地址以及指令信息。在计算机的存储系统中，寄存器具有最快的访问速度。寄存器为处理器本身提供了一定的存储能力，其速度比内存快得多，但是因为寄存器集成在微处理器芯片中，所以它的造价较高，存储容量一般也比较小。
高速缓存。处于CPU和物理内存之间，一般由控制器中的内存管理单元（MMU）管理，它的访问速度快于内存，低于寄存器，它利用程序局部性原理使得高速指令处理和低速内存访问得以匹配，从而大大提高了CPU的效率。

处理器中的寄存器：用户可见寄存器、控制和状态寄存器

用户可见寄存器


`数据寄存器`	又称为通用寄存器，主要用于各种算术逻辑指令和访存指令，对具有浮点能力和多媒体能力的处理器来说，浮点处理过程的数据寄存器和整数处理时的数据寄存器一般是分离的。
`地址寄存器`	存储数据及指令的物理地址、线性地址或者有效地址，用于某种特定方式的寻址。
`条件码寄存器`	保存CPU 操作结果的各种标记位，例如算术运算产生的溢出、符号等，这些标记在条件分支指令中被测试，以控制程序指令的流向。一般来讲，条件码可以被隐式访问，但不能通过显式方式修改。

控制和状态寄存器


`程序计数器`（PC）	记录了将要取出的指令的地址。
`指令寄存器`（IR）	包含了最近取出的指令。
`程序状态字`（PSW）	记录了处理器的运行模式信息，在有些处理器中，还包含了条件码。

指令执行的基本过程

处理器每次从存储器中读取一条指令，在取指令完成后，根据指令类别自动将程序计数器的值变成下一条指令的地址，通常是自增1 ; 取到的指令被放在处理器的指令寄存器中，处理器于是解释并执行这条指令。

开始 → 取下一条指令（取指） → 执行指令（执行） → 停止

指令分类
访问存储器指令	负责处理器和存储器之间的数据传送。
I/O指令	负责处理器和I/O模块之间的数据传送与命令发送。
`算术逻辑指令`	又称为数据处理指令，用以执行有关数据的算术和逻辑操作。
控制转移指令	可以指定一个新指令的执行起点。
处理器控制指令	这种指令用于修改处理器状态，改变处理器工作方式。

特权指令和非特权指令

特权指令是指指令系统中那些只能由操作系统使用的指令。特权指令是不允许一般用户使用的，因为如果允许用户随便使用这些指令（如设置程序状态字、启动某设备、设置中断屏蔽、设置时钟指令、清内存指令和建立存储保护指令等），就有可能使系统陷入混乱。

用户只能使用非特权指令，只有操作系统才能使用所有指令（包括特权指令和非特权指令）。如果一个用户程序需要使用特权指令，那么一般将引起一次处理器状态的切换，这时处理器通过特殊机制，将处理器状态切换到操作系统运行的特权状态，然后将处理权移交给操作系统中的一段特殊代码。通常将这一个过程形象地称为陷入（Trap）。

处理器的状态及其转换

内核态一般指操作系统管理程序运行时的状态，具有较高的特权级别，又称为管态、特权态、系统态或核心态。当处理器处于内核态时，全部指令（包括特权指令）可以执行，可使用所有资源，并具有改变处理器状态的能力。

用户态一般指用户程序运行时的状态，具有较低的特权级别，又称为目态、普通态。当处理器处于用户态时，就只有非特权指令能执行。

不同处理器状态之间的区别就在于赋予运行程序的特权级别不同，可以运行的指令集合也不相同，一般来说，特权级别越高，可以运行的指令集合越大，而且高特权级别对应的可运行指令集合包含低特权级的。

操作系统管理程序运行的状态称为管态。
系统启动时，处理器的初始状态为管态。
当用户程序占用处理器时，应让处理器在目态下工作。
当处理器处于管态时，可以执行全部指令。

CPU状态的转换

用户态到内核态的转换：其转换的唯一途径是中断。

内核态到用户态的转换：可通过设置PSW指令（修改程序状态字），实现从操作系统向用户程序的转换。当CPU处于内核态时，可执行包括特权指令在内的一切机器指令；当CPU处于用户态时，不允许执行特权指令。在系统启动时，CPU的初始状态为内核态，然后装入操作系统程序。操作系统退出执行时，让用户程序在用户态执行。

限制用户程序执行特权指令

用户程序中不能使用特权指令。

程序状态字（PSW）

在处理器中，最常见的控制和状态寄存器是程序状态字。程序状态字的作用是指示处理器状态，用程序计数器这个专门的寄存器来指示下一条要执行的指令。

处理器的状态字中通常包括以下状态代码。

CPU的工作状态代码。指明当前CPU的工作状态是内核态还是用户态，用来说明当前在CPU上执行的是操作系统还是一般用户，从而决定其是否可以使用特权指令或拥有其他特殊权力。
条件码。反映指令执行后的结果特征。
中断屏蔽码。指出是否允许中断。

存储系统

存储器的类型和分块

读写型存储器（RAM）

可以把数据存入其中任一地址单元，并且可在以后的任何时候把数据读出来，或者重新存入新的数据的存储器。常被称为随机访问存储器（RAM）。 RAM主要用作存放随机存取的程序的数据。

只读型存储器（ROM）

只能从其中读取数据，不能随意地用普通方法向其中写入数据。要向其中写入数据，只能用特殊方法实现。又称为只读存储器（ROM）。

存储分块

存储的最小单位称为“二进位”，它包含的信息为0或1。存储器的最小编址单位是字节，一个字节一般包含八个二进位。两个字节一般称为一个字，4 个字节称为双字。1024个字节称为1kB, 1024个1kB称为1MB, 1024个1MB称为1GB。

在为用户分配内存空间时，以块为最小单位，这样的块有时被称为一个物理页。内存空间的最小分配单位是块。

存储器的层次结构

对于计算机存储系统的设计，主要考虑三个问题：容量、速度和成本。

容量、速度和成本的匹配

存取速度越快，平均每比特价格越高，容量越小；存取速度越慢，平均每比特价格越低，容量越大。

采用层次化存储体系结构。当沿着层次下降时，每比特的价格将下降，容量将增大，速度将变慢，而处理器的访问频率也将下降。

较小、较贵而快速的存储设备以较大、较便宜而慢速的存储设备作为后盾，在整体上通过对访问频率的控制来提高存储系统的效能。

存储访问局部性原理

提高存储系统效能的关键在于程序的存储访问局部性原理。

存储保护

界地址寄存器。在CPU中设置一对界限寄存器来存放该用户作业在内存中的下限和上限地址，分别称为下限寄存器和上限寄存器。
存储保护键。

中断机制

中断的基本概念

中断是指CPU对系统中或系统外发生的异步事件的响应。异步事件是指无一定时序关系的随机发生的事件。

当发生某个异步事件后，处理器会中断对当前程序的执行，而转去处理该异步事件（称作执行该事件的中断处理程序）。在该异步事件处理完之后，处理器再转回原程序的中断点继续执行。

中断是一种常用的打断处理器的正常工作，要求它去处理某一事件的手段。

从通用的观点来看，中断依据被激发的手段可以分为强迫性中断和自愿性中断。

强迫性中断

程序性中断。在某些条件下由指令执行结果产生，例如算术溢出、被零除、用户态程序试图执行非法指令、访问不被允许访问的存储位置、虚拟存储中的缺页等。
时钟中断。由处理器内部的计时器产生，允许操作系统以一定规律执行函数，如时间片到时、硬件实时钟到时等。
输入输出(I/O)中断。由I/0控制器产生，用于通知一个I/0操作的正常完成或者发生的错误。
控制台中断。如系统操作员通过控制台发出命令等。
硬件故障中断。由掉电、存储器校验错等硬件故障引起。

中断依据中断事件发生和处理是否异步可以分为异步中断和同步中断。

异步中断简称为中断，同步中断一般称为异常。异步中断一般是由对当前程序而言的外部事件激发的，属于外源性质。这种类型的中断发生的时间具有很大的随机性。

异常则是由当前程序的编码和逻辑激发的，属于“内因”性质。对于当前程序，异常是必然事件。

中断系统

中断请求的接收

中断响应

中断处理

几种典型中断的处理

I/O中断
时钟中断。与系统运转、管理和维护相关的工作。主要包括：（1）维护软件时钟（2）处理器调度（3）控制系统定时任务（4）实时处理
硬件故障中断。由硬件引起，需要人工干预。硬件故障中断处理程序需要做的工作是保存现场，使用一定的手段警告管理员并提供一些辅助的诊断信息。
程序性中断。
系统服务请求（自愿性中断）

中断优先级、中断屏蔽与中断嵌套

多级中断与中断优先级

中断屏蔽

中断嵌套

允许优先级较高的中断打断优先级较低的中断处理过程称为中断嵌套。

I/O 技术

I/O 结构

通道

通道是独立于处理器，专门负责数据I/O传输工作的处理单元。通道对外部设备实行统一的管理，它代替CPU对I/O操作进行控制，从而使CPU和外部设备可以并行工作。

有了通道后，只要中央处理器启动了通道，通道就自行控制外设与主存间的信息传输，使CPU可以与设备并行工作。

通道的工作原理

在采用通道的计算机系统运行过程中，处理器按程序规定的顺序执行一条条指令。当处理器执行到一条“启动外设”（“启动I/O” ）的指令时，就按指令中给定的参数启动指定的设备。在设备启动之后，将该外部设备的控制权转移到通道，由通道控制该外部设备的有关操作。在该外部设备与内存之间发生的信息传送，由通道控制，而处理器则继续执行程序。

DMA技术

直接存储器访问（DMA）技术通过系统总线中的一个独立控制单元—DMA控制器，自动地控制成块数据在内存和I/O单元之间的传送。

缓冲技术

时钟

时钟一般分成硬件时钟和软件时钟。

时钟的功能

在多道程序运行的环境中，时钟可以为系统发现陷入死循环（由编程错误引起）的作业，从而防止机时的浪费。
在分时系统中，用时钟间隔来实现各个作业按时间片轮转运行。
在实时系统中，按要求的时间间隔输出正确的时间信号给相关的实时控制设备。
定时唤醒那些要求按照事先给定的时间执行的各个外部事件（如定时为各进程计算优先级，银行系统中定时运行某类结账程序等）。
记录用户使用各种设备的时间和记录某外部事件发生的时间间隔。
记录用户和系统所需的绝对时间，即年、月、日。

时钟的工作原理

硬件时钟：电路中的晶体振荡器，每隔一定间隔产生固定的脉冲频率，时钟电路中的时钟寄存器依据时钟电路所产生的脉冲数，对时钟寄存器进行加1的工作。

软件时钟：利用内存单元模拟时钟寄存器，并采用一段程序来计算相应的脉冲数，对内存时钟寄存器进行加1或减1的操作，从而模拟了时钟的功能。

系统调用

系统调用的概念

什么是系统调用

用户在程序中调用操作系统所提供的一些子功能。由特殊的机器指令实现。系统调用是操作系统提供给编程人员的唯一接口。

系统调用的分类


`进程控制类系统调用`	用于对进程的控制
`文件操作类系统调用`	创建文件、打开文件、关闭文件、读文件、写文件、创建一个目录、建立目录、移动文件的读/写指针、改变文件的属性等
`进程通信类系统调用`	用于进程之间消息和信号的传递
`设备管理类系统调用`	用来请求和释放有关设备，以及启动设备操作等
`信息维护类系统调用`	获得当前时间和日期、设置文件访问和修改时间、了解系统当前的用户数、操作系统版本号、空闲内存和磁盘空间的大小等

系统调用与一般过程调用的关系

系统调用处理过程

在系统中，为控制系统调用服务的机构称为陷入处理机构或异常处理机构。把由于系统调用引起处理机中断的指令称为陷入指令或异常指令(或称访管指令)。

进程的基本概念

进程的定义

进程是具有一定独立功能的程序在某个数据集合上的运行活动，是操作系统进行资源分配和调度的独立单位。

进程的特征

进程具有以下6 种特性：

并发性。一个进程可以与其他进程一起向前推进，即一个进程的第一个动作可以在另一个进程的最后一个动作结束之前就开始。
动态性。进程对应着程序的执行过程。进程的动态性体现在两方面：首先，进程有其生命周期，有产生，也有消亡；其次，在进程的生命周期内，进程的状态是不断变化的。
独立性。一个进程是一个相对完整的资源分配单位。
交互性。一个进程在运行过程中可能会与其他进程发生直接的或间接的相互作用。
异步性。每个进程按照各自独立的、不可预知的速度向前推进。
结构性。一个进程由程序、数据和进程控制块三部分组成。

进程的定义

进程状态及其转换

三状态进程模型

五状态进程模型

七状态进程模型

七状态模型与状态五状态进程模型相比，增加了就绪挂起和阻塞挂起两个状态。

进程从运行状态进入就绪状态的原因可能是时间片用完。

进程控制块

为了便于系统控制和描述进程的活动过程，在操作系统内核中定义了一个专门的数据结构，称为进程控制块（PCB）。

PCB的内容

进程的组成

进程由程序、数据和PCB三部分组成。

PCB的组织方式

为了便于管理，系统把所有的PCB用适当方式组织起来。一般来说，大致有以下三种组织方式。

线性方式
索引方式
链接方式

进程控制

进程控制方式：原语

进程有一个从创建到消亡的生命周期，这就需要对进程在整个生命周期中各种状态之间的转换进行有效的控制，称为进程控制。进程控制是通过进程控制原语来实现的。

对进程在整个生命周期中各种状态之间的转换进行有效的控制通过进程控制原语来实现。

原语，是由若干条指令组成的一个指令序列，用来实现某个特定的操作功能。这个指令序列的执行是连续的，具有不可分割性，在执行时也不可间断，直至该指令序列执行结束。原语是操作系统内核（由一组程序模块组成、完成操作系统中的基本功能）的一个组成部分。原语必须在管态下执行，并且常驻内存。

创建原语

一个进程可以使用创建原语创建一个新的进程，前者称为父进程，后者称为子进程。创建一个进程的主要任务是建立PCB。

撤销原语

阻塞原语

唤醒原语

Linux操作系统有关进程控制的系统调用

线程的引入及基本概念

线程的引入及基本属性

线程的组成

每个线程都有一个thread 结构，即线程控制块，用于保存自己的私有信息，主要由以下四个基本部分组成。

一个唯一的线程标识符。
描述处理器工作情况的一组寄存器（如程序计数器、状态寄存器、通用寄存器等）的内容。
每个 thread 结构都有两个栈指针：一个指向内核栈，另一个指向用户栈。当用户线程转变到内核态方式下运行时，就使用内核栈；当线程在用户态下执行时，就使用自己的用户栈。
一个私有存储区，用来存放现场保护信息和其他与该线程相关的统计信息等。

线程必须在某个进程内执行，它所需的其他资源，如代码段、数据段、打开的文件和信号等，都由它所属的进程拥有，即操作系统分配这些资源时以进程为单位。

一个进程可以包含一个或多个线程。其实，传统的进程就只有一个线程。当一个进程包含多个线程时，这些线程，除各自有少量资源以外，还要共享所属进程的全部资源。

线程与进程的关系

调度

线程是CPU调度的基本单位，进程是资源分配的基本单位。

在传统的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入线程的操作系统中，则把线程作为调度和分派的基本单位，把进程作为资源拥有的基本单位，从而使传统进程的两个属性分开。

线程的实现和实例

线程的实现方式：用户级线程、内核级线程和混合方式

Pthreads线程库

多线程应用程序需要用一组用户级程序库来编写，以便将所有线程映射到一个单独的内核级进程中，最著名的是Pthreads(POSIX threads)库。

协程

进程调度的基本概念

进程调度的任务是控制、协调进程对CPU的竞争，按照一定的调度算法，使某一就绪进程获得CPU的控制权，转换成运行状态。

进程调度的主要功能

进程调度的时机

两级调度模型

进程调度和作业调度是CPU主要的两级调度。

作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转换。

三级调度模型

进程调度算法的设计思路

调度策略的选择

性能评价标准：CPU利用率、系统吞吐量和平均周转时间

经典进程调度算法

先来先服务调度算法

时间片轮转调度算法

时间片轮转调度（RR）主要用于分时操作系统中的进程调度。

优先级调度算法

最短作业优先调度算法

最短作业优先（SJF）调度主要用于作业调度。其实现思想：从作业的后备队列中挑选那些需要运行时间（估计值）最短的作业放入内存。这是一种非抢占的策略。系统一旦选中某个短作业，就让该作业投入执行，直到该作业完成并退出系统为止。如果有四个作业 A、B、C 和 D，它们的预计运行时间分别为 6、3、15 和 8 个时间单位，利用最短作业优先调度，它们的执行顺序是 B → A → D → C。

最短作业优先调度算法能有效降低作业的平均等待时间和提高系统的吞吐量。但该算法对长作业很不利，并且不能保证紧迫性作业会被及时处理。

最短剩余时间优先调度算法

最短剩余时间优先（SRTF）调度是最短作业优先调度的变形，它采用抢占式策略。当新进程加入就绪队列时，如果它需要的运行时间比当前运行的进程所需的剩余时间还短，则运行进程被强行剥夺 CPU 的控制权，把那个新进程调度去运行。这种算法总能保证新的短作业一进入系统就会很快得到服务。但是实现这种算法要增加系统的开销（如保存进程断点现场和统计进程剩余时间等）。

假设有三个进程 P1、P2 和 P3，它们需要的 CPU 时间分别为 5、3 和 4 个单位时间。它们到达的时间相同，都是在时间 0 到达。

在时间 0，所有进程都处于就绪状态，根据 SRTF 调度算法，选择需要时间最短的进程 P2 开始执行。
在时间 3，P2 运行完毕，此时 P1 和 P3 的剩余运行时间分别为 2 和 4 个单位时间，因此选择 P1 执行。
在时间 8，P1 运行完毕，此时只剩下 P3，所以选择 P3 继续执行。
在时间 12，P3 运行完毕，所有进程执行完毕。

因此，按照 SRTF 调度算法，这些进程的执行顺序为 P2、P1 和 P3。

多级队列调度算法

多级反馈队列调度算法

其他进程调度算法

公平共享调度算法

基于进程组的调度决策是非常具有吸引力的。该方法通常称作公平共享调度。

保证调度算法

保证调度算法的目标是保证每个进程享用CPU的时间完全一样，即如果系统里一共有n个进程，则每个进程占用CPU的时间为1/n。

彩票调度算法

彩票调度算法是一种概率调度算法。

操作系统调度算法实例

BSD多级反馈队列调度算法

BSD UNIX系统主要用于分时交互环境中，调度算法设计成为交互用户提供好的响应时间，同时保证低优先级的后台作业不会“饿死”。

UNDC SVR4调度算法

Linux抢占式调度算法

Linux 系统的调度基本上采用抢占式优先级方式，当进程在用户模式下运行时，不管它是否自愿，内核在一定条件下（如该进程的时间片用完或等待 I/O）可以暂时中止其运行，而调度其他进程运行。一旦进程切换到内核态下运行，就不受以上条件限制，而一直运行，仅在重新回到用户态之前才会发生进程调度。

Windows调度算法

Windows中的优先级被组织成两段（两类）：实时和可变。

多处理器调度算法

多处理器调度算法的设计问题

多处理器调度的进程调度

在任何情况下，都可以把系统看作多服务器排队结构。

多处理器调度的线程调度

在多处理器线程调度和处理器分配的各种方案中，有以下四种比较突出的方法。

负载分配：不是将进程分配到一特定的处理器，而是维护一个就绪进程的全局队列，每个处理器只要空闲就从队列中选择一个线程。
组调度：一组相关的线程基于一对一的原则，同时调度到一组处理器上运行。
专用处理器分配：这种方法正好与负载分配的方法相反，它通过把线程指定到处理器来定义隐式的调度。在程序执行过程中，每个程序被分配给一组处理器，处理器的数目与程序中线程的数目相等。当程序终止时，处理器返回到总的处理器池中，可供分配给另一个程序。
动态调度：在执行期间，进程中线程的数目可以改变。

线程调度常用的方法有加载共享，组调度，专用处理器分配，动态调度。

实时调度算法

实时调度算法概述

限期调度算法

速率单调调度算法

为周期性任务解决多任务调度冲突的一个非常好的方法是速率单调调度（RMS）。

优先级反转问题

优先级继承协议的基本思想是优先级较低的任务继承任何与它共享同一个资源的优先级较高的任务的优先级。

存储管理概述

存储体系

存储体系中包含：

寄存器。处理器中暂存信息。
高速缓存。少量的、非常快速的、昂贵的、内容易变的。
内存。中等速度的、中等价格的、内容易变的。通常是GB数量级。
外存。低速的、价廉的、内容不易变的。通常是TB数量级（外存部件包括磁盘或闪存组成的固态硬盘、光盘、磁带机等，总容量可以达到TB或PB级别）。
云存储。大量外存部件有组织地组合在一起并通过高速网络和用户连接。

存储管理的任务

内存的分配与回收。
内存共享。内存共享是指两个或多个进程共用内存中相同区域。
存储保护。
“扩充” 内存容量。

地址转换

与绝对地址对应的内存空间称为物理地址空间。与逻辑地址对应的内存空间称为逻辑地址空间。

重定位的方式分为“静态重定位”和“动态重定位”两种

静态重定位

动态重定位

若程序执行时，被改变了存放区域仍能正确执行，则称程序是可浮动的。

采用动态重定位的系统支持“程序浮动”。采用静态重定位的系统不支持“程序浮动”。

分区管理方案

固定分区

可变分区

紧缩技术

解决外碎片问题的办法是在适当时刻进行碎片整理，通过移动内存中的进程，把所有空闲碎片合并成一个连续的大空闲区，这种方法称为“内存紧缩”, 又称为紧缩技术或“压缩技术”。

空闲区的分配策略

最先适应算法。
最优适应算法。
最坏适应算法。当接到内存申请时，查找分区说明表，找到能满足申请要求的最大空闲区。

分区管理方案的优缺点

分区管理是实现多道程序设计的一种简单易行的内存管理技术。通过分区管理，内存真正成为共享资源，有效利用了处理器和 I/O 设备，从而提高了系统的吞吐量和缩短了周转时间。分区内存管理算法比较简单，所采用的表格不多，实现起来比较容易，内存额外开销较少，内存保护措施也很简单。

在内存利用率方面，可变分区的内存利用率比固定分区高。

缺点：内存使用仍不充分，并且存在着较为严重的外碎片问题。虽然可以解决外碎片问题，但需要移动大量信息，浪费了处理器时间。此外，分区管理不能为用户提供“虚存”，即不能实现对内存的“扩充”，每一个用户程序的存储要求仍然会受到物理存储器实际内存容量的限制。分区管理要求运行程序一次全部装入内存之后，才能开始运行。这样，内存中可能含有一些实际不使用的信息。

覆盖与交换技术

覆盖技术

覆盖技术是指一个程序的若干程序段，或几个程序的某些部分共享某一个存储空间。

覆盖技术不需要任何来自操作系统的特殊支持，可以完全由用户实现，即覆盖技术是用户程序自己附加的控制。

覆盖技术打破了需要将一个程序的全部信息装入内存后程序才能运行的限制。

覆盖技术是早期采用的简单的扩充内存的技术。

覆盖技术主要用于系统程序的内存管理。

交换技术

进程从内存移到磁盘，并再移回内存称为交换。交换技术是进程在内存与外存之间的动态调度，是由操作系统控制的。

虚拟页式存储管理方案

页式存储器提供的编程使用的虚拟地址由两部分组成：虚拟页号和页内地址。

虚拟存储技术

虚拟页式存储管理

采用页式存储管理的主要目的是提高内存的利用率。

页式存储管理物理内存的分配与回收

虚拟页式存储地址转换过程：地址转换、页表项、缺页异常处理、页面调度策略、页面置换算法（Belady异常现象）和缺页率

页表

多级页表。
散列页表。
反置页表。

为避免页表占用较多存储空间的情况，大多数操作系统采用的进程页表是二级页表。大多数32位操作系统中采用二级页表，即由页表页和页目录一起构成进程页表。

转换检测缓冲区（TLB）

利用高速缓冲存储器存放当前访问最频繁的少数活动页面的页号，这个高速缓冲存储器称为“转换检测缓冲区”（TLB）,也称为“快表”。

页式存储管理器中的快表（TLB）一般存放在高速缓冲存储器。

虚拟页式存储管理的优缺点

优点：不要求进程的程序段和数据在内存中连续存放，因此有效地解决了碎片问题。这既提高了内存的利用率，又有利于组织多道程序执行。

缺点：存在页面空间的浪费问题。因为各种程序代码的长度是各不相同的，但页面的大小是固定的，所以在每个程序的最后一页内总会有一部分空间得不到利用，称为内碎片。如果页面较大，则由此引起的存储空间的损失仍然较大。

虚拟存储管理的性能问题：颠簸和工作集。

文件管理的基本概念

文件管理的任务

文件系统

文件系统，是操作系统中一种统一管理信息资源的软件。它管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。

文件的存储介质及存取方式

外存储设备的特点

容量大、非易失、速度较慢、成本较低

外存储设备的存储介质

磁带
磁盘
光盘
闪存

文件在存储设备中的存取方式

文件常用的存取方法有顺序存取和随机存取。

文件的分类

按文件的用途分类

系统文件。操作系统和各种系统应用程序与数据所组成的文件。对于普通用户，系统文件中的程序文件只允许用户通过系统提供的调用接口来执行，数据文件也只允许系统程序来读写，但不允许用户对该类系统文件直接进行读写和修改。对于超级用户，则可以对某些系统文件进行读写修改。
库函数文件。标准子程序及常用应用程序组成的文件。该类文件允许用户对其进行读取、执行，但不允许对其进行修改。例如，C 语言子程序库、FORTRAN子程序库等。
用户文件。用户委托文件系统保存的文件。只有文件的所有者或所有者授权的用户才能使用。用户文件可以由源程序、目标程序、用户数据文件、用户数据库等组成。

按文件的组织形式分类

普通文件。普通文件主要是指文件的组织格式为文件系统中所规定的最一般的格式的文件，文件的内容是一般的数据或程序，例如由字符流组成的文件。普通文件既包括系统文件，又包括用户文件、库函数文件和用户实用程序文件等。
目录文件。目录文件是由文件的目录构成的特殊文件。显然，目录文件的内容不是各种程序或应用数据，而是包含文件的目录信息，通常是有结构的，主要用来检索文件。
特殊文件。特殊文件是以文件形式存在和访问的设备，可进行查找文件等操作，但对文件的读写会对应于对设备的读写，并由设备驱动程序来完成具体的读写操作。比如，在UNIX类系统中，输入输出设备被看作特殊文件。当应用程序对这些特殊文件进行读写操作时，实际上是通过设备驱动程序直接读写相应的输入输出设备。

文件的逻辑结构和物理结构

文件的逻辑结构

文件的逻辑结构就是用户所看到的文件的组织形式。文件的逻辑结构是一种经过抽象的结构，所描述的是文件中信息的组织形式，与文件在物理介质上的具体存储结构不同。

可以把文件划分成三类逻辑结构：无结构的字符流式文件、有结构的定长记录文件和不定长记录文件构成的记录树。定长记录文件和不定长记录文件可以统称为记录式文件。

流式文件。流式文件是有序字符的集合，其长度为该文件所包含的字符个数，所以又称为字符流式文件。在流式文件中，构成文件的基本单位是字符，通常一个字符占用一个字节。
记录式文件

文件的物理结构

常用的文件物理结构有顺序结构、链接结构、索引结构。

顺序结构

链接结构

文件的链接结构的实质就是为每个文件构造所使用磁盘块的链表。使用这种链接结构的文件，将逻辑上连续的文件分散存放在若干不连续的物理块中。在每个物理块中都设有一个指针，该指针指向其后续的物理块

优点：

解决了存储碎片问题，有利于文件动态扩充，以及文件插入和删除，提高了磁盘空间利用率。
在建立链接结构的文件时，只需在文件目录中建立一个新的目录条目，并将该条目中的首块指针初始化为空，以说明该文件现在是空的，文件长度初始化为0。
链接结构的文件动态扩充也很简单，从空闲空间中得到一个空闲块，亦即第一个空闲块，然后将该块链接到文件尾部，并改变文件的长度即可。只要还能申请到空闲块，文件就可以一直动态扩充。

缺点：

存取速度慢，不适于随机存取文件；
磁盘的磁头移动多，效率相对较低；
存在文件的可靠性问题，比如指针出错，文件也就出错了；
链接指针需要占用一定的空间。

采用链接结构的物理结构，有利于文件动态扩充，解决了存储的碎片问题，但是不合适随机存取。

索引结构

UNIX的三级索引结构

文件目录

文件控制块

文件系统的一个特点是“按名存取”，即用户只要给出文件的符号名就能方便地存取在外存空间的该文件中的信息，而不必了解和处理文件的具体物理地址。

在操作系统中，为了管理大量的文件，为每个文件都设置一个描述性数据结构—文件控制块，把所有文件的文件控制块有机地组织起来，就构成了文件控制块的一个有序集合，称为文件目录。

目录结构

一级目录结构
二级目录结构
多级目录结构。把二级目录的层次关系加以推广，就形成了多级目录，又称树形目录结构。

当前目录与目录检索

文件系统向用户提供了一个当前正在使用的目录，称为“当前目录”，又称“工作目录”。如果需要，用户可随意更改当前目录。

用户在访问文件时，需要进行目录检索，这时用户给出文件名，系统按名寻找目录项。有两种根据路径名检索的方法：一种是使用全路径名，另一种是使用相对路径。

目录项分解法

UNIX的文件目录实现

FAT文件系统的实现

文件存储空间管理

磁盘空间管理

在计算机系统中，存储空间是一种宝贵的资源。外存储设备中的空间容量比较大,但也不是无限的，故对于文件删除之后而不再使用的空间，必须加以回收，然后在建立文件等操作中重新利用。

为了进行存储空间的分配与回收，在外存储设备上设置了空闲空间登记表，该表可以动态跟踪该外存储设备上所有还没有分配给任何文件的空闲块的数目和块号。

磁盘空间的分配回收算法

位示图

空闲块表

空闲块链表

UNIX系统的空闲块成组链接法

实现文件系统的表目

当用户申请打开一个文件时，系统要在内存中为该用户保存一些必要的信息，这些信息以表格栏目中内容的形式出现，被称为表目。

系统打开文件表

用户打开文件表

文件及文件目录的操作

典型的文件操作

建立文件

用户首先调用文件系统的建立文件操作，在请求调用该操作时，提供所要创建的文件的文件名及若干参数：用户名、文件名、存取方式、存储设备类型、记录格式、记录长度等。

建立文件系统调用的一般格式：create（文件名，访问权限，（最大长度））。

打开文件

打开文件系统调用的一般格式：fd = open（文件路径名，打开方式）。

读文件

读文件系统调用的一般格式：read（文件名，（文件内位置），要读的长度，内存目的地址）。

写文件

写文件系统调用的一般格式：write（文件名，记录键，内存位置）。

关闭文件

关闭文件系统调用的一般格式：close（文件名）。

删除文件

删除文件系统调用的一般格式：delete（文件名）。

指针定位

指针定位的一般格式：seek（fd，新指针的位置）。

典型的目录操作

在UNIX中，.代表当前目录，..代表根目录。

create，创建目录。
delete，删除目录。
opendir，打开目录，使内容可读取。
closedir，关闭目录。
readdir，系统调用它返回打开目录的下一目录项。
rename，文件可换名，目录也可换名。
link，链接技术允许在多个目录中出现同一文件。
unlink，删除目录项。

文件系统的性能

磁盘高速缓存

记录的成组

把若干个逻辑记录合成一组存放一个物理块的工作称为记录的成组，每块中的逻辑记录个数称为“块因子”。

RAID技术

文件共享、保护

文件共享

文件存取控制

UNIX的文件使用权限管理方案

设备管理的基本概念

设备管理的任务

输入输出设备的分类

按设备的使用特性分类

可分为输入设备、输出设备、交互式设备、存储设备。

输入设备是计算机用以“感受”或“接触”外部信息的设备。

输出设备是计算机用以产生普通人可感知的信息或输出用以“影响”或“控制”其他外部装置的设备。

按设备的信息组织方式分类

分为字符设备和块设备。

字符设备：键盘、终端、打印机等以字符为单位组织和处理信息的设备。

块设备：磁盘、磁带等以信息块为单位组织和处理信息的设备。

按设备使用时可共享性分类

设备管理与文件管理的关系

设备硬件和设备管理软件的组成

从硬件的角度来看，设备由物理设备和电子部件两部分组成。

一个典型的计算机系统的硬件结构，中心部分是CPU和主存，通过总线与第二层的接口部件（适配器）相连，第三层是各种外部设备控制器，最外层是外部设备。

设备硬件的组成

为了使CPU能够访问设备控制器中的寄存器，必须为每个寄存器分配唯一的地址，该地址称为I/O端口地址或I/O端口号。

设备管理软件的组成

设备驱动程序是操作系统底层中唯一知道各种输入输出设备的控制器细节及其用途的部分。

从功能上来看，设备独立层是I/O软件的主要部分；从代码量上来看，设备驱动层是I/O软件的主要部分。

设备独立性

设计I/O软件的一个最关键的目标是设备独立性，也就是说，除了直接与设备硬件打交道的低层软件以外，其他部分的软件并不依赖于硬件。

设备命名
设备保护
提供一个与设备无关的逻辑块
缓冲
- 对于字符设备，当用户进程把数据写到设备的速度快于系统输出数据的速度时，必须使用缓冲。
存储设备的块分配
独占设备的分配和释放
错误处理

I/O设备的控制方式

程序控制方式

程序直接控制方式也称为PIO（ProgrammedI/O, 程控I/O）方式，是指由用户进程直接控制处理器进行内存和外部设备之间信息传送的方式，也称为“忙-等”方式、轮询方式或循环测试方式，这种方式的控制者是用户进程。

中断控制方式

DMA控制方式

DMA是一种完全由硬件执行I/O数据交换的工作方式。在这种方式中，DMA控制器从CPU完全接管对总线的控制，数据交换不经过CPU, 而直接在内存和外部设备之间进行。在采用DMA控制方式工作时，由DMA控制器占用系统总线并向内存发送地址和控制信号，对传送信息的个数计数，并且以中断控制方式向CPU报告传送操作的结束。

优点：

操作均由硬件电路实现，传输速度快。
CPU仅在初始化和结束时参与，对数据传送基本上不干预，可以减少大批量数据传输时CPU的开销。
CPU与外设并行工作，效率高。

DMA是直接内存访问（Direct Memory Access）的缩写，它是一种完全由硬件执行I/O数据交换的工作方式。

通道控制方式

通道（Channel）是一个具备特殊功能的处理器，它有自己的指令和程序，可以实现对外部设备的统一管理，以及外部设备与内存之间的数据传送。

设备的分配与回收

设备分配的相关数据结构和策略

数据结构

分配原则

设备分配方式有两种：静态分配和动态分配。

分配策略

设备的分配策略通常采用先来先服务（FIFO）和高优先级优先。

独占设备的分配

设备的绝对号与相对号

设备的指定方式

用户在申请独占设备时，应指定需要什么设备。指定设备的方式可以有两种，一种是指定设备的绝对号，另一种是指定设备类、相对号。

为了提高设备分配的灵活性，用户申请设备时应使用设备类、相对号。

独占设备的分配和释放

独占设备通常是指打印机、磁带机、扫描仪、绘图仪等，这类设备在一段时间内只能由一个进程所占有。在执行申请命令之后和执行释放命令之前，用户独占该设备。

操作系统设置“设备分配表”，用来记录计算机系统所配置的独占设备类型、台数以及分配情况等。设备分配表可由设备类表和设备表两部分组成。

共享设备的分配

由于独占设备的分配和回收必须遵守“独占”的要求，使得设备的利用率低，死锁的概率增大，不利于调度。能将独占设备转变为共享设备的技术称为SPOOLing（外部设备同时联机操作）技术，也称为虚拟设备技术或假脱机技术，

磁盘驱动调度

信息传输时间

移臂调度及其调度算法

旋转调度优化

磁盘信息的优化分布

缓冲技术

缓冲的引入

为了缓解I/O设备和CPU的处理速度不匹配问题，引入缓冲技术。

缓冲的种类

根据系统设置的缓冲区的个数，可把缓冲技术分为单缓冲、双缓冲、多缓冲以及缓冲池。

单缓冲：在I/O设备和CPU之间设置一个缓冲区。
双缓冲：解决两台I/O设备或者打印机和终端之间的并行操作问题的办法是设置双缓冲区。
多缓冲：一种具有多个缓冲区，其中一部分缓冲区专门用于输入，另一部分缓冲区专门用于输出的缓冲结构。
缓冲池：把多个缓冲区连接起来统一管理，缓冲池中的每个缓冲区既可用于输入又可用于输出的缓冲结构。

用于实现两台I/O设备之间的并行操作的是：双缓冲、多缓冲、缓冲池。

缓冲池管理

对于各缓冲区的排列以及每次取出和插入缓冲队列的顺序都应有一定的规则。最简单的方法是FIFO, 即先进先出的排列方法。

虚拟设备技术

虚拟设备技术，又称为SPOOLing技术，是多道程序设计系统中处理独占外部设备的一种方法，它可以提高设备利用率并缩短单个程序的响应时间。它可以使进程在所需的外部设备不存在或被占用的情况下使用该设备。

虚拟设备的实现原理—SPOOLing系统工作原理

SPOOLing系统主要包括输入程序模块、输出程序模块、作业调度程序三部分。

在SPOOLing系统中，作业执行时，从磁盘上的输入井中读取数据，并把作业的执行结果暂时存放在磁盘上的输出井中。

SPOOLing系统的组成和实现

进程的同步与互斥

与时间有关的错误

进程的同步与互斥

信号量（Semaphore）和P、V原语

经典的进程同步问题

Dijkstra把同步问题抽象成一种生产者-消费者关系。

简单生产者-消费者问题

多个生产者-消费者问题

读者-写者问题

死锁

死锁的定义

所谓死锁，是指在多道程序系统中的一种现象，一组进程中的每一个进程均无限期地等待被该组进程中的另一个进程所占有且永远不会释放的资源。系统发生这种现象称为系统处于死锁状态，简称死锁。处于死锁状态的进程称为死锁进程。

死锁产生的原因

死锁产生的必要条件

互斥条件
不可剥夺条件
请求和保持条件
循环等待条件

死锁发生后的处理方法：预防、避免、检测与解除、忽略

死锁的检测与解除

死锁的解除方法可归纳为以下两大类：

剥夺资源
1. 还原算法，即恢复资源分配前的计算结果和状态。
2. 建立检查点，主要用来恢复分配前的状态。这对实时操作系统和长时间运行的数据处理来说是一种常用技术。
撤销进程

哲学家就餐问题及其他实例

哲学家就餐问题

哲学家就餐问题是操作系统中关于进程同步与互斥的经典问题，也是涉及死锁的关键问题。

其他实例