操作系统

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

操作系统的核心内容实际上只有处理器管理、存储器管理、文件管理和设备管理

用户对硬件的调用，对于普通用户而言可以使用GUI或是命令接口，而对于程序员则主要需要实现程序接口（系统调用）

操作系统的四个特征：并发（并发和并行）、共享（互斥和同时）、虚拟（空分复用、时分复用）、异步

并发和共享互相充要->虚拟和异步

手工操作系统（纸带）->单道批处理系统（磁带）->多道批处理系统（并行磁带，没有人机交互）->分时操作系统->实时操作系统（软、硬）

CPU具有内核态（可执行特权指令）和用户态，其由PSW寄存器保存。CPU从内核态倒用户态通过执行修改PSW特权指令完成。用户态到内核态使用中断

中断分为内外中断，内中断又叫异常（缺页等故障、陷入故意引发、除数为0非法特权等终止致命错误），应用程序需要请求内核服务时使用陷入指令。外中断（时钟中断、I/O中断）。中断机制由中断向量表实现。

系统调用和库函数的区别比较重要，系统调用是操作系统提供的接口，库函数是高级语言提供的接口，底层可能会用到系统调用。系统调用主要是对共享资源进行保护来提供的。系统调用的流程如下：应用程序发起陷入指令->进入中断处理程序根据寄存器参数决定系统调用服务->进行对应的系统调用处理程序->继续程序运行

操作系统体系结构，就是说内核：内核的设计方法主要有大内核和微内核结构：

然后增加了考核内容：

操作系统引导，这怎么也考啊。磁盘内部有主引导记录（MBR），C盘（引导记录PBR、根目录）和其它分区。除此之外与引导有关的就是BIOS的引导程序。所以在开机时，CPU执行主板里的ROM的自举程序->进入磁盘的第一块——主引导记录读入内存，执行磁盘引导程序->从活动分区读入分区引导记录并执行其中的程序->从根目录下找到完整的操作系统初始化程序并执行

虚拟机

进程管理

首当其冲的就是PCB包含诸多消息：

注意，一个进程实体由PCB、程序段、数据段组成。进程是动态的而进程实体是静态的。进程是系统资源分配和调度的独立单位。

进程的特征如下：动态、并发、独立、异步、结构性

进程的状态主要有创建态、就绪态、运行态、终止态、阻塞态

进程的组织主要有链接方式和索引方式（索引表指向PCB）

进程控制为对进程进行管理，具备原子性，对应的就有了原语这个概念，其由关中断开中断来实现。进程创建原语的流程如下：申请空白PCB-为新进程分配资源-初始化PCB-PCB插入就绪队列。进程撤销原语的流程如下：找到对应的PCB-剥夺CPU-终止子进程-资源归还父进程或OS-删除PCB。阻塞原语：找到PCB-保护现场-转为阻塞态-暂停运行-插入等待队列。唤醒原语与阻塞对应。切换原语：运行环境信息村入PCB-移入队列-选择另一个进程并更新PCB-恢复环境。

进程通信也成为重点了，主要有共享存储、信息传递、管道通信。共享存储就是在内存中开辟一片共享存储区，但是需要互斥访问（速度快，高级通信），基于数据结构的共享慢且限制多，是低级通信。由操作系统提供发送/接收消息原语进行数据交换，分为直接通信（直接指明PID）和间接通信（通过信箱进行，指明邮箱）。管道通信，是一个特殊的pipe共享文件（在内存中开辟的内存缓冲区），与共享存储的最大差距就是数据结构类似队列，且半双工（争议：管道允许多个写进程一个读进程、或是允许多个写进程多个读进程，考试按照前者；再者是管道不会写满，只会读空）

然后就是线程了，现在线程是更屌的东西了。线程是一个基本的CPU执行单元、也是程序执行流的最小单位。提升了并发度，且现在线程是调度的基本单位，进程只是资源分配的基本单位。线程的数据结构就是TCB和线程ID，且只有就绪、阻塞和运行三种状态，不具有系统资源。同一进程不同线程共享进程资源。

线程的实现方式包括用户级线程和内核级线程。前者由线程库实现的（OS看到的实际是进程，而且不能使用多核），内核级线程的管理由OS完成且需要变态，并发性强。由于两者各有优劣，所以有了多线程模型，分为一对一（需要变态，管理成本大），多对一（本质就是用户级线程），多对多(n-m)

线程的状态和转换也是新内容：

线程的组织和控制主要是通过TCB实现

进程调度属于低级调动，按照某种算法从就绪队列中选择一个进程分配处理机。（注意：进程在操作系统内核程序临界区不能进行调度和切换（PCB队列），但是能够在临界区进行处理机调度（打印机），这主要是由于内核程序临界区一般是用来访问某种内核数据结构的）

进程的调度方式主要有非剥夺调度方式和剥夺调度方式。

在创建新进程、进程退出、进程阻塞或是I/O中断发生的时候会触发调度程序。对于非抢占式，只有阻塞或退出时才会触发调度程序而对于抢占式调度，每个时钟中断或是k个时钟中断会触发调度程序工作。

除了前面的进程，还有一种闲逛进程，优先级最低，在就绪队列为空时最后运行。

调度算法的指标：$利用率=\frac{忙碌的时间}{总时间}$ $吞吐量=\frac{完成的作业数量}{总时间}$ $周转时间=从提交到完成的时间$ $平均周转时间$ $带权周转时间=\frac{作业周转时间}{实际运行时间}$ $平均带权周转时间$$等待时间=等待处理机状态时间之和$$响应时间=用户从提交到首次产生响应的事件$

注意，进程和作业都有等待时间，但是前者只包含进程建立后等待被服务的时间之和，而后者不仅要考虑建立进程后的等待时间还要加上作业在外存后备队列中等待的时间，所以也有平均等待时间这个概念。

接着就是合理的调度算法，题目默认是非抢占式。在所有进程可同时运行时SJF(SPF)的平均等待时间、平均周转事件最小，而抢占式的调度算法往往更快。由于FCFS看重等待时间而很拉，且SJF会造成长作业哒咩的问题，既有了HRRN算法（一般是非抢占式），计算相应比=$\frac{等待时间+要求服务时间}{要求服务时间}$

时间片流转(默认抢占)（注意，我们默认新到达的进程先进入就绪队列）优先级调度算法（还可以用于I/O调度），根据设置的优先数进行，可以静态或是动态优先级，通常情况下

对上面所有算法的缝合就有了多级反馈队列，设计多级就绪队列，每个队列的时间片从小到大

前面提到的算法主要着重于宏观指标所以常用于批处理系统而后面提到的三种算法着重于实际使用所以常用于现代计算机

除了上面的了六种以外还有一个特殊的调度算法

然后就是进程的另一个重难点了——进程同步与互斥。对于互斥访问主要分为进入区、临界区、退出区、剩余区。进程互斥需要满足四个原则：空闲让进、忙则等待、有限等待、让权等待

进程互斥的软件实现方法主要有单标志法（违反空闲让进）、双标志先检查（违反忙则等待）、双标志后检查（违反空闲让进、有限等待）、Peterson算法（违反让权等待）

除了使用软件实现互斥，也可以使用硬件完成互斥

中断屏蔽只适用于单处理机内核进程，TestAndSet(TSL)，Swap(Exchange/XCHG)

虽然上面提到了很多方法，但是我们实际使用较多的一种是锁。互斥锁（违反忙则等待，单核解锁不了）

互斥的软件实现和硬件实现均不能实现让权等待问题，主要是由于一些操作不能一气呵成导致的。所以对信号量使用原语操作就能解决这些问题，那么使用的原语就是wait(S)和signal(S)也叫做PV操作。实际上整形信号量可以看作前面软件实现的标志。

信号量机制主要包括整型信号量（会出现忙等）和终极解决方案——记录型信号量

由于信号量机制是重中之重，所以要花大功夫来搞。

信号量机制实现进程互斥主要需要如下流程

实现同步的流程如下

前驱关系的实现是比较冗杂的，不大可能会考：

然后就是经典的问题了：生产者消费者问题

多生产者消费者模型：

(缓冲区的数量为1时可能不需要互斥信号量)

抽烟者问题：

（使用循环实现单生产者多产品）

读者写者问题（count计数器）：

上述方案解决了if判断时的冲突，但是仍然会导致写的饥饿问题，所以：

哲学家进餐问题（多解，解决死锁）

管程主要考概念，在管程出来之前主要使用信号量，虽然很强但是会导致编程的复杂。所以就有了管程，管程包括：共享数据结构的声明、执行操作的过程、初始值、管程的名称。管程的特征：管程的数据结构只能被其操作所访问、一个时刻仅有一个进程可以访问。之所以不用考虑互斥问题，是因为这些工作由编译器负责实现进程互斥进入管程

死锁：互相等待对方手里的资源。产生的必要条件：互斥条件、不可剥夺条件、请求和保持条件、循环等待条件（可能是必要不充分条件）。死锁的处理方式：预防死锁、避免死锁、死锁的检测和解除。

预防主要是破坏前面的必要条件：将只能互斥的资源改成允许共享使用（破坏互斥条件SPOOLing），破坏不可剥夺条件（会导致饥饿），使用静态分配一次性分配所有资源（破坏请求和保持），按编号递增顺序请求资源（破坏循环等待条件）

避免死锁的银行家算法很容易考，不安全状态可能会发送死锁。在资源分配之前预先判断是否会导致不安全状态

死锁的检测和解除。死锁的检测使用资源分配图来实现，可完全简化的图一定没有发生死锁，而无法被消除的就是会死锁的进程。检测死锁之后需要立刻解除，方法包括资源剥夺法、撤销进程法、进程回退法。

内存部分

OS对内存负责：内存空间的分配与回收、对内存空间进行扩充，负责逻辑地址与物理地址的转换，内存保护（互不干扰，使用基址寄存器和界地址寄存器检测）

覆盖技术和交换技术。覆盖技术就是将程序分为多个段，将常用的段放在内存里，不需要的放外面，将互斥的模块放在同一个覆盖区，但是需要程序员提前设置覆盖结构。交换进程是把满足运行条件的进程换入内存（这里就是上一章的进程调度了）

一般会为磁盘分为文件区（离散分配利用率高）和对换区（连续分配速度快），在运行过程中缺页较多时进行交换，将阻塞的进程换出

内存的管理首先就是分配与回收：单一连续分配，需要将内存分为系统区（低地址放OS）和用户区（用户进程和数据），且内存中只有一道用户程序、固定分区（分为若干个分区），可以分为大小相等或大小不相等的空间，前者可能会浪费空间，后者需要一个分区说明表来说明每个分区的大小和起始地址来管理。动态分区分配，在进程装入的时候根据进程的大小动态建立分区，这个就是重点了

回收主要在于合并。关于分配，可能会导致内部碎片和外部碎片（分配的空间中有些用不上）、内存中一些空间太小不能用。使用紧凑技术将进程与进程之间空间搞掉。

动态分区分配算法就是接下来的重点了。

上面主要是连续分配管理，下面是非连续存储管理。

通过将内存空间分为大小相等的分区。（注意：页框=页帧=内存块=物理块=物理页面），OS为每个进程建立一个页表（通常放在PCB中）实际上只需要使用块号即可得到对应的页号

对于给出的逻辑地址，除以页面长度得到页号，加上偏移量即可得到物理地址（实际上通常低地址为偏移量高地址为页号）。

地址变换和块表这部分在计组已经提到了，所以不用再过多说明了。接下来的重点是二级页表，实际上并不难理解：（通常用页目录表来表示二级页表）

可以解决页表很大的问题，同时没必要页表常驻内存，同样可以放在外存中通过缺页中断来获取新页。注意，由于相当于是使用页来保存页，所以各级页表项大小不能超过页面数量

分段存储管理：按照自身逻辑分为若干段（长度不一内部连续）

每个段对应一个段表，记录了起始位置和段长

除了上述的对比，分段对于分页最大的有点在于容易实现消息的共享和保护。（注意，不能修改的代码称为纯代码或可重入代码），这些代码可以共享。可修改的代码是不能共享的。

段页式管理是段式和页式的结合，分页不会产生外部碎片，但是不方便根据逻辑实现信息共享保护，而分段则与之相反，较长的段长难以分配，且会产生外部碎片（使用紧凑有较大的时间代价）

段页式同样是二维的（但是需要三次访存）：

虚拟内存，传统的存储管理，例如上面的连续分配和非连续分配有很大的缺点：一次性：需要作业一次性全部装入内存中，且会导致由于进程数量减少而降低并发度。驻留性：一旦进入内存会驻留至作业运行结束。所以根据时间局部性和空间局部性的原理搞出了虚拟内存：只把需要的部分装到内存，用不到的放在外村，信息不在内存时OS负责将信息调入内存，若内存不够则调出（多次性、对换性、虚拟性）。由于允许一个作业多次调入调出，所以需要在离散分配（段、页、段页）的基础上进行。对应的需要OS实现请求调页（段）功能或页面（段）置换功能

请求分页管理方式：分为页表机制、缺页中断、地址变换机制。请求分页的页表新增了许多内容：

为了实现请求分页，需要实现缺页中断机构：页面不在内存-产生缺页中断-中断处理程序处理终端-缺页进程阻塞-唤醒。在调页时，如果有空闲块则分配空闲块，并修改页表项，否则使用页面置换算法选择页面淘汰，如果页面被修改过，还需要进行写回。

缺页中断属于内中断，一条指令执行过程可能会导致多次缺页中断。

页面置换算法有很多种

（字面意思，最佳的）

页面分配策略：

驻留集指请求分页存储管理中给进程分配的物理块的集合（驻留集小导致大量时间缺页，驻留集大导致并发度、资源分配率下降）。所以驻留集的调整可以有固定分配也可以有可变分配。对于缺页的处理方式有局部置换（只跟自己的物理块置换）和全局置换（跟别人的物理块置换)

固定分配局部置换，可变分配全局置换（选择一个未锁定的页面换出外存，只要某进程发生缺页，都将获得新的物理块。被选中的进程拥有的物理块会减少，缺页率会增加），可变分配局部置换

预调页策略：预测不久之后可能访问到的页面，调入（一般用于首次调入），请求调入（运行时调，一次一块）。调换的区域为对换区（前面提到对换区、文件区）。在运行时首先将数据从文件区调入对换区，之后与内存进行交换，如果对换区空间不足时，不会被修改的数据从文件去调入，可能修改的仍需要写回磁盘对换区。

抖动指频繁的页面调度。指访问的页面数量高于可用的数量。使用工作集来控制物理块数。驻留集的大小是不能小于工作集的大小

内存映射文件：OS向程序员提供的系统调用。传统的文件访问方式

文件管理

重点在于文件内部如何组织、文件之间如何组织、文件属性、文件的操作和文件在磁盘中的存储。

文件的属性主要有：文件名（同一目录不能重名）、标识符（区分文件）、类型（后缀）、路径（用户使用的）、大小、创建修改时间、保护信息。

文件的逻辑结构分为无结构文件和有结构文件（分为顺序文件、索引文件、索引顺序文件）。其中有结构文件由一组相似的记录组成，包含关键字，根据记录的长度是否相同可以分为定长记录和可变长记录。

顺序文件在逻辑上一个接一个存储，在物理结构上可以顺序存储或链式存储：

为了使可变长文件同样可以随机查询，所以需要使用索引表

但是当索引项过多导致的索引表项太大时，就会降低存储空间的利用率，所以有了索引顺序文件（B+树是吧）

文件目录实现需要使用文件控制块，使用一个目录文件实现文件的控制，所以FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。FCB中包含了基本信息（文件名、物理地址、）、存取控制信息、使用信息。

对于目录可以进行诸如：操作、创建文件、删除文件、显示目录、修改目录的操作。多个FCB的组织就形成了文件目录。最初的目录就够就是单级目录结构（按名存取，不允许重名），两级目录结构，分为主文件目录MFD和用户目录UFD：

所以现在常用的是多级目录结构，需要使用路径名来标识文件。但是树型目录结构不便于文件的共享，所以在此基础上出现了无环图目录结构

放在内存的索引节点需要增加修改位等相关信息

文件的物理结构是一个比较重要的部分，主要包含了非空闲磁盘块和空闲磁盘块。文件在外存中的存放方式主要有连续分配、链接分配和索引分配。在进行物理结构之前首先需要知道文件的存储是以块为单位的（通常和内存块大小一致），所以文件的逻辑地址可以表示为逻辑块号+块内地址。

连续分配逻辑上连续的文件块在物理上也连续。则物理块号=起始块号+逻辑块号（支持顺序访问和随机访问，且在读取时速度较快，但是问题是不容易拓展）。连接分配使用指针指向离散的块（隐式）只支持顺序访问，显式链接使用一张文件分配表（FAT），既支持顺序也支持随机访问（而且快且不会担心扩展问题），注意，每个磁盘只会建立一张文件分配表。索引分配为每个文件建立索引表，记录文件每个逻辑块对应的物理块：（支持随机访问和文件拓展）

如果一个索引表太大以至于一个索引块装不下，所以需要将多个索引块链接起来存放。链接方案为最后一个逻辑块号指向一个新的物理块，但是由于彼此链接，所以无法方便的实现随机访问。多层索引类似多级页表，各级索引表的大小同样不能超过一个磁盘块（会考察文件最大长度的计算，三层的索引结构就有256^3*1KB=16GB）。混合索引使用了多种索引分配方式，直接地址索引指向数据块、一级间接索引指向单层索引表、两级间接索引指向两层索引表：

注意区分文件逻辑和物理分配的区别

文件存储空间的管理首先是划分和初始化，之后是管理方法，存储空间的划分：

存储空间的管理方法：空闲表法（连续分配，类似对换的FF、BF方法，主要是要做合并工作）

空闲链表法以盘块为单位租成链，空闲盘区链以盘区（多个连续盘块）为单位组成空闲链。分配的时候申请K个盘块从链头一一取下并修改链头指针，回收时依次放到链尾并修改链尾指针。空闲盘区链同样可以使用FF、BF等方法，找到一个适合大小的盘区，若找不到，则把相连的分配给一个文件。位示图法直接用位来表示块是否空闲，通常会考字号位号到盘块号的的转换（注意起始地址），分配时找到K个相邻或不相邻的0来得到盘块号并设为1，反之类似。UNIX中采用成组链接法来进行空闲块的管理，这个比较棘手（但是貌似不常考）

文件的操作（create、delete、read、write、open、close），create系统调用参数：所需空间、路径、文件名，进行了空间的查找和创建目录项的工作。delete系统调用参数：路径，文件名，找到目录项，回收磁盘块，删除对应的目录项。open系统调用参数：路径、文件名、操作类型，找到对应的目录项，检查操作权限:

文件的保护方式包括口令保护（访问时提供口令，存在FCB中，开销小，但是存放在内部，不安全），加密保护（访问时提供密码，对文件使用密码解密，安全但是慢），访问控制表ACL，访问类型用位表示（类似Linux下的权限管理）

层次系统不再是重点了，简要了解即可

文件系统的物理布局：在外存中：

在内存中：

最后是虚拟文件系统和文件系统的挂载。对于不同文件系统，操作的系统调用可能存在区别，为了进行统一，提供了一个虚拟文件系统层VFS，其要求下层的文件系统实现VFS需要的接口函数，再者，由于不同文件系统的目录项存在较大的区别，在内存中的存储会使用不同的数据结构，所以open的时候使用vnode数据结构来存储任何文件

vnode中的函数功能指针指的就是文件系统中提供函数功能的位置，从而进行操作时直接使用文件系统提供的功能来操作。

原本属于IO部分的磁盘现在在这里提前说明一下。

磁盘的分类根据磁头是否移动，盘片是否可以更换分类。

磁盘的调度是另一个重点：一次磁盘的读写所需要的时间

磁盘调度算法也是重点：FCFS、最短寻找时间优先SSTF（贪心但不是整体最优、会饥饿）、扫描算法SCAN（到达一侧后才会回去且对于不同磁道的访问非常不平均，边缘易于访问）、LOOK调度算法解决了SCAN算法的第一个问题、C-SCAN解决了第二个问题，达到边缘后从0开始、C-LOOK则是结合了上面两个方法，到达最靠右需要访问的就返回到最靠左需要访问的地方

磁盘延迟时间的减少方法：采用交替编号的策略（由于读取一个数据块之后会需要处理时间而无法读取，只需要将数据块之间制造间隔即可使得读取连续逻辑扇区的延迟减少）。磁盘地址的结构设计为柱面、盘面、扇面：

继续说明延迟时间减少的方法：错位命名，即将不同盘面的角度错位

磁盘的管理包括磁盘的初始化。磁盘的初始化时首先进行低级格式化，将每个磁道分为扇区，之后对磁盘进行分区，接着逻辑格式化以创建文件系统。完成上述操作之后安装操作系统，ROM利用自举装入程序将磁盘中的操作系统读入内存

今年在OS和CI中都添加了SSD作为考点，所以要学力。

最后是IO设备的管理，UNIX会将外部设备抽象为文件来操作。

IO控制器，我们着重了解IO设备的电子部件（IO控制器）

I/O控制器作为CPU与设备的接口（实际上就是计组中的I/O接口！）

OS中的I/O控制器组成：

计组中的I/O接口组成：

关于寄存器的位置和编址，通常有两种方式（内存编址和独立编址，详见计组）

I/O控制方式：程序直接控制、中断驱动方式、DMA方式、通道控制方式

I/O软件层次如下：

用户层会向用户提供与用户交互的接口（库函数），用户层软件使用系统调用来请求操作系统内核的服务。设备独立性软件需要实现1系统调用2设备的保护3差错处理4设备的分配与回收（临界资源）5数据缓冲区管理6建立逻辑设备到物理设备的映射并选择调用相应的驱动程序（设计了逻辑设备表LUT）

设备驱动程序负责对硬件设备的具体控制，向上层发出一系列命令。中断处理程序是在I/O控制器完成I/O任务时使用的。

实际上，用户层的软件是无法处理多种硬件的，这里主要就说明了字符设备、块设备和网络设备。对于字符设备接口使用get、put系统调用，对于块设备接口使用read、write、seek等系统调用，而对于网络控制器使用网络设备接口（网络套接字socket接口）使用bind、connect、read、write

系统调用的类型分为阻塞I/O和非阻塞I/O，前者需要进程转为阻塞态（get）而后者无需（write）。设备程序接口需要设备独立软件调用设备驱动程序接口来调用，需要厂商设计符合调用规范的驱动

I/O核心子系统各个层次对应的功能