操作系统

两大操作系统会议：（sosp）（usenit）
功能：对上：控制软件（应用程序通过操作系统提供的API（应用程序接口）来使用物理资源）；对下：资源分配器。
组成：cpu调度器；物理内存管理；虚拟内存管理；文件系统管理；中断处理与设备驱动。
特征：并发（一段时间内，多个程序可以运行）；共享；虚拟；异步；

操作系统的启动

硬盘（DISK）：存放OS
BIOS：基本I/o处理系统
bootloader：加载OS

中断异常和系统调用

中断：由外设造成；异常：应用程序意想不到的行为；系统调用：应用程序请求操作提供服务。

硬件

设置标记号：1：将内部，外部事件设置标记号；2：依据事件的ID来找到对应的事件。

软件

（用户态：cpu不能访问特定的指令，内核态：OS能使用任何指令）

中断：1：保存当前处理状态；2：中断服务程序处理；3：清除中断标记；4：恢复之前保存的处理状态。
异常：1：保存现场；2-1：杀死产生异常的程序；2-2：OS弥补服务，重新执行异常指令；3：恢复现场。
系统调用：程序通过高层次API来进行系统调用；1：OS从用户态转换到内核态；（应用程序和OS拥有各自的堆栈）2：OS对系统调用ID号做出标识，完成服务。

计算机体系结构及内存分层体系

计算机体系结构：CPU，内存，设备。
内存：cpu：寄存器，L1缓存，L2缓存；主存；磁盘。
OS管理内存的不同方法：程序重定位；分段；分页；虚拟内存；按需分页虚拟内存。

地址空间与地址生成

逻辑地址空间通过OS访问物理地址空间。
逻辑地址空间生成：应用软件使用指令的逻辑地址，通过cpu里面的mmu表（逻辑地址到物理地址映射表）找到对应的物理地址，过程中OS的作用就是提前建立逻辑地址到物理地址的映射表。OS要确保程序有效访问的地址空间，（地址空间包括：起始地址；长度）

连续物理内存分配

（程序的物理空间是连续的）

内存碎片与分区的动态分配

（内存碎片：内存中不能被利用的空闲空间）

外部碎片：在分配单元之间未使用的内存
内部碎片：在分配单元内未使用的内存

分区的动态分配

OS管理内存的作用：1：OS要在内存中分配一个连续的区域让程序跑起来。2：程序在运行中需要访问数据，这时候OS需要给数据一个连续的内存空间。
OS简单分配方式：首次适配；最优适配；最差适配。
**首次适配算法：**把空闲内存块按地址排序，从0地址开始找，第一个满足地址大小的块就被分配出去了，回收的时候看能不能把相邻的空闲分区合并。（简单，易于产生更大空闲块，但容易产生外碎片）
**最优分配算法：**按空闲块大小排序，分配最适合地址大小的快，回收的时候看能不能把相邻的空闲分区合并。（对分配小尺寸的地址很有效，比较简单，但不利于外部碎片后续的管理）
**最差适配算法：**按空闲块大小排序，分配最大的快，回收的时候看能不能把相邻的空闲分区合并。（对分配中大的快效果最好，后续若有大块则不易分配）
压缩式碎片整理：当程序处于等待状态时，把地址块进行移动，减少外部碎片。
交换式碎片整理：把等待程序的地址块从内存移到磁盘，当等待的程序要运行时，则从磁盘移到内存。

非连续物理内存分配

（程序的物理空间是非连续的，能更好利用内存空间，允许共享，支持动态加载，但开销很大，思考如何建立虚拟地址和物理地址之间的转换需要相应的软件方案和硬件方案。硬件上为了解决开销问题，采用两种方法：分段；分页）

分段？

（一维的逻辑地址：段号（s）：段起始号，段内偏移（addr）：段长度）

段访问机制：方案一：段寄存器+地址寄存器（eg：x86）；方案二：单地址实现方案

分页？

（页是连续的虚拟内存，帧是非连续的物理内存，通过OS建立的页表（页+帧）由逻辑页地址到物理帧地址。页的大小是2的n次幂，每页的大小一样。）
帧地址：帧号+帧偏移
页地址：页号+页偏移
eg：16bit的物理地址空间，每个页帧的大小是9bit（=512byte），某个页帧号是3，页偏移为6，那么可以推出它的物理地址为1542（物理地址：0000011（3）000000110（6）=1542）

虚拟内存

OS利用硬盘来弥补内存空间小。

覆盖技术

把常用代码放内存，不常用代码放硬盘。
程序员把程序划分若干功能相对独立的模块，采用分时方式让一个程序的不同模块使用同一块内存空间。

交换技术

把当前没在跑的程序放在硬盘上。
OS把整个进程的地址导出到硬盘中，把要使用的进程导入内存中。硬盘速度很慢，所以要减少导入导出的频率，所以需要控制好交换区大小。交换技术最好采用动态地址映射的方式。

###虚存技术

覆盖技术和交换技术的结合。
一个程序具的局部性（一个数据的一次访问和下次访问都集中在一个比较短的时间内，当前数据和邻近几个数据都集中在一个较小区域内）

eg：一个页面大小为4k，分配给每个进程的物理页面数为1，在一个进程中，定义了如下的二维数组int A[1024] [1024],该数组按行存放在内存，每一行放在一个页面中。以下为两种方式：

//程序一
for(j=0;j<1024;j++)
for(i=0;i<1024;i++)
	A[i][j]=0;

//程序二
for(i=0;i<1024;i++)
for(j=0;j<1024;j++)
	A[i][j]=0;

由于内存中：
第1页：a0,0 a0,1 a0,2 …a0,1023
第2页：a1,0 a1,1 a1,2 …a1,1023
…
第1024页：a1023,0 a1023,1 a1023,2 …a1023,1023
程序一：那么每次访问都会产生一次缺页中断，总共产生1024x1024次缺页中断
程序二：只产生1024此缺页中断

OS怎么处理缺页中断呢？
OS将外存中对应的页面调入内存中（虚拟内存管理算法实现），使得程序能够继续运行，

虚拟页式内存管理

虚拟页表表项：

驻留位为0，缺页中断处理过程：
1：如果内存中有空闲的物理页面，则分配一个空闲的物理页帧f，转到4，否则转到2.
2：采用页面置换算法，选择一个将被置换的物理页帧f，他所对应的逻辑页为q，如果该页在内存期间被修改过，则需要 需要把它写回外存。
3：对q所对应的页面项进行修改，把驻留位置为0.
4：将需要访问的页p装入到物理页面f中。
5：修改p所对应的页表项的内容，把驻留位置为1，把物理页帧号置为f；
6：重新运行被中断的指令

后备存储（BackingStore）
从硬盘上读出数据

虚拟内存性能
有效存储器访问时间EAT(effective memory access time)=访存时间 * 页表命中几率+处理时间 * 几率

页面置换算法

虚拟内存中发生缺页中断时当前的内存物理页已经满了，则需要替换掉当前内存物理页的某些页面。页面置换算法需要尽可能减少页面换入换出的次数。

最优页面置换算法

**理想：**当发生中断时那一刻计算当前保存在内存中每个逻辑页面，计算下次访问所需要的等待时间，从中选择等待时间最长的那个作为被置换的页面。**现实：**OS无法知道计算下次访问所需要的等待时间（把未来最久不被使用的页面被替换出去）

先进先出算法（FIFO）

（First-in First-out）

选择在内存中驻留时间最长的页面被替换出去。（实现简单，但产生缺页次数很多。）

最近最久未使用算法（LRU）

（Least Recently Used）

选择过去最久未使用的那个页面被替换出去。（开销太大，但效果挺好）
两种方法：链表；堆栈
**链表：**把刚访问的页面作为首结点，最久未使用的页面作为尾结点。每次访问对应的页面时把它从链表中摘下来放到链表之首，每次发生中断时淘汰链表末尾的页面。
**堆栈：**设置一个活动页面栈，把刚访问的页面压入栈顶，然后检查栈内是否有与此页相同的页号，若有则抽出。需要淘汰一个页面时，选择栈底的页面淘汰（也就是最久未使用的）

时钟页面置换算法（Clock）

当一个页面被装入内存中时，把该页访问位初始化为0，然后若这个页面被访问，则把访问位置为1。把全部页面组成环形链表，把指针指向最老页面（最先进来的那个页面）。当发生缺页中断时，考察指针所指向的最老页面。若它访问位为0则立即淘汰；若它访问位为1则把该位置置为0，后把指针向下移动一格，如此下去直到找到被淘汰的页面然后把指针移到它的下一格。

二次机会法

减少写回操作的次数，同时钟页面置换算法类似，但是选择访问位和修改位两个

最不常用算法（LFU）

（Least Frequently Used）

当缺页中断时，选择被访问次数最少的那个页面被替换。
对每个页面设置一个访问计数器，当该页被访问时计数器加一，当中断发生时，淘汰计数值最小的那个页面。

###页面置换算法的讨论

Belady现象

采用先进先出（FIFO）算法时，有时会出现分配的物理页面增加，缺页率反而提高的异常现象。
原因：FIFO算法的置换特征与进程访问内存的动态特征时矛盾的，与置换算法的目的不一致，因此被它置换出去的页面并不一定时进程不会访问的。

替换算法的问题，工作集模型

上面介绍的各种页面置换算法都是基于程序具有局部性原理的前提。
缺页率：缺页次数/内存访问次数；
**工作集：**一个进程当前正在使用的逻辑页面的集合。{ W(t,x) **t:**当前执行时刻；**x：**工作集窗口（定长的页面访问时间窗口；**W(t,x)：在当前时刻t之前的x时间窗口当中的所有页面组成的集合。|W(t,x)|：**工作集大小，即页面数目 }
常驻集：当前时刻，进程实际驻留在内存当中的页面集合。（当工作集所涉及到的页都在常驻集中最好，重叠越少就越会产生更多缺页中断）

工作集页面置换算法：随着程序执行，把不属于工作集窗口的页丢掉。
缺页率页面置换算法：常驻集大小可变（程序运行时，先依据程序大小分配一定数目的物理页面，然后在动态程序运行过程中，动态的调整常驻集的大小）（当缺页率高>增加工作集；当缺页率低>减少工作集；）

抖动问题：分配给一个进程的常驻集小于工作集，那么进程会产生很多缺页中断，需要频繁的在内存和外存之间替换页面，那么把这种状态成为“抖动”。（抖动会使进程的运行速度变得很慢）
（当打开的应用程序很多时，OS会变得很卡。所以OS要找到缺页平均时间几乎等于缺页服务时间的这一点）

进程

**定义：**一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程（程序是静态的有序代码的集合。进程是动态的程序的执行。进程有核心态/用户态），进程=管理资源（进程的主要作用）+线程
特点：动态性（可动态的创建结束进程）；并发性（可独立调度并占用处理机运行）;独立性（不同进程的工作不相互影响）；制约性（因访问共享数据/资源或进程同步而产生制约）

进程控制结构

进程控制块：OS管理控制进程运行所用的信息集合。OS用pcb来描述进程的基本情况以及运行变化的过程，pcb是进程存在的唯一标志。

pcb=进程标识信息（本进程的标识）+处理机状态信息保存区（保存进程的运行现场信息）+进程控制信息
{进程标识信息：父进程标识；用户标识。
处理状态信息保存区：用户可见寄存器（用户程序可以使用的数据，地址等寄存器）；控制和状态寄存器（程序计数器 （PC），程序状态字（PSW））；栈指针（过程调用/系统调用/中断处理和返回时需要用到它）；
进程控制信息：调度和状态信息（操作系统调度进程并占用处理机使用）；进程间通信信息（支持进程间的通信相关的各 种标识，信号，信件等。这些信息存在接收方的进程控制块中；）存储管理信息（包含有指向本进程映像存储 空间的数据结构）；进程所用资源（由进程打开，使用的系统资源，如打开的文件等）；有关数据结构连接幸 喜（进程可以连接到一个进程队列中，或连接到相关的其他进程的pcb）}
pcb的组织方式：链表（同状态进程的pcb成链表，多个状态对应多个不同链表）；索引表（同状态进程归入一个index表 （由index指向pcb），多个状态对应多个index表）

进程的生命周期原理

进程生命周期：进程创建，进程运行，进程等待，进程唤醒，进程结束
进程创建：系统初始化时（OS初始创建一个MIT进程，这个进程负责创建其他进程）；用户请求创建新进程；正在运行 的进程执行创建进程的系统调用。
进程运行：内核选择一个就绪进程，让它占用处理及并执行
进程等待：eg：1，请求并等待系统服务，无法马上完成；2.启动某种操作，无法马上完成；3，需要的数据没有到达。 (进程只能自己阻塞自己，因为只有进程自身知道何时等待的事情发生)
进程唤醒：eg：被阻塞进程需要的资源可被满足；被阻塞进程等待的事件到达；将该进程的pcb插入到就绪队列。（进程 只能被别的进程或者操作系统唤醒）
进程结束：eg：正常退出（自愿）；错误退出（自愿）；致命错误（强制）；被其他进程所杀（强制）；

进程状态变化模型：创建状态；运行状态；就绪状态；等待状态；结束状态；

进程挂起

定义：进程没有占用内存空间，处于挂起状态的进程映像在硬盘上。
挂起状态：阻塞挂起状态（进程在外存并等待某事件的出现）；就绪挂起状态（进程在外存，但只要进入内存即可运 行）；
挂起的几种情况：1，阻塞到阻塞挂起：提交新进程或运行就绪进程
2，就绪到就绪挂起：当高优先级阻塞和低优先就绪进程时，系统选择挂起低优先就绪进程。
3，运行到就绪挂起：对抢先式分时系统，当有高优先阻塞挂起进程进入就绪挂起时，OS可能把运行进 程转到就绪挂起状态。
解挂/激活：把进程从外存转到内存：就绪挂起到就绪（没有就绪进程或挂起就绪进程优先级高于就绪进程时）；阻塞挂起到阻塞（进程释放足够内存时，系统会把一个高优先级阻塞挂起进程转为阻塞进程）

状态队列：由OS来维护一组队列，用来表示系统当中所有进程的当前状态。不同的状态用不同队列来表示，每个进程pcb都根据它的状态加入相应的队列中，当进程状态发生变化时，他的pcb从一个状态中脱离出来，加入另外一个队列。

线程

进程当中的一条流程，一个进程可以同时存在多个线程，各个线程之间可以并发执行和共享地址空间和文件等资源。当一个线程崩溃会导致所属进程的所有线程都崩溃。
线程的实现：用户线程（OS看不到的线程，在用户空间实现）；内核线程（OS管理的线程，在内核中实现）；轻量级线 程（在内核中实现，支持用户线程）；
轻量级进程：内核支持的用户线程，一个进程可以有一个或者多个轻量级进程，每个轻量级进程由一个单独的内核线程来支持。

进程控制？

**上下文切换：**当前进程从运行状态改变成其他状态（不同进程共享cpu资源，不同进程之间切换时需要占用cpu资源）

创建进程

加载和执行进程

等待和终止进程

调度算法

选择哪个进程在某个时候占用cpu资源
调度原则：cpu使用率（cpu“忙”状态所占时间的百分比）；吞吐量（单位时间内完成的进程数量）；周转时间（进程从初始化到结束所花费的时间）；等待时间（进程在就绪队列中的总时间）；响应时间（请求从被提交到响应的时间）。

通用调度算法（二？）

FCFS(first come first served)：先来先服务
SRT(shortest process next (shortest job first) shortest remaining time)：短进程优先（短作业优先）短剩余时间优先）：最优平均等待时间
HRRN(highest response ratio next)：最高响应比优先：R=(w+s)/s *w：等待时间 s：执行时间
RoundRobin：轮循：
MultilevelFeedbackQuenes：多级反馈队列
FairShareScheduling：公平共享调度

实时调度

某些任务必须在规定的时间内完成，eg：工业控制
RM(rate monotonic)速率单调调度：人物的优先级在程序执行前就确定了。
EDF(earliest deadline first)最早期限调度：任务优先级会动态调整，任务离deadline最短优先级越高

多处理器调度

优先级反转>1：优先级继承；2：优先级天花板

同步

临界区：进程中需要访问共享资源的那段代码
互斥：某时刻只允许一个进程的临界区访问共享资源时
死锁：两个或以上的进程，在相互等待，而无法将任务进行下去
饥饿：一个可执行的程序处于永远等待的状态

临界区

互斥：同一时间临界区最多存在一个线程
progress（前进）：一个线程想进入临界区，那么最终回成功
有限等待
无忙等待（可选）：如果一个进程等待进入临界区，那么在它可以进入之前会被挂起

禁用硬件等待?

基于软件的解决方案?

基于硬件的原子操作的高层抽象？

信号量和管程

信号量：初始化一般为大于0的整数，p减1；v加1；
管程：包含了一系列的共享变量以及针对这些变量的操作函数的模块。

经典同步问题