Overview 进程的描述 进程的状态 State 线程 Thread 进程间通信 Inter-Process Communication 进程互斥与同步 死锁 DeadLock 进程的描述 在操作系统中，通常来说进程 Process 是当前正在执行的东西。因此，一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程，可以称之为进程。 程序是静态的文件 进程是程序动态执行的过程 进程的组成 进程包括 : 程序的代码 程序处理的数据 程序计数器 (PC) 中的值, 指示下一条将运行的指令 一组通用的寄存器的当前值, 堆 Heap , 栈 Stack 一组系统资源(如打开的文件、内存、网络) 而进程的主要构成如下， Stack Section Heap Section Data Section Text Section Stack Stack部分包含： 局部变量 函数和返回地址 main函数 如上图所示，Stack和 heap 以相反的方向增长，如果两者都以相同的方向增长，那么其两者可能会重叠，因此如果它们以相反的方向增长则很好。 示例：如，调用下列函数时，将存储在Stack部分，一旦函数返回，该函数堆栈部分的值将被删除。 Stack上有一个堆栈帧，其中包含main函数以及局部变量a, b sum 。使用 printf()，创建的帧以及局部变量只能在内存中访问，帧的持续时间在从函数 return 0 后释放。 c 1 2 3 4 5 6 7 8 int main(void) { int a, b, sum; a = 2; b = 3; sum = a + b; printf("%d\n", sum); return 0 } Stack是一种后进先出 (LIFO) 数据结构，最后一个被推到Stack上的内容就是从顶部弹出的第一个内容。不允许从Stack的中间插入或移除。因此Stack必须至少支持两种操作：push 和 pop ；其他操作也是可以，但不是必需的。...

Overviews 功能与目标 实验设置与评价方法 局部页面算法 最优页面置换算法 先进先出算法 最近最久未使用算法 时钟页面置换算法 最不常用置换算法 Belady现象 LRU FIFO Clock对比 全局页面置换算法 工作集模型 工作集页面置换算法 缺页率置换算法 功能与目标 功能 : 当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。 目标 : 尽可能地减少页面的换进换出次数(即缺页中断的次数)。 具体来说，把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测。 页面锁定 frame locking：用于描述必须常驻内存的操作系统的关键部分或时间关键（time critical）的应用进程。实现的方式是：在页表中添加锁定标记位(lock bit)。 实验设置与评价方法 实例：记录一个进程对页访问的一个轨迹 举例 : 模拟一个实验环境，记录对应的地址访问序列，虚拟地址跟踪(页号, 偏移)… (3,0) (1,9) (4,1) (2,1) (5,3) (2,0) … 而offset可以忽略（页不存在才会产生 page fault），生成的页面轨迹 3, 1, 4, 2, 5, 2, 1, …（替换为，3,1,4,2,5,2,1） 模拟一个页面置换的行为并且记录产生页缺失数的数量 更少的缺失，更好的性能 局部页面置换算法 最优页面置换算法 基本思路：当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之前，还需等待多长时间，从中选择等待时间最长的那个，作为被置换的页面。 这是一种理想情况, 在实际系统中是无法实现的, 因为操作系统无法知道每一个页面要等待多长时间以后才会再次被访问. 最优页面置换算法（Optimal Page Replacement）可用作其他算法的性能评价的依据，(在一个模拟器上运行某个程序, 并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法) 在该算法中，会替换在未来最长持续时间内不会使用的页面。如下图所示有 a b c d e五个页，但是只有四个页帧。此时会产生物理页不够，会产生 Page Fault。...

Objective 覆盖技术 交换技术 虚拟内存 目标 程序局部性原理 基本概念 基本特征 虚拟页式内存管理 覆盖技术 overlay 在固定分区中的主要遇到的问题是进程的大小受到分区的最大大小的限制，这将意味着一个进程将不能跨越另一个进程。为了解决这个问题，早期使用了称为覆盖(overlay) 的解决方案，覆盖技术是为了在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。这样并非所有模块都需要同时存在于内存中，实现了运行大于物理内存大小的程序的技术。 覆盖技术的原理： 将程序按照执行逻辑拆分为多个功能上相对独立的部分（overlays）, 那些不会同时执行的模块共享同一块内存区域, 按时间先后来运行（分时）。 必要部分，常驻内存的代码和数据，负责管理，在某个时间片将相应的程序和数据导入或导出内存。 可选部分，在其他程序模块中实现, 平时存放在外存中, 在需要用到时才装入内存; 不存在调用关系的模块不必同时装入到内存, 从而可以相互覆盖, 即这些模块共用一个分区. 覆盖技术实例 覆盖技术说明： 有一个程序，分位A B C D E F G 六个模块，每一个模块占用了一定空间，程序的覆盖树如图所示。 问：当满足加载（和运行）该程序所需物理内存中的大小是多少？ 使用覆盖技术，实际上不需要将整个程序放在主内存中。只需要在对应时间片时所需要的部分即可，其逻辑调用关系树可以分为：Root-A-D或者 Root-A-E ; Root-B-F 或 Root-C-G 部分。 Root是常驻内存，因为其需要调用A B C D E F G 六个模块，占用2KB 如图：加载与运行改程序所需的物理内存大小是多少？ ​ (a) 12 KB ​ (b) 14 KB ​ (c) 10 KB ​ (d) 8 KB 答：由公式可得，最大运行层所需的物理内存为14KB，即拥有 14KB 大小的分区就可以运行上图任意一个分区...

overview Q1: 为什么需要非连续内存分配 连续内存管理 （contiguous memory allocation）, 即 : 操作系统加载到内存以及程序加载到内存中时, 分配一块连续的内存块. 但这种方式会出现碎片问题，而非连续内存分配（Non-contiguous memory allocation ）可以有效的减少碎片（Fragmentation）的出现。 Q2: 主要的非连续内存分配的管理方法 分段（Segmentation） 分页（Paging） 页表 （Page Table） 1.非连续内存分配的必要性 连续内存管理的缺陷： 内存利用率较低（memory wastage），在程序运行时分配的内存是增长的，但在进程使用为达到分配大小时，分配的块并未使用，并且也不能给其他进程使用，造成了内存的浪费。 分配给一个程序的物理内存必须是连续的。 碎片化问题 不灵活（inflexibility），当进程或文件使用的内存超出预期时（即：超出分配的内存块大小），将停止并抛出异常，例如：No disk space。 非连续内存分配的优点: 一个程序的物理地址空间是非连续的 更好的内存利用和管理，（减少了内存浪费） 允许共享代码与数据(共享库等…) 支持动态加载和动态链接 非连续内存分配的缺点： 建立虚拟地址和物理地址的转换难度大 软件方案 硬件方案(采用硬件方案) : 分段 / 分页 分段（segmentation） 首先 segmentation mechanism需要考虑的问题： 程序的分段地址空间 分段寻址方案 什么是segmentation 段（segmentation）是一个逻辑单元 (logical unit)，例如： 主程序 main program 程序（主要是指功能的代码，如一段函数） procedure 函数 function 方法 method 对象 object 局部变量和全局变量 local variables, global variables 公共块 common block 堆 stack 符号表 symbol table 数组 arrays [segmentation的逻辑视图] 可以看到左边是逻辑地址，右边是不连续的物理地址，中间有一个映射机制将两边建立了一个关联关系（ST Segment Table）。通过映射机制将不同的块（如stack，function....

一 计算机体系结构及内存分层体系 1.计算机硬件体系结构大致分为 CPU，完成程序的执行控制 主存 （main memory），放置程序代码和数据 I/O（外）设备，配合程序工作。 2.内存分层体系（金字塔结构) 什么是内存结构：CPU所访问的指令和数据在什么地方。 第一类：位于CPU内部，操作操作系统无法直接进行管理的，寄存器，cache；特点，速度快，容量小 第二类：主存或物理内存，主要用来放置操作系统本身及要运行的代码；其特点是，容量比cache要大很多，单速度交于cache要慢一些。 第三类：磁盘，永久保存的数据及代码，当对于主存要慢，容量比主存大很多。 操作系统的作用可以将数据访问的速度（cache与内存）与存储的大小（硬盘）很好的融合在一起 3.OS管理内存时需要完成的目标 ① 抽象：逻辑地址空间（将物理内存，外设等抽象成逻辑地址空间，只需要访问对应地址空间) ② 保护（独立）：操作系统完成隔离机制实现，独立地址空间（每段程序执行时，不受其他程序的影响） ③ 共享：进程间安全，可靠，有效，进行数据传递，访问相同的内存。 ④ 虚拟化：更多的地址空间（利用磁盘的空间) 4.需要完成在操作系统中管理内存的不同方法 操作系统层面 程序重定位 分段 分页 虚拟内存 按需分页虚拟内存 硬件层面 必须知道内存架构 MMU(内存管理单元)：处理CPU的内存访问请求 二 地址空间&地址生成 地址空间的定义 地址生成器 地址安全检查 1.内存地址的定义 ① 物理内存地址：硬件支持的地址空间，如主存（内存）和硬盘，由硬件完成管理和控制 ② 逻辑内存地址：一个程序运行时所需要的内存范围。 两者间的关系：逻辑地址空间最终是一个存在的物理地址空间，两者间的映射关系是由操作系统来管理的 2.逻辑地址生成过程（把代码转化为计算机能理解语言） 一段代码运行→编译→汇编语言→机器语言→产生链接文件→将硬盘中程序载入到内存当中运行（完成逻辑地址的分配） 如C中变量的名字，函数的位置，为逻辑地址。 3.物理地址生成（逻辑地址对应的物理地址的过程） CPU方面 MMU表示映射关系 ① CPU ALU Arithmetic logic unit 发出请求，为逻辑地址 ② CPU MMU Memory management unit 查找逻辑地址映射表，不存在会去内存中找 ③ 控制器提出内存请求（需要的内容，内容即指令） 内存方面 ④ 内存通过bus发送物理内存地址的内容给CPU OS方面 建立逻辑地址和物理地址之间的映射关系（需在前四部前将映射管理建立好）...