第五讲物理内存管理

5.1 计算机体系结构和内存层次

一个进程使用内存时要满足其要求，在不用时应及时回收。
寄存器是非常小的；内存的最小访问是8bit，一次读写32位的话也要注意对齐问题。
高速缓存如果不命中，则到内存中查找，在内存中找不到，就读取到内存中再读取，需要操作系统的介入。
内存中每一个字节有一个物理地址，硬盘中扇区512字节最小单位，我们希望将线性的物理内存空间转换成逻辑内存空间；很好的把保护（独立地址空间）和共享（访问相同内存）结合，虚拟化（实现更大的逻辑空间）。
操作系统中采用的内存管理：重定位（段地址+offset）、分段（希望他能够不连续，将程序分成三个相对独立的空间，代码数据加堆栈）、分页（把内存分成最基本的单位）。
MMU（内存管理单元）

5.2 地址空间和地址生成

物理地址空间是硬件支持的地址空间，多少位就是有多少条地址线；逻辑地址是CPU运行时进程看到的地址，对应可执行文件中的区域，进程的逻辑地址空间需要转换成物理地址空间，最后在总线上访问相应的物理单元。
逻辑地址生成：将程序转成汇编码，添加逻辑地址，再进行链接，把多个模块和函数库排成线性的序列，在程序加载要进行重定位，把链接时生成的地址进行平移。
在编译时，如果已知运行时起始地址，则可以直接生成地址，如果起始地址改变则要重新编译；在加载时也可生成绝对地址，编译器生成可重定位的代码；执行时地址生成出现在使用虚拟存储的情况下，在执行指令时进行地址转换，最灵活，可以移动指令实现虚拟内存。

CPU：ALU需要逻辑地址的内存内容，MMU进行逻辑地址和内存地址的转换，CPU控制逻辑给总线发送物理地址请求，内存发送物理地址的内容给CPU，操作系统建立逻辑地址和物理地址的映射。
CPU在执行指令时，如果访问数据段的数据，如果数据段基址+offset超过了数据段，则内存访问异常，执行失败，调用中断处理程序；如果正确那在段基址寄存器配合下得到相应的地址。

5.3 连续内存分配

为了提高效率，采用动态分配算法。
连续内存分配指给进程分配一块不小于指定大小的连续物理内存区域，会产生一些碎片，一种是两块分配单元之间的未被使用的内存，内部碎片是分配单元内部的未被使用的内存，取决于分配单元大小是否要考虑取整和对齐。
动态分区分配是指程序加载时分配一个进程指定大小可变的分区，分配得到的地址是连续的。操作系统维护两个数据结构，一个是所有进程已分配的分区，另一个是空闲分区。动态分区分配策略有很多：
最先匹配（从空闲分区列表里找第一个符合的，释放时检查是不是可以和邻近的空闲分区合并，在高地址有大块的空闲分区，但有很多外部碎片，分配大块时较慢）；
最佳匹配（全找一遍，找最合适的，空闲分区按照从小往大排序，释放时跟邻近地址的合并，并且重排序，大部分分配的尺寸较小时比较好，避免大的空闲分区被拆分，减小外部碎片，但是增加了无用的小碎片）；
最差匹配（找相差最大的，空闲分区从大到小拍，分配时找最大的，释放时检查可否与邻近的空闲分区合并，进行合并并重排序，如果中等大小的分配较多，则最好，避免出现太多小碎片，但是释放分区比较慢，容易破坏大的空闲分区）。

5.4碎片整理

调整已分配的进程占用的分区位置来减少或避免分区碎片，通过移动分配给进程的内存分区，以合并外部碎片。保证所有程序可动态重定位！
分区对换：通过抢占并回收处于等待状态进程的分区，以增大可用内存空间。采用对换使多个进程同时运行。

5.5 伙伴系统

连续内存分配实例。
整个可分配的分区约定为2^U，需要的分区大小为2^(U-1) < s < 2^(U)，把整个块分配给这个进程。如s<2^(i-1)-1，将大小为2^i的当前分区划分成2个大小为2^(i-1)的空闲分区，重复划分过程，直到2^(i-1)-1<\s<2^(i)，把一个空闲分区分配给该进程。
数据结构：空闲块按照大小和起始地址组织成二维数组，初始时只有一个大小为2^U的块，由小到大在空闲数组找最小的，如果空闲块过大，则进行二等分，直到得到需要的大小是空闲块的1/2还大些。总之，找比它大的最小的空闲块，看是不是比它的二倍大，如果是，就切块，不是的话就分配给它。合并：大小相同且地址相邻，起始地址较小的块的起始地址必须是2^(i+1)的倍数。两个块具有相同大小，且它们物理地址连续。

为了便于页面的维护，将多个页面组成内存块，每个内存块都有 2 的方幂个页，方幂的指数被称为阶 order。order相同的内存块被组织到一个空闲链表中。伙伴系统基于2的方幂来申请释放内存页。
当申请内存页时，伙伴系统首先检查与申请大小相同的内存块链表中，检看是否有空闲页，如果有就将其分配出去，并将其从链表中删除，否则就检查上一级，即大小为申请大小的2倍的内存块空闲链表，如果该链表有空闲内存，就将其分配出去，同时将剩余的一部分（即未分配出去的一半）加入到下一级空闲链表中；如果这一级仍没有空闲内存；就检查它的上一级，依次类推，直到分配成功或者彻底失败，在成功时还要按照伙伴系统的要求，将未分配的内存块进行划分并加入到相应的空闲内存块链表
在释放内存页时，会检查其伙伴是否也是空闲的，如果是就将它和它的伙伴合并为更大的空闲内存块，该检查会递归进行，直到发现伙伴正在被使用或者已经合并成了最大的内存块。

第六讲物理内存管理: 非连续内存分配

6.1 非连续内存分配的需求背景

一种是段，一种是页，还有段页式。
非连续分配的目的是提高内存利用效率和管理灵活性：

允许一个程序使用非连续的物理地址空间；
允许共享代码与数据；
支持动态加载和动态链接。
如何实现虚拟地址和物理地址的转换？软/硬件。

6.2 段式存储管理

段的地址空间是如何组织的，内存访问如何进行。
进程的地址空间看成若干个段，主代码段、子模块代码段、公用库代码段、堆栈段、初始化数据段、符号表等。段式管理更精细。把逻辑地址空间转换成一个不连续的物理地址空间集。
每一个段是访问方式和存储数据等属性一致的一段地址空间；对应一个连续的内存块，若干个段组成了逻辑地址空间，把逻辑地址分成一个二元组（段号，段内偏移地址），再转换成原来的地址。
程序访问物理单元时，首先用段号查段表，找到段的起始地址和长度，硬件的存储管理单元（MMU）检查越界，在MMU里利用段地址和偏移找到实际地址。

6.3 页式存储管理

物理内存空间分成“帧”，大小是2的n次幂，让这个转换变得方便，逻辑地址空间里也划分成相同大小的基本分配单位“页”，页面到页帧的转换涉及了“页表”、MMU/TLB。
物理地址组织成二元组（帧号，帧内偏移量）。逻辑地址空间也是二元组（p，o），逻辑地址中页号是连续的，物理地址的帧号是不连续的，逻辑地址中页号是p，物理地址的帧号是f，用p到页表中找对应的f，页表中保存了每个页的页表基址，用p就可以找到。每个帧的大小是2的n次方，把f左移s位再把页内偏移加上，就可以找到物理地址。

6.4 页表概述

从逻辑页号到物理页号的转换，每一个逻辑页号对应一个物理帧号，且随着程序运行变化，动态调整分配给程序的内存大小。这个表存在页表基址寄存器，告诉你这个页表放在哪。页表项中有帧号f，有几个标志位：

存在位：如果有对应的物理帧则为1；
修改位：是否修改对应页面的内容；
引用位：在过去一段时间里是否有过引用。

内存访问性能：访问一个内存单元需要2次内存访问，先获取页表项，再访问数据。
页表大小问题：页表可能非常大。
处理缓存或者间接访问（一个很长的表，多级页表等）

6.5 快表和多级页表

快表：缓存近期访问的页表项，在TLB使用关联存储实现，查找对应的key，并行查找表项，具备快速访问性能。如果没有命中只能再次查找内存中的页表并把它加到快表中。
多级页表：通过间接引用将页号分为k级。整个访问次数是k+1。建立页表树。先查第一段逻辑地址作为第一级页表的偏移，找到第二级页表的起始，第二段地址作为第二级页表项的偏移，找到第三级页表项的起始。就是说第一段地址是这个页在第一级页表中的偏移，第二段是这个页在第二级页表中的偏移地址。利用多级页表减少了整个页表的长度。

6.6 反置页表

对于大地址空间系统，多级页表变得繁琐，让页表项和物理地址空间的大小对应，不让页表项和逻辑地址空间的大小对应。这样进程数目的增加和虚拟地址空间的增大对页表占用空间没影响。
页寄存器：每个帧和一个页寄存器关联，寄存器里有：使用位表示此帧是否被使用；占用页号表明对应的页号p，保护位表明使用方式是读或者写。
页寄存器中的地址转换：CPU生成的逻辑地址如何找对应的物理地址？对逻辑地址做Hash映射，并解决Hash冲突，利用快表缓存页表项，如果出现冲突，遍历所有的对应页表项，查找失败时产生异常。

6.7 段页式存储管理

在段式管理的基础上，给每个段加一级页表，得到段的页表，再得到页的地址。

第七讲实验二物理内存管理

7.1 x86保护模式的特权级

x86的特权级有0，1，2，3，一般只需要0（Kernel）和3（user），有些指令只能在ring 0中执行，CPU在某些情况下也会检查特权级。
段选择子位于段寄存器中，程序在代码段中执行，指令执行会访问代码段和数据段。它的DPL位于段描述符中，来进行特权控制。中断门和陷入门中也有对应的DPL。产生中断和内存访问都有对应的CPL和RPL，进行检查确保当前的操作合法。 RPL处于数据段（DS或ES中最低两位），CPL处于指令代码段中（CS最低两位）。
数字越低特权级越高，数字越高特权级越低。
DPL是要被访问的目标的特权级。访问门时代码段的CPL要小于门的DPL，门的特权级要比较低，执行代码段的特权级比较高，这样才允许通过门（中断陷入什么的）一般特权级的应用程序可以访问处于内核态的操作系统提供的服务；访问段的时候CPL和RPL中的最大值小于DPL，即发出请求的特权级要高于对应目标，DPL的特权级要比较小。

7.2 了解特权级切换过程

通过中断切换特权级。有一个中断门，通过中断描述符表进行切换，如果产生了中断，内核态ring 0中的栈会压入一系列东西（当前执行的程序的堆栈信息SS，ESP，EFLAGS，保存了回去的地址CS，EIP等）以便恢复现场。如何回到ring3？如果是从ring0跳到ring3的，在栈中会存SS（RPL=3）和ESP，用户的ss和内核态的ss不是同一个数据段，这是特权级的转换，内核栈把数据弹出来了。通过构造一个能返回ring3的栈，再通过iret指令把相关信息弹出栈，这时候运行环境已经变成用户态。
从ring3到ring0的转换，建立中断门，一旦产生中断需要保存一些信息。通过对堆栈修改，使其执行完iret后留在ring0执行，修改CS使其指向内核态的代码段。
TSS是特殊段，任务状态段，在内存中，保存了不同特权级的堆栈信息。在全局描述符表中有一个专门指向这个TSS。硬件有一个专门的寄存器缓存TSS中的内容，建立TSS是在pmm.c中。

7.3 了解段/页表

x86内存管理单元MMU
有一系列寄存器和段描述符，寄存器里的信息最高端的十几位作为索引来找全局描述符表（GDT）里的一项，找对应的项，一项就是一个段描述符，描述了地址和基址，base address+EIP这个offset找到最终的线性地址。如果没有页机制的话，线性地址就是物理地址。
MMU放在内存中，每次访问要先查找GDT（段表），靠硬件实现把建立在GDT里的段描述符的相关信息放在一些寄存器中的隐藏部分，缓存了基址和段大小等隐藏信息，放在CPU内部的。
在entry.S中建立了映射机制，lab1建立的是对等映射，而lab2中base_address是 -0xC0000000，虚地址比线性地址大0xC0000000.只是这个用到的映射关系（放在GDT中的信息）不同。

7.4 了解UCORE建立段/页表

一个虚拟地址它分了三块，一个典型的二级页表是32位的地址，第一个是Offset，占了12位，中间的二级页表对应的页表项占了10位，高的页目录项也占了10位。那么高的这10位是用来作为index查找这个页目录表里面的对应的项，这叫PDE，是页目录的entry，PDE记录的是二级页表里面的起始地址。所以说根据PDE里面的信息可以找到Page Table的起始地址。同时根据第二级Table这里面的10位作为index来查这个Page Table对应的项。称之为PTE。这个PTE就是Page Table Entry。存的是这个线性地址它所对应的一个页的起始地址。这一个页大小多其实由它的Offset可以算出来，12位意味着一个页的大小是4k。base_address加上offset得到了地址。
进入保护模式后段机制一定存在，为了保护。
根据地址的前10位找到Page Table的物理地址，中间12位找到PDE，计算物理页的基址。利用PDE和PTE加上offset算出地址。
CR3寄存器保存了页目录地址。 CR0的31位如果置1的话就打开了页机制。
页的基址、页表的基址都是20位，剩下12位存下了一些信息（只读？用户态或内核态）
分配一个4k的页作为页目录的Table，清理这个Page做初始化，建立页表，在页目录表和页表中填好对应信息。0xC0000000到0xF8000000这块空间会映射到物理地址的0x00000000到0x38000000这么一个地址，它的偏移值是0xC0000000，链接时用到的起始地址就是0xC0000000，把0x00000000到0x00100000映射到0x00100000的对等映射，且把CR0的31位置1，即enable了页机制，需要UPDATE GDT，使段机制的不对等映射变成对等映射，又做了取消0x00000000到0x00100000映射的操作。

第八讲虚拟存储概念

8.1 虚拟存储的需求背景

对存储容量的需求，需要容量更大、速度更快、价格更便宜的非易失性存储器。

8.2 覆盖和交换

覆盖：在较小的内存中运行较大的程序，依据程序逻辑结构，将程序划分为若干功能独立的模块，不会同时执行的模块共享同一块内存。必要部分通常是常用功能，常驻内存，可选部分不常用只需要在用到时装入内存。不存在调用关系的部分共享一部分内存。将程序分成多组，每组按照这一组里最大的内存进行分配。开发难度增加，由程序员进行模块划分，确定模块间的覆盖关系；也增加了执行时间，从外存装入覆盖模块。
交换：增加正在运行或需要运行的程序的内存，将暂时不运行的程序放到外存。这是以进程为单位的交换技术。只有当内存空间不够或有不够的可能时才换出。交换区是用来存放所有用户进程的所有内存映像的拷贝。程序换入时采用动态地址映射的方法，重定位。

8.3 局部性原理

把内存中的信息放到外存中来需要准备工作。只把部分程序放到内存中，从而运行比物理内存大的程序，操作系统自动加载而不需要程序猿干预。实现进程在内外存之间的交换，从而获得更多的空闲内存空间。
局部性原理：所谓局部性原理呢是指程序在执行的过程当中在一个较短的时间里，它所执行的指令和指令操作数的地址分别局限于在一定区域里，因为通常情况下我们指令是存在代码段里的，指令所访问的操作数呢通常是存在数据段里的，这两个各是一个地方，那这两个的地方分别局限在一定区域里头。

第一个叫时间局部性，也就是说我一条指令的连续两次执行和一个数据的连续两次访问通常情况下都集中在一段较短的时间里；
空间局部性，我相邻的几条指令访问的相邻的几个数据通常情况下是局限在一个较小的区域里头；
叫分支局部性，一条跳转指令的两次执行很多时候是会跳转到同一个地址的。
如果能判断他们局部的地区在哪，就可以充分利用这种局部性，虚拟存储也具有可行性。

8.4 虚拟存储概念

将不常用的内存块暂存到外存。
装载程序时只需将当前指令所需要的页面加载到内存，指令执行中需要的指令或数据不在内存时处理器通知操作系统将相应的页面调入内存。
基本特征：

不连续性：物理内存分配非连续，虚拟地址空间使用非连续；
大用户空间：提供给用户的虚拟内存可以大于实际的物理内存；
部分交换：只对部分虚拟地址空间进行调入和调出。

硬件支持：页式或短时存储的地址转换机制。
操作系统：管理内存和外存页面或段的换入换出。

8.5 虚拟页式存储

在页式存储管理的基础上增加请求调页和页面置换。当用户程序要装载到内存中时只装入部分页面就启动程序运行，进程在发现运行中需要的代码或数据不在内存中时，发送缺页异常请求，操作系统在处理缺页异常时将外村中相应的页面调入内存，使进程能继续运行。需要一个缺页异常的处理例程。
造成的修改：原来以逻辑页号为序号就可以找到物理帧号，有了这个物理页帧号之后，就能转换出相应的物理地址。现在增加一些标志位：

驻留位：它是表示该页面是否在内存当中，如果是1表示在内存当中，此时一定可以找到它的页帧号，可以转换成物理内存单元的地址；如果它是0，表示这一页在外存中这时候就会导致缺页。
修改位：表示这一页在内存当中是否被修改，这必须是驻留位有效的情况下。这一页如果被修改过，若想把这一页淘汰，必须把内存当中修改的内容写回到外存当中。
访问位：表示是否被访问过，用于页面置换算法；
保护位：可读可写可执行等。

在32位x86系统中，有12位的页内偏移，两个10位的二级页表项，物理地址也是32位，其中20位是物理页帧号。这时使用二级页表。页表项的起始地址是CR3，一个页表项四字节，4k为一页，一页里有1024页表项，刚好是10位。
地址转换：先是一级页表项里头的页号到以及页表中，作为它的偏移找到相应的页表项。这个页表项里有一个第二级页表项的物理页号，这时再加上第二级的页号，第二级页表项里以它页号作为偏移找到相应的页表项，这时就是要访问的物理页面的物理帧号，帧号和偏移加在一起得到你的物理地址。
变化的是页表项内部的东西：前20位的物理页帧号无变化，后边的标志位有变化。用户态标志U表示是否可以在用户态访问；保留位AVL；WT位写出到缓存还是直接写出到内存，CD缓存是否有效。

8.6 缺页异常

在CPU要访问一条指令，load M，去找M对应的表项，如果M无效，抛出异常调用缺页异常服务例程。首先找到对应的一页在外存中的位置，找到了且有空闲页则读进来并修改对应的页表项。
如果空闲页没找到，则根据页面替换算法找到被替换的物理页帧，再判断这个物理页帧是否修改过，如果修改过，就写回。修改各种驻留位。重新执行产生缺页的指令。
外存管理：在何处保存未被映射的页？外存中有对换区。
虚拟页式存储中的外存选择：代码段直接指向可执行文件；动态加载的共享库指向动态库文件；其他段就可以放到对换区中。
有效存储访问时间：访存时间*(1-p) + 缺页异常处理时间*缺页率p

第九讲页面置换算法

9.1 页面置换算法的概念

出现缺页异常时，调入新页面且内存已满时置换页面。尽可能减少页面调入调出次数。把近期不再访问的页面调出。有些页面必须常驻内存，或是操作系统的关键部分，或是要求响应速度的页面，加上一个锁定位。

局部页面置换：置换页面的选择仅限于当前进程占用的物理页面；最优算法、先进先出、最近最久未使用
全局置换算法：选择所有可换出的物理页面

9.2 最优算法、先进先出算法和最近最久未使用算法

最优算法：缺页时计算内存中每个页面的下一次访问时间，选择未来最长时间不被访问的页面。缺页次数最少，但无法实现，无法预知每个页面在下次访问的间隔时间。可以作为置换算法的评测依据。
先进先出算法：选择在内存中驻留时间最长的页面进行置换。维护一个记录所有位于内存中的逻辑页面链表，链表元素按照驻留内存时间排序，链首时间最长。出现缺页时把链首页面进行置换，新加的页面加到链尾。性能差，调出的页面可能是经常访问的，可能出现belady现象。
最近最久未使用算法：选择最长时间没有被引用的页面进行替换，如果某些页面长时间未访问，那在未来可能也不访问。缺页时计算每个逻辑页面上次访问时间。

LRU可能的实现：

页面链表。系统维护一个按最近一次访问时间排序的页面链表，链表首节点是最近刚刚使用过的页面，尾节点是最久未使用的页面。访问内存时，找到相应页面并将其移动到链表之首，缺页时替换尾节点的页面。
活动页面栈，访问时将页号压入栈顶，并将栈内相同页号抽出，缺页时置换栈底页面。开销大！

9.3 时钟置换算法和最不常用算法

时钟置换算法：对页面访问进行大致统计，过去一段时间访问过就不管它，如果没访问过就按照时间踢出去。先对数据结构做了一些改动，页表项里增加了一个访问位，用来描述在过去一段时间里这个页是否被访问过，把这些页面组织成一个环形链表，定义指针在环形链表上进行周期性的循环，这也是我们这个时钟这个词的。指针指向最先调入的页面。访问页面时在页表项中记录页面访问，缺页时从指针处开始顺序查找未被访问的页面进行置换。

装入页面时访问位初始化为0，访问时页面置为1，缺页时，从指针当前顺序检查环形链表，访问位为0则置换，访问位为1，则访问位置为0，指针移动到下一个页面，直到找到可替换的页面。
改进的Clock算法：减少修改页的缺页处理开销。在页表项中加入修改位，并在访问时进行修改，缺页时，修改页面标志位，跳过有修改的页面。如果访问位和修改位都是0，那就直接替换。访问1修改0的改成访问0修改0，访问1修改1的改成访问0修改1，改修改标志的时候并不写出，由系统执行写出。主要修改时考虑了修改的页面，推迟了被修改页面的替换。
最不常用算法（LFU）：每个页面设置一个访问计数，访问页面时访问次数加一，缺页时置换计数最小的页面。可能有开始常用但是之后不常用的，这时需要定期对计数器进行衰减。LRU关注多久未访问，LFU关注访问次数。

9.4 BELADY现象和局部置换算法比较

belady现象是指采用FIFO等算法时，可能出现随着分配的页面增加，缺页次数反而升高的现象。原因是FIFO算法的置换特征与进程访问内存的动态特征矛盾，被他置换出去的页面并不一定是进程近期不会访问的。LRU是没有belady现象的。类似于栈的算法（LRU）一般不会有belady现象。
比较：

LRU依据页面的最近访问时间排序，动态调整；
FIFO依据页面进入内存时间排序，页面进入时间固定不变；
CLOCK是折中，页面访问时不动态调整页面在链表中的顺序，缺页时再把它移动到链表末尾。

9.5 工作集置换算法

全局置换算法之一：工作集置换算法
为进程非配可变数目的物理页面。进程的内存需求时有变化，分配给进程的内存也要在不同阶段变化，全局置换算法需要确定分配给进程的物理页面数量。
CPU利用率和并发进程的关系：

随着并发进程增加CPU利用率增加；
但是之后随着内存吃紧，利用率下降；
进程数少时提高并发进程数，可以提高CPU利用率；
并发进程导致了内存访问增加；
并发进程的内存访问会降低访存的局部性特征，导致了缺页率上升。

工作集是进程当前使用的逻辑页面集合，表示为二元函数（t, delta），t是当前执行时刻，delta是工作集窗口，代表定长页面访问时间窗口。W(t, delta)是当前时刻t前的delta时间窗口的所有访问页面组成的集合。
工作集变化：

进程开始执行时，随着访问新页面逐步建立稳定的工作集；
当内存访问的局部性区域位置大致稳定时，工作及大小也逐步稳定；
局部性区域改变位置时，工作集快速扩张和收缩过渡到下一个稳定值。

令全局置换算法与工作集变化曲线相拟合。
常驻集是进程实际驻留内存的页面集合，工作集是进程在运行中的固有属性，而常驻集是取决于系统分配给进程的物理页面数目和页面置换算法。
常驻集如果包含了工作集，缺页率比较小；工作集发生剧烈变动时，缺页较多；进程常驻集达到一定大小之后，缺页率也不会明显下降。

工作集置换算法
换出不在工作集中的页面。维护一个访存页面链表，访存时换出不在工作集的页面，更新访存链表，缺页时换入页面，更新访存链表。

工作集的大小是变化的。

相对比较稳定的阶段和快速变化的阶段交替出现。

根据局部性原理，进程会在一段时间内相对稳定在某些页面构成的工作集上。

当局部性区域的位置改变时，工作集大小快速变化。

当工作集窗口滑过这些页面后，工作集又稳定在一个局部性阶段。

工作集精确度与窗口尺寸 ∆ 的选择有关。如果 ∆ 太小，那么它不能表示进程的局部特征；如果 ∆ 为无穷大，那么工作集合是进程执行需要的所有页面的集合。

如果页面正在使用，它就落在工作集中；如果不再使用，它将不出现在相应的工作集中。

工作集是局部性原理的近似表示。

如果能找出一个作业的各个工作集，并求出其页面数最大者，就可估计出该进程所需的物理块数。

利用工作集模型可以进行页面置换。工作集页面置换法的基本思想：找出一个不在工作集中的页面，把它淘汰。

9.6 缺页率置换算法

缺页率：缺页次数与内存访问次数的比值，或缺页平均时间间隔的倒数，受到页面置换算法、分配给进程的物理页面数目、页面大小和程序本身的影响。缺页率随着物理页面的增加而降低。
通过调节常驻集的大小，使每个进程的缺页率保持在合理范围内，若进程缺页率过高，则增加常驻集以分配更多物理页面，若进程缺页率过低，则减少常驻集以给其他进程分配更多物理页面。
方法：访存时设置引用位标志，出现缺页时计算从上次缺页时间到现在时间的时间间隔，如果隔的时间比较长，则置换这段时间被没有被引用的页，认为这段时间的缺页率比较低；如果这段时间大于特定的值，则认为这段时间的缺页率较高，则增加常驻集。
进程驻留在内存中的页面是有变化的。与前边的工作集算法的区别主要在于缺页率置换把置换放到缺页中断中完成

9.7 抖动和负载控制

抖动是指进程物理页面较少，不能包含工作集，造成大量缺页，频繁置换，使进程运行速度变慢。主要原因是随着驻留内存进程数目不断增加，分配给每个进程的物理页面数量不断减少，缺页率不断上升。因此，操作系统需要在并发数目和缺页率之间达到一个平衡，选择适当的进程数目和进程需要的物理页面数。
通过调节并发进程数来进行系统负载均衡。
平均缺页间隔时间（MTBF）是否等于缺页异常处理时间（PFST）。间隔大于处理时间则处理是可以完成的，比较好。

第十讲实验三虚拟内存管理

10.1 实验目标：虚存管理

有关虚拟内存管理。提供给比实际物理内存空间更大的虚拟内存空间。完成Page Fault异常和FIFO页替换算法。

10.2 回顾历史和了解当下

Lab1 完成了保护模式和段机制的建立，完成了中断机制，可以输出字符串。
中断描述符表寄存器存了中断门，记录了当产生一个中断时用哪个例程处理这个中断。一旦产生中断，根据它的编号找到IDT，记录了一个offset和一个选择子，这个选择子作为一个索引来查找另外一个表GDT全局描述符表（段表），找到基址，这个基址加上offset形成了中断服务例程的入口地址。
Lab2完成物理内存管理，查找物理内存，建立基于连续物理内存空间的动态内存分配与释放算法，完成了页机制的建立。
页表的起始地址放在CR3寄存器中，页目录表中每一项是一个页目录项，其中的address指向对应页表的起始地址，对页表项，存放着物理页页帧的起始地址，加上页内偏移形成最终地址。
初始化函数在kern_init中，vmm_init。关键数据结构：vma_struct和mm_struct。swap.c和swap.h中有相应说明。

10.3 处理流程、关键数据结构和功能

swap_init：如何建立交换分区并完成以页为单位的硬盘读写。
vmm_init：分配一定物理页，如何建立模拟访问机制访问特定虚拟页。

10.4 页访问异常

产生页访问异常时，调用_alltrap的trap进行处理，调用pgfault_handler，进一步调用do_pgfault，建立一个使用者的虚拟环境，根据缺页异常的地址查找，看是不是硬盘中的一个页，把这一页读到内存中，建立映射关系，这样可以正确访问内存了。重新执行产生缺页异常的指令。

10.5 页换入换出机制

应该换出哪个页？在kern/mm/swap.c中有具体说明。建立虚拟页和磁盘扇区的对应关系：用到了swap_entry_t，其中有24bit代表磁盘扇区的编号，虚拟页编号在页表的index中，磁盘扇区的index可以写到页表项（PTE）中，虚拟页和磁盘扇区的对应也可以放到页表项中。页表项多了一个功能，是虚拟页和磁盘扇区的对应关系，如果present位是0，代表没有映射关系，不存在物理页和虚拟页帧的对应关系，这样就可以代表虚拟页和硬盘扇区的关系。
页替换算法：FIFO、Clock等。
何时进行页换入换出：主动、被动。

第十一讲进程和线程

11.1 进程的概念

进程是一个具有一定功能的程序在一个数据集合中的一次动态执行过程。源代码到可执行文件再到加载到进程地址内存空间（堆、栈、代码段）。进程浩瀚了正在运行的一个程序的所有状态的信息，进程是由：

代码
数据
状态寄存器：CPU状态CR0、指令指针IP等
通用寄存器：AX、BX、CX…
进程占用系统资源：打开文件、已分配内存

特点：

动态性：动态创建
并发性：独立调度并占用处理机运行
独立性：不同进程相互工作不影响
制约性：因访问共享数据和资源或进程间同步产生制约

进程是处于运行状态程序的抽象，程序是一个静态的可执行文件，进程是执行中的程序，是程序+执行状态；同一个程序的多次执行过程对应不同进程；进程执行需要内存和CPU。
进程是动态的，程序是动态的，程序是有序代码的集合，进程是程序的俄执行，进程有核心态和用户态；进程是暂时的，程序是永久的，进程的组成包括程序、数据和进程控制块。

11.2 进程控制块（PCB）

是操作系统控制进程运行的信息集合。操作系统用PCB来描述进程的基本情况和运行变化的过程。PCB是进程存在的唯一标志。

进程创建：生成该进程的PCB；
进程终止：回收PCB；
进程的组织管理：通过对PCB的组织管理实现。

进程控制块内容：

进程标识信息
处理机现场保存：从进程地址空间抽取PC、SP、其他寄存器保存
进程控制信息：调度和状态信息（调度进程和处理机使用情况）、进程间通信信息（通信相关的标识）、存储管理信息（指向进程映像存储空间数据结构）、进程所用资源（进程使用的系统资源，文件等）、有关数据结构链接信息（与PCB有关的进程队列）

进程控制块的组织：

链表：同一状态的进程其PCB组织成一个链表，多个状态对应不同链表；
索引表：同一状态的进程归入一个索引表，由索引指向PCB，多个状态对应多个不同的索引表。

11.3 进程状态

操作系统为了维护进程执行中的变化来维护进程的状态。进程的生命周期分为：

进程创建：创建PCB、拷贝数据。引起进程创建主要有：系统初始化、用户请求创建进程、正在执行的进程执行了创建进程的调用；
进程就绪：放入等待队列中等待运行；
进程执行：内核选择一个就绪进程，占用处理机并执行；
进程等待：进程执行的某项条件不满足，比如请求并等待系统服务、启动某种操作无法马上完成，只有进程自身知道何时需要等待某种事件的发生；
进程抢占：高优先级的进程就绪或进程执行时间片用完；
进程唤醒：被阻塞的进程需要的资源可满足，进程只能被别的进程或操作系统唤醒；
进程结束：把进程执行占用的资源释放，有几种可能：正常、错误退出、致命错误、强制退出。

N个进程交替运行，假定进程1执行sleep()，内核里调用计时器，进程1把当前进程占用寄存器的状态保存，切换进程2，如果计时器到点了，计时器产生中断，保存进程2的状态，恢复进程1的状态。

11.4 三状态进程模型

核心是：

就绪：进程获得了除了处理机之外的所有资源，得到处理机即可运行；
运行：进程正在处理机上执行；
等待：进程在等待某一事件在等待。

辅助状态两种：

创建：一个进程正在被创建，还未被转到就绪状态之前的状态；
结束：进程正在从系统中消失的状态，这是因为进程结束或其他原因所导致。

状态转换：

创建 -> 就绪：进程被创建并完成初始化，变成就绪状态；
就绪 -> 运行：处于就绪状态的进程被调度程序选中，分配到处理机上运行；
运行 -> 结束：进程表示它已经完成或因为出错，当前运行今晨会由操作系统作结束处理；
运行 -> 就绪：处于运行状态的进程在其运行过程中，由于分配给它的处理机时间片用完而让出处理机；
运行 -> 等待：当进程请求某资源且必须等待时；
等待 -> 就绪：进程等待的某事件到来时，它从阻塞状态变到就绪状态；

11.5 挂起进程模型

处于挂起状态的进程映像在磁盘上，目的是减少进程占用内存。

等待挂起：进程在外存并等待某事件的发生；
就绪挂起：进程在外存，但是只要进入内存即可运行；
挂起：把进程从内存转到外存

增加了内存的转换：

等待 -> 等待挂起：没有进程处于就绪状态或就绪状态要求更多内存资源；
就绪到就绪挂起：有高优先级等待进程（系统认为很快就绪）和低优先级就绪进程；
运行 -> 就绪挂起：对抢先式分时系统，当有高优先级等待挂起进程因事件出现而进入就绪挂起；

从外存转到内存的转换：激活

就绪挂起 -> 就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程；
等待挂起 -> 等待：进程释放了足够内存，并有高优先级的等待挂起进程；

状态队列：有操作系统维护一组队列，表示系统所有进程的当前状态。
根据进程状态不同，进程PCB加入不同队列，进程状态切换时，加入不同队列。

11.6 线程的概念

为什么要引入线程
在进程内部增加一类实体，满足实体之间可以并发执行且实体之间可以共享相同的地址空间。线程是进程的一部分，描述指令流执行状态，它是进程中指令执行流的最小单元，是CPU调度的单位。这种剥离为并发提供了可能，描述了在进程资源环境中的指令流执行状态；进程扮演了资源分配的角色。
原来只有一个指令指针，现在有多个堆栈和指令指针。线程=进程-共享资源。
但是如果一个线程有异常，会导致其所属进程的所有线程都崩。
比较
进程是资源分配单位，线程是CPU调度单位；
进程有一个完整的资源平台，线程只独享指令流执行的必要资源，如寄存器和栈；
线程具有就绪、等待和运行三种基本状态和其转移关系；
线程能减少并发执行的时间和空间开销：

线程创建时间短；
线程的终止时间比进程短；
同一进程的线程切换时间比进程短；
由于同一进程的各个线程共享内存和文件资源，可不通过内核进行直接通信。

11.7 用户线程

三种实现方式：

用户线程：在用户空间实现，通过用户级的线程库函数完成线程的管理。在操作系统内核中仍然只有进程控制块来描述处理机的调度的情况，操作系统并不感知应用态有多线程的支持，多线程的支持是用户的函数库支持的。在应用程序内部通过构造相应的线程控制块
来控制一个进程内部多个线程的交替执行和同步。
这种方法不依赖操作系统内核，用于不支持线程的多线程的操作系统。每个进程有私有的线程控制块(TCB)，TCB由线程库函数维护；同一进程的用户线程切换速度快，无需用户态/核心态的切换，且允许每个进程有自己的线程调度算法。
缺点就是不支持基于线程的处理机抢占，除非当前运行的线程主动放弃CPU，他所在进程的其他线程无法抢占CPU。
POSIX Pthreads、Math C-threads、Solaris threads
内核线程：在内核中实现，Windows、Solaris、Linux
轻量级进程：在内核中实现，支持用户进程。

11.8 内核线程

内核通过系统调用完成的线程机制。由内核维护PCB和TCB，线程执行系统调用而阻塞不影响其他线程，以线程为单位的进程调度会更合理。
轻权进程：内核支持的用户线程，一个进程有多个轻量级进程，每个轻权进程由一个单独的内核线程来支持。在内核支持线程，轻权进程来绑定用户线程。
用户线程与内核线程的对应关系：一对一、多对一、多对多。

第十二讲进程控制

12.1 进程切换

上下文切换，暂停当前运行的进程，从当前运行状态转变成其他状态，调度另一个进程从就绪状态变成运行状态，在此过程中实现进程上下文的保存和快速切换。维护进程生命周期的信息（寄存器等）。

进程控制块PCB：内核为每个进程维护了对应的PCB，将相同状态的进程的PCB放置在同一个队列中。

ucore中的进程控制块结构proc_struct：

进程ID、父进程ID，组ID；
进程状态信息、地址空间起始、页表起始、是否允许调度；
进程所占用的资源struct mm_struct* mm；
现场保护的上下文切换的context；
用于描述当前进程在哪个状态队列中的指针，等。

ucore的切换流程：开始调度 -> 清除调度标志 -> 查找就绪进程 -> 修改进程状态 -> 进程切换switch_to()。
switch_to用汇编写成。。。

12.2 进程创建

Windows进程创建API：CreateProcess
Unix进程创建系统调用：fork/exec，fork()把一个进程复制成两个进程，exec()用新程序重写当前进程。

fork()的地址空间复制：fork调用对子进程就是在调用时间对父进程地址空间的一次复制。执行到fork时，复制一份，只有PID不同。系统调用exec()加载新程序取代当前运行的程序。加载进来后把代码换掉。

ucore中的do_fork：分配进程控制块数据结构、创建堆栈、复制内存数据结构、设置进程标识等。操作系统没有新的任务执行，则创建空闲进程，在proc_init中分配idleproc需要的资源，初始化idleproc的PCB。

fork的开销昂贵，在fork中内存复制是没用的，子进程将可能关闭打开的文件和连接，所以可以将fork和exec联系起来。产生了vfork，创建进程时不再创建一个同样的内存映像，用时再加载，一些时候称为轻量级fork。这时子进程应立即执行exec。现在使用写时复制技术。

12.3 进程加载

应用程序通过exec加载可执行文件，允许进程加载一个完全不同的程序，并从main开始执行。不同系统加载可执行文件的格式不同，并且允许进程加载时指定启动参数（argc,argv），exec调用成功时，它与运行exec之前是相同的进程，但是运行了不同的程序，且代码段和堆栈重写。主要是可执行文件格式的识别，有sys_exec、do_execv、load_icode函数。

ucore中第一个用户态进程是由proc_init创建的，执行了init_main创建内核线程，创建了shell程序。

12.4 进程等待与退出

父子进程的交互，完成子进程的资源回收。

子进程通过exit()向父进程返回一个值，父进程通过wait()接受并处理这个返回值。wait()父进程先等待，还是子进程先做exit()，这两种情况会导致它下面的处理有一些区别。

如果有子进程存活，也就是说父进程创建的子进程还有子进程，那这时候父进程进入等待状态，等待子进程的返回结果，父进程先执行wait，等到子进程执行的时候它执行exit()，这是exit ()是在wait之后执行的。这时候，子进程的exit()退出，唤醒父进程，父进程由等待状态回到就绪状态，父进程就处理子进程的返回的这个返回值，这是wait在前exit()在后的情况。

如果不是这样那就有一种情况，就是有僵尸子进程等待，就是子进程先执行exit()，这时它返回一个值，等待父进程的处理，exit()在前，如果子进程还一直处在这个等待的状态，在这里等待父进程的处理，父进程的wait就直接返回，如果有多个的话就从其中一个返回它的值。

进程的有序终止exit()，完成资源回收。

调用参数作为进程的结果；
关闭所有打开的文件等占用资源；
释放内存，释放进程相关的内核数据结构；
检查父进程是否存活，如存活则保留结果的值直到父进程需要他。
清理所有等待的僵尸进程。

第十三讲实验四内核线程管理

13.1 总体介绍

了解内核线程创建执行的管理过程。了解内核线程的切换和基本调度过程，对TCB充分了解。

13.2 关键数据结构

struct proc_struct：TCB

pid和name代表了标识符。
state、runs、need_reshed代表了状态和是否需要调度
cr3不太需要，因为共用进程的页表
kstack代表了堆栈
mm_struct不太需要，在ucore的统一管理下
context是通常说的上下文，基本都是寄存器，代表了当前线程的状态
trap_frame代表中断产生时的信息（硬件保存）、段寄存器的信息（软件保存）
一些list，父进程的信息和线程控制块的链表
基于hash的list，查找对应的线程比较快

13.3 执行流程

kern_init最开始初始化，proc_init完成一系列的创建内核线程并执行。

创建第0号内核线程idleproc：

alloc_proc创建TCB的内存块
-init idle_proc，设置pid、stat、kstack等

创建第1个内核线程：

initproc：
keep trapframe调用了do_fork，copy_thread等，如何跳到入口正确执行？是用户态还是内核态？
init_proc
init kernel stack，可以放到两个list中执行了
开始调度执行
找到线程队列中哪个是处于就绪的，切换switch kstack、页表、上下文，根据trapframe跳到内核线程的入口地址，开始执行函数。

13.4 实际操作

关注proc_init创建第0、1号线程。switch_to完成两个内核线程的切换。

第十四讲实验五用户进程管理

14.1 总体介绍

第一个用户进程如何创建、进程管理的实现机制、系统调用的框架实现。
构造出第一个用户进程：建立用户代码/数据段 —-> 创建内核线程 —-> 创建用户进程“壳” —-> 填写用户进程 —-> 执行用户进程(特权级转换) —-> 完成系统调用 —-> 结束用户进程(资源回收)

14.2 进程的内存布局

内核虚拟内存布局有一部分是对实际物理空间的映射，0xC0000000到0xF8000000，映射为物理空间。一个Page Tabel，0xFAC00000到0xB0000000，一开始只是管理内核空间的映射关系，有了用户进程后，页表需要扩展。

进程虚拟内存空间：
Ivalid Memory
User Stack——————0xB0000000
………..
User Program & Heap—-0x00800000
Invalid Memory
User STAB Data(optional，调试信息)
Invalid Memory

Invalid Memory一旦访问为非法，确保访问到这些是产生page fault，使之不能随意访问。

14.3 执行ELF格式的二进制代码-do_execve的实现

do_execve建好一个壳并把程序加载进来。本实验用到一个PCB（process control block），其实是跟上一个实验的TCB一样的。

首先，把之前的内存空间清空，只留下PCB，换成自己的程序。把cr3这个页表基址指向boot_cr3内核页表；把进程内存管理区域清空，对应页表清空，导致内存没有了；load_icode加载执行程序。

14.4 执行ELF格式的二进制代码-load_icode的实现

前边已经把内存管理清空了，先创建一个新内存管理空间mm_create和新页表setup_pgdir；填上我执行代码的内容，找到要加载的程序的代码段和数据段，根据代码段和数据段的虚拟地址通过mm_map完成对合法空间的建立；从程序的内存区域拷贝过来，建立物理地址和虚拟地址的映射关系；准备all_zero的内存；设置相应堆栈空间（用户态空间），使用mm_map建立；把页表的起始地址换成新建好的页表的起始地址。

完成trapframe的设置。trapframe保存了打断的中断状态保存，完成特权级转变，从kernel转换到user。

x86特权级：从ring 0 —-> ring 3，一个ring 0栈空间，构造一个信息使得执行iret时能回到用户态，重新设置ss和cs，从ring0到ring3。

用户进程有两个栈，用户栈和内核栈，通过系统调用转化。

14.5 进程复制

父进程如何构造子进程？
一个函数叫do_fork，是一个内核函数，完成用户空间的拷贝。首先，父进程创建进程控制块，初始化kernel stack，分配页空间和内核里的虚地址。copy_mm为新进程建立新虚存空间。copy_range拷贝父进程的内存到新进程。拷贝父进程的trapframe到新进程。添加新的proc_struct到proc_list并唤醒新进程。执行完do_fork后父进程得到子进程的pid，子进程得到0。

14.6 内存管理的copy-on-write机制

进程A通过do_fork创建进程B，二者重用一段空间，使得空间占用量大大减少，如果是只读的话没问题。一旦某进程做了写操作，因为页表设置成只读，则产生page_fault，触发copy-on-write机制，真正为子进程复制页表。进程创建的开销大大减小，且有效减少空间。

一个物理页可能被多个虚拟页引用，这个个数很重要，因为在进程运行时可能会出现换入换出，如何进行有效换入换出，有可能那个页既在内存中也在虚存中。

dup_mmap完成内存管理的复制。

处理机调度

处理机调度概念

进程切换是CPU资源的当前占用者的切换，保存当前进程在PCB中的执行上下文（CPU状态），恢复下一个进程的执行上下文。

处理机调度是从就绪队列中找一个占用CPU的进程，从多个可用CPU中挑选就绪进程可使用的CPU资源。

调度准则

调度时机

操作系统维护进程的状态序列。进程从运行状态切换到等待状态，这样CPU就空闲了，或者进程被终结了，CPU又空闲了。这两种情况对应着非抢占系统，当前进程主动放弃CPU。对可抢占系统，中断请求被服务例程响应完成，或当前进程因为时间片用完时会被抢占，进程从等待切换到就绪，这时更急迫的想占用CPU，也会发生抢占。

调度策略

进程在CPU计算和IO操作间交替，在时间片机制下，进程可能在结束当前CPU计算之前就被迫放弃CPU。

CPU使用率：CPU处于忙状态的时间百分比。

吞吐率：单位时间内完成的进程数量

周转时间：进程从初始化到结束（包括等待）的时间

等待时间：进程在就绪队列中的时间

响应时间：从提交请求到产生相应所花费的时间

调度算法希望“更快”的服务。

响应时间目标：

减少相应时间，及时处理输入请求
减少平均响应时间的波动，提高可预测性
低延迟调度改善了交互体验

吞吐量目标：

增加吞吐量，减少开销（操作系统开销，上下文切换）
系统资源的高效利用（CPU、IO）
减少等待时间，提高响应性能和吞吐量性能
吞吐量是系统的计算带宽

公平性目标：

保证每个进程占用相同的CPU时间
公平通常会增加响应时间

先来先服务、短进程优先和最高响应比优先调度算法

先来先服务

按照就绪队列的先后顺序排列，进程进入等待或结束状态时，就绪队列中的下一个进程占用CPU。

周转时间：每个进程的平均总时间（等待+执行）

优点：简单，排队依据容易获得。

缺点：平均等待时间波动大，排队位置对算法影响大，IO和CPU资源利用效率低。

短进程优先

考虑进程的特征，选择就绪队列中执行时间最短进程占用CPU进入运行状态。它具有最好的平均周转时间。

但可能导致饥饿，连续的短进程会使长进程无法获得CPU资源。且需要预知未来，可以用历史执行时间预估未来的执行时间。

最高响应比优先

考虑进程在就绪队列中的等待时间。选择就绪队列中响应比R最高的进程。R = (w + s) / s，w是等待时间，s是执行时间。这种算法基于短进程优先算法，不可抢占，关注了进程等待时间，以防止无限等待。

时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

时间片轮转

时间片是分配处理机资源的基本时间单元，各个进程占用一个时间片，仍按照先来先服务策略，时间片结束时按照先来先服务切换到下一个就绪进程，每隔(n-1)个时间片进程执行一个时间片。

时间片太大的话，等待时间过长，退化成先来先服务；若太短，产生了大量上下文切换，影响系统吞吐量。

这时需要选择一个合适的时间片长度。

多级反馈队列

就绪队列排成多个子队列，不同队列可以有不同算法，进程可以在队列之间转换。队列间的调度可以采用时间片方法。

多级反馈队列：进程在不同队列间移动的多级队列算法。时间片大小随优先级级别增加而增加，如进程在当前的时间片没有完成，则降到下一个优先级。CPU密集型的进程优先级下降很快，这样时间片会增大，IO密集型的则优先级上升。

公平共享调度算法

注重资源访问的公平，一些用户比另一些用户重要，保证不重要的组无法垄断资源。未使用的资源按照比例分配，没有达到资源使用率目标的组获得更高的优先级。

uCore的调度队列run_queue

struct run_queue{
	list_entry_t run_list;
	unsigned int proc_num;
	int max_time_slice;
	list_entry_t rq_link;
}

实时调度和多处理器调度

实时调度对时间有要求，实时操作系统的正确性以来其时间和功能两方面，其性能指标是时间约束的及时性。

周期实时任务：一系列相似任务，任务有规律的重复，周期p=任务请求时间间隔，执行时间e=最大执行时间，使用率U=e/p。

硬实时是指错过任务时限会导致灾难性或非常严重的后果，必须验证，在最坏情况下能满足时限。软实时是指尽量满足任务时限。

可调度性：一个实时操作系统能满足任务时限要求。需要确定实时任务的执行顺序。静态/动态优先级调度。

速率单调调度算法（静态）：通过周期安排优先级，周期越短优先级越高，执行周期最短的任务；

最早截止时间优先算法（动态）：截止时间越早优先级越高，执行截止时间最早的任务。

多处理器调度

针对多个处理机，一条系统总线连接多个物理CPU，一个CPU可能有几个逻辑CPU，处理机之间可以负载共享。

对阵多处理机（SMP）调度：每个处理器运行自己的调度程序，调度程序对共享资源的访问需要同步。

静态进程分配：进程开始执行到结束都被分配到一个固定的处理机上，每个处理机都有自己的就绪队列，调度开销小，但各个处理机可能忙闲不均。

动态进程分配：进程在执行中可以分配到任意空闲处理机执行，所有处理机共享一个公共的就绪队列，调度开销大，各个处理机的负载是均衡的。

优先级反置

操作系统中出现高优先级进程长时间等待低优先级进程所占用的资源，而导致高优先级进程长时间等待的现象。

优先级继承：占用资源的低优先级进程继承申请资源的高优先级进程的优先级。只有占有资源的低优先级进程被阻塞时才能提高占有资源进程的优先级。

优先级天花板协议：占有资源进程的优先级和所有可能申请该资源的进程的最高优先级相同，不管是否发生等待，都提升占有资源进程的优先级。优先级高于系统中所有被锁定的资源的优先级上限，任务执行临界区就不会被阻塞。

实验六调度器

16.1 总体介绍和调度过程

在lab5中，完成了用户进程的管理。lab6中完成了调度的初始化和调度过程。
实现一个调度类，绑定调度类（类似于多态或重载），设定调度点，触发调度时间，调整调度参数和调用调度算法，实现选择新进程和完成进程切换。

把当前进程放到就绪队列中，在就绪队列中选取一个适合的进程，出队然后完成切换。

16.2 调度算法支撑框架

调度点：出发做调度相关的工作

位置	原因
proc.c:do_exit	用户线程执行结束，主动放弃CPU
proc.c:do_wait	用户线程等待着子进程结束，主动放弃CPU
proc.c:init_main	Init_porc内核线程等待所有用户进程结束；所有用户进程结束后回收系统资源
proc.c:cpu_idle	idleproc内核线程等待处于就绪态的进程或线程，如果有选择一个并切换
sync.h:lock	进程无法得到锁，则主动放弃CPU
trap.c:trap	修改当前进程时间片，若时间片用完，则设置need_resched为1，让当前进程放弃CPU

进入/离开就绪队列的机制：

抽象数据结构，可以不是队列；
可根据调度算法的需求采用多种数据结构

schedule是一个总控函数，如果当前进程是 RUNNABLE会调用sched_class_enqueue，放到就绪队列中。

16.3 时间片轮转调度算法（RR调度算法）

前边介绍完成一个sched_class，

RR_init{
list_init;
run_queue->proc_num = 0;
}

在产生时钟中断时调用
RR_proc_tick{
if(proc->time_slice > 0)
proc->time_slice —;
if(proc->time_slice == 0)
proc->need_resched = 1;
}
一旦标志位为1，则说明需要调度了

当有一个进程需要进队列，则调用list_add_before，如果要选择一个进程，则选择一个尾list_next

16.4 Stride调度算法

如果有三个进程，每个进程有2个属性，stride表示现在执行到什么地方，数字大小表示执行进度；pass表示一次前进的步数。

选择当前步长最小的一个进程，执行目标是当前步长加path。

它是基于优先级的且每一步的调度策略是特定的。

可以使用priority_queue实现，又可以用Skew heap（斜堆）的优先队列实现。

stride在不停累加下如何正确判断最大最小？uint32_t！

第十七讲同步互斥

背景

独立进程：不和其他进程共享资源或状态，具有确定性（输入决定结果）；可重现（能够重现起始条件）；调度顺序不重要。

并发进程：多个进程之间有资源共享；不确定性；不可重现。某些情况下调度的不一致会造成结果的不一致，也可能出现不可重现性。程序错误也可能是间歇性发生的。

进程需要与计算机中的其他进程和设备合作。有几个好处：

共享资源。多个用户使用同一个计算机；
提高速度。IO和计算可以重叠；程序可划分为多个模块放在多个处理器上并行执行；
模块化。将大程序分解成小程序。

并发创建新进程时的标识分配：程序调用fork()创建进程，操作系统需要分配一个新的且唯一的进程ID，在内核中，这个系统调用会执行new_pid = next_pid++。

原子操作是一次不存在任何中断或失败的操作。要么成功要么不执行，不会出现部分执行的情况。操作系统需要利用同步机制在并发执行的同时，保证一些操作是原子操作。

现实生活中的同步问题

利用原子操作实现一个锁。

Lock.Acquire()
- 在锁被释放前一直等待，然后获得锁；
- 如果两个线程都在等待同一个锁，那如果锁被释放了，只有一个进程能得到锁
Lock.Release()
- 解锁并唤醒任何等待中的进程。
过程：
- 进入临界区
- 操作
- 退出临界区

进程之间的交互关系：相互感知程度。

相互不感知（完全不了解其他进程）：独立
间接感知（双方与第三方交互）：通过共享合作
直接感知（直接交互，如通信）：通过通信合作

可能会出现如下几种：

互斥：一个进程占用，则其他进程不能使用
死锁：多个进程各自占用部分资源，形成循环等待
饥饿：其他进程轮流占用资源，一个进程一直得不到资源

临界区和禁用硬件中断同步方法

临界区是互斥执行的代码，进入区检查进程进入临界区的条件是否成立，进入之前设置相应“正在访问临界区”的标志；退出区清除“正在访问临界区”标志。

临界区访问规则：

空闲则入：没有进程在临界区时任何进程可以进入；
忙则等待：有进程在临界区，则其他进程均不能进入临界区；
有限等待：等待进入临界区的进程不能无线等待；
让权等待：不能进入临界区的进程，需要及时释放CPU；

实现方法：

禁用硬件中断：没有中断和上下文切换，因此没有并发，硬件将中断处理延迟到中断被启用之后，现在计算机体系结构都提供指令来实现禁用中断，进入临界区时禁止所有中断，退出临界区时使能所有中断。这种办法有局限性，关中断之后进程无法停止，也可能导致其他进程处于饥饿状态；临界区可能很长，无法确定相应中断所需的时间。

基于软件的同步方法

软件方法：两个线程，T0和T1，线程可以通过共享一些共有变量来同步行为。
- 采用共享变量，设置一个共享变量表示允许进入临界区的线程；
- 设置一个共享变量数组，描述每个变量是否在临界区中，先判断另一个线程的flag是否是1，如果可以进入了，设置自己的flag；可能会同时等待或同时进入；
- Peterson算法：turn表示该哪个进程进入临界区，flag[]表示进程是否准备好进入临界区。在进入区进程i要设置flag[i]=true，且turn=j，判断（flag[i] && turn==j），如果j没有申请进入，则i直接进去没问题。如果j也申请了，看谁先向trun里写数据，谁先写谁进入，由总线仲裁决定先后顺序！
- N线程时，采用Eisenberg和McGuire算法，采用一个处理循环。
- 基于软件的方法很复杂，是一个忙等待

高级抽象的同步方法

借用操作系统的支持采用更高级的抽象方法，例如，锁、信号量等，用硬件原语来实现
锁：一个二进制变量（锁定，解锁），Acquire和Release，使用锁控制临界区访问。
原子操作指令：CPU体系结构中一类特殊的指令，把若干操作合成一个原子操作，不会出现部分执行的情况
- 测试和置位（TS），从内存中读取，测试值是否为1并返回T/F，内存单元置为1。
- 交换指令：交换内存中的两个值。

使用TS指令实现自旋锁：

class Lock {
	int value = 0;
}
Lock::Acquire() {
	while(test_and_set(value))
		; // spin
}
Lock::Release() {
	value = 0;
}

用TS指令把value读出来，向里边写入1。

如果锁被释放，那么TS指令读取0并将值设置为1
- 锁被设置为忙并且需要等待完成
如果锁处于忙状态，那么TS指令读取1并将指令设置为1
- 不改变锁的状态并且需要循环

无忙等待锁：

class Lock {
	int value = 0;
	WaitQueue q;
}
Lock::Acquire() {
	while(test_and_set(value)){
		add this TCP to wait queue
		schedule();
	}
}
Lock::Release() {
	value = 0;
	remove one thread t from q
	wakeup(t)
}

原子操作指令锁的特征：

优点：
- 适用于单处理器或共享内存的多处理器中任意数量的进程
- 支持多临界区
缺点：
- 忙等待的话占用了CPU时间
- 可能导致饥饿，进程离开临界区时有多个等待进程的话？
- 可能死锁，低优先级的进程占用了临界区，但是请求访问临界区的高优先级进程获得了处理器并等待临界区。

第十八讲信号量与管程

信号量

多线程的引入导致了资源的竞争，同步是协调多线程对共享数据的访问，在任何时候只能有一个线程执行临界区代码。

信号量是操作系统提供的协调共享资源访问的方法，软件同步是平等线程间的一种同步协商机制。信号量是由OS负责管理的，OS作为管理者，地位高于进程。用信号量表示一类资源，信号量的大小表示资源的可用量。

信号量是一种抽象数据类型，由一个整型变量（共享资源数目）和两个原子操作组成。

P()（荷兰语尝试减少）
- sem减一
- 如sem<0，进入等待，否则继续
V()（荷兰语增加）
- sem加一
- 如sem<=0，唤醒一个等待进程

信号量是被保护的整型变量，初始化完成后只能通过PV操作修改，是由操作系统保证PV操作是原子操作的。

P操作可能阻塞，V操作不会阻塞。P操作中sem可以等于0，但是如果小于0的话，说明我没有资源了，把这个进程放入等待队列，并且阻塞。退出时执行V操作，如果sem++后还小于0，则说明还有等着的，就把一个进程唤醒开始执行。

class Semaphore{
	int sem;
	WaitQueue q;
}
Semaphore::P(){
	sem --;
	if(sem<0){
		Add this thread t to q;
		block(p)
	}
}
Semaphore::V(){
	sem++;
	if(sem<=0){
		remove a thread t from q;
		wakeup(t)
	}
}

它的原子性是操作系统保证的，执行不会被打断。

信号量使用

两种：二进制信号量，资源数目是0或1；资源信号量，资源数目为任意非负值。

一种是临界区的互斥访问。每类资源设置一个信号量，对应一个临界区，信号量初值为1，

mutex = new Semaphore(1)

mutex->P();
Critical Section
mutex->V()

第一个进程进来之后，mutex是0了，第二个进程再执行到P操作时，mutex变成-1，则会等待。第一个进程执行结束后，执行V操作，-1变成0，这时候唤醒第二个进程。

必须成对使用P()和V()操作。P()保证互斥访问，V()操作保证使用后及时释放。

一种是条件同步，初值设置为0。事件出现时设置为1。这个事件就相当于是一种资源。

1	condition = new Semaphore(0)

生产者-消费者：一个或多个生产者在生成数据后放在缓冲区总，单个消费者从缓冲区中取出数据，任何时刻只能有一个生产者或消费者可访问缓冲区（互斥关系），也就是缓冲区是一个临界区。缓冲区空时必须等待生产者（条件同步），缓冲区满时生产者必须等待消费者（条件同步）。

三个信号量：二进制信号量mutex描述互斥关系；资源信号量fullBuffer和emptyBuffer代表了条件同步关系。

刚开始时缓冲区都是空的，所以fullBuffers为0，emptyBuffers为n

class BounderBuffer{
	mutex = new Semaphore(1);
	fullBuffers = new Semphore(0);
	emptyBuffers = new Semphore(n);
}

mutex实现了对缓冲区的互斥访问，但是只是这样是不够的，先检查是否有空缓冲区，有的话则检查是否有另外的消费者占用缓冲区。

BounderBuffer::Deposit(c){
	emptyBuffers->P();
	mutex->P();
	Add c to the buffer
	mutex->V();
	fullBuffers->V();//生产者写了之后就释放一个资源
}
BounderBuffer::Remove(c){
	fullBuffers->P();
	mutex->P();
	Remove c from buffer
	mutex->V();
	emptyBuffers->V();//消费者用了一个之后释放一个
}

管程

在管程内部使用了条件变量，管程是一种用于多线程互斥访问共享资源的程序结构，采用了面向对象的方法，简化了线程间的同步控制，在任意时刻最多只有一个线程执行管程代码。正在管程中的线程可临时放弃管程的互斥访问，等待事件出现时恢复。

收集现在要同步的进程之间共享的数据，放到一起处理。在入口加一个互斥访问的锁，任何一个线程到临界区后排队，挨个进入。管理共享数据的并发访问。需要共享资源时对应相应的条件变量，使用管程中的程序。

条件变量是管程内的等待机制，进入管程的线程因资源占用而进入等待，每个条件变量表示一种等待原因，对应一个等待队列。两个操作：

Wait()：将自己阻塞到等待队列中，唤醒一个等待者或释放管程的互斥访问。

Signal()：将等待队列中的一个线程唤醒；如果等待队列为空，则相当于空操作。

Class Condition{
	int numWaiting = 0;
	WaitQueue q;
}
Condition::Wait(lock){
	numWaiting ++;
	Add this thread t to q;
	release();
	schedule();
	require(lock);
}
Condition::Signal(){
	if(numWaiting > 0){
		Remove a thread t from q;
		wakeup(t);
		numWaiting --;
	}
}

numWaiting为正表示有线程处于等待状态；把它自己放到等待队列中，释放管程使用权，开始调度。在Signal中，把一个进程从等待队列中拿出来，开始执行，numWaiting减一，等待的线程数目减少。

用信号量解决生产者-消费者问题的话，生产者消费者各对应一个函数，其他地方要使用的话直接调用这两个函数即可。首先放到一个管程里，这是由管程进入的申请和释放，如果没有空的，就在条件变量上等待。

class BoundedBuffer{
	...
	Lock lock;
	int count = 0;
	Condition notFull, notEmpty;
}
BoundedBuffer::Deposit(c){
	lock->Acquire();
	while(count == n)
		notFull.Wait(&lock);
	Add c to the buffer;
	count ++;
	notEmpty.Signal();
	lock->Release();
}
BoundedBuffer::Remove(c){
	lock->Acquire();
	while(count == 0)
		notEmpty.Wait(&lock);
	Remove c from buffer;
	count --;
	notFull.Signal();
	lock->Release();
}

管程可以把PV操作集中在一个函数里。

哲学家就餐问题

#define N 5
semphore fork[N];
void philosopher(int i){
	while(TRUE){
		think();
		if(i%2 == 0){
			P(fork[i]);
			P(fork[(i+1)%N]);
		} else{
			P(fork[(i+1)%N]);
			P(fork[i]);
		}
		eat();
		V(fork[i]);
		V(fork[(i+1)%N]);		
	}
}

读者-写者问题

共享数据的两种使用者：读者只读取数据，不修改；写者读取和修改数据。

有三种情况：

读读允许：同一时刻允许多个读者同时读
读写互斥：没有读者时写者才能写，没有写者时读者才能读
写写互斥：没有其他写者时写者才能写

用信号量描述每个约束。信号量WriteMutex是控制读写操作的互斥，初始化为1.读者计数Rcount是对正在读操作的读者数目，初始化为0。信号量CountMutex控制对读者计数的互斥修改，初始化为1。
Writer：

1
2
3

P(WriteMutex);
	write();
V(WriteMutex);

Reader:

P(CountMutex);
	if(Rcount == 0)
		P(WriteMutex);
	++Rcount;
V(CountMutex);
read();
P(CountMutex);
	--Rcount;
	if(Rcount == 0)
		V(WriteMutex);
	++Rcount;
V(CountMutex);

管程实现读者-写者问题：

Database::Read(){
	StartRead(); 
	//Wait until no writers;
	read database;
	DoneRead();
	//checkout - wakeup waiting writers;
}

Database::Write(){
	Wait until no reader/writer;
	write database;
	checkout - wakeup waiting reader/writer
}

状态变量。正在读和正在写只有一个大于等于0

AR = 0;  # of active reader
AW = 0;  # of active writer
WR = 0;  # of waiting reader
WW = 0;  # of waiting writer
Lock lock;
Condition okToRead, okToWrite

Private Database::StartRead(){
	lock.Acquire();
	while(AW + WW > 0){//写者优先
		WR++;
		okToRead.wait(&lock);
		WR--;
	}
	AR++;
	lock.Release()
}

Private Database::DoneRead(){
	lock.Acquire();
	AR --;
	if(AR==0 && WW>0) //没有读者，写者在等
		okToWrite.Signal();
	lock.Release();
}

Private Database::StartWrite(){
	lock.Acquire();
	while(AW + AR > 0){//有正在写的写者或正在读的读者
		WW++;
		okToWrite.wait(&lock);
		WW--;
	}
	AW++;
	lock.Release()
}

Private Database::DoneWrite(){
	lock.Acquire();
	AW --;
	if(WW>0) //写者优先
		okToWrite.Signal();
	else if(WR > 0)
		okToRead.broadcase();
	lock.Release();
}

第十九讲实验七同步互斥

总体介绍

底层支撑

定时器：进程睡眠，进入等待状态（do_sleep）。可以添加一个timer。

时钟中断时会遍历timer链表，看哪个进程的定时器到期了。

typedef struct{
	unsigned int expires;
	struct proc_struct* proc;
	list_entry_t timer_link;
} timer_t;

屏蔽中断完成了互斥的保护，使得这个进程不会被调度或打断。有一个Eflag寄存器，有一个bit叫做Interrupt Enable Flag，这个flag如果置成1，当前允许中断，置成0表示不允许中断。两个指令CLI和STI分别屏蔽中断和使能中断。uCore中使用local_intr_save和local_intr_restore封装。

等待项和等待队列：

typedef struct {
	struct proc_struct* proc;
	uint32_t wakeup_flags;//等待的原因
	wait_queue_t* wait_queue;//等待项在哪个队列中
	list_entry_t wait_link;
} wait_t
typedef struct {
	list_entry_t wait_head;
} wait_queue_t;

信号量设计实现

class Semaphore{
	int sem;
	WaitQueue q;
}
Semaphore::P(){
	sem --;
	if(sem<0){
		Add this thread t to q;
		block(t);
	}
}
Semaphore::V(){
	sem++;
	if(sem<=0){
		Remove a thread t from q;
		wakeup(t);
	}
}

管程和条件变量设计实现

typedef struct monitor{
	semaphore_t mutex;
	semaphore_t next;
	int next_count;
	condvar_t *cv;
}

哲学家就餐问题

第十九讲实验七同步互斥

第二十讲死锁和进程通信

死锁概念

由于竞争资源或通信关系，两个或更多线程在执行中弧线，永远相互等待只能由其他进程引发的事件。

进程访问资源的流程：资源类型有R1、R2、R3等，每类资源Ri有Wi个实例，进程访问资源时先申请空闲的资源，再占用，最后释放资源。

可重用资源是不能被删除且在任何时刻都只能有一个进程使用，一个进程释放之后其他进程就可以使用了，比如CPU，文件、数据库等，可以被多个进程交替使用。可能出现死锁。

消耗资源：一个进程创建，并有其他进程使用，比如消息等，可能出现死锁。

资源分配图描述了资源和进程之间的分配和占用关系，是一个有向图。一类顶点是系统中的进程，另一类顶点是资源；一类有向边是资源请求边，另一类有向边是资源分配边。如果有循环等待的话，就会出现死锁。但是有循环也可能不会出现死锁。

出现死锁的条件：

互斥：任何时刻只能由一个进程使用一个资源实例，如果资源是共享的不会互斥的则不会死锁；
持有并等待：进程保持至少一个资源并正在等待获取其他进程持有的资源；
非抢占：资源只在进程使用后自愿放弃，不可以强行剥夺；
循环等待：存在等待进程集合，0等1，1等2，。。。n-1等n，n等0，类似这样。

死锁处理方法

死锁预防：确保系统永远不会进入死锁状态，四个必要条件的任何一个去掉都可以避免死锁，但是这样的话资源利用率低；
死锁避免：在使用前进行判断，只允许不会出现死锁的进程请求资源；
死锁检测和恢复：在检测到死锁后，进行恢复；
通常由应用进程来处理死锁，操作系统忽略死锁的存在。

死锁预防：采用某种机制，限制并发进程对资源的请求，使系统不满足死锁的必要条件。

比如可以把互斥的共享资源封装成可以同时访问的，比如打印机，加上缓冲区，在打印机内部协调先后；
持有并等待，进程请求资源时，不能占用其他任何资源，想申请资源时，必须把全部资源都申请到，也可以在进程开始执行时一次请求所有需要的资源，资源利用效率低；
非抢占：如进程请求不能立即分配的资源，则立即释放自己已占有的资源，只有能同时获取到所有需要资源时，才执行分配操作；
循环等待：对资源排序，进程需要按照顺序请求资源，可能先申请的资源后续才用到；

死锁避免：利用额外的先验信息，在分配资源时判断是否会出现死锁，如果可能会出现死锁，则不分配。要求进程声明资源需求的最大数目，限定提供与分配的资源数目，确保满足进程的最大需求，且动态检查资源分配状态，确保不会出现死锁。

进程请求资源时，系统判断是否处于安全状态。

针对所有已占用进程，存在安全序列；
序列是安全的，则Pi要求的资源<=当前可用资源+所有Pj持有资源（j<\i），如果Pi的资源不能立即分配，则要等待。

银行家算法

判断并保证系统处于安全状态。

n=线程数量，m=资源类型数量；
Max（总需求量）：n*m矩阵，线程Ti最多请求类型Rj的资源Max[i,j]个实例
Available(剩余空闲量)：长度为m的向量，当前有Available[i]个类型Ri的资源实例可用
Allocation(已分配量)：n*m矩阵，线程Ti当前分配了Allocation[i,j]个Rj的实例
Need(未来需求量)：n*m矩阵，线程Ti未来需要Need[i,j]个Rj资源实例；
Need[i,j]=Max[i,j]-Allcation[i,j]

安全状态判断：

Work 和 Finish 分别是长度为 m 和 n 的向量初始化： Work = Available，Finish = false for i = 1,2,…,n
寻找线程 Ti ，Finish[i] = false，Need[i] <= Work，找到 Need 比 Work 小的线程 i ，如果没有找到符合条件的 Ti ，转4
Work = Work + Allocation[i] ，Finish[i] = true，线程i的资源需求量小于当前系统剩余空闲资源，所以配置给他再回收。转2
如果所有线程Ti满足Finish[i]=true，则系统处于安全状态。
这种迭代循环到最后，则是安全的

初始化：Requesti：线程Ti的资源请求向量，Requesti[j]：线程Ti请求资源Rj的实例

循环：

如果Requesti < Need[i]，转到2，否则拒绝资源申请，因为县城已经超过了其最大要求；
如果Requesti <= Available，转到3，否则Ti必须等待，因为资源部可用；
通过安全状态判断是否分配资源给Ti，生成一个需要判断状态是否安全的资源分配环境：
- Available=Available-Requesti
- Allocation[i] = Allocation[i]+Requesti
- Need[i] = Need[i]-Requesti

死锁检测

允许系统进入死锁状态，并维护一个资源分配图，周期性调用死锁检测算法，如果有死锁，就调用死锁处理。

Available：长度为m的向量，表示每种类型可用资源的数量；
Allocation：一个n*m矩阵，表示当前分配给各个进程每种类型资源的数量，当前Pi拥有资源Rj的Allocation[i,j]个实例。

死锁监测算法：

Work是系统中的空闲资源量，Finish时线程是否结束。Work = Available，Allocation[i] > 0时，Finish[i] = false；否哦则Finish[i] = true；
寻找线程Ti满足Finish[i] = false且Requesti <= Work，线程没结束且能满足线程资源请求量。
Work = Work + Allocation[i]，Finish[i] = true，转到2。
如果某个Finish[i] = false，则系统会死锁。

死锁检测的使用：

多长时间检测一次
多少进程需要回滚
难以分辨造成死锁的关键进程

死锁恢复：

终止所有的死锁进程
一次终止一个进程，看还会不会死锁
终止进程的顺序应该是
- 进程优先级
- 进程已运行的时间和还需运行的时间
- 进程已占用资源
- 进程完成所需要的资源
- 进程终止数目
- 进程是交互还是批处理
  方法
- 选择被抢占的资源
- 进程回退

进程通信（IPC）概念

IPC提供两个基本操作：

发送：send(message)
接收：recv(message)

流程：

建立通信链路
通过send/recv交换

通信方式：

间接通信：在通信进程和内核之间建立联系，一个进程把信息发送到内核的消息队列中，另一个进程读取，接受发送的时间可以不一样。通过操作系统维护的消息队列通信，每个消息队列有一个唯一的标识，只有共享了相同消息队列的进程，才能够通信。
- 链接可以单向，也可以双向
- 每对进程可以共享多个消息队列
- 创建消息队列、通过消息队列收发消息、撤销消息队列
- send(A, message)、recv(A, message)，A是消息队列
- 阻塞发送是发送方发送后进入等待，直到成功发送
- 阻塞接受是接收后进入等待，直到成功接受
- 非阻塞发送是发送方发送后返回
- 非阻塞接受是没有消息发送时，接收者在请求接受消息后，接受不到消息。
直接通信：两个进程同时存在，发方向共享信道里发送，收方读取。进程必须正确的命名接收方。
- 一般自动建立链路
- 一条链路对应一对通信进程
- 每对进程之间只有一个链路存在
- 链路可能单向，也可以双向

进程发送的消息在链路上可能有三种缓冲方式：

0容量：发送方必须等待接收方
有限容量：通信链路缓冲队列满了，发送方必须等待
无限容量：发送方不需等待

信号和管道

信号是进程间软件中断通知和处理机制，如果执行过程中有意外需要处理，则需要信号，Ctrl-C可以使进程停止，这个处理是通过信号实现。如SIGKILL，SIGSTOP等。

信号的接收处理：

捕获：执行进程指定的信号处理函数被调用
忽略：执行操作系统的缺省处理，例如进程终止和挂起等
屏蔽：禁止进程接受和处理信号，可能是暂时的。

传送的信息量小，只有一个信号类型，只能做快速的响应知己。

首先进程启动时注册相应的信号处理例程到操作系统；
其他程序发出信号时，操作系统分发信号到进程的信号处理函数；
进程执行信号处理函数。

管道：进程间基于内存文件的通信机制，内存中建立一个临时文件，子进程从父进程继承文件描述符，缺省文件描述符：0 1 2

进程不知道另一端，可能时从键盘、文件等。

系统调用：

读管道read(fd,buffer,nbytes)
写管道write(fd,buffer,nbytes)
创建管道pipe(rgfd)，rgfd时两个文件描述符组成的数组，rgfd[0]是读文件描述符，rgfd[1]是写文件描述符。利用继承的关系在两个进城之间继承文件描述符。

消息队列和共享内存

消息队列是操作系统维护的字节序列为基本单位的间接通信机制，若干个进程可以发送到消息队列中，每个消息是一个字节序列，相同标识的消息组成先进先出顺序的队列。
系统调用如下：

msgget(key,flags)：获取消息队列标识
msgsnd(QID,buf,size,flags)：发送消息
msgrcv(QID,buf,size,flags)：接收消息

消息队列独立于进程，进程结束了之后消息队列可以继续存在，实现两个不同生命周期的进程之间的通信。

共享内存是把同一个物理内存区域同时映射到多个进程的内存地址空间的通信机制。每个进程都有私有内存地址空间，需要明确设置共享内存段。同一进程的线程总是共享相同的内存地址空间。

第五讲 物理内存管理

5.1 计算机体系结构和内存层次

5.2 地址空间和地址生成

5.3 连续内存分配

5.4碎片整理

5.5 伙伴系统

第六讲 物理内存管理: 非连续内存分配

6.1 非连续内存分配的需求背景

6.2 段式存储管理

6.3 页式存储管理

6.4 页表概述

6.5 快表和多级页表

6.6 反置页表

6.7 段页式存储管理

第七讲 实验二 物理内存管理

7.1 x86保护模式的特权级

7.2 了解特权级切换过程

7.3 了解段/页表

7.4 了解UCORE建立段/页表

第八讲 虚拟存储概念

8.1 虚拟存储的需求背景

8.2 覆盖和交换

8.3 局部性原理

8.4 虚拟存储概念

8.5 虚拟页式存储

8.6 缺页异常

第九讲 页面置换算法

9.1 页面置换算法的概念

9.2 最优算法、先进先出算法和最近最久未使用算法

9.3 时钟置换算法和最不常用算法

9.4 BELADY现象和局部置换算法比较

9.5 工作集置换算法

9.6 缺页率置换算法

9.7 抖动和负载控制

第十讲 实验三 虚拟内存管理

10.1 实验目标：虚存管理

10.2 回顾历史和了解当下

10.3 处理流程、关键数据结构和功能

10.4 页访问异常

10.5 页换入换出机制

第十一讲 进程和线程

11.1 进程的概念

11.2 进程控制块（PCB）

11.3 进程状态

11.4 三状态进程模型

11.5 挂起进程模型

11.6 线程的概念

11.7 用户线程

11.8 内核线程

第十二讲 进程控制

12.1 进程切换

12.2 进程创建

12.3 进程加载

12.4 进程等待与退出

第十三讲 实验四 内核线程管理

13.1 总体介绍

13.2 关键数据结构

13.3 执行流程

13.4 实际操作

第十四讲 实验五 用户进程管理

14.1 总体介绍

14.2 进程的内存布局

14.3 执行ELF格式的二进制代码-do_execve的实现

14.4 执行ELF格式的二进制代码-load_icode的实现

14.5 进程复制

14.6 内存管理的copy-on-write机制

处理机调度

处理机调度概念

调度准则

调度时机

调度策略

先来先服务、短进程优先和最高响应比优先调度算法

先来先服务

短进程优先

最高响应比优先

时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

时间片轮转

多级反馈队列

公平共享调度算法

uCore的调度队列run_queue

第五讲物理内存管理

第六讲物理内存管理: 非连续内存分配

第七讲实验二物理内存管理

第八讲虚拟存储概念

第九讲页面置换算法

第十讲实验三虚拟内存管理

第十一讲进程和线程

第十二讲进程控制

第十三讲实验四内核线程管理

第十四讲实验五用户进程管理

实验六调度器

第十七讲同步互斥

第十八讲信号量与管程

第十九讲实验七同步互斥

第十九讲实验七同步互斥