第二章-用户接口与作业管理

1. 作业的组成：包括程序、数据、作业控制信息
2. 作业调度:高级调度-即作业调度；中级调度-即对换调度；低级调度-即进程级调度
3. 作业调度算法：
   • 单道批处理系统：先来先服务(FCFS)/短作业优先调度算法(SJF)/最高响应比优先调度算法(HRP)-优先调度响应比高的作业
     • 响应比RP = 作业响应时间/作业估计运行时间 = (作业估计运行时间+作业等待时间)/作业估计运行时间 = 1+ 作业等待时间/作业估计运行时间
   • 多道批处理系统：优先级调度算法/均衡调度算法

第三章-进程管理

1. 进程
   • 程序的执行顺序执行(顺序性、封闭性、可再现性)和并发执行(宏观串行、微观并行)
   • 通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。
   • 进程基本状态：运行态、就绪态、阻塞态
   • 进程调度属于低级调度--从就绪队列中按照一定的算法选择某个进程占用CPU
2. 进程调度算法：先来先服务FCFS、基于优先级、时间片轮转、多级队列轮转
3. 互斥区的原则：若干个进程应一个进程进入不应互相等待、一次只允许一个进程进入、任何一个都必须在有限时间内释放所占资源
4. 信号量 5 信号量：公用信号量(实现进程间的互斥，初值通常设为1)、私用信号量(实现进程间的同步，初始值通常设为0或n)。信号量值的含义：>= 0还有可用的资源数，<0绝对值表示进程因申请该信号量表示的资源数，得不到而进入阻塞态 6 P，V操作都是成对出现的：互斥操作同一进程中；同步操作处于不同的进程

第四章-死锁：

1. 产生死锁的四个条件(破坏其一就可预防死锁)：

   []内为预防死锁的方法，但都有实行的困难

   1. 互斥使用(资源独占) [对所有资源进行SPOOLing操作]
   2. 非剥夺控制(不可强占) [将资源剥夺]
   3. 零散请求[进城创建时申请所有的资源]
   4. 循环等待[对资源进行编号，逐序申请]

2. Allocation-占有的，Claim-申请的

3. 资源分配图：永久性资源->找非阻塞非独立的进程，临时性资源->生产者不被阻塞就OK

第五章-存储管理

1. 存储管理的任务：

   1. 存储的分配和回收
   2. 地址变换(地址在定位)
   3. 存储共享和保护
   4. 存储器扩展

2. 地址重定位：

   • 绝对装入
   • 可重定位装入：静态再定位、动态…

3. 内碎片是指占用分区之内未被利用的空间；外碎片是指占用分区之间未被利用的空间。

4. 分区存储管理方式：单一连续分区、固定分区、可变分区(没有内碎片，有外碎片)

5. 分区分配算法(某个空闲分区大小需大于或等于程序要求，若大于则分成2块，1个标为"占用"1个标为"空闲")

   • 最先适应算法(释放区域临近空闲相连，则合并)
   • 最适(在所有大于或者等于要求分配长度的空闲区中挑选一个最小的分区)
     • |->从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。
   • 最差(空闲分区按容量递减顺序排序，取所有空闲分区最大一块)
   • 循环最先(从上次分配的地方开始查找)

6. 页式存储管理

   • 每次访问数据或指令至少需要访问两次内存，第一次是查找页表，第二次才是真正访问指令或者数据
     • 优点：没有外碎片，每个内碎片不超过页大小。一个程序不必连续存放
     • 缺点：程序全部装入内存，没有足够的空闲页面就无法执行。动态地址变换机构增加成本和降低速度。表占用内存空间，花费时间来建立和管理。不易实现共享、动态链接。
   • 页表基址寄存器PTBR、页表长度寄存器PTLR
   • 联想存储器：用来存放当前运行作业的页表表项，以加速地址变换过程，称为快表。主存中的页表有时也称为慢表
   • 在进行地址变换时，变换机构根据虚拟地址字中页号同时查找快表和慢表

7. 段式存储管理

   • 每次访问一个数据或者指令访问内存两次。 # 再增设一个关联寄存器，用于保存最近常用的段表项。
     • 优点：没有内碎片，外碎片可以通过内存紧缩来消除。便于改变进程占用空间的大小。
     • 缺点：进程全部装入内存，不能实现存储扩充。
   • 段表基址寄存器、段表长度寄存器。
   • 联想存储器－快表，保存正在运行进程的段表的子集（部分表项），其特点是按内容并行查找。
   • 分页是出于系统管理的需要，分段是出于用户应用的需要。一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处页大小是系统固定的，而段大小则通常不固定。分页是一维的，分段是二维的。通常段比页大。段式可以内存共享，而页式不能。都不能存储扩充。

8. 段页式存储管理

   • 三次访问内存[访问段表得页表地址->访问页表得物理块号+页内地址的物理地址->去除指令或数据]
   • 将用户程序分为若干各段，再把每个段划分成若干个页。即将用户程序按段式划分，而将物理内存按页式划分
   • 引入联想存储器每次访问内存，同时利用段号和页号进行检索。

9. 覆盖技术(早期作系统)与交换技术(小型分时系统)

   • 同：程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间进行信息交换
   • 覆盖：必要部分常驻内存，可选部分用到时再装入
     • 缺点：对用户不透明；执行效率低；有碎片。
   • 交换：内存空间紧张时某些进程暂时移到外存，外存中某些进程换进内存，占据前者所占用的区域(内存和外存之间的动态调度)
     • 优点：增加并发执行数目；对程序员透明。
     • 缺点：增加处理机开销；整个地址空间交换，信息量大；程序换入时需要重定位。
   • 交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。

10. 虚拟存储

    1. 局部性原理：时间局部性、空间…
    2. 好处：小可用内存中执行大程序；容纳更多程序并发执行；不影响编程时的程序结构(与覆盖技术比较)；提供的虚拟内存空间通常大于物理内存
    3. 特征：物理内存分配不连续性，虚拟地址空间使用不连续性；与交换的比较：调入和调出是对部分虚拟地址空间进行；通过物理内存和快速外存相结合，提供大范围虚拟地址空间，但占用容量不超过物理内存和外存交换区容量之和。
    4. 种类：虚拟页式、段式、段页式
    5. 缺页中断：指令执行期间产生和进行处理缺页中断(不是在一条指令执行完毕之后)所缺页面调入之后，重新执行被中断的指令
    6. 缺页率=缺页次数/内存访问次数
    7. 分配给进程的物理页面数目越多，缺页率越低；页面很小页数多，通过调页很快适应局部性原理的要求，缺页率低；页面很大，大部分地址空间都在内存，缺页率低；页面中等大小，局部性区域只占每页的较小部分，缺页率高。[面向对象技术和多线程会破坏局部性；采用大页面，可提高从交换区调页的I/O效率]
    8. 若虚拟地址空间很大而每页比较小，则进程页表太长，采用两级或多级页表
    9. 调入策略：请求调页、预调页
    10. 页面置换(淘汰)算法：
        • 最佳算法OPT
        • 先进先出算法FIFO[表中若有则不动]
        • 最久未使用算法LRU(栈底最久未使用、移位寄存器(访问时最高位置1定期右移高位补0)、行1列0行最小最久二阶矩阵)[最近被访问的页面在上前]
        • 最不经常使用NFU(淘汰访问次数最少的)
        • 最近未使用算法NRU(每页设置标志位,被访问置1；置换时采用指针从当前位置查找0；指针经过的也都被修改为0，最后停留在置换页的下一页面)
    11. 虚拟段式(增加请求调段和段置换)、虚拟段页式

第六章-文件管理

1. 文件包括文件体(文件本身的信息)和文件说明(文件存储和管理信息)

2. 文件类型：

   • 用途：系统、用户、库文件
   • 保存期限：临时、存档、永久
   • 保护方式：只读、读写、可执行、不保护
   • UNIX中：普通、目录、特别

3. 文件的逻辑结构：有结构文件(记录式文件)、无结构…(流式文件)

4. 文件物理结构： 1 连续存储(顺序)：简单，课顺序存取和随机存取，速度快；文件不能动态增长，不利于插入和删除，有外部碎片 2 链接结构：提高了磁盘空间利用率,无外部碎片，有利于插入和删除，可动态扩充；速度慢，不适于随机存取，指针可能出错，更多寻道次数和时间，指针占用一定空间。 3 索引结构：即能顺序存取,又能随机存取，文件动态增长、插入删除，充分利用外存空间；较多寻道次数和时间，索引表带来开销(空间、时间) - UNIX文件系统采用的是三级索引结构，文件系统中inode(I节点)是基本结构。 - di_addr[40]->文件索引表，存放文件物理盘块号，每3个字节组成一个单元，记录文件的物理盘快号，构成了13个表项的地址索引。设成40字节使得I节点大小64字节。 - 直接寻址：数组前10个表项直接指向文件前10个逻辑块的物理盘块地址(直接块指针) - 一级间接寻址：第11个表项指向文件索引块的地址，即第11个表项登记的不是文件物理盘块号而是索引块的地址。 - 二级间接寻址：第12个表项指向第一个具有341个表项的间接索引块的地址。 - 三级间接寻址：第13个表项指向第一个具有341个表项的二级间接索引块的地址，访问的文件最大长度为：(10+341+341×341＋341×341×341)KB，将近40GB。

5. Hash文件

6. 目录内容

   • 文件控制块(FCB)构成：文件名、文件的物理地址|文件所有者、访问权限|创建时间、最晚一次读、最晚一次写
   • 目录结构：
     • 一级目录：结构简单|查找速度慢、不允许重名、不便于实现文件共享
     • 二级目录：为每一个用户建立一个单独的用户目录UFD(User File Directory)，系统中再建立主文件目录MFD(Master File Directory)，每个用户文件目录都占有一个目录项，包括用户名和指向该用户目录文件的指针
     • 多级目录(树状目录)：

7. 空闲空间管理的数据结构通常称为磁盘分配表。 1 空闲区表--适用于连续文件结构 2 位示图--申请时在位示图中查找为0的位，归还时将对应位转置0 3 空闲块链接--每块有指向下一空闲块的指针，所有构成链表(不需要磁盘分配表节省，每次申请只需取出链表开头空闲块) 4 成组链接法--空闲块每100块为一组，每组的第一个空闲块记录下一组空闲块的物理盘块号和空闲块总数

8. 文件共享--基于索引结点(静态、动态)

   • 会画文件共享图

   注意子进程包含父进程的所有进程

9. 磁盘移臂调度算法

   1. 先来先服务
   2. 最短寻道时间优先--造成某些访问请求长期等待得不到服务
   3. 扫描算法(电梯算法)--一个方向移动，该方向上有则继续扫描，否则改变移动方向
   4. 循环扫描调度算法--
   5. N步循环扫描调度算法--等待队列分为N个子队列，先来先服务处理队列，队列里用循环扫描调度算法
   6. FirstN步扫描调度算法

10. 旋转调度算法

第七章-设备管理

1. I/O系统的控制方式
   • 程序控制I/O
   • 中断驱动I/O--只适于传输率较低的设备
   • 直接存储访问I/O(DMA, Direct Memory Access)--CPU只需干预I/O操作的开始和结束适于高速设备
   • 通道控制方式I/O
2. I/O设备分类
   1. 按数据组织分类：块设备(有结构设备，速率高、可寻址、常用DMA)|字符设备(无结构设备，速率低、不可寻址、常用中断驱动)
   2. 数据传输率分类：低速设备、中、高
   3. 资源分配角度：独占设备、共享、虚拟
3. 缓冲管理队列
   • 自由buf队列(队尾进，队首出)
   • 设备buf队列(缓存若被分配，则进入该设备的fub队列)
   • NODEV设备队列(队头队尾双向勾连)--避免了重复、费时的I/O操作过程，从而大大提高了系统的效率。如果要将一个缓存重新分配，只需要简单地将它从自由buf队列和设备buf队列中同时抽出，送入新的设备buf队列。实现了进程对有限缓存的共享。