操作系统

By Kirino: 之前复习的时候为了方便查阅知识点，把一些个人认为重要的条目整理了一下。建议使用方法：ctrl+F查找关键字. 联系方式: he-jx19@mails.tsinghua.edu.cn

第一章概述

主板上有中央处理器、内存、显示器、键盘、磁盘驱动器等。

计算机指令是计算机运行的最小功能单元。包括算数、逻辑、移位、输入输出等指令。

操作系统是硬件和应用软件之间的通用软件，可以管理部件、提供接口。

发展历史

没有操作系统时期，一次完成一个功能。
串行的单通道批处理。CPU和I/O设备忙闲不均。
多通道批处理（现代意义的操作系统）。宏观上并行，微观上串行。等待I/O时可以使用CPU。
分时系统。多个用户通过终端分享一台计算机。CTSS、MULTICS、UNIX
现代操作系统：受保护指令、系统调用、内存保护、中断、I/O、时钟

特权指令：访问硬件、IO设备直接访问、内存管理状态操作、特殊状态位设置、停机等

CPU的管态和目态：x86的R0、R1、R2相当于管态R3相当于目态。通过程序状态字PSW表征状态。

从管态切换到目态只需要修改PSW，从目态切换到管态的唯一途径是中断。

内存保护可以通过基地址寄存器和边界寄存器完成。

中断是驱动齿轮，指的是由于某个事件的发生，改变了正在CPU上执行的指令的顺序。中断可以不响应。

同步中断：异常，由CPU检测到（错误Fault、陷阱Trap和中止Abort，如除以0）或由程序设定的中断请求（即调用系用调用的软中断）。
异步中断：其他的硬件设备在任意时刻所发出的中断
- 可屏蔽：外部设备正常结束或发生错误。可以处理
- 不可屏蔽：掉电等硬件故障引起的中断。不可处理

用0～255（一个字节）的整数表示中断，称为中断向量。

分时系统中，间隔时钟实现进程间按时间片轮转。实时系统中，按要求的间隔输出正确的时间信号给实时的控制设备。

第二章进程管理

进程

指令执行过程：

取指周期：取指（PC向后移动）、译码。若有间接地址，进行地址映射
执行周期：执行指令。之后判断是否有中断。若有，进入中断周期。

进程是一个正在执行的程序，包括程序代码、数据、CPU寄存器的值、堆栈、系统资源（如地址空间、文件）。

全局变量放在进程的数据段，局部变量放在栈里。未初始化的放在dss。

进程的内存由高到低微内核区、栈、堆、数据段、代码段、保留段。

进程具有动态性、独立性和并发性。

只有一种创建进程的方法，即在一个已经存在的进程(用户进程或系统进程)当中，通过系统调用来创建一个新的进程。

进程的三种状态：运行、就绪、阻塞

转移时不能从阻塞回到运行，而就绪了就不会被阻塞。

通过进程控制块PCB描述进程，是进程存在的唯一标志，存放在内存中。包括进程管理、存储管理和文件管理。

通过维护运行、就绪、阻塞队列来管理进程。

线程

线程是功能运行的基本单位，线程之间并发执行，享用相同地址空间。

线程通过线程控制块TCB描述。寄存器和程序状态字等由线程独享，在TCB中。文件、内存等资源由线程共享，不在TCB中。

线程同样具有三种状态。

进程间通信与同步

进程互斥：访问共享资源时不会互相妨碍。
进程同步：存在依赖关系时的先后次序。

低级通信：只能传递状态和整数值

信号量：面向用户
信号：面向OS

高级通信：传递任意数量数据

共享内存：三份缓冲区，共享区（存放共享变量）、写入区、读取区。读和写都需要先把共享区做一个映射，映射到本地划出来的空间，在本地访问。
消息传递：向中间件发送消息，订阅后获得消息。分为直接通信（利用套接字）和间接通信（利用消息队列）两种模式。
管道：一个进程的输出直接连接到另一个进程的输入

进程互斥是因为竞争CPU或共享资源，处于竞争状态。

互斥：同一时刻，只允许一个进程访问同一个共享数据。

临界资源：把需要互斥访问的共享内存或文件

临界区：访问临界资源的代码

互斥访问的四个条件

不能同时进入临界区
不能假定CPU核数
在临界区外时不能妨碍其他进程进入临界区
不会被饿死

几种实现方法

基于关闭中断：进入临界区后关闭所有中断，不会进行进程切换，退出再打开。操作系统经常干。
基于繁忙等待
加锁标志法：图书馆借书。会竞争锁，套娃。
强制轮转法：定义顺序。违反条件三。
Peterson

interested[process] = TRUE; // 表明本进程感兴趣 
turn = other; //设置标志位，谦让给对方 
while(interested[other] == TRUE && turn == other);

缺点：浪费CPU时间、高优先级抢走CPU后会死锁

信号量
- P原语:申请一个空闲资源(把信号量减1)，若成功，则退出;若失败，则该进程被阻塞
- V原语:释放一个被占用资源(把信号量加1)，若发现有被阻塞的进程，则选择一个唤醒之。

互斥时，初始化为资源数量；同步时，初始化为0，且P和V在不同进程间交替出现。

信号量由操作系统创建，使用不当时也会造成死锁。

进程调度

CPU繁忙：大部分时间处于运行和就绪

I/O繁忙：大部分时间处于阻塞

调度时机：新进程被创建、进程运行完、等待I/O、I/O中断发生（异步中断）、时钟中断发生（同步中断）

调度方式：

不可抢占：需要等待进程主动放弃CPU。批处理。
可抢占：可以被中断打断。交互式、实时。

评价指标：周转时间、平均周转时间、等待时间、响应时间、吞吐量、CPU利用率等

进程切换：寄存器被push进栈，而栈指针SP等值被更新到PCB中

调度算法：

先来先服务FCFS
短作业优先SJF（属于优先级）。可以得到最小平均周转时间
时间片轮转Round-Robin：时钟中断中把现在执行的进程扔到队尾。
- 公平性、活动性
- 时间片q太大退化为FCFS，太小系统开销大。一半确定在20-50ms
优先级
- 可抢占、不可抢占
- 优先级的确定分为动态和静态
- 静态：创建时就确定优先级，低优先级的进程处于“饥饿状态”
- 动态：每执行一个时间片就降低优先级，等待时间延长就提高优先级
- 优先级队列法：按照不同优先级分组，各级别之间使用优先级，统一级别之间使用时间片轮转。但是会出现优先级反转。
- 多级队列算法：先按照性质和类型（系统、用户、批处理）将就绪队列分为子队列，不同队列可以采用不同的调度算法。
- 多级反馈队列：优先级越高的队列时间片越短，如果用完了时间片还没进行完，则降级，如果提前用完，则升级。只有高优先级队列为空时才调度低优先级的。照顾短作业/IO繁忙/新进程。CPU繁忙进程采用最大时间片来执行，减少调度次数。

第三章存储管理

存储器层次结构：寄存器、高速缓存、主存储器（DRAM）、外存。寄存器读取只要半个时钟周期。

单道存储管理

把内存分为系统区和用户区，每次将一个程序装到用户区，和操作系统共享内存。

简单，开销小，易于管理。每次只能运行一个程序，内存资源使用效率不高。

分区管理

把用户区再划分为多个分区，那个进程占用一个分区。支持多通道和并发。

分区策略

固定分区
- 一半分为多个小分区，适当中分区，少量大分区。
- 通过内存分配表实现。表中记录分区号、起始地址、状态、进程名。
- 使用最先匹配或最佳匹配进行分配（会有内碎片）
动态分区
- 进程若干占用区和空闲区相间的布局
- 减少了内碎片（但也有空间预留），有外碎片，即个占用分区之间难以利用的空间
- 通过分区链表记录每个内存块是否被占用、起始地址和长度
- 使用内存紧缩技术可以合并空闲空间
- 最先、下次匹配法：从某一位置出发，找到第一个比他大的就分配。下次匹配可以保证空闲空间最平均
- 最佳匹配法：找到大小最相近的。但是外碎片很细碎，浪费很大
- 最坏匹配：与上一个相反。大小最平均。
物理地址：内存地址、绝对地址、实地址。可以直接寻址
逻辑地址：相对于分区首地址的地址
静态地址映射：装入内存时直接对指令代码进行修改，相当于编译时改了源码。
动态地址映射
- 运行时通过硬件地址映射机制完成，即访问时在相对地址上加上几地址寄存器的值。进程切换时填入基地址寄存器。加入限长寄存器可以保护内存。
- CPU发送逻辑地址给存储管理单元MMU，判断是否越界，若不，则取出基地址寄存器的值，加上得到物理地址。MMU再将物理地址给内存。

段式和页式管理

页式管理

把物理内存切分为固定大小的内存块，为物理页框，逻辑地址空间也切开，为逻辑页面。用不必连续的页框装在页面即可。有内碎片。

通过页表给出内存块号和物理页号之间的关系。在内存中访问页表得到物理页框号。由操作系统创建。

用物理页面表表征物理页框的分配情况。使用Bitmap即可。

分配时，申请一个页表，放入PCB。填充分配情况，同时物理页面表修改Bitmap。

若只有一页，退化为固定分区。

每个页表项包含以下信息：逻辑页号、物理页号、驻留位、保护位、修改位、访问位。

地址映射：逻辑地址->页面号->页框号->物理地址

若取页面大小为\(2^n\)，则逻辑地址低n位就为偏移量，高位为页面号。

页表保存在内核空间，用户不能修改。页表通过页表基地址寄存器+页号（偏移量）寻得物理页框号。

需要两次内存访问，若使用TLB（Translation Lookaside Buffer），可以减少到一次。

没有外碎片，内碎片平均为半页。但是程序必须都装进内存，那个进程都要维护一张页表。

段式管理

根据逻辑单元分段。采用可变分区管理，段内不必连续。

维护段表进行管理和寻址。高几位为段号，后面为段内偏移。保存在内存中，同时设置基地址寄存器和长度寄存器。

地址映射与页式类似。

没有内碎片，但是有外碎片。

若只有一段，退化为可变分区。

bss段存储未初始化的全局变量，不在可执行文件中，由系统初始化。

段页式管理

先分段，段内分页

最高几位为段号，其次为页号，低位为页内地址。

有多少个段就有多少个页表。段表记录每段页表的起始地址和段长，而非段段物理地址。

需要访问三次内存。

虚拟存储

局部性原理：较短时期，执行指令地址和操作数地址分别局限于一定区域。TLB和Cache都体现了局部性。

大部分采取虚拟页式存储。增加请求调页和页面置换功能。

程序运行时，不是所有页面都装进内存。

后备存储：把部分页面保存在磁盘上

后备页面：保存在磁盘上的页面

页表表项：逻辑页号、物理页号、访问、修改、驻留、保护位。若驻留位位0且访问到，引发缺页中断。若修改过，则应该把内容写会外存。

缺页中断引发后，PC不变，还是执行当前的指令。

缺页中断后不一定要执行页面置换算法，若还有内存可以直接载入。

置换算法：

最优OPT：淘汰到下一次访问等待时间最长的。只有理论意义。
最近最久未使用LRU：淘汰最老页面。访问后移到链首，淘汰链尾。使用移位寄存器实现。
最近最少使用LFU：淘汰被访问次数最少的。但是可能违背局部性原理
FIFO：性能较差，对常驻内存应用不友好。存在Belady现象。
时钟置换：指针指向最老的。被访问到的flg置为1，淘汰时跳过1，并把1置为0。

工作集：\(W(t,\Delta)\) 时间t处，在之前的窗口长度\(\Delta\)中访问的逻辑页面集合。是进程的固有属性。

驻留集：当前时刻实际驻留在内存中的逻辑页面。取决于物理页面数和置换算法。其大小代表了内存中的页框数。

固定分配：驻留集大小固定，局部页面置换。但分配的物理页面数难以确定
可变分配：驻留集大小可变，全局页面置换。系统开销较大。使用缺页频率算法PFF动态调整。

缺页率 = 缺页次数/内存访问次数

若缺页率过高，增加物理页面数，过低减少。

第四章 I/O设备管理

I/O硬件

交互方向：输入、输出、输入输出设备
数据组织：块设备（以数据块为单位，有块地址。例如磁盘的扇区）、字符设备（数据为字符流，无定位寻址）、网络设备（包含唯一IP地址，接收和发送帧数据）

I/O单元由机械部分和电子设备（设备控制器或适配器）两部分组成。

适配器是印刷电路卡，控制器是一组芯片，用于完成与主机间的连接和通讯。

CPU与设备控制器的通信

I/O独立编址：每个I/O设备一个不同的地址。需要专门的I/O指令，直接操作寄存器。
内存映像编址：把端口号映射到内存。不需要专门的I/O指令，但是不能对寄存器中的内容进行缓存，且每一次需要判断访问的是内存还是I/O
混合编址：独立+内存映像

I/O控制

对CPU依赖从高到低为

循环检测（轮询）
中断驱动
- I/O设备发出一个信号
- 中断控制器接受，将设备编号放到地址线，向CPU发送一个中断信号
- CPU查询中断向量表，处理中断
直接内存访问（Direc Memory Access）（键盘、磁盘）
- 硬件上有一个DMA控制器，可以直接访问总线。其中也有各种寄存器
- 内存地址寄存器、控制寄存器、字节数计数器
- CPU预先向控制器编程
- 之后DMA按照写好的程序控制I/O设备
- 完成后发出中断（开始时不会发出中断）

截屏2022-01-06 下午9.40.51

为了缓解I/O和CPU速度不匹配的矛盾，可以在内存中设置缓冲区。

I/O软件

重视设备独立

阻塞I/O和非阻塞I/O

由底层到顶层：硬件、中断处理、设备驱动、设备独立的系统软件、用户I/O软件

设备驱动程序与设备类型相关，一般由设备生产商提供。

设备驱动直接控制设备控制器。

两种方案

系统调用调用设备驱动程序，驱动被阻塞。I/O完成后产生中断，唤醒驱动程序。中断处理由厂家完成。
请求队列。设备驱动程序为上层函数，管理请求队列；底层函数与硬件打交道。

设备独立的I/O软件实现了某些通用I/O功能，并向用户软件提供统一接口。

用户空间的I/O软件

库函数：将请求发送到系统调用
SPOOLing技术：把独占设备转变成具有共享特征的虚拟设备

磁盘

磁道：磁头固定在某一位置，转一圈能够访问到的圆环

柱面：所有盘面上等半径的磁道

扇区：一个磁道被划分为若干个扇区

格式化

低级格式化：标出扇区和磁道。
扇区=相位编码（开始码）+数据区+纠错码
分区：0扇区存放系统启动码和分区表
高级格式化：生产引导块、根目录和空白文件系统

磁盘调度

优化柱面定位时间，旋转延迟和数据传送时间无法优化

使用连续扇区存储
使用磁盘调度算法调整I/O请求的执行顺序

调度算法

FCFS：简单，公平，但是效率不高
最短定位时间SSTF：最短距离贪心。磁盘两侧的会饥饿
电梯算法：扫描算法。磁头移动总距离不会超过柱面总数的两倍

第五章文件系统

文件是信息存储和访问的基本单位，负责文件相关的系统为文件系统。实现对文件的按名存取。

文件可以看成单独的、连续的逻辑地址空间，与进程地址空间无关。

文件

对文件系统而言，文件是由无结构的字节流序列组成的（逻辑结构），每种文件的存储方式都是一样的。

分类

普通文件
- ASCII文件（明文的文本文件）
- 二进制文件（具有某种内部逻辑结构）
目录文件（directory）

常见文件属性：文件长度（与占用空间不同，占用空间是文件块大小的和，可能占不满一块）、时间戳、只读隐藏标志位

文件存取：随机存取。每次操作需要指定起始位置。

访问：打开关闭、读写、添加、定位

控制：创建删除、获取设置属性、修改名称

扇区存储

块：把磁盘空间划分为大小相同的物理块，文件也划分成逻辑块。一个物理块由一个或多个连续的扇区组成。块是操作的基本单位。

主引导记录（Master Boot Record，MBR）：磁盘的0扇区。装载了操作系统的代码，在此启动。末尾存在分区表，记录分区情况。

BIOS：加电自检（POST），初始化中断向量表、寄存器等，读入引导扇区，启动造作系统。提供硬件和操作系统的衔接。

扇区大小为\(2^9\)字节（512字节）

若是n位寻址，则分区大小为\(2^n\times 2^9\)。32位为2T。

分区总数为4，或3主1扩

Windows限制分区大小256TB，个数128个

文件控制块FCB：存在硬盘中，访问时会加载到内存中。包括文件信息和文件所在物理块信息。Unix中称为I节点。

存储：

连续结构：存在连续物理块中，只需要第一个块号和文件大小即可。速度快，但存在外碎片。且大小不能动态变化。使用存储紧缩技术合并碎片。
链表结构：访问第n个逻辑块，要做n-1次磁盘访问。只适合顺序访问。且指针占用额外空间。
文件分配表FAT（Allocation）：给出逻辑块和物理块的映射关系。把指针单独放到一个文件里（FAT放在磁盘）。将其读入内存中，查到第n块的物理块号，直接读取。
- 项数等于物理块数
- 表项宽度n（物理块编号位数）由后面的数字决定（32是28）
- \(FAT表大小 = 表项\times宽度\)
- \(寻址最大容量 = 2^n \times 块的大小\)
索引结构：物理块编号直接记录在FCB中，支持随机访问，且易于扩展，可以直接定位。

目录项：位于外存，通过直接法（文件名返回FCB）或间接法（文件名返回FCB地址）组织文件

系统调用

外存中的目录结构、FCB
内存中的系统内打开文件表（每个文件最多出现一次，使用共享计数，常驻内存。含共享计数和FCB）、进程内打开文件表（进程独享，含打开方式、读写指针和指向系统打开文件表的系统指针表）

关闭文件时如果做过修改，要把更新后的文件复制回外存，然后从系统打开文件表中删除。

空闲空间管理

空闲空间列表：记录磁盘上的空闲物理块

Bitmap。位图本身需要放在磁盘上，分配的物理块比较连续。
链表法：空闲的物理块链在一起。删除时，可以先放到队尾，方便数据恢复。
索引法：记录所有空闲物理块的编号，常驻内存。

第六章操作系统安全

计算机安全的三个目标：数据的私密性、完整性、系统的可用性

加密

原文\(E\)，加密密钥\(K_E\)，密文\(D\)，解密密钥\(K_D\)

若\(K_E\)与\(K_D\)有联系或者相同，为对称加密；若毫无关系为非对称加密

私钥加密：基本就是对称加密。DES、AES。
- 简单、安全。但是密钥交换不保险
公钥加密：每个人的加密密钥公开，要发给谁就用谁的公钥加密，只有那个人可以用私钥解开。RSA。
- 无需传输密钥，但是计算量大，加密慢
目前使用RSA对私钥加密的私钥进行加密，大的文件直接使用私钥加密。

数字签名：对文件进行Hash，生成digest，并加密。作为验证的数字签名。

数字证书：使用CA的私钥对公钥加密做认证。

用户认证

基于密码的认证：Cracker可以通过猜密码破解
基于物理对象的认证：各种卡
基于生物特征的认证

系统内部攻击

特洛伊木马：程序内嵌破坏性代码
登陆欺骗：钓鱼网站
逻辑炸弹：需要定期输入密码，不然就会引爆
后门：反汇编嵌入代码，跳过检查
缓冲区溢出

系统外部攻击

病毒：感染文件+破坏，通过移动存储器和网络传播，寄生在宿主程序中
- 可执行程序病毒（插入到正常运行到程序中，寄生）
- 常驻内存病毒（修改中断，运行在内核态，寄生在0扇区，先于操作系统启动）
- 宏病毒
网络蠕虫：通过网络传播的，不断自我复制的程序，传播但是不更改系统。栖息在内存

第二点五章死锁

死锁：每个进程都占用着若干资源，同时又在等待改组进程中另一进程所占用的资源。

可抢占资源：CPU、内存
不可抢占资源：I/O设备

死锁一般由不可抢占资源引起

死锁发生的必要条件

互斥：同一时刻每个资源最多只能被一个进程使用
请求和保持：占有资源时申请新资源
不可抢占
环路等待

资源分配图

用圆圈表示进程，方框表示资源（与Petri网相反）

如果图没有环路，不会有死锁
如果有环路，且每种资源只有一个，死锁。否则说不准。

死锁对应

无为而治
检测和解除
- 检测
  - 人工观察环路
  - 环路检测算法：资源分配图化简
- 解除
  - 剥夺资源
  - 进程回退（需要存储备份，代价高）
  - 撤销进程（kill一个进程，如编译进程）
动态避免：系统状态+银行家算法
死锁预防
- 破坏互斥：假脱机技术。但不通用
- 破坏请求保持：不允许占用时申请其他的。可能被饿死
- 破坏环路等待：按编号来获取。但是可能无法获取到全部所需资源。

资源分配图化简

第一步：先看系统还剩下多少资源没分配，再看有哪些进程是不阻塞（“不阻塞”即：系统有足够的空闲资源分配给它）的
第二步：把不阻塞的进程的所有边都去掉，形成一个孤立的点，再把系统分配给这个进程的资源回收回来
第三步：看剩下的进程有哪些是不阻塞的，然后又把它们逐个变成孤立的点。
第四步：最后，所有的资源和进程都变成孤立的点。这样的图就叫做“可完全简化”。

系统状态的表示

总资源向量E：每种资源有多少资源
空闲资源向量A：每种资源有多少空闲资源
当前分配矩阵C：Cij为进程i占用资源j的个数
请求矩阵R：Rij为进程i还需要的资源j个数

分配的 + 空闲的 = 总的

安全状态：本身不死锁+存在某种调度顺序，就算同时请求最大量也不会寄

不安全状态不一定会死锁，但死锁一定不安全

银行家算法：只有系统保证安全状态才分配，避免死锁。但是需求矩阵R难以获得。

本站总访问量次