概述

操作系统目的是：为了填补人与机器之间的鸿沟，即建立用户与计算机之间的接口，而为裸机配置的一种系统软件。操作系统也包括了系统软件。操作系统也是软硬件之间的接口。

操作系统的功能：

进程管理
存储管理
文件管理
作业管理
设备管理

特殊操作系统

程序、进程（process）、线程（thread）

程序：存储在磁盘上的静态指令集合，是代码的“死”文件，未被运行。
进程：
- 进程是程序的一次执行过程。
- 进程是操作系统中执行程序的基本单位。
- 每个进程都有自己的独立内存空间和系统资源（PCB）。
线程：
- 进程内的一个执行单元，是CPU调度和执行的最小单位。
- 共享进程的资源。

	程序	进程	线程
存在形式	静态文件（硬盘）	动态实例（内存），程序的一次执行	进程内的执行流，共享进程资源
资源占用	不占用系统资源	独立内存空间、系统资源	仅少量私有数据，共享进程资源
并发性	无	多进程可并发，彼此隔离	多线程可并发，共享资源，相互影响
开销	无	创建、切换、销毁开销大	创建、切换、销毁开销小
独立性	完全独立	独立运行，互不影响	依赖进程，线程间不独立
通信方式	无	IPC（管道、消息队列、共享内存等）	直接共享内存，需同步机制

程序顺序执行时的主要特征包括：顺序性、封闭性和可再现性。

程序并发执行时的主要特征包括：失去了程序的封闭性、程序和机器的执行程序的活动不再一一对应、并发程序之间的相互制约性。

进程的状态

三态模型

在多道程序系统中，进程在处理器上交替运行，状态也不断地发生变化，因此进程一般有3种基本状态：运行、就绪和阻塞。

运行：当一个进程在处理机上运行时。
就绪：一个进程获得了除CPU外的一切所需资源，一旦得到CPU即可运行。
阻塞（等待或睡眠）：一个进程因为等待某一事件发生而暂时停止运行，这时即使把处理机分配给进程也无法运行。当等待的事件发生之后，会先进入就绪状态，不能直接恢复运行状态。

等待某个事件发生：还处于运行状态，因为在是执行到某行代码才会发生需要去等待结果这个情况。
等待事件发生：已进入了等待阶段，这时候已经是阻塞状态了。

五态模型

做题时多使用排除法，比如下面，单CPU中，不能同时有两个运行态，直接排除第二空的BD。

进程间的通信

在多道程序环境的系统中存在多个可以并发执行的进程，故进程间必然存在资源共享和相互合作的问题。进程通信是指各个进程交换信息的过程。

同步和互斥

临界资源：在多道程序系统环境中，那些一次只能供一个进程使用的资源。如打印机、共享变量和表格等。
临界区：是进程中对临界资源实施操作的那段程序。
同步：合作进程间的直接制约问题。
进程间的同步：是指在系统中一些需要相互合作，协同工作的进程，这样的相互联系称为进程的同步。

例如，进程A向缓冲区送数据，进程B从缓冲区取数据加工，当进程B要取数据加工时，必须是进程A完成了向缓冲区送数据的操作，否则进程B必须停下来等待进程A的操作结束。

互斥：申请临界资源进程间的间接制约问题。
进程间的互斥：是指系统中多个进程因争用临界资源而互斥执行。

对互斥临界区管理的4条原则如下：

有空即进：当无进程处于临界区时，允许进程进入临界区，并且只能在临界区运行有限的时间。
无空则等：当有一个进程在临界区时，其他欲进入临界区的进程必须等待，以保证进程互斥地访问临界资源。
有限等待：对于要求访问临界资源的进程，应保证进程能在有限的时间进入临界区，以免陷入“饥饿”状态。
让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等状态

PV操作

信号量：是一种特殊的变量
S ≥ 0：表示某资源的可用数，此时有可用资源；
S＜0：则其绝对值表示阻塞队列中等待该资源的进程数，此时无可用资源且有进程被阻塞。

PV操作：实现进程同步与互斥的常用方法，是操作系统的一段原语,在执行期间不可分割。其中：

P操作（减）：表示申请一个资源；S := S−1（S表示信号量）
V操作（加）：表示释放一个资源。S := S+1

P减V加，P进V出。

利用PV操作实现进程的互斥：

令信号量mutex的初始值为1；
进入临界区：执行P操作；
退出临界区：执行V操作。

利用PV操作实现进程的同步：

实现进程的同步可用一个信号量与消息联系起来。

信号量的值：

为0：表示希望的消息未产生；
非0：表示希望的消息已经存在。

假定信号量S表示某条消息，进程可以：

调用P操作：测试消息是否到达；
调用V操作：通知消息已经准备好。

死锁

死锁四大条件:

互斥
保持和等待
不剥夺
环路等待

当有 n 个进程，m个资源，且每个进程所需要的资源数为k，并且系统采用的分配策略是轮流地为每个进程分配资源时，满足如下公式时不会发生死锁：

表示n个进程，每个进程都是分配了k-1个资源，这就是最悲观的情况，只要给任意一个进程再分配一个资源，该进程就可以继续，然后释放资源给其他进程，就不会再发生死锁。所以当所拥有的资源数满足这个条件时，就可以避免死锁。

死锁的处理策略主要有4种：鸵鸟策略（即不理睬策略）、预防策略、避免策略和检测与解除死锁。

前趋图

执行当前任务需要在其他任务之后，那么箭头就由该任务指向当前任务。依赖之前的步骤用P操作，执行完之后用V操作标识已经准备好了，可以进行下一个步骤。

进程资源图

所谓可化简，就是在执行完之后会释放资源，该资源又可以被原先阻塞的节点所使用，最后所有节点都可以执行。

线程

传统进程有两个基本属性：
可拥有资源的独立单位；
可独立调度和分配的基本单位。

引入线程的原因是，进程的系统必须付出较大的时空开销。引入线程后，将传统进程的两个基本属性分开：

线程：作为调度和分配的基本单位；
进程：作为独立分配资源的单位。

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

线程的特点：

线程基本上不拥有资源，只拥有一点运行中必不可少的资源（如程序计数器、一组寄存器和栈），它可与同属一个进程的其他线程共享进程所拥有的全部资源。
线程也具有就绪、运行和阻塞3种基本状态。
线程可创建另一个线程。
同一个进程中的多个线程可并发执行。

线程因其具有许多传统进程所具有的特性，故称为"轻型进程"；而传统进程称为"重型进程"。

线程分为：

用户级线程（User-Level Threads）：不依赖于内核，该类线程的创建、撤销和切换都不利用系统调用来实现；
内核支持线程（Kernel-Supported Threads）：依赖于内核，即无论是在用户进程中的线程，还是在系统中的线程，它们的创建、撤销和切换都利用系统调用来实现。

某些系统同时实现了两种类型的线程。

与线程不同的是，不论是系统进程还是用户进程，在进行切换时，都要依赖于内核中的进程调度。因此，不论是什么进程都是与内核有关的，是在内核支持下进行切换的。

存储管理

程序局部性原理
程序在执行时将呈现出局部性规律，即在一段时间内，程序的执行仅局限于某个部分。相应地，它所访问的存储空间也局限于某个区域内。
时间局限性：程序执行了某条指令，则不久的将来很可能再次执行该指令；程序访问了某个存储单元，不久的将来很可能再次访问。
空间局限性：程序访问了某个存储单元，在不久的将来很可能访问其附近的存储单元。
产生时间局限性的原因是程序中存在着大量的循环操作。
产生空间局限性的原因是程序是顺序执行的。

分页存储管理

页式存储：将程序与内存均划分为同样大小的块，以页为单位将程序调入内存。在为进程分配主存时，将进程中若干页分别装入多个不相邻接的块中。

分页的过程是由操作系统完成的，对用户是透明的，所以用户不必关心分页的过程。

优点：利用率高，碎片小，分配及管理简单
缺点：增加了系统开销;可能产生抖动现象
页：将程序划分成大小相同的页。
页框（块）：将物理地址划分成以页为大小的块，用于运行时存放程序的页内容。
页表：用于映射程序的页与实际内存的关系。

逻辑地址：页号+页内地址
物理地址：页帧号(块号)+页内地址

例题

页式存储系统中，每个页的大小为4KB。逻辑地址为：10 1100 1101 1110，求对应的物理地址？

4KB = 4096B = 2^12B（默认以B为单位），说明需要12位二进制来表示页内地址的范围。
逻辑地址10 1100 1101 1110为14位，则其前两位为页号，即页号为2
根据页表可知，页号2对应的块号为6，二进制为110，所以物理地址为：110 1100 1101 1110

页淘汰策略

在程序的执行过程中，并不一定所有的页都在内存里，若执行到的页不在内存，则会产生缺页中断。需要将缺失的页调入内存，若内存满了，还需要将存在的页淘汰。

优先淘汰页表里访问位为0的：为1的表示访问过，根据局部性原理，很可能再次访问。
其次淘汰修改位为0：为1表示页被修改了，若淘汰，还需要同步修改到程序文件。

段式存储管理

由于分页式存储可能将循环体分开到两个页，这样就可能导致程序运行时需要大量的淘汰-调入重复逻辑，引起不必要的开销。

段式存储：按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样。

段逻辑地址：段号+段内地址
合法段地址：不超过段长，如(0,25K)，0号段段长是30K，25K合法。

段页式存储管理

结合分页和分段存储管理方式，形成一种新的存储管理方式，即段页式存储管理。段页式系统有两种系统的优点。

段页式系统的基本原理是：

将整个主存划分成大小相等的存储块（页框）。
将用户程序按程序的逻辑关系分为若干个段，并为每个段赋予一个段名。
将每个段划分成若干页，以页框为单位离散分配。

段页式地址空间的结构：

设备管理

设备管理主要是磁盘管理，磁盘也是存储设备，所以磁盘管理也是存储管理。

缓冲技术

缓冲技术可提高外设利用率，尽可能使外设处于忙状态。缓冲技术可以采用两种方式：

硬件缓冲：利用专门的硬件寄存器作为缓冲；
软件缓冲：通过操作系统来管理的。

单缓冲

单缓冲工作过程图：

当第1块数据送入用户工作区后（进行数据处理），缓冲区是空闲的，可以传送第2块数据（输入）。即第1块数据的处理C1与第2块数据的输入T2是可以并行的，以此类推：

总耗时计算：

双缓冲

双缓冲进一步加快I/O的速度，提高了设备的利用率。其工作基本过程是在设备输入时，先将数据输入到缓冲区1，装满后便转向缓冲2。

双缓冲工作过程图：

双缓冲的工作特点是，可以实现对缓冲中数据的输入T和提取M，与CPU的计算C，三者并行工作：

磁盘结构

磁盘有多个盘面，这些盘面在立柱上叠加。每个判断有多个磁道和山区，最外层的磁道是0磁道。

主杆上面是磁头，可以同时读取不同盘面的内容，但是所有磁头只能一起移动。

存取时间=寻道时间+等待时间

寻道时间是指磁头移动到磁道所需的时间
等待时间为等待读写的扇区转到磁头下方所用的时间。

磁盘读取数据的时间=存取时间+传输时间

相连数据块的移动距离为10个磁道，每个磁道需要10ms，则数据块之间移动需要100ms。
每个块读取时间=寻道时间100ms+旋转延迟时间100ms+传输时间2ms=202ms
100个块读取时间=100*202ms = 20200ms

磁盘调度算法(移臂算法)

先来先服务（FCFS）：根据进程请求访问磁盘的先后次序进行调度。
- 优点：公平、简单，且每个进程的请求都能依次得到处理，不会出现某进程的请求长期得不到满足的情况。
- 缺点：此算法由于未对寻道进行优化，致使平均寻道时间可能较长。
最短寻道时间优先（SSTF，最短移臂算法）：该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，使得每次的寻道时间最短。
- 优点：可能会出现饥饿现象。
- 缺点：不能保证平均寻道时间最短。
扫描算法（SCAN，电梯调度算法）：总是从磁头当前位置开始，沿磁头的移动方向去选择离当前磁头最近的那个柱面的请求。如果沿磁头的方向无请求访问时，就改变磁头的移动方向。
在这种调度方法下磁头的移动类似于电梯的调度，所以它也称为电梯调度算法。
- 优点：避免了饥饿现象的出现。
- 缺点：当磁头刚从里向外移动过某一磁道时，恰有一进程请求访问此磁道，这时该进程必须等待，待磁头从里向外，再从外向里扫描完所有要访问的磁道后才处理该进程的请求，致使该进程的请求被严重地推迟。
单向扫描算法（CSCAN，循环扫描算法）：为了减少上述SCAN缺点中存在的这种延迟，算法规定磁头只做单向移动。
例如，只是自里向外移动，从当前位置开始沿磁头的移动方向去选择离当前磁头最近的那个柱面访问，如果沿磁头的方向无请求访问时，磁头立即返回到最里面的欲访问的柱面，再亦即将最小柱面号紧接着最大柱面号构成循环，进行循环扫描。

总结：

先来先服务（FCFS）：根据进程请求访问磁盘的先后次序进行调度。
最短寻道时间优先(SSTF)：该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，使得每次的寻道时间最短。
扫描算法/电梯调度算法（SCAN）：扫描算法不仅考虑到要访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。
单向扫描调度算法（CSCAN）：为了减少这种延迟，算法规定磁头只做单向移动。

I/O管理软件

文件管理

文件目录

文件控制块（FCB）：用于文件的描述和控制的数据结构，实现了文件的“按名存取”。
文件控制块至少要包括文件名和存放文件的物理地址。
文件控制块也称为文件的说明或文件目录项（简称目录项）。
文件目录：文件控制块的有序集合。
即文件目录是由文件控制块组成的，专门用于文件的检索。

文件控制块

文件控制块中包含以下信息：

基本信息类：例如文件名、文件的物理地址、文件长度和文件块数等。
存取控制信息类：文件的存取权限。
UNIX中，用户分成三类：
- 文件主用户
- 同组用户
- 一般用户
以上三类用户对文件的权限为：
- 读
- 写
- 执行
使用信息类：文件建立日期、最后一次修改日期、最后一次访问的日期、当前使用的信息（如打开文件的进程数、在文件上的等待队列）等。

目录结构

组织好文件的目录是设计文件系统的重要环节，文件目录结构的组织方式直接影响到文件的存取速度，关系到文件的共享性和安全性。

常见的目录结构有：

一级目录结构：一级目录的整个目录组织是一个线性结构，在整个系统中只需建立一张目录表，系统为每个文件分配一个目录项。
优点：结构简单；
缺点：查找速度慢，不允许重名和不便于实现文件共享等。
主要用在单用户环境中。
二级目录结构：为了克服一级目录结构存在的缺点引入了二级目录结构。
二级目录结构的组成为：
- 主文件目录（MFD）：每个用户文件目录都占有一个目录项，其目录项中包括用户名和指向该用户目录文件的指针；
- 用户目录（UFD）：由用户所有文件的目录项组成的。
优点：提高了检索目录的速度，较好地解决了重名问题。
缺点：该结构虽然能有效地将多个用户隔离开（这种隔离在各个用户之间完全无关时是一个优点），但当多个用户之间要相互合作去共同完成一个大任务，且一个用户又需要去访问其他用户的文件时，这种隔离便成为一个缺点，因为这种隔离使诸用户之间不便于共享文件。
多级目录结构：在多道程序设计系统中常采用多级目录结构。
多级目录结构是树型目录结构。从根结点向下，每一个结点是一个目录，叶结点是文件。
在采用多级目录结构的文件系统中，用户要访问一个文件，必须指出文件所在的路径名：
- 路径名：从某个目录开始到该文件的通路上所有各级目录名拼起来得到的。
  在各目录名之间、目录名与文件名之间需要用分隔符隔开。
- 绝对路径名：指从根目录开始的完整路径。
  全文件名：指绝对路径名加上该文件的文件名。
- 相对路径名：从当前所在目录开始到其他目录或文件的路径。

位示图

位示图是一种空闲空间管理方法。通过在外存上建立一张位示图，记录文件存储器的使用情况。

位示图用二进制的一位来表示一个物理块的使用情况：

0：表示空闲；
1：表示占用。

例如：

位示图的大小由磁盘空间的大小（物理块总数）决定。

位示图的描述能力强，适合各种物理结构。

做题技巧：

块号从0开始，字号从1开始，公式：

索引文件