第四章节——操作系统
计算机系统知识
一、操作系统概述
1. OS作用
- 操作系统的定义：
能有效的组织和管理系统中的各种软/硬件资源，合理地组织计算机系统工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口。 - 操作系统的两大作用
（1）通过资源管理提高计算机系统的效率。
（2）改善人机界面向用户提供友好的工作环境。
2. OS特征
特征： 并发性，共享性，虚拟性，不确定性
功能： 进程管理，文件管理，存储管理，设备管理和作业管理
3.OS分类
批处理操作系统、分时操作系统、实时操作系统、网络操作系统、分布式操作系统、微型计算机操作系统和嵌入式操作系统等类型。
二、进程管理
1. 进程状态
1.1 程序与进程：
进程由程序、数据和进程控制块（PCB）组成。进程是资源分配和独立运行的基本单位。特征动态性，并发性，共享性，独立性，结构性，制约性。
进程与程序的区别：
- 进程是
动态的，程序是静态的，进程是程序在数据集上的一次执行； 进程具有并发性，程序没有；- 进程是
资源分配的基本单位，程序不是 - 进程与程序不是一一对应，
一个进程通常对应一个程序，而一个程序可以对应零个或多个进程
1.2 进程的状态及其转换：
（1）三态模型： 运行态、就绪态和阻塞态
（2）五态模型： 运行态、就绪态、阻塞态、新建态和终止态
- 进程控制是由操作系统内核（Kernel）中的
原语实现的 - 原语是指由若干条机器指令组成的，
用于完成特定功能的程序段。原语的特点是在执行时不能被分割
2. 通信
多个并发进程存在资源共享和相互合作，因此进程之间需要进行通信。
2.1 同步和互斥:
同步是合作进程间的直接制约问题，互斥是申请临界资源进程间的间接制约问题。
进程的同步： 系统中需要相互合作，协同工作的进程之间的通信。
进程的互斥： 系统中多个进程因争夺临界资源而互斥执行。每次只能给一个进程使用的资源称为临界资源，如打印机。
2.2 信号量机制：
信号量机制是一种有效的进程同步和互斥的工具。两类信号量
（1）公用信号量：互斥信号量，对临界资源采用互斥访问，初值为1或资源的个数
（2）私有信号量：同步信号量，对共享资源的访问控制，初值为0或某个正整数。
信号量S的物理意义：若S≥0表示可用的资源数；若S≤0，其绝对值表示阻塞队列中等待该资源的进程数。
P，V操作：均为原子操作，是实现同步和互斥的常用方法。
P操作：表示申请一个资源，即S = S - 1，若S ≥ 0，则执行P操作的进程继续执行；若S＜0，则执行P操作的进程进行阻塞状态。
V操作表示释放，即S = S + 1，若S>0，则执行V操作的进程继续执行；若S ≤ 0，则唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续执行。
2.3 前趋图：
用来表示任务之间的顺序关系，并行执行关系。
其中，P2、P3可以并行执行，但是P2、P3必须都执行完后，才能执行P4，这就确定了两点:任务间的并行、任务间的先后顺序。
2.4 管程
- 在传统的操作系统中，当多个进程或线程同时访问
共享资源时，可能会导致数据的不一致性、竞态条件和死锁等问题。为了避免这些问题，需要引入一种同步机制来协调并发访问。 - 管程（Monitor）是一种操作系统中的
同步机制，它的引入是为了解决多线程或多进程环境下的并发控制问题。 - 管程
提供了一种高级的同步原语，它将共享资源和对资源的操作封装在一个单元中，并提供了对这个单元的访问控制机制。 - 相比于信号量机制，用管程编写程序更加简单，写代码更加轻松。
2.5 进程调度：
进程调度方式是指当有更高优先级的进程到来时如何分配CPU。调度方式分为可剥夺和不可剥夺两种。
- 可剥夺:指当有更高优先级的进程到来时，
强行将正在运行进程的CPU分配给高优先级的进程 - 不可剥夺:指当有更高优先级的进程到来时，必须
等待正在运行的进程释放占用的CPU，然后将CPU分配给高优先级的进程。
三级调度:
(1）高级调度:作业调度，决定哪个后备作业可以调入主系统做好运行的准备。
(2）中级调度:对换调度，决定交换区中的哪个就绪进程可以调入内存。
(3）低级调度:进程调度，决定内存中的哪个就绪进程可以占用CPU。低级调度是操作系统中最活跃、最重要的调度程序。
调度算法：
(1）先来先服务（FCFS）： 按先后次序分配CPU。有利于长作业，不利于短作业;有利于CPU繁忙型作业，不利于I/O繁忙型作业。
(2）时间片轮转： 分配给每个进程时间片，轮流占用CPU。通过时间片轮转提高进程并发性和响应时间特性，从而提高资源利用率。
(3）优先级调度： 系统选择优先级大的进程占用CPU。
(4）多级反馈调度： 时间片轮转和优先级调度结合而成。设置多个就绪队列1、2、3…n，每个队列分别赋予不同的优先级，队列1最高，队列n最低，分配不同的时间片长度;新进程先进入队列1的末尾，按FCFS原则，执行队列1的时间片;若未能执行完进程，则转入队列2的末尾，依次类推。
2.6 线程：
线程是进程中的一个实体，是可独立分配和调度的基本单位。线程是调度的最小单位，进程是拥有资源的最小单位，线程可以共享进程的公共数据、全局变量、代码及一些进程级的资源(如打开文件和信号)等，但不能共享线程独有的资源，如线程的栈指针等标识数据。一个进程内的线程在其他进程不可见。
3. 死锁
3.1 死锁及其产生的必要条件
所谓死锁，是指两个以上的进程因相互争夺对方占用的资源而陷入无限等待的现象
死锁产生的4个必要条件： 互斥（资源互斥）、请求保持（进程占有资源并等待其他资源）、不可剥夺（系统不能剥夺进程资源）和环路（进程资源是一个环路）
请求资源：O→口；分配资源：O→口，若同时有请求和分配，分配优先。
3.2 进程资源图
进程资源图，用来表示进程和资源之间的分配和请求关系
P代表进程，R代表资源，R方框中有几个圆球就表示有几个这种资源。在上图(a)中，R1指向P1，表示R1有一个资源已经分配给了P1;P1指向R2，表示P1还需要请求一个R2资源才能执行。（资源先分配后申请)
- 阻塞节点:某进程
请求资源得不到满足时，该进程即为阻塞节点。如上图(a)中P1、P2都是阻塞节点，所以该图不可以化简，是死锁的。 - 非阻寨节点:某进程
请求的资源能够满足时，该进程即为非阻塞节点。如上图(b)中P2是阻塞节点，PI、P3是非阻塞节点，该图可以化简，是非死锁的。 - 图的化简/死锁:当一个进程资源图中
所有进程都是阻塞节点时，该图不可化简，即陷入死锁状态。
进程资源图化简的方法: 先看系统还剩多少资源没分配，再看有哪些进程是不阻塞的，然后将不阻塞的进程的所有边都去掉，形成一个孤立的点，再把系统分配给这个进程的资源回收回来，这样，系统剩余的空闲资源便多了起来，然后再看剩下的进程有哪些是不阻塞的，把它们逐个变成孤立的点。最后，所有的资源和进程都变成孤立的点，即完成图的化简。
3.3 死锁的处理策略
(1）死锁预防: 采用某种策略限制并发进程对资源的请求，破坏死锁产生的4个必要条件，使系统在任何时刻都不满足产生死锁的必要条件。
(2）死锁避免: 提前计算出一条不会产生死锁的资源分配方法。著名的死锁避免算法有银行家算法。
(3）死锁检测: 允许死锁产生，但系统定时运行一个死锁检测程序，判断系统是否发生死锁，若检测到有死锁，则设法加以解除。
(4）死锁解除: 即死锁发生后的解除方法，如资源剥夺法、撤销进程法等
死锁资源的计算: 系统内有n个进程，每个进程都需要R个资源，那么发生死锁的最大资源数为n *(R一1)，不发生死锁的最小资源数为n * (R -1)＋1。
三、存储管理
1. 存储结构
1.1 存储器的结构
1.2 地址重定位
逻辑地址： 是由操作系统分配给程序使用的虚拟地址，它是在程序中使用的地址，而不是实际存在的地址，也被称为虚拟地址
物理地址： 物理地址是实际存在于计算机中的地址，也称为实际地址。物理地址是存储器的绝对地址。范围从00000H~FFFFFH，是CPU访问储存器时由地址总线发出的地址。
定义变量时，变量的地址并不是实际的物理地址，而是操作系统分配的逻辑地址(虚拟地址)。这个逻辑地址通过地址映射得到真正的物理地址。在程序编译时，变量的虚拟内存地址是固定的，然而映射的物理内存地址是随机的。
地址重定位将逻辑地址变换成主存物理地址的过程，分为静态重定位（程序装入主存时就完成了变换）和动态重定位（边运行边变换）。
2. 存储管理方案
2.1 分区存储管理
将主存的用户区划分成若干个区域，每个区域分配给一个用户作业使用，并限定它们只能在自己的区域中运行。
按划分方式不同，分区存储可分为：
（1）固定分区： 静态分区方法，将主存划分为若干个固定的分区，将要运行的作业装配进去，由于分区固定，且与作业大小可能不同，会产生碎片，造成空间浪费。
（2）可变分区： 动态分区方式，主存空间的分区在作业装入时划分，分区大小与作业大小相同。
可变分区请求与释放算法
① 最佳适应算法:假设系统中有n个空白分区，当用户申请空间时，从这n个空白分区中找到一个最接近用户需求的分区。可能会产生许多无用的小分区，称为外碎片。
② 最差适应算法:系统总是将用户作业装入最大的空白分区。
③ 首次适应算法:系统从主存的低地址开始选择一个能装入作业的空白分区。
④ 循环首次适应算法:每次分配都是从刚分配的空白分区开始寻找一个能满足用户要求的空白分区
（3）可重定位分区： 可解决碎片问题，移动所有已经分配好的分区，使之成为连续区域，在用户请求空间得不到满足或某个作业执行完毕时进行。
分区保护：分区保护的目的是防止未经核准的用户访问分区。
2.2 分页存储管理
分区管理方案的主要问题是用户程序必须装入连续的地址空间中，若无法满足用户要求的连续空间，需要进行分区靠拢操作，这是以耗费系统时间为代价的。为此，引入了分页存储管理方案。
（1）纯分页存储管理
将进程的地址空间划分成若干个大小相等的区域，称为页。响应地，将主存划分成与页相同的若干物理块，称为块。在为进程分配主存时，将进程中若干页分别装入多个不相邻的块中。
分页地址结构:
（2）快表
将页表中经常使用的页号等对应关系存放在Cache中，称为快表。加快变换速度，快速得到真正的物理地址。
（3）逻辑地址与物理地址的映射 ：
2.3 分段存储管理
将进程空间划分成若干个段，每段也有段号和段内地址，每段是一组完整的逻辑信息。
分段地址结构：
分页与分段的区别: 分页是根据物理空间划分，每页大小相同;分段是根据逻辑空间划分，每段己一个完整的功能，便于共享，但是大小不同。
2.4 段页式存储管理
先将整个主存划分成若干个大小相等的存储块，将用户程序按程序的逻辑关系分为若干个段，再将每个段划分成若干个页。既具有分页系统能有效地提高主存利用率的优点，又具有分段系统能很好地满足用户需要的长处。
段页式地址结构：
段页式优缺点：
优点： 空间浪费小，存储共享容易，存储保护容易，能动态连接；
**缺点：**由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降。
2.5 虚拟存储管理
- 在以上存储管理方案中，必须为每个作业分配足够的空间，以便装入全部信息。当主存空间不满足作业要求时，作业无法装入主存执行。
- 如果一个
作业只部分装入主存便可开始启动运行，其余部分暂时留在磁盘上，在需要时再装入存。从用户角度看，该系统所具有的主存容量将比实际主存容量大得多，人们把这样的存储器为虚拟存储器。
**程序的局部性原理： **
CPU对主存中的指令和数据的访问，在一小段时间内，总是集中在一小块存储空间里。
① 时间局部性: 最近被访问过的指令和数据很可能被再次访问;
② 空间局部性: 最近访问过的指令和数据往往集中在一小片存储区域中。
页面置换算法：
有时候，进程空间分为10个页面，而系统内存只有3个物理块，无法一次性全部分配，就需要先分配一部分进程,再根据算法进行淘汰，淘汰的算法称为页面置换算法。
缺页：需要执行的页不在物理内存中，需要从外部调入内存。会增加执行时间，因此缺页次数越多，系统效率越低。
(1）最佳置换算法: 理想化的算法，选择最长时间不再被访问的页面置换。
(2）先进先出置换算法: 淘汰最先进入主存的页面，即选择在主存中驻留时间最久的页面予以淘汰。
(3）最近最少未使用置换算法: 选择最近最少未使用的页面予以淘汰，根据局部性原理，这种方式效率较高。
(4）最近未用置换算法: 优先淘汰最近未访问的，而后淘汰最近未被修改的页面。
四、设备管理
1. I/O软件
设计IO软件的主要目标是设备独立性和统一命名。IO软件独立于设备，就可以提高设备管理软件的设计效率。当输入/输出设备更新时，没有必要重新编写全部设备驱动程序。
设备管理采用的相关技术
（1）通道技术：
CPU只需要向通道发出I/O命令，通道收到命令后，从主存中取出本次I/O要执行的通道程序并执行，仅当通道完成IO任务后才向CPU发出中断信号。目的:使数据传输独立于CPU，将CPU从烦琐的I/O工作中解脱出来。
（2）DMA技术：
直接内存存取（DMA)，是指数据在主存与设备之间直接成块传送，即在主存与设备间传送一个数据块的过程不需要CPU的任何干涉。
（3）缓冲技术：
包括硬件缓冲（硬件寄存器）和软件缓冲（操作系统〉。是为了提高外设利用率，尽可能使外设处于繁忙状态。引入缓冲技术的原因:①缓和CPU与I/O设备之间速度不匹配的矛盾。②减少对CPU的中断频率，放宽对中断响应时间的限制。③提高CPU和IO设备之间的并行性。
（4）Spooling技术：
假脱机技术，用一类物理设备模拟另一类物理设备的技术，是使独占使用的设备变成多台虚拟设备的一种技术。
系统如何利用Spooling技术将打印机模拟为虚拟打印机: 当某进程要求打印输出时，操作系统在磁盘上的输出井中为其分配一块区域，该进程的输出数据高速存入输出井的相关区域中，而不直接在打印机上输出。输出井上的区域相当于一台虚拟打印机，各进程的打印输出数据都暂时存放在输出井中，形成一个输出队列。最后，由Spooling的输出程序依次将输出队列中的数据实际打印输出。这样,从用户的角度来看，他似乎独占一台打印机，可以随时根据运行的情况输出各种结果;但从系统的角度来看，同一台打印机又可以分时地为每个用户服务。用户进程实际上获得的是虚拟设备。Spooling技术缓和了CPU与I/O设备之间速度不匹配的矛盾 ，提高了CPU与I/O设备之间的并行程度。
2. 磁盘调度
磁盘的结构: 磁盘有正反两个盘面，每个盘有多个同心圆，每个同心圆是一个磁道，每个同心圆
又被划分为多个扇区，数据就被存放在一个个扇区中。寻道时间 : 磁头移动到磁道所需的时间。磁盘调度的目标是使磁盘的平均寻道时间最少。
**磁盘调度算法: **
(1）先来先服务（FCFS): 根据进程请求访问磁盘的先后次序进行调度。
(2）最短寻道时间优先(SSTF): 最短移臂调度算法，要求访问的磁道与当前磁头所在的磁道距离最近，使得每次寻道时间最短，但平均寻道时间不一定最短。
(3）扫描算法(SCAN): 电梯调度算法，每次选择距离最近的同一个方向的磁道访问。
(4）单向扫描调度算法(CSCAN): 每次均从头到尾依次扫描访问。
五、文件管理
1. 文件与文件系统
文件(File）是具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。例如，一个源程序、一个目标程序、编译程序、一批待加工的数据和各种文档等都可以各自组成一个文件。
文件的命名: 一般包括文件名和扩展名。
2. 文件结构和组织
2.1 文件的逻辑结构
无结构的流式文件，是由一串二进制或顺序字符流构成的文件，如二进制文件或字符文件。有结构的记录式文件，是由一个以上的记录构成的文件，称为记录式文件，如数据库表
2.2 文件的物理结构
文件的物理结构是指文件的内部组织形式，即文件在物理存储设备上的存放方法。
①连续结构，逻辑上连续的文件信息（如记录）依次存放在连续编号的物理块上;
②链接结构，逻辑上连续的文件信息存放在不连续编号的物理块上;
③索引结构，逻辑上连续的文件信息(如记录)存放在不连续的物理块中，系统为每个文件建立一张索引表。索引表记录了文件信息所在的逻辑块号对应的物理块号;
④多个物理块的索引表，根据一个文件大小的不同，其索引表占用物理块的个数不同，一般占一个或多个物理块。
在UNIX文件系统中采用的是三级索引结构，其文件索引表项分4种寻址方式:直接寻址、一级间接寻址、二级间接寻址和三级间接寻址。
三级索引文件结构：0-9为直接索引，即每个索引节点存放的为数据;10为一级间接索引;11为二级间接索引。
三级索引文件结构举例：假设文件索引节点中有8个地址项i_addr[0] - i_addr[7]，每个地址项大小为4字节，其中i_addr[0] - i _addr[4]采用直接地址索引，i_addr[5]和i_addr[6]采用一级间接地址索引,i_addr[7]采用二级间接地址索引，磁盘索引块和磁盘数据块大小均为1KB。
2. 文件目录
文件目录也是一种数据结构，用于标识系统中的文件及其物理地址，供检索时使用。
（1）文件控制块：
文件控制块（FCB）是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。为了创建一个新文件，系统将分配一个FCB，成为目录项。
文件控制块（FCB）主要包含以下信息：
基本信息，如文件名、文件的物理地址、文件的长度和文件块数等。
存储控制信息，如文件存取权限等。
使用信息，如文件建立时间、修改时间等。
（2）目录结构：
文件目录结构的组织方式直接影响到文件的存取速度，关系到文件的共享性和安全性。常见的目录结构有3种：一级目录结构、二级目录结构和多级目录结构。
- 一级目录结构：整个系统中只建立一张目录表，每个文件占一个目录项。
- 二级目录结构：早期的多用户操作系统，采用两级日录结构。分为主文件日录(MFD，Master File Directory〉和用户文件日录(UFD，User Flie Directory)。
多级目录结构：在多道程序设计系统中常采用多级目录结构，这种目录结构像一棵倒置的有根树，所以也称为树形日录结构。从树根向下，每一个结点是一个日录，叶子结点是文件。Windows、UNIX、MS-DOS等操作系统均采用多级目录结构。
3. 文件空闲储存空间的管理
常用的空闲空间管理的方法有：空闲区表、位示图、空闲块链和成组链接法。
（1） 空闲区表
将外存空间上的一个连续的未分配区域称为"空闲区"。操作系统为磁盘外存上的所有空闲区建立一张空闲表，每个表项对应一个空闲区，空闲表中包含序号、空闲区的第一块号、空闲块的块数和状态等信息。它适用于连续文件结构。
（2） 位示图
在外存上建立一张位示图(Bitmap)，记录文件存储器的使用情况。每一位对应文件存储器上的一个物理块，0表示空闲，1表示占用。主要特点:位示图的大小由磁盘空间的大小(物理块总数)决定。
位示图一般用连续的“字”来表示。假设系统字长为32位，位示图中的每个二进制位对应一个物理块，因此可以用(字号，位号）对应一个物理块。
（3） 空闲块链
每个空闲物理块中有指向下一个空闲物理块的指针，所有空闲物理块构成一个链表，链表的头指针放在文件存储器的特定位置上(如管理块中)，不需要磁盘分配表，节省空间。每次申请空闲物理块只需根据链表的头指针取出第一个空闲物理块，根据第一个空闲物理块的指针可找到第二个空闲物理块，依此类推。
（4） 成组链接法
系统将空闲块分成若干组，假设每5个空闲块为一组，每组的第一个空闲块登记了下一组空闲块的物理块号（的地址）和空闲块总数。UNIX系统采用该方法。
六、作业管理
1. 作业控制
作业是系统为完成一个用户的计算任务(或一次事务处理)所做的工作总和。例如，对用户编写的源程序，需要经过编译、连接、装入以及执行等步骤得到结果，这其中的每一个步骤称为作业步。
（1）作业
作业由程序、数据和作业说明书3个部分组成。
（2）作业状态及转换
作业的状态分为4种：提交、后备、执行和完成。其中，执行就是作业调入系统中执行，与进程执行状态类似。实际上，作业调度是比进程调度更加高级的调度。
（3）作业控制块和作业后备队列
作业控制块(JCB）:是记录与该作业有关的各种信息的登记表。是作业存在的唯一标志，包括用户名、作业名和状态标志等信息。
2. 作业调度
（1）作业调度算法
- 先来先服务： 按作业到达的先后进行调度，即启动等待时间最长的作业。
- 短作业优先算法： 优先调度运行时间最短的作业。
- 响应比高优先算法： 响应比高的作业优先调度。
- 优先级调度算法： 优先级高的作业优先调度
- 均衡调度算法： 根据系统运行情况和作业本身的特性对作业进行分类。作业调度程序从这些不同类别的作业中挑选作业执行
（2）作业调度算法性能衡量指标
在一个批量处理为主的系统中，通常用平均周转时间或平均带权周转时间来衡量调度性能的优劣。
作业周转时间=作业响应时间=作业等待时间＋作业执行时间
系统平均周转时间或平均带权周转时间越小，作业调度算法的性能越好
