OS

Background 多进程作为现代操作系统的重要特性，交互则会引起同时对共享资源的访问，当这些资源访问不正确会出现冲突或产生不适当的输出（冲突、死锁、饥饿）；而在同步的基础上，进程被分为以下两种类型： 独立进程 Independent Process 不和其他进程共享资源或状态 确定性，输入状态确定结果 可重现，能够重现起始条件，I/O 调度的顺序不重要 协作进程 Cooperative Process； 多进程共享资源或状态 不确定性 probabilistic 不可重现 不确定性和不可重现意味着bug可能是间歇性发生的 Cooperation 进程的互相影响，即进程间的合作（相互或破坏）；最简单的例子就是两个进程使用同一个文件，一个进程读，一个进程写。读进程的结果会被写进程所影响。 进程需要合作的原因： 资源共享：多个进程访问相同的数据 一台电脑，多个用户 一个银行存款余额,多台ATM机 嵌入式系统（机器人手臂和收的协调） 计算加速： I/O 和 CPU计算可重叠 多处理器 - 将任务分解为子任务并分布在不同的进程中，它通常可以更快地运行（也需要多个可共享的 CPU） 模块化：复杂的任务组织成单独的子任务，让不同的进程运行 大程序分成小程序 是系统易于扩展 程序可以调用函数fork()来创建一个新的进程 操作系统需要分配一个新的并且唯一的进程ID 因此在内核中,这个系统调用会运行 new_pid = next_pid++; 翻译成机器指令: Load next_pid Reg1 STORE Reg1 new_pid INC Reg1 STORE Reg1 next_pid 假设两个进程并发执行 如果next_pid等于100, 那么其中一个进程得到的ID应该是100, 另一个进程的ID应该是101, next_pid应该增加到102 可能在INC前进行了上下文切换, 最终导致两个进程的pid都是100,而next_pid也是101 无论多个线程的指令序列怎样交替执行,程序都必须正常工作 多线程程序具有不确定性和不可重现的特点 不经过专门设计,调试难度很高 不确定性要求并行程序的正确性 先思考清楚问题，把程序的行为设计清楚 切忌给予着手编写代码，碰到问题再调试 Race Condition 竞态条件是由操作系统软件中的同步错误。出现在进程试图同时执行两个或多个操作时，这是一种不希望出现的情况。 怎么样避免竞态?...

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....