凭记忆，部分内容参考西安电子科技大学操作系统书

操作系统，主要功能是两个，向下管理硬件资源，向上提供命令、接口，增大吞吐量throughtput和利用率是操作系统的目标。

人机矛盾，速度不匹配，试试加缓冲。

进程，进程唯一标识是进程控制块PCB（Process Control Block），进程状态转换，三态、五态、七态。多进程，必然涉及资源共享，互斥控制，死锁定义，四个必要条件，多进程，多线程，管程。

Chapter 1操作系统概述

目标：方便性，有效性，可扩展性，开放性

作用：1）向上，为用户和应用程序提供接口—系统调用、命令、鼠标点击窗口；

2）向下，管理硬件设备，提高系统利用率和吞吐量。

基本特性：重要

并发：并发-两个或者多个事件在同一时间间隔内发生；并行-两个或者多个事件在同一时刻发生

共享：

虚拟：时分-空分复用技术

异步

Chapter 2 进程描述与控制

进程的创建终止：简答5分

Part 1.进程创建：

1）为进程申请一块空白PCB，

2）分配必需的资源，物理和逻辑资源，

3）初始化PCB，

4）如果进程就绪队列能够接纳新进程，将新进程插入就绪队列

Part 2.进程的终止：

1. 从PCB集合中找到该被终止进程的PCB，读出其状态
2. 如果该进程正处于执行状态，立即终止其执行，将调度标志改为真，指示后面应该重新调度该被终止进程；若该进程还有子孙进程，终止其子孙进程；
3. 将被终止进程的所有资源还给父进程或者是系统
4. 将被终止进程PCB从所在队列或者链表中移除，等待其他程序来搜集信息

小题

状态转换：

三态：就绪态，执行态，阻塞态

五态：创建态，结束态

七态：静止就绪，活动就绪，静止阻塞，活动阻塞

临界资源：一段时间只允许一个进程访问的进程

临界区：访问临界资源的那段代码

信号量

前驱关系—生产者消费者—哲学家进餐—读者写者

Chapter 3 处理及调度与死锁

高级调度：长程-作业调度******外存->内存***作业

中级调度：内存调度************内存->外存

低级调度：短程-进程调度******内存->CPU***进程

调度算法

先来先服务-FCFS---时间先后

短作业优先-SJF----引入固定的优先级

高响应比优先调度算法—动态优先级 sum(等待时间+要求服务时间)/要求服务时间

多级反馈队列—简答5分

1. 设置多个就绪队列，每个就绪队列给不同的优先级，第一个队列优先级最高，第二个次之，其余的以此类推·，优先级越高的队列给的时间片越小
2. 每个队列采用FCFS，新进程进入内存，首先放到第一优先级队列队尾，按照FCFS调度，轮到该进程执行时，如果能在时间片内完成，则该进程撤离系统；如果不能，将该进程调度到第二优先级的队列队尾等待调度；该进程如果在第二队列的时间片内完成了，将其撤离系统，否则，依次将它放入第三队列，以此类推
3. 按照队列优先级进行调度。调度程序首先调度最高优先级队列中的进程，仅当第一队列空闲时再调度第二队列中的进程，仅当第一、二队列为空时才调度第三队列中的进程。如果处理机正在第i队列中为某进程服务，同时有新进程进入任意一个优先级较高的队列，则立即将正在运行的进程放回第i队列，并将处理机分配给新到的高优先级进程，

死锁：简答：5分

定义：如果再一组进程中，每个进程都在等待仅有该组进程中的其他进程才能引发的事件，那么，称该组进程是死锁的

四个必要条件：

互斥条件--请求和保持条件—不可抢占条件—循环等待条件

互斥条件：在一段时间内，该组进程中分配到的资源只能由一个进程使用

请求和保持条件：进程获得需要的部分资源，同时还需要新的资源并提出请求，但是尚不可抢占条件：未分配到的资源已经被其他进程占有，该请求被阻塞，但是该进程仍然保持着自己已经分到的资源

循环等待条件：进程获得的资源在尚未使用完之前不能被抢占，只能由进程自己释放

发生死锁时，必然存在一条进程-资源的循环链

银行家算法 10分

步骤，画表

可用资源向量—最大需求矩阵—分配矩阵—需求矩阵

已知表

Max  Allocation  Available

第一个表

Max  Allocation  Need  Available

第二个表

Work  Need  Allocation  Work+Allocation  Finish

假设分配了，画出下表

Max  Allocation  Available

分配

Request（）  与  Need（），Request（）  与  Available（），

安全性序列

Chapter4存储器管理

存储器层次结构：CPU寄存器—主存—辅存

重定位：地址转换，使用一个映射，不直接使用物理地址，而是采用物理地址到逻辑地址的转换

怎么分配内存，连续分配—离散分配

动态分区分配，分页存储管理方式—页块—物理块，地址变换机构，

Chapter 5虚拟存储器

一次性-驻留性

局部性原理

请求分页系统—请求调页+页面置换+分页管理系统

请求分页中的地址变换过程 重点

明确  快表是一个CPU寄存器，页表是一个在内存，页号-物理块号，外存

快表和页表是大小有限的，只能存一些数据，会有快表中找不到的数据，会有页表中找不到的数据，外存里都有数据，但是，外存速度慢，根据局部性原理，调常用的数据到内存中（常用的数据当然可能不包含当前需要的数据，就需要页面置换算法，从外存调页到内存）

请求分页中的地址变换过程

程序请求访问某一页

1. 越界中断检查，页号大于页表长度，越界了；反之，查询
2. 快表中查询，查到了，直接根据物理块号和逻辑地址中的偏移量，一拼接，得到物理地址，修改访问位和修改位，根据物理地址去内存中取数据；
   1. 没有查到，去内存中的页表去查，在页表中查到了，修改快表，修改访问位和修改位，根据物理地址去内存中取数据
   2. 没有查到，说明该页不再内存，要进行调页，缺页中断，从外存中找到所缺的页，
      1. 如果内存满了，进行页面置换，选择一页换出来，
         1. 换出的页，如果没有被修改，不需要将该页写回外存，
         2. 否则需要将该页写回外存，
      2. 如果内存没有满

将所缺的页从外存换入内存，（外存->内存）

修改页表，（内存）

修改快表（寄存器），修改访问位和修改位，形成物理地址，根据物理地址去内存取数据

请求分段系统

内存分配策略：固定分配—可变分配

页面置换策略：全局置换—局部置换

置换算法（外存<->内存）计算题10分

最佳置换算法---理想解，其他算法性能参照

先进先出页面置换算法

LRU最近最久未使用算法---置换率，缺页率，缺页不代表置换了，置换一定是缺页了）

Clock置换算法—简单的，改进型

有效访问时间不考

画过程图解

抖动：总是在进行页面的换入换出，而来不及去执行有效的工作（处理机利用率急剧下降）

工作集：程序过去的某段时间的行为作为将来某段时间的近似---预测）工作集w(t-a,t)，a是工作集窗口大小

Chapter 6 输入输出系统---I/O系统

基本功能：

隐藏物理设备的细节

与设备无关性

提高处理机和I/O设备的利用率

对I/O设备进行控制

I/O软件的层次结构

用户层软件—产生I/O请求，格式化I/O，Spooling

设备独立性软件---映射，保护，分块，缓冲，分配

设备驱动程序：设置设备寄存器；检查状态

中断处理程序

硬件—执行I/O操作

I/O通道是一种特殊的处理机

中断系统调用，不是用户调用，就像数据库中说的，事务回滚，完整性保护是系统自动完成的，而不是用户调用完成的

中断：中断是CPU对I/O设备发来的中断信号的一种响应—外部中断（内部中断，CPU自身内部事件导致的中断，陷入）

中断向量表：为每种设备配有相应的中断处理程序，将该程序入口地址放在中断向量表的一个表项中，为每个设备的中断请求规定一个中断号，直接对应于中断向量表的一个表项。I/O设备发来中断请求时，根据设备对应的中断号查中断向量表，找到中断程序入口地址，转入中断处理程序，执行中断处理程序

中断优先级：来了多个中断信号，该怎么处理，谁先谁后，确定中断处理次序

对待多个中断源，屏蔽中断，嵌套中断，

中断处理程序简答

中断请求信号唤醒被阻塞的驱动程序进程，对被中断的CPU环境进行保护，分析中断原因，转入相应的中断处理程序，中断处理程序执行完后，恢复被中断进程的现场，返回被中断的进程，继续执行

中断处理流程

1. 测定是否有未响应的中断信号
2. 保护现场，保护被中断进程的CPU环境
3. 转入相应的设备处理程序
4. 中断处理
5. 恢复现场，退出中断

设备驱动程序：抽象上层的I/O指令，转换为具体硬件能够识别的指令，发送给设备控制器

组成：两个接口（向上—向下），一个I/O逻辑（控制设备）

上层（CPU）--设备驱动程序—设备控制器

设备中断程序---接受上层抽象指令，检查请求的合法性，发出I/O请求，响应中断请求

设备处理方式：给每一类设备设置进程，设置一个I/O进程，不设专门的设备处理进程

设备驱动程序的处理过程：将抽象指令转换为具体的要求，对服务请求进行校验，检查设备的状态，传送必要的参数，启动I/O设备

I/O设备的控制方式

1. 轮询可编程方式，字节为单位，CPU启动I/O后循环检测是否完成
2. 中断可编程方式 字节为单位， CPU启动I/O后无需检测，设备完成工作向CPU发送中断信号
3. 直接存储器访问方式 数据块为单位

DMA工作流程简答题5分

为什么下面出现很多DMA，不是很清楚哪些是属于DMA中的，哪些是属于CPU的，同时清晰划分出DMA与CPU

1. 1. 数据块作为基本单位，数据在传输开始和结尾需要CPU干预，不经过CPU直接和内存交互
   2. 组成：主机与DMA控制器的接口、DMA控制器与块设备接口、I/O控制逻辑
   3. 寄存器：命令状态寄存器CR—接收从CPU发来的I/O命令或控制信息或设备状态；内存地址寄存器MAR—需要传输的数据存储的位置；数据寄存器DR—暂存从设备到内存或内存到设备的数据；数据计数器DC—要读写数据字节数
2. 工作流程
   1. 当CPU需从磁盘中读取一数据块时，向磁盘控制器发送一条读命令。该命令被送到DMA中的命令寄存器CR中，同时，本次要读入数据在内存中的起始目标地址被送到DMA中的内存地址寄存器MAR中，要读数据的字节数送到DMA中的数据计数器DC中，磁盘中的源地址被送到DMA中的I/O控制逻辑上，上面所有工作完成，启动DMA进行控制，CPU则可以处理其他任务，整个数据传输过程由DMA控制器完成。

DMA从磁盘读取一个字节的数据，送入DMA中的数据寄存器DR后，再挪用一个存储器周期，将该字节传输到DMA中MAR所指示的内存单元中。然后，对MAR数据加1，将DC内容减1，若减1后DC内容不为0，继续传输下一个字节；否则，传输完成，由DMA控制器发出中断请求。

假脱机Spooling技术  5分简答

将一台物理I/O设备虚拟为多台逻辑I/O设备，做到允许一台物理设备被多个用户共享

Spooling组成：

1. 输入井和输出井—磁盘上开辟的区域—输入磁盘**输出磁盘---井中数据是文件形式管理，井文件一个进程的输入或者输出数据消耗一个文件，所有进程的输入或者输出数据文件连接成为一个输入或者输出队列
2. 输入缓冲区和输出缓冲区—内存中开辟的区域—缓和CPU和磁盘间速度不匹配—输入缓冲区**输入设备传输的数据->输入井---输出缓冲区**输出井的数据->输出设备
3. 输入进程和输出进程—预输入进程—缓输出进程—模拟脱机输入时的外围控制机，将用户要求的数据从输入设备传送到输入缓冲区，再存放到输入井，当CPU需要输入设备时，直接从输入井读入内存---模拟脱机输出时的外围控制机，将用户要求输入的数据从内存传送并存放到输出井，当输出设备空闲时，再将输出井中的数据经过输出缓冲区输出到输出设备上
4. 井管理程序—控制作业与磁盘井之间的信息交换—当作业执行过程中向某台设备发出启动输入或输出操作请求时，操作系统调用井管理程序，由井管理程序控制从输入井读取信息或者将信息输出至输出井

提高I/O速度

将独占设备改成为共享设备

实现虚拟设备的目的

守护进程

磁盘存储器的性能和调度

盘面，磁道，扇区

磁盘访问时间（本次不考计算）：寻道时间-旋转延迟时间-传输数据时间

磁盘调度算法 大题10分

先来先服务FCFS

最短寻道时间优先SSTF

扫描SCAN算法—电梯调度算法

循环扫描SCAN算法--磁头单向移动

计算平均寻道长度—发生“磁臂粘着“

表

被访问的下一个磁道号      移动距离（磁道数）

平均寻道长度

第八章

磁盘容量计算

FAT12以  盘块  为基本分配单位

       一个物理磁盘分为四个逻辑磁盘，每个逻辑磁盘是一个卷—分区

       每个盘块512字节（即512B），FAT表项占12位—有2^12个表项

       512B*2^12*4 = 2^(9+12+2) = 2^23B=8MB

NIFS以  簇  为基本分配单位

卷—簇

Chapter 7 文件管理

数据项-记录、文件---小题

之前整理的笔记：

第二章进程：

（管程VS进程

1. 数据结构属性---私有共有：进程定义的是私有数据结构PCB，管程定义的是公有数据结构，如消息队列
2. 进程是由顺序程序执行的有关操作，管程是进行同步操作和初始化操作
3. 进程实现并发，管程解决共享资源互斥，管程不能实现共享
4. 进程具有动态性，管程是操作系统中的一个资源管理块，供进程调用
5. 进程通过调用管程中的过程操作共享数据，进程是主动工作方式，管程是被动工作方式）

进程VS线程

调度—并发性—拥有资源—独立性—系统开销—支持多处理机系统

线程—调度的基本单位

进程—资源分配的基本单位

进程的同步问题

信号量的应用

Case1：分析共享资源---一定是针对共享的资源来设置信号量---信号量解决共享资源互斥

Case2：分析前驱关系---针对前驱关系设置信号量

生活中的例子

第一个：去看电影，先买票，再去入影院，凭票看电影，此时进去一定有座位。

共享资源是电影院的座位，所有想看电影的人相当于并发的进程，要先买票（只有买到票了才能进影院，否则硬闯进去了，可能没有作为，如下面的坐公交车的例子，没有位子坐）

第二个：坐公交车，先上车，司机开门，但是车上可能没有空座位了。

1. Producer-Consumer Problem

共享资源：生产者在生产时消费者不能取，消费者在取时生产者不能生产，因此这要设置一个信号量

1. The Dining Philosophers Problem

共享资源：筷子，同一个筷子不能由两个人用

为避免所有筷子都被拿起，却没有一个人同时左右手拿到，需要处理

1. Reader-Writer Problem

共享资源：读者可以读内容，同时写者不能写，可以有其他的读者去读；写者可以写内容，同时不能给读者去读。