操作系统课程学习

本文主要是操作系统的一些学习笔记。

第一章 操作系统概述

操作系统是控制软件，管理应用程序，限制软件资源，杀死应用程序。

资源管理，外设管理，资源分配。

层次在硬件之上，应用程序之下。

组件包括：CPU调度，物理内存管理，虚拟内存管理，文件系统管理，中断处理和设备驱动。

Kernel特征：

• 并发：一段时间内多个程序运行。 并行：一个时间点运行多个程序。
• 共享资源，给不同的应用程序。同时访问，互斥共享。
• 虚拟：多道程序设计技术，每个用户都觉得计算机专门服务。
• 异步：程序执行走走停停，但运行环境相同，OS保证运行结果相同。

微内核：只把最基础服务放入内核，其他服务放入用户态。

外核：由应用程序而不是操作系统管理硬件资源。

VMM：虚拟机监视器，跑在传统OS之下，虚拟出整个计算机，包含各种外设。因硬件资源过剩而诞生。

第二章 操作系统基础操作

启动

DISK存放OS。

BIOS基本IO系统，让计算机启动后检测各种外设。检测完成后才能完成加载响应软件。

Bootloader：加载OS。

BIOS加典后从特定地址（x86 CS:IP = 0xf000:fff0 CS段寄存器 IP指令寄存器）加载bootloader。

BIOS加电后先POST加电自检，寻找显卡和执行BIOS。

然后从硬盘上加载Bootloader，在硬盘第一个引导扇区512KB。主要功能把OS从硬盘加载到内存。

x86上，将bootloader从引导扇区加载到0x7c00。CPU控制权交给bootloader。

bootloader：找到硬盘扇区，了解os长度，加载到内存。完成后跳到os起始地址，控制权交给os。

中断 异常 系统调用

操作系统：系统调用，异常，中断。

系统调用：主动向操作系统发出服务请求。

异常：非法指令或者坏的处理状态。

中断：来自外设，计时器或网络的中断。

内核是被信任的第三方，只有OS可以执行特权指令。

三者源头不同，处理时间不同。

中断异步，异常同步，系统调用异步或者同步。

响应：中断对应用程序不可见，异常会杀死应用程序或者重新执行。系统调用会等待和持续。

首先要知道中断或者异常是谁产生的。收到中断后查找中断表，保留现场，转到目标地址。

硬件需要设置各种事件中断标记，提供中断ID。

软件需要保存处理现场，处理中断服务，清除中断标记，重新执行服务。

异常也有异常编号，然后处理异常（杀死或重新执行），然后恢复现场。

系统调用：程序访问高层次API而非系统调用。如WIN32-API POSIX-API Java-API（非系统调用，而是JVM）。

系统调用需要维护序号，建立索引，系统调用接口进行调用，返回系统调用的状态以及其他返回值。用户不需要知道系统调用如何实现。

用户态：特权级低，无法访问特殊指令。内核态：可以执行任何指令。

应用程序和操作系统存在各自的堆栈，有转换的开销。

内核核心转换的开销：找到中断/异常/系统调用，并初始化开销。建立堆栈开销。验证参数的开销，内核态映射到用户态的地址空间的开销，需要更新页面映射权限。内核态有着自己独立的地址空间。内存拷贝存在开销。

第三章 连续内存分配

层次

计算机主要结构有CPU 内存 外设。

内存有层次结构，操作系统无法更改L1 L2这些CPU的cache。

管理目标：

• 抽象：不用考虑物理内存，置用逻辑地址空间。

• 保护：独立地址空间。

• 共享：访问相同内存。

• 虚拟化：有着更多的地址空间。

管理内存不同方法：程序重定位，分段，分页，虚拟内存，按需分页虚拟内存。

操作系统依赖硬件，如MMU。

地址空间 地址生成

物理地址空间：硬件支持的地址空间。

逻辑地址空间：一个运行的程序所拥有的内存范围。

运行程序对程序而言地址仍然是逻辑地址。有映射关系。

MMU用来表示映射关系。

操作系统需要确保地址合法，找到界限寄存器，保证是否小于目标界限，否则产生异常。

连续内存分配

外碎片：分配单元之间无法使用的内存。

内碎片：分配单元内无法使用的内存。

fist fit/best fit/worst fit/

压缩式碎片整理：调整位置，把程序挪到一些挨紧，开销大不大。

交换式：把硬盘当作内存后备，抢占等待的程序并回收内存，交换到硬盘。

第四章 非连续内存分配

分段，分页，页表。

非连续分配优点：物理地址空间非连续，更好的内存利用和管理，允许共享代码和数据，允许动态加载动态链接。

缺点：开销大，软件或硬件转换虚拟地址-物理地址。

硬件方法：分段分页。

分段

分离和共享，将不同的段分散到不同的物理地址空间，如堆，栈，数据，text段。

分段寻址方案：访问内存需要段号和段内偏移，这俩可以放在两个寄存器，也可以放在单一地方。

段有段表，由操作系统建立，存逻辑段号和物理段号映射。

先检测Limit，再加上偏移形成物理地址。

分页

段尺寸可变，页大小不变。页划分物理内存到固定的大小，2的幂。frame表示物理，page表示逻辑。

MMU和TLB转换逻辑地址到物理地址。

帧包含帧号（f 有2eF个帧）和帧内偏移（S位）（f,o) ，得出物理地址2eS×f + o。

页与帧计算类似，但页号和帧号大小不一定对应。

页表

大数组。先查询flag，访问不存在的页时候会缺页异常，否则查到页号对应帧号。

存在问题，访问一个内存单元需要两次内存访问。页表可能非常大。

解决方法：缓存。间接访问，多级页表。

TLB：缓存近期访问的页帧转换表项。快表，在CPU中。页表存在内存中，会慢。

多级页表，对大地址寻址可以变成多级寻址。使得某一些不存在关系的数据不需要占用内存。

大地址空间问题：映射变得繁琐，让页表与物理地址空间相对应，而非逻辑地址空间大小相对应。

页寄存器：根据物理帧号对应页号。空间小，但双对应关系要更新。

可以使用关联存储，但关联存储硬件成本大。难以在单个时钟周期内完成。耗电。

可以使用哈希计算，可以硬件加速。查找时候可能碰撞，还需要类似TLB加速。

第五章 虚拟内存

起因

更多的程序能跑在有限的内存内。软件增长速度比内存增长速度快。

有手动的覆盖技术，自动的交换技术和自动的虚拟存储技术。

覆盖技术

在比较小的内存中运行比较大的程序。将程序根据逻辑分类，划分为必要部分和可选部分。必要不放呢常驻内存，可选部分必要时候才装入内存，不存在调用关系的模块不必要同时装入内存，因此相互覆盖，共用分区。

交换技术

将暂时不能运行的程序送到外存，获得空闲内存。

需要考虑什么时候交换，只有不够且危险的时候交换。考虑交换区域的大小，能够够大。需要重定位，因此要动态地址映射。

虚存技术

目标：像覆盖技术一样，只把一部分放在内存中，从而运行比当前空闲内存还要大的程序。由操作系统自动完成。像交换技术一样，导出导入存储空间，获得更多空闲内存空间，但做得更好，只对进程部分进行交换。

程序需要有局部性。样例（二维数组遍历，缺页率问题）。

基本特征：

• 空间大，通过硬盘补充。
• 部分交换
• 不连续性

虚拟页式内存管理：将部分放入内存，如果不存在则发送缺页异常，从外存中调入内存。

需要在虚拟页表表项增加表项，如驻留位（在内存还是外存），保护位（能否访问，如只读），修改位（该页是否被写过，那么和在硬盘中内存数据不一样），访问位（用于置换算法）。

缺页中断：找空闲空间，如果没有则执行页面置换算法，选择页面，如果修改过则写入外存，没写过就抛弃，然后修改页表表项，之后将对应页写入到物理页面f中，修改驻留位，回到被中断的指令。

如何保存未被映射的页：能够简单识别在二级存储器中的页，或者用交换空间，用于存储未被映射的页面。

后备存储：虚拟地址空间页面可以被映射到一个文件某个位置，有代码段，动态链接段，其他段。

性能评估：访存时间×页表命中几率+缺页处理时间×缺页几率。

第六章 页面置换算法

功能：选择页面被置换。

页面锁定：标志锁定位，不去管。

最优页面置换：基本思路，计算在它下一次访问之前，还需要等待多少时间。用模拟器跑一遍来换。

FIFO算法：驻留最长的页面淘汰。维护链表。性能较差，调出的可能是经常要访问的页面。会有belady现象

Belady现象：使用FIFO时候，分配的物理页面增多，缺页率反而提高。算法没有考虑动态特征。

LRU：最久未被使用。开销较大。

Clock页面置换算法：LRU的近似，对FIFO的改进。环形链表，从最老的页面开始访问，如果访问位是0则置换，如果访问位是1则置为0，并且继续。

二次机会法：脏页替换代价很大，需要修改clock算法，基于修改位和访问位，减少写回的次数。第一次把两个0的换回去，把01和10会变成00，第二次再换。

最不常用算法：LFU，算频率淘汰。

LRU算法符合栈算法特性，FIFO不符合，所以会有Belady算法。

全局页面置换算法：根据不同的页面算法扩展页容量。

工作集模型能用来表示局部性。

工作集：当前正在使用的逻辑页面的集合，参数为时间和窗口长度。

常驻集：进程实际驻留再内存中的页面集合。

我们希望这两个集合尽量交叉。当常驻集大小达到某个数目，分配过多物理页面缺页率也不会明显下降。

只要不属于工作集替换算法，就不保留，即使不缺页。

根据缺页率动态调整页缺失。

OS需要选择合适的常驻集，来防止抖动。

第七章 进程管理

进程：一个具有一定独立功能的程序在一个数据集合上的一次动态执行的过程。

进程组成：代码，数据，PC计数器，寄存器，堆栈，系统资源如打开的文件。

程序是产生进程的基础，程序可以多次运行，进程是程序功能的体现，一个程序可对应多个进程，通过调用一个进程也可以包括多个程序。

进程有核心态和用户态区别。

进程可动态创建，结束，可以并发，独立性，制约性（资源抢占）

进程控制块：管理控制进程所用的信息集合。包含进程标识信息（本进程标识，产生者标识，用户标识），处理机状态信息保存区（保存进程运行现场，包括数据，地址，PC，状态，栈指针），进程控制信息（调度和状态信息，进程间通信信息，存储管理信息，进程所用资源，有关数据结构链接信息。）

控制块一般用链表来组织，可以动态删除动态创建。

进程状态：进程创建，进程运行，进程等待，进程唤醒，进程结束。

创建：系统初始化时候，用户请求创建新进程，正在运行的进程执行了创建进程的系统调用。

进程运行：让操作系统选择就绪进程，需要调度。

进程等待（阻塞）：系统服务无法马上完成，操作无法马上完成，需要的数据没有到达。进程只能自己阻塞自己，因为只有自己才知道合适需要等待事件发生。

进程唤醒：被阻塞进程资源可满足，等待事件到达，PCB被加入就绪队列。进程只能被OS或其他进程唤醒。

进程结束：正常，错误，致命错误（强制），被其他进程所杀（强制）。

基本状态：运行，就绪，等待。阻塞在事件发生能变到就绪，就绪在被调度能到运行，运行在时间调度后转到就绪，运行在缺少资源后阻塞。

进程不占内存空间 称为进程挂起

挂起:
阻塞挂起状态 -等待事件出现

就绪挂起-只要进入内存，就能运行

阻塞到阻塞挂起:请求更多内存资源时候，会进行这种转换

就绪到就绪挂起:高优先级阻塞进程和低优先级就绪进程，会挂起低优先级就绪进程

运行到运行挂起:高优先级进程因为事件出现而进入就绪挂起，可能转到挂起状态

阻塞挂起可能转换为就绪挂起，但全在外存上，仅仅变了状态

就绪挂起到就绪:没有就绪进程或者挂起进程优先级高于就绪进程

阻塞挂起到阻塞:当一个进程释放足够内存，会把高优先级阻塞挂起进程放进内存

操作系统需要维护一组队列，来表示系统当中所有进程的当前状态

不同状态用不同队列管理 就绪队列 挂起队列

状态变化之后，从队列出来放进另一个队列

线程 独立运行的基本单位 并发执行并且共享地址空间

进程执行功能交给线程管理

一个线程崩溃，所有线程崩溃。

进程创建需要一些管理信息，进程可以直接重用

属于同一进程的线程有着一样的地址空间，切换线程很快，不需要切换页表。

同一进程共享资源，不需要通过内核通信。

用户线程:操作系统看不到的线程，由用户线程库来管理

内核线程:操作系统看得到，由操作系统管理

用户线程:在库中实现线程控制块，不依赖内核，由函数完成创建 终止 同步 调度 操作系统无法管理。有自定义算法，不需要用户态核心态转换

缺点:如果一个线程发起系统调用，整个进程都会等待。除非主动交出CPU使用权，否则其他线程无法运行。多线程时间片分得少。

内核线程:有操作系统完成内核创建，终止和实现，由内核维护进程和线程上下文，如windows。切换开销大。

轻量级进程:

内核支持的用户线程，一个进程可以有一个或者多个轻量级进程。

上下文切换:CPU状态，寄存器，栈指针等寄存器

fork之后返回俩返回值，exec加载程序取代当前进程，堆栈都会覆盖

fork开销高，exec后开销更高，因为fork需要拷贝内存信息，子进程可能关闭打开的文件和连接。

可以用vfork。也可以通过虚存管理COW，来实现。并不真实复制。

wait等待子进程结束，当子进程exit时候wait等待。当exit虽然无法在用户空间执行，父进程wait帮助释放子进程。

进程结束后调用exit，将结果作为参数，关闭所有文件，连接，释放内存，释放大部分操作系统结构，检查父进程是否存活(如果是，则进入僵尸状态，会保留结果。如果不是，则释放所有，进程死亡)

进程终止是最终的垃圾收集。

第八章 cpu调度

选择进程，调度程序，什么时候调度。

调度条件:运行切换到等待，或者被终结

不可抢占:必须等待事件结束

可抢占:调度程序在中断被响应后执行，从运行切换到就绪，从等待切换到就绪，可以被换出。

执行模型：程序在CPU突发和IO中交替，CPU繁忙还是IO繁忙。CPU占用率波动。

调度算法：CPU占用率（CPU忙的时间比），吞吐量（单位时间完成的进程熟练），周转时间（一个进程从初始化到结束，包括等待时间的所有时间，等待时间（就绪队列中的总时间），响应时间（响应花费的总时间）

更快：高带宽，低延迟。

减少响应时间（输出尽快提供），减少平均响应时间波动（可预测性更重要），增加吞吐量（开销减少，系统资源高效利用），减少等待时间。

低延迟增加交互，高吞吐量保证效率。

FCFS先来先服务。简单，但时间波动较大，花费时间少的任务可能排在花费时间长的前面，IO和CPU之间可能重叠。

短任务优先：不可抢占（短任务到来之后不管，塞最前面），抢占（短任务来的时候调度）。

有最优平均等待时间，连续短任务可能会让长任务饥饿，短任务可用时候任何长任务CPU时间会增加平均等待时间。需要知道进程的执行时间，需要预知未来。

可以用公式预估进程执行时间。

最高相应比优先：考虑等待时间，防止无限期延迟。

轮询：让进程轮流占CPU，设置时间片。时间片设置困难，经验：维持上下文切换开销处于1%。

多级队列，不同队列用不同调度算法。前台轮询，后台FCFS之类的。

多级反馈队列，时间片随优先级别增加而增加，如果没有完成则降低优先级。IO密集型会很快执行，CPU密集型则优先级下降很快。

公平共享服务FFS：一些用户组比其他用户更重要，保证不重复的组无法垄断资源。

实时调度（面向实时系统），正确性依赖于时间和功能的OS。

强实时系统（必须完成），弱实时系统（尽量完成）。

多处理器调度：需要负载均衡。

优先级反转：环境强制高优先级

第九章 同步

进程相对独立，则执行十确定的。不独立且不可重现，意味着bug可能间歇性发生。

临界区：访问共享资源的代码称为临界区。

互斥：没有多个资源访问临界区域。

死锁：都无法进行下去

饥饿：无限等待

进入临界区aquire锁，离开临界区release。

进入临界区禁用中断，离开临界区开启中断。但外部事件可能无法及时响应。临界区执行长短也无法确定。

基于软件：进入临界区

当硬件可以用原子操作，可以抽象硬件。

test and set：读取值，测试值是否为1，返回值且设置为1。

交换：交换两个内存里的值。

上述2个机器指令不允许被打断。

//忙等待
void acquire(){
    while(test_and_set(value)){
    spin();
	}
}
void release(){
    value = 0;
}

无忙等待：spin时候加入队列，release时候取出队列。

第十章 信号量与管程

信号量：p(): sem-1 除非sem<0 v(): sem+1 如果sem<=0则唤醒一个p。

信号量是整数，被保护（只能被p，v操作），p能阻塞，v不会。信号量是公平的。

有二进制信号量和整数信号量，给定一个可以实现另一个。

信号量可以实现同步，线程的执行需要另一个线程提供的结果，初始化为0，实现调度约束。

生产消费者模型：任何时间只能有一个线程操作缓冲区，缓冲区为空，消费者必须等待生产者。缓冲区满，生产者必须等待消费者。

每个约束都需要单独的信号量。