- 操作系统是一个控制软件，管理应用程序，为应用程序提供服务，杀死应用程序，资源管理，管理外设/分配资源
- 操作系统是资源管理器，应用程序与硬件中间层，管理计算机软硬件资源，提供访问软硬件的高效手段，解决资源访问冲突，确保资源公平使用
——————-------操作系统---- |\ 抽象/虚拟化能力 硬件之上，应用程序之下 应用软件：办公，视频播放等软件 操作系统位于应用软件之下，为应用软件提供服务支撑 内核由负责响应中断的中断服务程序，管理多个进程从而分享处理器时间的调度程序，负责管理进程地址空间的内存管理程序和网络，进程间通信的系统服务程序共同完成
并发：计算机系统中同时存在多个应用程序，需要OS管理调度。并行是指在同一个时间点上有多个应用程序，需要多核，并发是在一段时间内有多个应用程序，不一定是多核 共享：同时访问，一块内存单元划分了两个独立空间，可以同时访问，同一个时间点，一个程序只能访问一个内存单元。 虚拟：利用多到程序设计，让每个用户都觉得有一个计算机专门为他服务
程序的执行不是一贯到底，而是走走停停，向前推进速度不可预知 但只要运行环境相同，OS需要保证程序运行的结果也要想通
内核独立于普通程序，一般处于系统态，拥有受保护的内存空间和访问硬件设备的所有权限，这种系统态和被保护起来的空间，叫做内核空间，应用程序在用户空间执行，只能看到自己被允许的部分系统资源，只能使用某些特定的系统功能，当内核运行时，系统以内核态进入内和空间，当一个普通程序运行，系统以用户态进入用户空间执行 应用程序1 应用程序2 内核子系统 设备驱动程序 内和空间
但一个应用程序执行一条系统调用接口，内核带其执行，应用程序被称为通过系统调用在内和空间执行，内核被称为运行于进程上下文空间中，内核还负责管理系统硬件设备，当硬件设备想和系统通信，首先要发出一个异步中断信号打断处理器执行，继而打断内核执行，中断对应一个终端号，内核通过终端号找到中断服务程序，并调用这个程序响应和处理中断
可执行代码从一个可执行文件载入到进程的地址空间，一般程序在用户空间执行，但当一个程序执行了系统调用或触发了某个异常，就陷入内核空间，称内核代表进程执行并处于进程上下文中 每个处理器在任何时间点的活动，为下面三个活动之一 运行于用户空间，执行用户进程 运行于内和空间，处于进程上下文，代表某个特定进程执行 运行于内核空间，处于中断上下文，与任何进程无关，处理某个特定的中断
简单操作系统：MS-DOS（81-94）不分模块的单体内核 容易被攻击 不易扩展 单内核架构：内核从整体上作为一个单独的大过程来实现，业运行在一个单独的地址空间，内核通常以单个静态二进制文件的形式存放于磁盘中
微内核架构：微内核功能被划分为独立的过程，每个过程叫做一个服务器，只有强烈请求特权服务的服务器才运行在特权模式下，其他服务器都运行在用户空间，所有的服务器都在各自的地址空间，不能像单模块那样直接调用函数，采用进程间通信（IPC）机制服务器来互换消息，互换服务 VMM(虚拟机监视器) VM0 VM1 VMn （VMs）每台VM都是一台完整的计算机 多操作系统共享硬件资源 虚拟机监视器
VMM 也称为管理程序 平台硬件 （内存 处理器 I/O设备） BIOS：基本的I/O处理系统 POST：加电自检 寻找显卡和执行BIOS 2. Bootloader 将OS的代码和数据从硬盘加载到内存中，在跳转到OS的起始地址，接下来CPU控制权交给OS OS:OS初始化，创建启动程序，响应中断/异常/系统调用 -> 程序：执行各种功能
检测系统中内存和显卡等关键部位的存在和工作状态 查找并执行显卡等接口卡BIOS，进行设备初始化 执行系统BIOS，进行系统检测 更新CMOS中的扩展系统配置数据ESCD 按指定启动顺序从软盘，硬盘或光驱启动 初始态是16位实模式，CS:IP 16位寄存器，指令指针PC=16*CS+ip，最大地址空间1MB
加载程序（bootloader）:加载程序：从文件系统读取启动配置信息->启动菜单：可选的操作系统内核列表和加载参数 -> 操作系统内核：依据配置加载，制定内核并跳，转到内核执行
# 为什么需要中断，异常和系统调用
在计算机运行中，内核是被信任的第三方，只有内核可以执行特权命令，方便应用程序
# 中断和异常希望解决的问题
当外设连接计算机时，会出现什么现象，当应用程序处理意外情况时，会出现什么现象
# 系统调用希望解决的问题
用户应用程序是如何得到系统服务
系统调用和功能调用有何不同
应用程序主动向操作系统发出服务请求
非法指令或者其他坏的处理状态（内存出错）
异常进一步分类为故障（Fault），陷阱（Trap），终止（abort）
来自不同的硬件设备的计时器和网络的中断
在计算机运行中，内核是被信任的第三方，只有内核可以执行特权指令，为了方便应用程序，提供统一的接口调用
中断：来源于外设 键盘 鼠标 网卡网络包事件 声卡 显卡
异常：应用程序意想不到的行为
系统调用 sys call：应用程序请求操作提供服务 主动请求 读写文件 开关文件 发送网络包
系统调用：异步或同步 应用程序发出请求后去干其他事情，等执行完了OS告诉他执行完了，发出命令时刻同步，接收到返回是异步
中断：持续，对用户应用程序是透明的，不会影响应用
异常：杀死或重新执行意外的应用程序指令
中断是外设的事件，异常是内部CPU的事件
中断和异常迫使CPU访问一些被中断和一场服务访问的功能
设置中断标记（CPU初始化时设置中断使能标志） 将内部外部事件设置中断标记（判断是哪些进程导致的中断），中断事件ID，指程序访问的中断向量地址，依据中断向量
保留现场 保存当前处理的状态（时间点 现场） CPU+编译器
中断服务程序处理 根据中断标记找到对应的程序进行处理 服务历程
清楚中断标记 服务历程
现场恢复 恢复之前保存的处理状态 CPU+编译器
标准C库 ———————————— 程序访问主要是通过高层次的API接口而不是直接进行系统调用 通常情况下，与每个系统调用相关的序号， 系统调用接口根据这些序号来维护表的索引 系统调用接口调用内核态中预期的系统调用， 并返回系统调用的状态和其他返回值 用户不需要知道系统调用如何实现， 只需要获取到API和了解操作系统将作为什么返回结果
操作系统接口的细节大部分都隐藏在API中，通过运行程序支持的库来管理（用包含编译器的库来创建函数集） 用户态：应用程序在执行的过程中，CPU所处于特权级的某种状态，该状态特权级很低，不能访问很多特殊的机器指令和IO 内核态：。。。，在该状态下，CPU可以执行任何一条指令，包括特权指令，IO指令等 系统调用时，有用户态向内核态转化，引用程序传参给系统调用，CPU切到内核中，来完成具体的服务 #
系统调用与函数调用的区别 系统调用：INT和IRET指令用于系统调用 系统调用时，堆栈切换和特权级切换 函数调用：CALL和RET用于常规调用 常规调用时没有堆栈切换 # 跨越操作系统边界的开销 在执行时间上的开销超过程序调用 建立中断/异常/系统调用号与对应服务例程映射关系的初始化开销 内核态映射到用户态的地址空间，内存拷贝，更新页面映射权限 内核态独立地址空间：TLB
计算机体系结构/内存分层体系
# 计算机基本硬件结构
程序执行在这 当执行程序和数据驻留在这
存储管理单元 MMU 主存 快 1.3GHz 容量大 速度慢一些 掉电后数据小时 应用
|/ 交换/分页 5ms 寻道时间 操作系统
磁盘（虚拟内存） 慢 数据
虚拟化：更多的地址空间
0
# OS中内存管理方式
LINUX 采用按需页式虚拟存储
与计算机存储架构紧密耦合
MMU：处理CPU存储访问请求的硬件
# 地址空间 地址生成
物理地址空间：硬件支持的地址空间，起始地址0到地址MAXsys 主存 硬盘 地址
逻辑地址空间：一个运行程序多拥有的内存范围 0 - MAXprop
逻辑地址生成 函数库 函数库
编译 汇编 链接 程序加载（重定位）
编译时：假设起始地址已知，如果起始地址改变，必须重新编译
加载时：如果编译时起始地址未知，编译器需生成可重定位的代码（relocated code）
执行时：执行代码可移动，需地址转换（映射）硬件支持
CPU: 1. 运算器需要知道内存内容的逻辑地址 ALU要知道指令的内容，即逻辑地址
2. 内存管理单元MMU寻找在逻辑地址和物理地址之间的映射 MMU查映射表，没有就去内存中MAP找
3. 控制器从总线发出请求对应物理地址的内存内容的请求
4. 内存发送对应物理地址的内容给CPU
5. 建立逻辑地址和物理地址之间的映射 放在内存中 由CPU进行缓存 加快访问过程
-> 内存接受物理地址
逻辑地址空间 段长度寄存器 段基址寄存器
操作系统 设置起始base和最大limit
连续内存分配：给进程分配一块不小于制定大小的连续的物理内存区域
内存碎片：空闲内存不能被利用
外部碎片：分配单元之间的未被使用内存
内部碎片：分配单元内部的未被使用的内存
取决于分配单元大小是否要调整
进程空间 P2 地址空间
进程空间 P1 地址空间
当程序被加载执行时，分配一个进程制定大小可变的分区（块，内存块）
OS需要维护的数据结构：
所有进程已分配分区，空闲分区（Empty-blocks）
- 为了分配400字节，就放在此处
1k bytes 空闲块 - 为了分配n字节，使用第一个比n字节大的可用空闲块
需求： 按地址排序的空闲块列表
分配需要寻找一个合适的分区
重分配需要检查，看是否自由分区能合并于相邻的空闲分区（若有）
优势：简单，易于产生更大的空闲块，因为找到第一个合适的就返回，不会影响后面的，向着地址空间的结尾
劣势：产生外部碎片，第一次找到一个返回，下一次又找到下一个返回
- 为了分配n字节，查找并使用不小于n的最小空闲分区
为了最小化外部碎片产生的尺寸
需求： 按尺寸排列的空闲块列表 大小排序
分配需要寻找一个合适的分区
重分配需要搜索和合并与相邻的空闲分区
优势：当大部分分配是小尺寸时非常有效，比较简单
劣势：产生外部碎片，重分配慢，已产生很多无用的细小碎片
占用快 分配n字节，使用尺寸不小于n的最大空闲分区
为了避免有太多微小的碎片
需求：按尺寸排列的空闲块列表
分配很快（获得最大分区）
重分配需要合并于相邻的空闲分区，然后调整空闲块列表
优势：分配是中等尺寸的最好
劣势：重分配慢，外部碎片，易于破碎大的空闲块以至于大分区无法被分配
碎片整理：通过调整进程占用的分区位置来减少或避免分区碎片
碎片紧凑：通过移动分配给进程的内存分区以合并外部碎片
条件：所有的应用程序可动态重定位
解决什么问题：什么时候移动 程序运行时不行 移动地址可能就找不到了
开销 频繁操作内存 拷贝 开销很大
通过抢占并回收处于等待状态的分区，以增大可用内存空间
P3 运行 P3 需要更大的内存 就可以吧P4的三个内存抢占过来，而先把P4放到硬盘里区
当P4需要执行的时候，也许P3已经不需要这么多内存，就再把P4拷到内存中来
主存 磁盘（虚拟内存）
问题：哪些程序进行交换 如果程序大 换入换出的开销也很大
# 连续分配内存的问题
分配给一个程序的物理内存是连续的
有外碎片，内碎片的问题
一个程序的物理地址空间是非连续的
允许共享代码与数据（共享库。。）
支持动态加载和动态链接
如何建立虚拟地址与物理地址的转换，软硬件方案，纯软件开销很大
进程的段地址空间由多个段组成 主代码段，子模块代码段，公用库代码段，堆栈段（stack），堆数据（heap），初始化数据段，符号表 段式存储管理的目的：更细粒度和灵活的分离与共享 逻辑地址空间 物理地址空间 # 段地址空间逻辑视图 1 1 映射到物理空间的位置和大小都不一样 段：表示访问方式和存储数据等属性都相同的一段地址空间 若干个段组成进程逻辑地址空间
段寄存器+地址寄存器实现方案 x86 单地址实现方案 |/ 看内存长度是否合法 段号 偏移 | 否 是 查段表 段长度寄存器 段基址寄存器 把物理地址空间划分为大小相同的基本分配单元 页面（页，逻辑页面，page） 把逻辑地址空间划分为相同大小的基本分配单位 逻辑地址到物理地址的转换 物理内存大小被划分为大小相同的帧 内存物理地址的表示：二元组(f, o)
f-帧号（F位，共有2^F个帧）2的n次方 基本单元 o-帧内偏移（S位，每帧有2^S字节） f | (f, o) 物理地址 ————f—|————o——————— # 基于页帧的物理地址计算 进程逻辑地址空间被划分为大小相等的页 页面偏移=帧内偏移 通常页号大小不等于帧号大小 进程逻辑地址表示：二元组(p,o) p-页号（P位，2^p个页） o-页内偏移(s位，每页有2^s字节) #
页式存储中的地址映射 - | - | 物理地址空间是不连续的 (p1,o1) | / | 不是所有的页都有对应的帧（还可能在虚拟内存中） | | 页表保存了逻辑地址-物理地址 逻辑地址空间 页表基址 每个运行的程序，进程都有一个页表 属于程序的运行状态，会动态变化 PTBR：页表基址寄存器 页表项的内容 Flags标志位 | | 第二位是0表示表中无该地址 内存访问异常 逻辑地址空间
物理内存空间 逻辑地址空间与物理地址空间不对等 # 分页机制的性能问题 问题：访问一个内存单元需要2次内存访问 64位及其如果每页有1024字节，那么一个页表大小会是多少 2^64/ 缓存近期访问的页帧转换表项 如果TLB命中，物理页号可以很快被获取 如果TLB未命中，对应的表项被更新到TLB中 存放最常用的访问 TLB缺失：写程序的时候把地址放在一个区域，避免缺失
当出现TLB缺失，在页表中查到了数据以后，要将数据更新到TLB中，这个过程在CPU是X86会自动完成 在MIX则需要软件完成 省空间：当一级页表没有找到，二级页表根本不需要存 不像一级页表就算不存在还是会存 通过把页号分为k各部分，来实现多级间接页表 --- 建立页表树 有大地址空间 64-bit，前向映射页表变的繁琐 比如5级页表
不是让页表和逻辑地址空间大小相对应，而是让页表与物理地址空间的大小相对应 逻辑（虚拟）地址空间增长速度快于物理地址空间 表不再是以页号为索引 存的帧号，而是反过来，以帧好为索引，存的页号 每个帧和一个寄存器关联，寄存器包括： 页寄存器带来的额外开销：32K/16M=0.2% 耗内存小 优点：也表达小相对于物理内存而言很小，页表大小与逻辑空间大小无关 问题：需要通过页号找到页帧号
帧数较少，页寄存器可以被放置在关联内存中 在关联内存中查找逻辑页号 限制因素：大量的关联内存非常昂贵 难以在单个时钟周期内完成 # 基于哈希查找的方案 通过哈希函数，输入pid和页号得到帧号 在反向页表中通过哈希计算来搜索一个页对应的帧号 对页号做哈希运算，为了在帧表中获取对应的帧号 页i被放置在表f(i)位置，f是哈希函数 计算哈希函数f(i)并且使用他作为页寄存器的索引，获取对应页寄存器
检查寄存器标签是否包含i，包含则成功否则失败 问题：可能会出现哈希冲突，一个页号找到多个帧号，传入pid缓解冲突 但是需要把反向页表放到内存里去，内存开销很大 反向页表只会在高端CPU才存在，相比传统的一级多级页表占用的空间很小，相应的代价是需要高速函数，硬件计算，解决冲突的机制，才能让访问效率得到保障，硬件软件配合在时间空间取得不错的效果
段式存储在内存保护方面有优势，页式存储在内存利用和优化转移到后备存储方面有优势 进程p的段表 段S的页表 在段式存储管理的基础上，给每个段加一级页表 段页式存储管理中的内存共享 存储器规模的增长速度远大于存储器容量的增长速度 理想中的存储器：更大，更快，更便宜的非易失性存储器 在计算机系统中，在多道程序运行的环境下，可能会出现内存不够用的情况
如果程序太大，超过了内存容量，可以采用手动覆盖（overlay），只把需要的指令和数据保存在内存中 如果程序太多，超过了内存容量，采用自动交换（swapping）技术，把暂时不能执行的程序送到外存中 如果想要在有限容量的内存中，以更小的页粒度为单位装入更多更大的程序，可以采用自动的虚拟存储技术 在较小的可用内存中运行较大的程序，常用于多道应用程序，与分区存储管理配合使用
把程序按照其自身逻辑结构，划分为若干功能上相对独立的程序模块，那些不会同时执行的模块共享一块内存区域，按时间先后来运行 必要部分（常用功能）的代码和数据常驻内存 可选部分（不常用功能）在其他程序模块中实现，平时存放在外村中，在需要用到时彩妆日内存中 不存在调用关系的模块不必同时装入内存中，从而可以相互覆盖，即这些模块公用一个分区（一个内存空间）
A调用完B，B的内存释放到硬盘，把C的代码加载到内存，用A去调用 C掉用E，D和F不会执行 另一种覆盖方法：100K 有程序员来吧一个大的程序划分为若干个小的功能模块，并确定各个模块的覆盖关系，费时费力，增加编码难度 覆盖模块从外存装入内存，实际上是以时间延长来换取空间节省 DOS操作系统支持的overlay系统单元支持程序员控制覆盖技术
目标：多道程序在内存中时，让正在运行的程序或需要运行的程序获得更多的内存资源
可将暂时不能运行的程序送到外存，从而获得空闲内存空间
操作系统是吧一个进程的整个地址空间的内容保存到外存中（换出swap out），而将外存中的某个进程的地址空间读入到内存中（换入swap in）。换入换出内容的大小为整个程序的地址空间
交换技术实现的几个问题
交换时机的确定：何时需要发生交换，只有当内存空间不够或有不够的危险时换出
交换区的大小：必须足够大以存放所有用户进程的所有内存映像的拷贝，必须能对这些内存映像进行直接存取
程序换入时的重定位：换出后再换入的内存位置一定要在原来的位置上吗？最好采用动态地址映射的方法
覆盖只发生在那些相互之间没有调用关系的程序模块之间，因此程序员必须给出程序间各个模块之间的逻辑覆盖结构
交换技术十以内存中程序大小为单位进行的，不需要给出模块间的逻辑覆盖结构。换言之，交换发生在内存中程序与管理程序或操作系统之间，覆盖发生在运行程序的内部
覆盖技术：必须确定模块间的覆盖关系，增加程序员负担
交换技术：以进程为交换的单位，需要把进程的整个地址空间都换进换出，增加了处理器的开销，粒度太大
虚存技术：不是吧程序的所有内容都放在内存中，能够运行比当前的空隙那空间还要大的程序，由操作系统完成，无需外接干预，只对进程部分内容在内存与外存之间进行交换
物理内存 + 硬盘 = 虚拟内存
程序在执行过程中的一个较短时期，所执行的指令和指令的操作数地址，分别局限于一定的区域，表现为
-时间局部性：一条指令的一次执行和瑕疵执行，一个数据的一次访问和下次访问都集中在一个较短的时期内
-空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的几个数据都集中在一个较小的区域内
表明：从理论上来说，虚拟存储技术是能够实现的，而且实现了以后能够取得满意的效果
程序的编写方法对缺页率的影响
例：页面大小为4K，分配给每个进程的物理页面数为1，在一个进程中，定义了如下的二维数组int A[],该数组按行存放在内存，每一行放在一个页面中
第一次访问a00之前数组在硬盘中会产生一次缺页异常，OS吧数组4K数据块放入内存
第二次访问a10，和a00有4K距离，OS再次把4K数据块导入内存，不具备空间时间局部性
共发生1024次缺页中断
# 实现-在页式或段式内存管理的基础上实现
在装入程序时，不必将其全部装入到内存，而只需要将当前需要执行的部分页面或段装入到内存，就可让程序执行
在程序执行过程中，如果需要执行的指令或访问数据尚未在内存（缺页或缺段），由处理器通知操作系统将相应的页面或段调入到内存，然后继续执行程序
另一方面，操作系统将内存中暂时不使用的页面或段调出保存在外存上，从而腾出更过的空闲空间存放将要装入的程序以及将要调入的页面或段
大的用户空间：通过把物理内存与外存相结合，提供给用户的虚拟内存空间通常大于实际的物理内存，即实现了二者的分离，如32位的虚拟地址理论上可以访问4GB，而可能计算机上仅有256M物理内存，单硬盘容量大于4GB
部分交换：与交换技术相比较，虚拟存储的调入调出是对部分虚拟地址空间进行的，交换粒度更小
不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续
大部分虚拟存储系统都采用虚拟页式存储管理技术，即在页式存储管理的基础上，增加请求调页和页面置换功能
当一个用户程序要调入内存运行时，不是将该程序的所有页面都装入内存，而是只装入部分页面，启动程序运行
在运行程序过程中，如果发现要运行的程序或要访问的数据不在内存，则向系统发出缺页中断请求信号，系统在处理这个中断时，将外存中相应的页面调入内存，使得该程序能够继续运行
i + 访问位 + 修改位 + 保护位 + 驻留位 + 物理页帧号
驻留位：表示该页是在内存中还是外存中。如果等于1，表示该页在内存中，即该页表项是有效的，可以使用，如果该位是0，表示该页当前还在外存中，如果访问该页表项，将导致缺页中断
保护位：表示允许对该页做何种类型的访问，如可读，可写，可执行等
修改位：表明此页在内存中是否被修改过，当系统回收该物理页时，根据此位来决定是否把他的内容写回外存，写过说明内存与硬盘不一致，需要将内存数据放入硬盘进行刷新，是0就不用写回去，直接释放就行
访问位：如果该页被访问过（读写），则设置此位为1，没被访问置0，页面置换算法要尽量将没有被访问的位换出去
逻辑地址空间 物理地址空间
16位的逻辑地址，从0到64K，而物理内存只有32K，页面大小为4K
1. 如果在内存中有空闲的物理页面，则分配一物理页帧f，跳转到4，否则跳转到2
2. 采用某种页面置换算法，选择一个将被替换的物理页帧f，他所对应的逻辑页为q。如果该页在内存期间被修改过，则需要把他写回外存，没有被修改，直接释放
3. 对q所对应的页表项进行修改，把驻留位设置为0, 被替换的页需要设置驻留位，说该逻辑地址已没有对应的物理地址
4. 将需要访问的页p装入到物理页面f中
5. 修改p所对应的页表项的内容，把驻留位设置为1，把物理帧号设置为f
6. 冲洗运行被中断的命令
在何处保存未被映射的页
能够简单的识别在二级存储器中的页
交换空间（磁盘或文件）：特殊格式，用于存储未被映射的页面
一个虚拟地址空间的页面可以被映射到一个文件（在二级存储中）中的某个位置
代码段：映射到可执行二进制文件
动态加载的共享程序段：映射到动态调用的库文件
其他段：可能被映射到交换文件（swap file）换入换出分区
1+q 做了写操作 会将数据写入硬盘 时间也是5ms 换入换出
p足够小 就能减小EAT 只要程序满足局部性 就能使p够小
功能：当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中那个物理页面被置换
目标：尽可能减少页面的换进换出次数（即缺页中断次数）。具体把未来不再使用的或短周期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据进行预测
页面锁定（frame locking）：用于描述必须常住内存的操作系统放入关键部分或时间关键（time-critical）的应用进程。实现：在页表中添加锁定标志位（lock bit）
记录一个进程对页访问的一个轨迹
例：虚拟地址跟踪（页号，偏移 offset）
生成页面轨迹 3 1 4 2 5 2 1 2 3 4 可忽略偏移 只在页不再是情况下才会出现页缺失
分类：局部页面置换算法：选择范围仅限于当前进程占用的物理页面内
最优算法，先进先出算法，最近最久未使用算法，始终算法，最不常用算法
全局置换页面算法：选择范围是所有可换出的物理页面
工作计算法，缺页率算法
基本思路：当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在他的下一次访问之前，还需等待多少时间，从中选择等待时间最长的那个，作为被置换的页面，根据未来推测未来
但这只是一种理想青情况，在实际的系统中无法实现，因为OS无从知道每一个页面要等待多久以后才会被再次访问
可用作其他算法性能的评价依据 在一个模拟器上运行某个程序，并记录每一次的页面访问情况，第二遍运行时即可运行最优算法
置换的页面是将来最长时间不需要的页面
每页访问下次访问时间 a=7
思路：选择在内存中驻留时间最长的页面并淘汰，具体系统维护者一个链表，记录了所有位于内存中的逻辑页面。从链表的排列顺序来看，链表首页的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首页面淘汰出局，并把新的页面添加到链表末尾
性能较差，调出的页面有可能是经常要访问的页面，并有belady现象（给的物理页越多，反而缺页越多），很少单独使用
# 最近最久未使用算法
思路：当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰之。
对最优页面置换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间（最近几条指令）内，如果某些页面被频繁的访问，那么在将来一小段时间，他还可能会再一次的被频繁访问。反过来说，如果在过去某些页面长时间未被访问，那么它在将来还会长时间的得不到访问。根据过去推测未来
a=2 a=7 a=3 指的是页面所在前面的位置，因此越小说明在越前面被访问，需要被替换
LRU 算法需要记录各个页面使用时间的先后顺序，开销较大，两种方式
1. 系统维护一个页面链表，最近刚刚使用过的的页面作为首结点，最久未使用的页面作为尾结点。每一次访问内存时，找到相应的页面，把他从链表中摘下来，在移动到链表之首。每次缺页中断发生时，淘汰链表末尾的页面
2. 设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后考察栈内是否有与此页面相同的页号，若有则抽出。当需要淘汰一个页面时，总是选择栈底的页面，他就是最久未使用的
LRU的近似，对FIFO的一种改进
需要用到页表项当中的访问位，当一个页面被装入内存时，把该位初始化为0，然后如果这个页面被访问（读/写），则把该位置为1（硬件完成 CPU置1）access bit
把各个页面组织成环形链表（类似钟表面），把指针指向最老的页面（最先进来）
当发生一个缺页中断时，考察指针所指向的最老页面，若他的访问位为0，立即淘汰，若访问位为1，则把改位置为0，然后指针往下移动一格，如此下去直到找到被淘汰的页面，然后把指针移动到他下一格
维持一个环形链表保存在内存中
用一个时钟（或者使用/引用）位来标记一个页面是否经常被访问
当一个页面被引用的时候，这个位被设置为1
时钟头扫遍页面寻找一个带有used bit=0
替换在一个周转内没有引用过的页面
used bit 1表示已经访问过一次 访问位
这里有一个巨大的代价替换脏页
修改clock算法，使他允许脏页总是在一次时钟头扫描下保留下来
当1 1 时指针经过变成 0 1，再经过变成0 0 有两次机会让指针经过
让经常被写的页有更大的机会留在内存中
思路：当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰之
实现：对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加1.在发生缺页中断时，淘汰计数值最小的那个页面
LRU和LFU的区别：LRU考察的是多久未访问。时间越短越好；而LFU考察的访问次数或频度，访问次数越多越好
问题：在初始化的时候一个页在进程中使用的很多，但初始化完毕就不使用了，就不准确
可以定期把次数寄存器左移一位，就是 次数/2
在采用FIFO算法时，有时会出现分配的物理页面增加，缺页率反而提高的异常现象 原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的（替换较少使用的页面），因此，被他置换出去的页面并不一定是进程不会访问的 当第三次访问1时，因为在队列中，所以不会更新，但实际上他是被访问的，但还是被作为最久未被访问的页存储 增加帧大小为4
但出现了10次缺页 LRU满足栈算法的特点，物理页帧越多就缺页就越少，而FIFO不满足
LRU算法和FIFO本质上都是先进先出思路，只不过LRU是针对页面最近访问时间来进行排序，需要在每一次页面访问动态调整各个页面的先后顺序（有个页面最近访问时间变了），而FIFO是针对页面进入内存的时间来进行排序，这个时间固定不变，所以各个页面之间的先后顺序是固定的。如果一个页面在进入内存后没有被访问，那么他的最近访问时间就是他进入内存的时间。也就是如果内存中的所有页面都没有被访问过，LRU算法就退化为FIFO算法
LRU算法性能较好，但系统开销大，FIFO算法系统开销小，但可能会发生belady现象，折中的办法就是clock算法，在每一次页面访问时，他不必去动态的调整该页面在链表中的顺序，而仅仅是做一个标记，然后等到发生缺页中断的时候，再移动到链表末尾，对于内存当中未被访问的页面，clock算法表现和LRU算法表现一样好，对于那些曾经被访问过的页面，她不能想LRU算法那样，记住他们的准确位置。
工作集：一个进程当前正在使用的逻辑页面的集合，用二元函数W(t, w)
W（t,w）=在当前时刻t之前的w时间窗口当中的所有页面所组成的集合（随着t的变化，该集合也在不断的变化）
|W(t,w)|指工作集的大小，即页面数目
工作集大小的变化：进程开始执行后，随着访问新页面逐步建立稳定的工作集，当内存访问的局部性区域位置大致稳定时，工作集大小也大致稳定，局部性区域的位置改变时，工作集快速扩张和收缩到下一个稳定值
指在当前时刻，进程实际驻留在内存中的页面集合
工作集是进程在运行过程中固有性质，而常驻集取决于系统分配给进程的物理页面的数目，以及采用的页面置换算法
如果一个进程的整个工作集都在内存中，即常驻集 包含于（=）工作集，那么进程将很顺利的运行，而不会造成太多的缺页中断（直到工作集发生剧烈变动，从而过渡到另一个状态），希望这两个集合尽量重叠
当进程常驻集的大小达到某个数目以后，再给他分配更多的物理页面，缺页率也不会明显下降
追踪之前w个引用，在之前的w个内存访问的页引用是工作集，w被称为窗口大小 w=4 与局部页面置换算法的区别：当前在物理内存中放哪些页取决于他是否是在时间窗口之期内，如果工作集窗口设置为4，那么所有超出工作集窗口老的页都会被换出去，确保物理内存中始终有足够多的页存在，给其他运行的程序提供足够的内存，在整个系统，多个程序层面置换的次数不多 # 缺页率页面置换算法
可变分配策略：常驻集大小可变，例如：每个进程在刚开始运行时，现根据程序大小给他分配一定数量的物理页面，再在进程运行的过程中，动态调整常驻集大小 可采用全局页面置换的方式，当发生一个缺页中断时，被置换的页面可以是在其他进程中，各个并发进程竞争的使用物理页面 优缺点：性能极好，但增加了系统开销 具体实现：可以使用缺页率算法（PFF, page fault frequency）来动态调整常驻集的大小
缺页次数/内存访问次数，影响因素： 分配给进程的物理页面的数目 若运行的程序缺页率过高，通过增加工作集来分配更多的物理页面，过低，则通过减少工作集来减少他的物理页面数，使每个运行的程序的缺页率都在一个合理的范围内 一个交替的工作集计算明确的师徒最小化页缺失 当缺页率高的时候增加工作集 当缺页率低的时候减少工作集 当缺页发生时，从上次页缺失起计算这个时间记录这个时间，tlast是上次页缺失的时间
如果发生页缺失之间的时间是大的，之后减少工作集 如果这个发生缺页的时间是小得，之后增加工作集 根据工作集或缺页频率来动态调整内存中需要把那些页放进来丢出去，而不像局部算法只有在满的时候才会丢，使得经常访问的页能驻留在内存中，操作系统能面对多个处理的程序 如果分配给一个进程的物理页面太少，不能包含整个工作集，即常驻集 包含于
工作集，那么进程将会造成很多缺页中断，需要频繁的在内存与外存之间替换页面，从而使进程运行速度变慢，称为抖动 产生抖动原因：随着主流内存的进程数增加，分配给每个进程的物理页面数不断减小，缺页率不断上升，OS要选择一个适当的进程数目和进程需要帧数，以便在并发水平和缺页率之间达到平衡 抖动问题可能被本地的页面置换改善 这时程序可以并发的个数最多
进程：一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程
处于执行期的程序以及相关资源的总称
源代码 -> 内存中进程
把静态的代码通过OS加载到内存通过CPU动态的执行起来
程序计数器中的值，指示下一跳将运行的指令
一组通用的寄存器的当前值，堆 栈
一组系统资源（如打开文件）
总之，进程包含了正在运行的一个程序的所有状态信息
动态性：可动态创建，结束进程
并发性：进程可以被独立调度并占用处理机运行，并发执行
并发：一段时间内，有多个进程在执行，切换时间很小，给人感觉在一块执行
并行：在一个时刻有多个进程在执行，一个CPU没法并行，多个CPU才能并行 与并发时间粒度不一样
独立性：不同进程工作互不影响 进程相互之间时间可能受影响 结果不会受影响 可以为不同进程分配不同页表 保证独立性
制约性：因访问共享数据/资源或进程间同步而产生制约 同步互斥特点
程序=文件（静态的可执行文件）
进程=执行中的程序=程序+执行状态
程序的每次运行构成不同的进程 处理的数据不一样
进程是程序功能的体现 功能是一样的
通过多次执行，一个程序可对应多个进程，通过调用关系，一个进程可包括多个程序
进程执行需要的资源： 内存：保存代码和数据 CPU：执行指令
进程是动态的，程序是静态的，程序是有序代码的集合，进程是程序的执行，进程有核心态，用户态
进程是暂时的，程序是永久的，进程是一个状态变化的过程，程序可长久保存
进程与程序的组成不同：进程的组成包括程序，数据和进程控制块（即进程状态信息）
科学家给女儿做蛋糕，找了一本食谱，买了一些原料，现学现做
食谱=程序 科学家=CPU 原料=数据 做蛋糕的过程=进程
小儿子哭着进来了，被蜜蜂遮了，科学家把蛋糕放在一边，在食谱上做了标记，把状态信息存储起来
又去找了一本医疗手册，超找相关内容，按照上面的指令一步步执行，处理完伤口后继续做蛋糕
CPU从一个进程（做蛋糕） 切换到另一个进程（医疗救护）进程在执行过程中动态切换进行不同的功能
B 相互独立执行 ——————————————————————> Time
程序 = 算法 + 数据结构
操作系统为每一个进程都维护了一个PCB，用来保存与该进程有关的各种状态信息
操作系统管理控制进程运行所用的信息集合。操作系统用PCB来描述进程的基本情况以及运行变化的过程，PCB是进程存在的唯一标志
进程的创建：为进程生成一个PCB
进程的终止：回收他的PCB
进程的组织管理：通过对PCB的组织管理来实现
1. 进程标志信息：如本进程的标志，本进程的产生者标识（父进程标识），用户标识
2. 处理机状态信息保存区：保存进程的运行现场信息
用户可见寄存器：用户程序可以使用的数据，地址寄存器
控制和状态寄存器：如程序计数器（PC），程序状态字（PSW）
栈指针：过程调用/系统调用/中断处理和返回时需要用到
调度和状态信息：用于操作系统调度进程并占用处理机使用
进程间通信信息：为支持进程间的与通信相关的各种标识，信号，信件等，这些信息存在接收方的进程控制块中
存储管理信息：包含有指向本进程映像存储空间的数据结构
进程所用资源：说明由进程打开，使用的系统资源，如打开的文件等
有关数据结构连接信息，进程可以连接到一个进程队列中，或链接到相关的其他进程PCB
链表：同一状态的进程其PCB成一链表，多个状态对应多个不同链表，更好完成动态插入，删除，索引数组方式慢
各状态的进程形成不同的链表：就绪链表，阻塞链表
索引表：同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表
引起进程创建的三个事件 用户请求创建了一个新进程 正在运行的进程执行了创建进程的系统调用 内核选择一个就绪的进程，让他占用处理机并执行 在以下情况下，进程等待（阻塞） 1. 请求并等待系统服务，无法马上完成 等待读写文件 2. 启动某种操作，无法马上完成 3. 需要的数据没有到达 进程只能自己阻塞自己，因为只有进程自身才能知道何时需要等待某种事件的发生 1.
被阻塞进程需要的资源可被满足 2. 被阻塞进程等待的事件到达 3. 将该进程的PCB插入到就绪队列 该进程只能被别的进程或操作系统唤醒 1. 正常退出（自愿） 2. 错误退出（自愿） 3. 致命错误（强制） 4. 被其他进程说杀（强制） 进程三种基本状态：进程在生命结束前处于且仅出于三种基本状态之一 不同系统设置的进程状态数目不同 运行状态running：当一个进程正在处理机上运行时
就绪状态ready：一个进程获得了除处理机外的一切所需资源，一旦得到处理机（CPU）即可运行 等待状态（阻塞状态BLOCKED）：一个进程正在等待某一事件而暂停运行时。如等待某资源，等待输入/输出完成 创建状态（new）:一个进程正在被创建，还没被转到就绪状态之前的状态 结束状态（exit）：一个进程正在从系统中消失时的状态，这是因为进程结束或由于其他原因所导致
CPU会给多个就绪的进程分配时间片，使得每一个就绪态进程获得公平的资源 New -> ready: 当进程被创建完成并初始化后，一切就绪准备运行时，变为就绪状态，时间会很快，准备PCB ready -> running：处于就绪态的进程被进程调度程序选中后，就分配到处理机上执行 running -> exit: 当进程表示他已经完成或因出错，当前运行进程会由操作系统坐结束处理
runnin -> ready: 处于运行状态的进程在运行过程中，由于分配给他的处理及时间片用完而让出处理机，由操作系统完成，OS管理时钟，将时间片完的进程停止，选择新的就绪进程 running -> blocked:当进程请求某样东西必须等待时，等待定时器的到达，等待读写文件 blocked -> ready:
当进程要等待某事件到来时，从阻塞状态变到就绪状态，由操作系统来完全状态转变 进程在挂起状态时，意味着进程没有占用内存空间，处在挂起状态的进程映像在磁盘上 | 事件发生 | 事件发生 | 阻塞挂起状态（blocked-suspend）:进程在外存并等待某事件的出现 处于阻塞态挂起 就绪挂起状态（ready-suspend）：进程在外存，但只要进入内存，即可运行 处于就绪态挂起 #
与挂起相关的状态转换 挂起 suspend：把一个进程从内存转到外存，情况： 1. 阻塞到阻塞挂起：没有进程处于就绪态或就绪进程要求更多资源时候，会进行该转换，已提交新进程或运行就绪进程 2. 就绪到就绪挂起：当有高优先级阻塞（系统认为很快就绪）进程和低优先就绪进程，系统会选择挂起低优先级就绪进程 3.
运行到就绪挂起：对抢先式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态 # 在外存时的状态转换 阻塞挂起到就绪挂起: 当有阻塞挂起进程因相关事件出现时，系统会把阻塞挂起进程转换为就绪挂起进程 把一个进程从外村转到内存 1. 就绪挂起到就绪：没有就绪进程或挂起进程优先级高于就绪进程时，会进行改装换 2.
阻塞挂起到阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起（系统认为会很快出现所等待的事件）进程转换为阻塞进程 # os如何通过PCB和定义的进程状态来管理PCB，帮助完成进程的调度过程 用进程的观点来看OS：用户进程，磁盘管理进程，终端进程 以进程为基本结构的OS，最底层为CPU调度程序（包括中断处理） 上面一层为一组各式各样的进程
由操作系统来维护一组队列，用来标志系统当中所有进程的当前状态 不同的状态分别用不同的队列表示（就绪队列，各种类型的阻塞队列） 每个进程的PCB都根据他的状态加入到相应的队列中，当一个进程的状态发生变化时，他的PCB从一个状态队列脱离出来，加入到另一个队列 事件2发生 等待事件2
60年代以来，OS一直用进程作为独立运行的基本单元，直到80年代中期，人们又提出了更小的独立运行的基本单元 - 线程
案例：编写一个MP3播放软件
1. 从MP3音频文件中读取数据
2. 对数据进行解压缩
3. 把解压后的音频数据播放出来
Read(); --- I/O 播放出来的声音不连贯 读取在硬盘中比较慢 卡在那
程序1 程序2 程序3
问题：进程间怎么通信，共享数据？ 另外维护进城系统开销较大
创建进程时，分配资源，建立PCB，撤销进程时，回收资源，撤销PCB
进程切换时，保存当前进程的状态信息
需要提出一种新实体，满足：
1. 实体之间可以并发的执行
2. 实体之间共享相同的地址空间
线程是进程一部分，描述指令流执行状态，他是进程中指令执行流最小单元，是CPU调度的基本单位
进程当中的一条执行流程
1. 从资源组合角度：进程把一组相关的资源组合起来，构成了一个资源平台（环境），包括地址空间（代码段，数据段），打开的文件，访问的网络等各种资源
2. 从运行的角度：代码在这个资源平台上的一条执行流程（线程），线程描述在进程资源环境中的指令流执行状态
线程 = 进程 - 共享资源
1. 一个进程中可以存在多个线程
2. 各个线程之间可以并发执行
3. 各个线程之间可以共享地址空间和文件等资源
一个线程崩溃会导致其所述的进程的所有线程崩溃，一个线程写错了，会破坏共享资源，影响所有线程
网页使用进程，不容易崩溃
1. 进程是资源分配单位，线程是CPU调度单位
2. 进城拥有一个完整的资源平台，而线程只独享必不可少的资源。如寄存器，栈
3. 线程同样具有就绪，阻塞，执行三种基本状态，同样具有状态之间的转换关系
4. 线程能减少并发执行的时间和空间开销
- 线程创建时间比进程短
- 线程中终止时间比进程短 不考虑哪些资源释放
- 通一进城内线程切换时间比进程短，线程拥有同一个页表不用切换，进程需要切换页表
- 由于同一进城的个县城间共享内存和文件资源，可直接进行不通过内核的通信
OS管理的线程，看得到 在用户空间实现的线程机制，不依赖于操作系统的内核，由一组用户级的线程库函数来完成线程的管理，包括进程的创建，终止，同步和调度 由于用户线程的维护由相应的进程来完成（通过线程库函数），不需要OS内核了解用户线程的存在，可用于不支持线程技术的多进程操作系统 每个进程都需要他自己私有的线程控制块（TCB）列表，用来跟踪记录他各个线程的状态信息（PC,
栈指针，寄存器），TCB由线程库函数来维护 用户线程的切换也是由线程库函数来完成，无需用户态/核心态切换，所以速度特别快 允许每个进程拥有自定义的线程调度算法 阻塞性的系统调用如何实现？如果一个线程发起系统调用而阻塞，则整个进程在等待 当一个线程开始运行后，除非他主动交出CPU使用权，否则他所在进程当中的其他线程无法执行
由于时间片分配给进程，故与其他进程相比，再多线程执行时，每个线程得到的时间片较少，执行较慢 指的是在操作系统的内核当中实现的一种线程机制，由OS的内核来完成线程的创建，终止和管理 在支持内河县城的OS中，由内核来维护进程和线程的上下文信息（PCB和TCB） 县城的创建，终止和切换都是通过系统调用/内核函数方式来实现，由内核态完成，系统开销较大，一次切换，创建，终止从用户态到内核态
在一个进程当中，如果某个内核线程发起系统调用而被阻塞，并不会影响其他内核线程的运行 时间片分配给线程，多线程的进程获得更多CPU时间 它是由内和支持的用户线程，一个进程可以有一个或多个轻量级进程，每个轻权进程由一个单独的内核线程来支持（solaris/linux）
停止当前运行进程（从运行状态改变成其他状态）并且调度其他进程（转变成运行状态）
必须在切换之前存储许多部分的进程上下文
必须能够在之后恢复他们，所以进程不能显示他曾经被暂停过
必须快速（上下文切换非常频繁）
一些时候可能会费时，所以我们应该尽可能避免
操作系统为活跃的进程准备了进程控制块（PCB）
操作系统将PCB放置在一个合适的队列里
内核把进程的列表存放在叫做任务队列的双向链表中，链表的每一项都是类型为task_struct，称为进程描述符(process descriptor)的结构,包含一个具体进程的所有信息，包括他打开的文件，进程的地址空间，挂起的信号，进程的状态
内核通过一个唯一的进程标识值(process identification value)或PID来表示每个进程，PID最大默认值32768（short int短整形的最大值），表示允许同时存在最大进程数目
所有进程都是pid为1的init进程后代，，内核在系统启动的最后阶段启动init进程，该进程读取系统的初始化脚本并执行相关程序，完成系统启动初始化流程，任务队列是双向循环链表，可通过next_task prev_task获取子父进程
等待I/O队列 （每个设备队列）
exec()用新程序重写当前进程 PID没有改变 fork通过拷贝当前进程创建一个子进程，子父进程的区别仅在于PID，PPID和某些资源统计量不同，exec负责读取可执行文件并将其载入地址空间开始运行 fork() 创建一个继承的子进程 复制父进程的所有变量和内存 复制父进程的所有CPU寄存器（有一个寄存器除外）
返回值：子进程fork()返回0，父进程fork()返回子进程标识符 fork()返回值可方便后续使用，子进程可用getpid()获取PID 允许进程加载一个完全不同的程序，并从main开始执行（即_start） 可以执行不同的应用程序 允许进程加载时指定启动参数(argc, argv) 但是运行不了不同的程序 代码段，堆栈，堆（heap）等完全重写 复制父进程的内存和CPU寄存器到子进程里
在99百分情况里，在调用fork()后调用exec()，意味着创建了新的进程，是为了让他跑不同的程序 在fork()操作中内存复制是没有作用的，因为如果调用了exec会完全覆盖掉，fork拷贝的内容没有意义 子进程将可能关闭打开的文件和链接 不拷贝父进程的页表项，其他和fork相同 创建进程时，不再创建一个同样的内存映像 一些时候称为轻量级fork() 子进程应该立刻几乎调用exec()
只复制父进程地址空间的元数据-页表，指向同一块地址空间，当子或父进程对某一进程空间进行写操作时，会触发一个异常，会把异常的页写成两份，使得子父进程有不同的地址，按需写复制，只读就不会去复制一份
写实拷贝可以推迟甚至免除拷贝数据的技术，内核并不会复制整个进程地址空间，让父子进程共享一个拷贝，只有在写入的时候，数据才会被复制，使各个进程有各自的拷贝，在页不会写入的情况，fork后立即exec，就无需复制 当子进程结束时，操作系统会回收所占用的资源，但是在内核态的PCB很难回收，所以就交给父进程完成，帮子进存释放内存，主要是PCB wait（）系统调用用于父进程等待子进程的结束
子进程结束时通过exit()向父进程返回一个值 父进程通过wait（）接受并处理返回值 wait()系统调用的功能 有子进程存活时，父进程进入等待状态，等待子进程的返回结果 当某子进程调用exit()时，唤醒父进程，将exit()返回值作为父进程中wait（）的返回值 有僵尸子进程等待时，wait()立即返回其中一个值 无子进程存活时，wait()立刻返回
进程结束执行调用exit()，完成进程资源回收 将调用参数作为进程的结果 关闭所有打开的文件等占用资源 释放大部分进程相关的内核数据结构 如存活，保留结果的值知道父进程需要他，进入僵尸（zombie/defunct）状态，表明exit（）执行完毕，但是父进程的wait还没有执行期间的状态，要死不死，只等被回收
如果没有，他释放所有的数据结构（root进程代替死的父进程），进程结果，以免父进程先于子进程死亡，就无法进行回收僵尸 清理所有等待的僵尸进程 进程终止是最终的垃圾收集（资源回收） # 其他进程控制系统调用 nice()指定进程的初始优先级 Unix系统中进程优先级会随执行时间而衰减 ptrace()允许一个进程控制另一个进程执行 sleep()可以让进程在定时器的等待队列等待指定 就绪
———————被调度—————————> 运行
