计算机系统概述

操作系统的四个特征

并发和共享是两个最基本的特征，两者互为存在条件
没有并发和共享，就谈不上虚拟和异步。

并发

并发：宏观上同时发生，微观上交替发生
并行：确实在同时发生

共享

共享即资源共享，指系统中的资源可供内存中多个并发执行的进程共同使用。
两种资源共享方式：互斥共享方式（一个时间段内只允许一个进程访问，如qq和微信视频摄像头），同步共享方式（宏观上一个时间段内多个进程“同时”访问）如qq和微信发文件，微观上实际上仍是交替访问硬盘）。

虚拟

把一个物理试题变为若干个用户能感受到的逻辑对应物。分为空分复用技术（如虚拟存储器技术）和时分复用技术（如虚拟处理器）。
eg1. 4GB内存，虚拟化之后远大于4GB
eg2. 虚拟处理器技术，实际上只有一个单核CPU，用户看来似乎有6个CPU同时服务

异步

由于资源有限，进程的执行又不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

操作系统的运行机制

CPU有内核态和用户态，CPU中有一个寄存器存二进制位来区分两种状态。处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令。处于用户态时，说明正在运行的是应用程序，此时只能执行非特权指令。
内核态切换到用户态：执行一条特权指令——修改标志位为用户态，这个动作意味着操作系统将主动让出CPU使用权
用户态切换到内核态：由“中断”引发，硬件自动完成切换过程，触发中断信号意味着操作系统将强行夺回CPU使用权

中断和异常

中断是让操作系统内核取回CPU使用权的唯一途径。
异常（exception）的类型：

同步：与当前执行的指令有关，中断信号来源于CPU内部 e.g. 用户态执行特权指令、执行指令非法、应用程序想请求操作系统内核的服务，则执行“陷入指令”发一个内部中断信号。
分为
- 陷阱（trap）：陷入指令引发，是应用程序故意引发的
- 故障（fault）：错误条件引起，可能被内核程序修复，如缺页故障
- 终止（abort）：致命错误引起，内核程序无法修复该错误，直接终止该应用程序
异步（中断interrupt）：与当前执行的指令无关，中断信号来源于CPU外部 e.g. 时钟部件每隔一个时间片给CPU发送一个时钟中断信号、由IO设备发来的中断信号

中断机制的原理：当CPU检测到中断信号后，根据中断信号的类型查表，找到对应程序指针，执行对应的中断处理程序（要在内核态中才能完成）。

系统调用

系统调用是OS给应用程序使用的接口，应用程序可以通过系统调用来请求获得操作系统内核的服务。与共享资源有关的操作（存储分配，IO，文件管理等），都必须通过系统调用的方式向OS内核提供服务请求，由内核代为完成，保证系统的稳定性和安全性。
与库函数的区别：库函数隐藏了系统调用的一些细节，使程序员编程更加方便。
系统调用的过程：传递系统调用参数，执行陷入指令（用户态）引发一个内中断使得CPU进入核心态，执行相应的内请求核程序处理系统调用（核心态），返回应用程序

操作系统的功能

处理机管理

核心任务：如何分配CPU时间

进程管理
线程管理

主要功能

公平分配
保证非阻塞
按优先级分配

存储器（内存）管理

核心任务：管理缓存、主存、磁盘等所形成的多级存储架构，为多道程序的并发提供良好的环境。
主要功能

内存分配和存储无关性：方便用户
内存保护：互不干扰
内存扩充：虚拟存储器

设备管理

核心任务：管理IO设备，屏蔽差异性，提供并发访问
主要功能

设备无关性：逻辑设备->物理设备
设备分配：独享、共享和虚拟
设备的传输控制：中断、通道

文件系统

核心任务：将磁盘变成一个很容易使用的存储媒介提供给用户使用。
主要功能

文件存储空间的管理
目录管理
文件读、写管理
文件保护
向用户提供接口

作业控制

作业调度，作业控制（批量性作业、终端型作业）

操作系统体系结构

内核：对系统资源管理的功能（进程管理，存储器管理，设备管理等）+时钟管理，中断处理，原语（设备驱动，CPU切换等，具有原子性，运行时一气呵成），运行在内核态
非内核功能（如GUI）：Ubuntu，CentOS的开发团队，主要工作是实现非内核功能，运行在用户态
内核+非内核功能=OS
大内核：内核都在内核态运行
微内核：对系统资源管理的功能（进程管理，存储器管理，设备管理等）也放在用户态运行。显而易见，需要频繁地切换核心态和用户态，性能较低

操作系统的引导（boot）

安装了操作系统的磁盘中，除了CDEF等盘中，还有一个区域，主引导记录（MBR），包含磁盘引导程序和分区表。如果把操作系统安装在C盘上，称C盘为活动分区。C盘中存在一个引导记录PBR，负责找到“启动管理器”。
计算机的组成包含RAM,ROM。RAM断电丢失，ROM断电不丢失，包含ROM引导程序，即自举程序。
操作系统引导过程：

开机通电时，执行ROM中的引导程序。（先硬件自检，再开机）
将磁盘的第一块——主引导记录读入内存，执行磁盘引导程序，扫描分区表。
从活动分区（又称主分区，即安装了操作系统的分区）读取分区引导记录PBR，执行其中的程序。
从根目录下找到完整的操作系统初始化程序（即启动管理器）并执行，完成“开机”的一系列动作。

虚拟机

使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机器，每个虚拟机器都可以独立运行一个操作系统。

进程管理

程序是静态的实体，进程（Process）是执行中的程序，是动态的。同一个程序多次执行会对应多个进程。

进程的组成

分为PCB，程序段（程序代码），数据段。

每一个进程有一个PID（Process ID）。操作系统记录PID，UID，还要记录给进程分配了哪些资源以及运行情况。这些信息都被保存在一个数据结构PCB（Process Control Block）中，即进程控制块，供操作系统使用。

同时挂三个QQ号会对应三个QQ进程，它们的PCB、数据段各不相同，但程序段内容相同。

进程的特征

动态性：最基本的特征。动态地产生、变化、消亡。
并发
独立
异步：各系统按各自独立的、不可预知的速度向前推进，操作系统要提供“进程同步机制”来解决异步问题。

进程的调度：创建、挂起、激活
进程间的通信：同步、互斥、死锁

进程的状态

创建态
就绪态：已经具备运行条件，由于没有空闲CPU暂时不能运行
运行态：上CPU运行
阻塞态：进程运行中，可能会等待某个事件发生（如等待某种系统资源分配，或者等待其他进程相应），此时OS会让这个进程下CPU并进入阻塞态，当CPU空闲时，又会选择另一个就绪态进程上CPU运行。
终止态：一个进程可以执行exit系统调用，请求操作系统终止该进程，进程进入终止态

进程状态的转换

就绪态到运行态：进程被调度
运行态到就绪态：时间片到，或CPU被其他高优先级进程抢占
运行态到阻塞态：等待系统资源分配，或等待某时间发生，为进程运行时自身做出的主动请求，因此必须从运行态开始转换。
阻塞态到就绪态：资源分配到位或等待时间发生，是被动行为
运行态到终止态：进程运行结束，或遇到不可修复错误

进程的组织方式

链接方式和索引方式

链接方式

分为多个队列
执行指针：指向处于运行态的进程
就绪队列指针：指向当前处于就绪态的进程
阻塞队列指针：可能存在多个阻塞队列，如等待打印机的阻塞队列，等待磁盘的阻塞队列

索引方式

建立索引表，操作系统持有指向各个索引表的指针

进程控制

创建新进程，撤销已有进程，进程状态转换（需要原子性，一气呵成）
可以用“关中断指令”和“开中断指令”这两个特权指令实现原子性，CPU执行了关中断指令后就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查。这样，关中断、开中断之间的指令就是不可被中断的，实现了原子性。

相关原语：进程创建，终止，阻塞，唤醒，切换（阻塞和唤醒要成对出现）

进程通信

IPC（Inter-Process Communication）进程间通信指的是两个进程间产生数据交互。

共享存储

通过增加页表项/段表项即可将同一片共享内存区映射到各个进程的地址空间中。为避免出错，各个进程对共享空间的访问应该是互斥的，各个进程可使用操作系统内核提供的同步互斥工具（如P、V操作）

基于数据结构的共享：比如共享空间只能放一个长度为10的数组，是一种低级通信方式
基于存储区的共享：数据形式和存放位置都由通信进程控制，而不是OS。速度快，是一种高级通信方式。

消息传递

进程通过操作系统提供的“发送、接受消息”两个原语进行数据交换。
分为直接通信方式（指明ID）、间接通信方式（信箱）。

管道通信

进程P向管道写数据，进程Q从管道读数据，数据流向和水管一样是单向的。管道是一个特殊的共享文件，又名pipe文件，其实就是在内存中开辟一个大小固定的内存缓冲区。数据读写FIFO。
各个进程要互斥地访问管道（由OS实现）
管道写满时，写进程将阻塞，直到读进程取走数据，即可唤醒写进程。

线程

有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此引入线程。
进程是资源分配的基本单位，线程是调度的基本单位。同一进程间的线程切换，不需要切换进城环境，系统开销小。这些线程共享进程的资源。

线程的实现方式

用户级线程

用户视角能看到的线程，由线程库实现

内核级线程

操作系统只“看得见”内核级线程，内核级线程才是处理机分配的单位

多线程模型

一对一：一个用户级线程映射到一个内核级线程
多对一
多对多（用户级线程比内核级线程多）

线程的状态与转换

和进程一样

处理机调度

高级调度：作业调度，创建进程，每个作业只调入一次调出一次无-创建态-就绪态
中级调度：内存调度挂起态-就绪态
低级调度：进程调度，分配处理机就绪态-运行态

调度算法

调度算法的评价指标

CPU利用率：忙碌时间/总时间
系统吞吐量：总共完成了几道作业/总共花了多少时间
周转时间：从作业被提交给系统开始，到作业完成为止的时间间隔
带权周转时间：作业周转时间/作业实际运行更高，必定大于等于1
以上两个时间都是越小越好
等待时间：进程/作业处于等待处理机的状态的时间
响应时间：从提交请求到首次产生响应所用的时间

先来先服务FCFS

按照作业到达的先后顺序服务
对短作业不友好

短作业优先

最短的进程优先服务
对长作业不友好

高响应比优先

调度时先计算各个作业的响应比，旋最高
响应比=（等待时间+要求服务时间）/要求服务时间大于等于1

时间片轮转

按照各个进程到达就绪队列的顺序，轮流让各个进程跑一个时间片。若进程一个时间片未执行完，则进程重新放到就绪队列队尾重新排队

优先级调度算法

非抢占式：每次调度时选择当前已到达且有限度最高的进程。

多级反馈队列调度算法

进程同步

协调工作次序而产生的制约关系。

进程互斥

我们把一个时间段内只允许一个进程是用的资源称为临界资源，而对临界资源的访问必须互斥地进行。
进入区上锁，临界区访问临界资源，退出去解锁，剩余区其余代码部分

进程互斥的软件实现方法

单标志法

设一个turn，表示当前允许进入临界区的进程号。进程turn不匹配则无法进入

双标志先检查法

布尔数组flag[]

双标志后检查法

Peterson算法

表达意愿

进程互斥的硬件实现方法

互斥锁

解决临界区最简单的工具就是互斥锁。主要缺点是忙等待

内存管理

内存的基础知识

从写程序到程序运行：编辑，编译（翻译为机器语言），链接（形成完整的逻辑地址），装入（将装入模块装入内存，之后形成物理地址）
三种链接方式：
三种装入方式：绝对装入（编译时产生绝对地址）、可重定位装入（装入时将逻辑地址转换为物理地址）、动态运行时装入（运行时转换，需设置重定位寄存器）

内存管理的概念

负责内存空间的分配与回收
虚拟技术，内存扩展
实现逻辑地址到物理地址的转换（地址重定位）：三种装入方式
内存保护，保证进程互不干扰：
- 方法一：CPU设置一对上下限寄存器，CPU检查是否越界
- 方法二：采用基址寄存器和界地址寄存器进行越界检查。分别存放起始物理地址和最大逻辑地址

内存空间的分配与回收

连续分配管理方式

为用户进程分配的是一个连续的内存空间。
内部碎片：分配给某进程的内存区域中，有些部分没用上
外部碎片：内存中的某些空闲分区由于太小，利用不了

单一连续分配

内存氛围系统区、用户区，内存中只能有一道用户程序，用户程序独占整个用户区空间。
优点：无外碎片
缺点：有内碎片（分配，但没用上），存储器利用率低

固定分区分配

建立一个分区说明表

分区号 |大小| 起始地址 |状态

优点：无外碎片
缺点：有内碎片

动态分区分配

根据进程大小动态建立分区。

用什么结构记录内存使用情况？空闲分区表、空闲分区链
有多个空闲分区能够满足需求，应选择哪个分区进行分配？
1. 首次适应算法：每次都从低地址开始查找，找到第一个能满足大小的空闲分区
2. 最佳适应算法：优先使用更小的空闲区
3. 最坏适应算法：优先使用最大的连续空闲区
4. 临近适应算法：首次适应算法每次都从链表头开始查找，开销较大。改为每次都从上次查找结束得到位置开始检索。
如何进行分区的分配与回收操作？总之，回收后相邻的空闲分区要合并

无内部碎片，有外部碎片，外部碎片可以用紧凑技术解决

非连续分配管理方式

基本分页存储管理（重难点）

将内存空间氛围一个个大小相等的分区，每个分区就是一个页框（内存块/物理页面）
将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个页。
页框号和页号都从0开始。
OS为每一个进程建立一张页表，通常存储在PCB中。
每个页表项由页号（不占字节）和内存块号（占字节）组成，这就完成了进程页面和实际存放的内存块的映射关系。

逻辑地址空间图：

重要考点：计算机中内存块数量->页表项中块号至少占多少字节？
E.g. 物理内存大小4GB，页面大小4KB，则每个页表项至少应该为多少字节？
共2^20个内存块，块号范围0~2^20-1，至少要用20bit表示->至少要用3字节表示块号（3*8=24bit）
注意页表记录的只是内存块号，而不是内存块的起始地址

如何实现地址的转换？如果要访问逻辑地址A，则：

确定逻辑地址A对应的页号P和页内偏移量
检查页号合法性（与页表长度对比）
找到P号页面在内存中的起始地址，根据页号找到页表项（需要访问内存查页表）
根据页表项中记录的内存块号和页内偏移量得到物理地址
访问物理地址对应的内存单元

逻辑地址的结构：
31…12 11…0
页号P 页内偏移量W
页面大小和页内偏移量位数可以互推

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。通常会在系统中设置一个页表寄存器PTR，存放页表在内存中的起始地址F和页表长度M（多少个页表项）

具有快表TLB的地址变换机构：TLB是页表项的缓存，加快地址变换的速度。TLB命中则直接找到了内存块号，，直接获取物理地址。因此若快表命中则仅需一次访存。

两级页表

单级页表存在的问题：

页表需要连续存放，才能使用页号查询的方式找到页表项，因此页表很大时，需要占用很多歌连续的页框。

解决：如何解决进程在内存中必须连续存储？将进程地址空间分页，建立页表，记录页面存放位置。同样的思路，把必须连续存放的页表再分页

31..22 21…12 11…0
一级页号二级页号页内偏移量W

先查一级页号对应的内存块号，去对应内存块号取出相应的二级页表（显然，各级页表的大小不能超过一个页面的大小，据此计算一个页面能存放多少个页表项，进而确定总共xx位的页号要分为多少级页表），再根据二级页号查到内存块号

根据局部性原理可知：很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了，因此没必要让整个页表常驻内存。

解决：可以再需要访问页面时才把页面调入内存（虚拟存储技术）。可以在页表项增加一个标志位，用于表示该页面是否已调入内存

基本分段存储管理

与分页最大的区别就是：离散分配时分配地址空间的基本单位不同
分段（类似于分页管理的分页）：按照自身逻辑关系划分为若干个段，每个段都有一个段名，每段从0开始编址。内存分配时以段为单位进行分配，每个段占据连续内存空间，但各段之间可以不相邻。分段系统的逻辑地址，也分为段号和段内偏移量组成

31…16 15…0
段号段内地址

段表：每个段对应一个段表项，其中记录了该段在内存中的起始位置（基址）和段的长度。而段表寄存器储存着段表始址F和段表长度M，根据这个查询段表，找到对应段表项。

分段分页管理的对比

页是信息的物理单位，对用户不可见。
段是信息的逻辑单位，对用户可见。分段的用户进程地址空间是二维的，既要给出段名，也要给出段内地址。
分段比分页更容易实现信息的共享和保护。不能被修改的代码可以共享，可修改的代码（比如有很多变量，各个进程并发访问可能造成数据不一致）不能共享

分页管理不会产生外碎片不方便共享
分段会产生外碎片

段页式管理方式

31…16 15…12 11…0
段号页号页内偏移量

页内偏移量决定了页面大小！

内存空间的扩充

覆盖技术

思想：程序分为多个段，常用的段常驻内存，然后按照自身逻辑结构，让那些不可能同时被访问的程序段共享同一个覆盖区
已退出历史舞台，对用户不透明，增加了用户编程负担。

交换技术

思想：进程在内存与磁盘间动态调度。
暂时换出外存等待的进程状态为挂起状态（suspend）、挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。

把磁盘空间分为文件区和对换区，文件区追求存储空间利用率，对换区空间占得小，提高IO速度。
内存吃紧时换出进程。如果缺页率明显下降，就可以暂停换出。
可优先换出阻塞进程，可换出优先极低的进程…
（注：PCB会常驻内存，不会换出外存）

覆盖与交换的区别

覆盖是在同一个进程中的，交换是在不同进程之间的

虚拟内存技术

程序不需全部装入即可运行，运行时根据需要动态调入数据，若内存不够还需要换出数据。也需要建立在离散分配的内存管理方式基础上。
区别：访问信息不在内存时，需要请求调页/段，弱内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

请求分页存储管理

请求分页存储管理的页表，比基本页表（页号-内存块号）多了状态位（是否已调入内存）、访问字段（访问过几次/上次访问时间，供换出算法参考）、修改位（调入内存后是否被修改过）、外存地址。
如果访问的页面不在内存，产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，调页完成后再将其唤醒，放回就绪队列。
如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改也表中相应的页表项。
如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，还要写回外存。

缺页中断属于内中断

页面置换算法

缺页中断未必发生页面置换。若还有可用的空闲内存块，就直接分配就好了。当内存空间不够时，由操作系统负责将内存中暂时不用的页换出

最佳置换算法：淘汰在最长时间内不会再被访问的页面
先进先出FIFO：淘汰最早进入内存的页面 Belady异常：分配的物理块数增大，缺页次数反而减少了！
最近最久未使用LRU：淘汰最近最久未使用。实现方法：每个页面对应的页表项中，用访问字段记录自上次被访问以来所经历的时间t。
简单时钟置换算法CLOCK（NRU）：每个页面设置一个访问位：页面通过链接指针链接成一个循环队列，被访问时访问位置置1。当需要淘汰一个页面时，开始扫描，检查页的访问位，如果为1则置0，直到访问到一个访问位为0的页面
改进时钟置换算法：再增加一个修改位，优先淘汰没有被修改过的页面，避免IO操作。第一优先级：最近没访问，且没修改。第二优先级：最近没访问，但修改过的页面。本轮把扫描过的访问位设为0。第三优先级：最近访问过，但没修改的页面。第四优先级：最近访问过，且修改过的页面

页面分配策略

页面分配、置换策略

驻留集：请求分页存储管理中，给进程分配的物理块的集合。采用虚拟存储技术时，大小一般小于进程的总大小。
固定分配+局部置换：分配一定数量物理块，缺页只从进程在内存中的页面换出
可变分配+全局置换：分配动态数量物理块，缺页可以从任意一个未锁定的物理块

何时调入页面？预调入，缺页时才调入
从何处调入页面？外存（磁盘）分为对换区和文件区，对换区采用连续分配方式，读写速度块

抖动（颠簸）现象：刚换出又要换入，刚换入又要换出，原因是分配给进程的物理块不够
工作集：在某段时间间隔里，进程实际访问页面的集合。
驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。