02323操作系统概论

单选题：20题，每题1分，一共20分  

填空题：10题，每题2分，一共20分

简答题：5题，每题4分，一共20分

综合题：4题，每题10分，一共40分

第一章操作系统简介

第一小节 什么是操作系统

1. 操作系统：os,是一种复杂的系统软件，是不同程序代码、数据结构、数据初始化文件的集合，负责管理计算机的资源，屏蔽了对硬件操作的细节，通过用户与计算机硬件之间的接口使应用程序的开发变得简单、高效

2. 操作系统必须完成的目标：承上启下，操作系统与硬件部分相互作用、为运行在计算机上的应用程序提供执行环境

3. 计算机系统重要的特点：支持多任务

4. 操作系统包括什么：处理机管理、内存管理、设备管理、文件管理

5. 网络操作系统：网卡、带宽

第二小节 操作系统的发展

1. 单道批处理系统：内存种只有一道作业，cpu和内存资源被用户作业独占，特点自动性、顺序性、单道性，优点是减少等待人工操作时间，缺点是cpu资源不能充分利用

 

2. 多道批处理系统：由操作系统的作业调度程序按一定策略从后备作业队列种选择若干个作业调入内存，使他们共享cpu资源，特点是多道性、无序性、调度性、复杂性业，优点是提高利用率和吞吐量，缺点是时间长、缺乏交互能力

3. 分时操作系统：允许多个用户通过终端机同时使用计算机，每个用户通过终端与主机交互时能得到快速响应（比如KTV点歌，可以多个人扫码在一个设备上点歌），特点是多路性、独立性、及时性、交互性，优点是提供了人机交互的方便性，使多个用户共享主机

-------多道批处理系统和分时操作系统是属于多道程序系统（可以并发就是因为引入多道程序系统）--------------

4. 实时系统：必须及时响应外部事件的请求，主要用于实时控制和实时信息处理领域，特点是多路性、独立性、及时性、交互性、可靠性

第三小节 操作系统的特征

5. 现代操作系统：支持多任务，具有并发、共享、虚拟和异步性特征

并发：两个或多个事件在同一时间间隔内发生，并行是多个事件同时发生

共享：系统中资源可供内存中多个并发执行的进程共同使用，共享分为互斥共享和同时共享，互斥共享是指任意时刻一种资源只能被一个进程访问，同时共享是指资源可以被多个进程同时访问

虚拟：最常用内存虚拟化，用户感觉到的内存大于实际内存（cpu在疯狂交互执行，把物理的变成逻辑的）

异步：进程以不可预知的速度向前推进（什么都不确定才叫异步）

第四小节 操作系统的功能

操作系统的功能分为两类：管理计算机资源、提供用户接口

6. 管理计算机资源：内存管理、进程管理、设备管理、文件管理

内存管理：提高内存利用率，以及从逻辑上扩充以实现虚拟存储（就是虚拟技术），内存管理管内容有内存分配(静态和动态)、内存保护（保护内存，彼此划分，互不干扰）、地址映射（用户感受到的叫逻辑，看得到的叫物理地址）、内容扩充（从逻辑方面，有两个步骤请求调用和置换）

内存保护，使用寄存器划分，使他们互不干扰

 

进程管理：执行中的程序（不考），进程控制是控制进程创建撤销唤醒等等

设备管理：输出输入设备，比如键盘鼠标

文件管理：文件存储空间的管理、目录管理、文件的权限

7. 提供用户接口：命令接口、图形用户接口、程序接口

命令接口：分为联机(一个命令执行一下然后输入下一个命令继续执行)和脱机(给一批命令)

图形用户接口：图形化界面

程序接口：为程序员提供的接口，也就是系统调用

第五小节 操作系统的体系结构

8. 操作系统的体系结构是操作系统作为一种软件的体系结构

--------------------------模型（一步步优化）------------------------

简单的监控程序模型：功能简陋（啥也不会，把功能堆在一起）

单体结构模型：所有的软件和数据结构都放置在一个逻辑模块中（把上一类堆在一起的进行分类，但是还是堆在一起）例子：unix系统，ms-dos、linux、mac os x和bsd系统

层次结构模型：把操作系统分解为多个小的层（分分类、分层级）

客户/服务器模型与微内核结构：核心功能外移（把不重要的去除），去除（文件系统、网络和驱动程序），保留（处理机调度、存储管理和消息通信），windows nt、cos、VxWorks

动态可扩展结构模型：动态实现

第六小节 指令的执行

9. 指令：程序是指令的集合

10. 指令周期：一个单一指令需要的处理称为指令周期，一个指令周期划分为取指周期和执行周期两个步骤

11. 程序计数器（pc）、指令寄存器（IR）：程序计数器保存下一次要执行的指令的地址，操作系统吧去取到的指令放在处理器的指令寄存器（存放当前执行的指令）中

12. 指令的构成：操作码、地址

13. 指令的分类：

处理器与存储器之间的指令或数据传送操作

处理器与I/O设备之间的指令或数据传送操作

算术运算操作或逻辑运算操作

控制操作，即修改指令的执行顺序的操作

 

第二章 进程管理

第一小节 进程的描述

顺序执行—一个一个来

1. 顺序执行特点：顺序性、封闭性、可再现性

顺序性：我运行完你运行

封闭性：只有当前运行的程序才能改变

可再现性：可以重复出现

2. 顺序执行的问题：不能使输入机、处理器和打印机同时忙碌

3. 并发：同一时间间隔内运行多个程序。一个程序执行结束前，可以运行其他程序

宏观并行：用户觉得程序同时向前推进

微观串行：任意时刻一个cpu只有一个程序在运行

4. 并发执行的特点：间断性、失去封闭性、不可再现性

间断性：程序在cpu上执行是是时断时续的，断断续续

失去封闭性：系统的状态不再只对正在执行的程序可见，可以简单理解为共享，比如买票，每个用户都可以提交订单，余票都会减少

不可再现性：同一个程序多次运行可能结果不一样

程序是静，进程是动

5. 进程：允许并发执行的程序在某个数据集合上的运行过程，进程=正文段+用户数据段+进程控制块（PCB，就是记录你在进程运行过程中所有东西）

6. 进程的特点：并发性、动态性、独立性、异步性、结构特征

并发性：多个进程实体能在一段时间间隔内同时运行

动态性：进程是实体的执行过程

独立性：独立运行和资源调度的基本单位

异步性：任何都无法预知

结构特征：进程实体包括用户正文段、用户数据段和进程控制块

7. 程序和进程的区别：程序是静态的、永久的、指令的集合的，进程是动态的、暂时的、正文段+用户数据段+进程控制块的

8. 程序和进程的联系：进程是程序的一次执行，一个程序可以对应多个进程，同一个进程能顺序执行几个程序

9. 进程控制块PCB：进程控制块是进程实体部分的一部分，是操作系统中最重要的数据结构，记录了操作系统所需要的全部信息

进程标识符信息：用于唯一标识一个进程

处理机状态信息：通用寄存器、指令计数器、程序状态字psw、用户栈指针

进程调度信息

进程控制信息

10. 进程的状态：执行态、就绪态、阻塞态（等待或封锁）

 

11. 进程的组织：

链接方式（把系统中具有相同状态的进程控制块pcb用其中一个链接字连成一个队列）

索引方式（系统根据所有进程的状态建立索引表，索引表的每一个表项指向一个进程控制块PCB）

进程队列（把具有相同状态的进程控制块用队列组织起来）（就是阻塞的和阻塞的放在一起，权重和权重相同的放在一起）

第二小节 进程的控制

进程有创建、阻塞、唤醒、终止

12. 创建进程的情况：用户登录、作业调度、提供服务、应用请求

13. 创建进程：申请空白pcb、为新进程分配资源、初始化进程控制块、将新进程插入到就绪队列（就绪态）

14. 新进程被创建时，有两种执行可能：父子进程并发执行、父进程等待，直到子进程全部执行完毕

15. 进程阻塞：条件没有达到

16. 进程阻塞过程：将进程的状态改为阻塞态、将进程插入相应的阻塞队列、转到进程调度程序，从就绪队列中选择进程给cpu

17. 进程唤醒的过程：将进程从阻塞队列中移出、将进程状态由阻塞态改为就绪态、将进程插入就绪态

18. 什么情况下会进程被终止：进程正常执行完毕

19. 完成进程终止的过程：从进程pcb中读进程状态、若进程正在执行，则终止进程的执行、释放资源、将终止进程的PCB移出

第三小节 操作系统内核

20. 操作系统内核：操作系统内核是计算机硬件的第一次扩充，内存执行操作系统与硬件关系密切，执行频率高的模块，常驻内存

21. 操作系统的功能：支撑功能（中断处理、时钟管理、原语操作）、资源管理功能（进程管理、存储管理、设备管理）

22. 中断：是改变处理器执行指令顺序的一种事件

23. 为什么需要中断：能有效提高cpu的利用率改善系统性能，支持系统的异步操作

24. 中断的分类：

同步中断（内部中断）：自己出问题了

异步中断（外部中断）：分为外部可屏蔽中断（执行中但是可以停），外部不可屏蔽中断（不能停）

25. 引起中断的原因：人为设置中断、程序性事故、硬件故障、I/O设备、外部事件（比如按exit退出了）

26. 中断响应：响应中断的条件、响应中断的时机（就是执行一个指令就去查一下中断信号，如果中断信号有数据，那么说明程序要停下来）

27. 单重中断处理

 

28. 时钟：时钟是计算机系统的脉搏，计算机的很多活动都是由定时测量来驱动的

------------------时钟可以限制用户进程在cpu上连续执行的时间（不是中断）---------------------

29. 实时时钟RTC\CMOS：类似钟表（北京时间），开机后的初始值（比如手机开机不可能显示为0）

30. Os时钟：类似秒表，计算机开机后初始值为0，是由操作系统控制的

两个时钟的工作原理是，开机后使用实时时钟的值作为初始值（北京时间），并且os时钟的值为0，然后os开始计时（像秒表一样），然后加到初始值上

--------------大部分pc中有两个时钟源，分别为实时时钟和os时钟------------------------

31. 操作系统的时钟机制：分为时钟硬件(保持当前的日期和时间)和时钟驱动程序（维持定时器）

Os时钟管理硬件：晶振（秒针），计数器（分针），保持寄存器（时针），秒针一直在走，走一下分针就-1，减完后从时钟在分配一个计数器，然后一直循环

32. 时钟驱动程序(简答题)：维护时间、进程运行防止运行超时、记录cpu使用情况、递减报警计数器

33. 系统调用：是预先定义好的模块，是系统程序与用户程序之间的接口

34. 系统调用和一般的函数调用的区别(简答题)：

用户空间：用户进程所在的地址空间

用户态执行：cpu执行用户空间代码时，称这个进程处于用户态执行(也称为目态)

系统空间：包含系统核心代码的地址空间

系统态执行：cpu执行系统核心代码时，称这个进程处于系统态执行(也称为管态)

区别1：系统调用运行在系统态，一般函数运行在用户态

区别2：执行过程不同（系统调用时，当前进程被中断）(系统态的权限较高，所以会中断其他的）

区别3：系统调用进行中断处理，比函数调用多了系统开销（因为中断会开辟系统空间保护现场，所以会有系统开销）

35. 系统调用的类型(简答题)：进程控制类、文件操作类、设备管理类、通信类、信息维护类

第四小节 进程同步（重点）   因为要访问临界资源才有了进程调度的算法

36. 多道程序环境下进程之间的关系（进程同步的任务）：

资源共享关系：保证各进程以互斥的方式访问临界资源

相互合作关系：保证相互合作的各进程协调执行

37. 临界资源：必须以互斥方式访问的共享资源称为临界资源，同时只有一个进程

38. 临界区：进程中访问临界资源的那段代码称为临界区

39. 同步机制遵循的准则：

空闲让进：没有进程在临界区，应该要也许一个请求进入临界区的进程进入

忙则等待：临界区里面又进程，其他试图进入的进程必须等待

有限等待：对于访问临界资源的进程，应该保证有限时间内进入临界区

让权等待：申请不到访问权，应该释放出立即，以免浪费cpu资源

40. 信号量机制：整型信号量机制、记录型信号机制、AND型信号量

41. 整型信号量机制：表示共享资源状态且只能由特殊的原子操作（wait申请资源,signal释放)改变的整型量，原理是定义一个整型变量，用这个变量的值来标记资源的使用情况，初始值为1，>0有资源可以用，<=0没有资源，需要等待

用整型信号量实现进程互斥：（整个结构就是这样子的，临界资源要在申请资源成功后才能使用）

wait(s)//申请资源

cs//申请资源后访问临界资源

signal(s)//释放资源

例题：p1和p2两个进程都访问同一个临界资源---打印机（用cs表示）对应的整型信号量为s,s的初始值为1，想要实现互斥的代码如下

P1                                                P2

 {...                                                  {...

wait(s);                                             wait(s);

cs                                                cs

signal(s);                                          signal(s);

...}                                                      ...}

42. 记录型信号量机制：原理定义一个记录型变量，用该变量的值来标记资源的使用情况，s.value>=0是，表示资源数量，s.value<0时，s.value的绝对值表示等待队列阻塞进程的数量

第五小节 进程通信

43. 进程通信机制：共享存储器系统、消息传递系统、管道通信、消息缓冲队列（不是高级通信机制）

第六小节 线程

44. 线程：线程是进程中可以独立执行的子任务，是被系统独立调度和分派的基本单位，和进程共享所有资源

45. 线程控制块TCB：每个线程由一个数据结构表示，这个数据结构就是tcb，记录了线程运行所需的全部信息

46. 线程与进程的区别（简答题）：

资源和调度：线程是程序执行的基本单位，进程是拥有资源的基本单位

地址空间资源：不同进程地址不相同，同一个进程下的线程地址相同

通信关系：同一进程下的线程间可以直接通信

并发性：都支持并发执行

系统开销：线程切换的开销比进程小

47. 线程控制：创建、阻塞、唤醒、调度、切换、终止

48. 线程阻塞：请求系统服务、新数据尚未到达、启动某种操作

49. 线程终止：正常结束、异常结束、外界干扰

 

 

第三章 进程调度与死锁

1. 进程调度的功能由谁完成，具体做什么：由进程调度程序完成，从就绪进程中选择新进程调入cpu

2. 进程调度时机：进程正常结束、进程异常结束、进程阻塞、有更高优先级进程到来、时间片用完

3. 选择调度方式和算法的准则（什么算法是好的算法/简答题）：周转时间短（作业从提交到完成的时间短）、响应时间快、截止时间的保证（在一定时间内完成）、系统吞吐量高、处理机利用率好

4. 带权周转时间：带权时间/服务时间,开始运行时间=上一个进程结束时间+上一个进程进入时间，周转时间=服务时间+等待时间，等待时间=开始运行时间-进入系统时间

5. 先来先服务算法FCFS：从就绪队列的队首选择最先到达就绪队列的进程，为该进程分配cpu

6. 短进程优先调度算法SPF：从就绪队列中选择估计运行时间短的进程，为该进程分配cpu，优点是和FCFS相比，SPF有效降低进程的平均等待时间、提高系统吞吐量，缺点是对长进程不利、进程长短由用户决定，不一定准确

7. 优先权调度算法：系统把cpu分配给优先权最高的进程，优先权调度算法类型有抢占式和非抢占式，优先权类型有静态优先权和动态优先权

8. 时间片轮调算法RR：系统按照先来先服务的原则排成一个队列，每次调度时把cpu分配给队首进程，并执行一个时间片，当时间片用完时，终止当前进程并将该进程送入队尾

时间片：一般时10~100ms，linux2.4是50ms

9. 时间片大小的确定：系统对响应时间的要求（短-小）、就绪队列中进程的数目（多-小）、系统处理能力（好-小）

10. 多级队列调度算法：把就绪队列分为多个独立队列，每个队列都有自己的调度算法

11. 多级反馈队列算法：建立多个优先权不同的就绪队列，每个队列有大小不同的时间片

12. 实现实时调度的基本条件：

提供必要的调度信息（开始截止时间、完成截止时间、就绪时间、处理时间、资源要求、优先级）、

系统处理能力强、采用抢占式调度机制、具有快速切换机制

13. 实时调度算法：最早截止时间优先算法EDF（运行越早、优先权越高）、最低松弛度优先算法LLF（L=T-Tc-Ts，T完成截止时间、Tc当前时间、Ts处理该任务还需要的时间）

14. 进程切换：正在执行的进程成为被替换进程，让出所使用的cpu，以运行新进程

15. 多处理系统的类型：耦合（紧密耦合、松弛耦合），结构（对称（静态分配和动态分配）、非对称（主-从式分配））

16. 死锁：多个进程竞争共享资源而引起的进程不能向前推进的僵死状态，产生原因是竞争资源且分配资源顺序不当

17. 产生死锁的必要条件：互斥条件、请求和保持条件、不剥夺条件、环路等待条件

18. 处理死锁：死锁的预防（通过破坏死锁的产生条件）、死锁的避免（通过算法合理分配资源）

19. 破坏死锁产生条件：摒弃请求和保持条件（一次性申请需要的全部资源、申请资源前需要释放当前占用的资源）、摒弃不剥夺条件（系统把被占用的资源分配给需要的进程，缺点是实现复杂、代价高）、摒弃环路等待条件（先申请资源少的）

----------死锁的避免--------------

20. 安全状态：能够找到一个进程执行序列，按照这个序列为每个进程分配资源可以保证进程的资源分配和执行顺利完成，不发生死锁

21. 银行家算法：一个进程提出资源请求后，系统先进程资源的试分配，分配后检测系统是否安全（安全就给他分配资源，不安全就不给），银行家算法的实质是避免系统进入不安全状态（不安全不一定等于死锁）

----------死锁的检测---------------

22. 什么时候检测/何时调用检测算法：死锁可能发生的频率、死锁发生时受影响的进程数量

23. 资源分配图：

图中ab线是给P1分配了两个资源，c线是P1申请资源，d线是分配给P2资源，e线是P2申请资源，f线是给P2分配资源

24. 死锁定理：用于检测系统所处的资源分配状态是否为死锁状态，死锁状态的充分条件是当且仅当S(S是指那张图)状态的资源分配图是不可完全简化的（简化是指某个进程可以正常执行完毕，给他分配资源或者他申请资源的线因为执行完成后消失，完全简化是指资源分配图全部线消失）

-------------死锁的解除------------

25. 死锁的解除：解除途径（进程终止(终止所有进程、一次只终止一个，直到死锁解除)、资源抢占(从其他进程抢占资源给其他进程使用，直到死锁解除)）

 

第四章 内存管理

1. 内存管理的目标：实现内存分配和回收，提高内存空间的利用率和内存访问速度

第一小节  存储器的层次结构

2. 存储器的层次结构：寄存器--L1高速缓存--L2高速缓存--主存储器（随机存储器ram（静动态）断电内容丢失）--本地二级存储--远程二级存储

3. 局部性原理：在短时间内，程序执行仅限于某个部分，相应的，它所访问的存储空间也局限于某个区域，局部性分为空间局部性和时间局部性

第二小节 程序的链接和装入

4. 程序的链接：将编译后的目标模块装配成一个可执行程序（把代码翻译成0和1，把0和1整合在一起变成可以执行的程序），程序的链接分为静态链接和动态链接

5. 静态链接：程序运行前，用链接程序将目标模块链接成一个完整的装入模块

6. 链接程序的任务：对逻辑地址进行修改（逻辑地址改成逻辑地址（所有的逻辑内容串起来））、变换外部调用符号

7. 重定位：程序装入时对目标程序中的指令和数据地址的修改过程叫重定位（地址映射）

8. 程序的装入：

绝对装入方式：编译时产生物理地址的目标代码

可重定位装入（静态重定位）：编译时地址时逻辑地址，装入是通过重定位转换为物理地址（物理地址=逻辑地址+程序在内存中的起始地址）

动态运行时装入（动态重定位）：程序执行时通过重定位转换为物理地址

第三小节 连续分配存储管理方式

9. 单一连续分配：任何时刻主存储器最多只有一个作业（只适用于单用户单任务的操作系统）

10. 固定分区分配：每个分区大小固定不变（区分大小相同、分区大小不等），每个分区只可以装入一个作业（上限寄存器和下限寄存器）

固定分区说明表：起始地址、长度、是否占用

11. 动态分区分配：分区大小和个数都是根据实际划分的

空闲分区表：分区编号、分区大小、分区起始地址

空闲分区链：每个分区建立一个结点（结点包括（简答题）：分区起始地址、分区大小、指向前一个空闲分区结点的指针、指向后一个空闲分区结点的指针）

12. 空闲区分配算法：

首次适应算法：空闲分区链以地址递增的顺序链接从链首开始查找，直至找到第一个满足要求的空闲分区，p1(20+30=50,120-30=90)

 

循环首次适应算法：从上次找到的空闲分区的下一个分区开始查找（优点：空闲区分布均匀、查找开销较小，缺点：缺乏大空闲区）

最佳适应算法：空闲分区链以分区大小递增（从小到大排）的顺序链接从链首开始查找，分配的空闲块与装入作业尺寸最接近（提高内存利用率）

 

13. 动态分区分配的流程（简答题）：检索空闲分区链->分配空闲分区->将分配给进程的分区其实地址返回给内存分配程序的调用者->修改空闲分区链表（检索、分配、反馈、修改）

14. 动态分区回收的流程：释放一块连续的内存区域->如果释放的区域与其他空闲区相邻，则合并空闲区->修改空闲分区链

 

第四小节 基于分页存储管理

15. 页：将一个进程的逻辑地址空间分成若干个大小相等的片

16. 页框：将物理内存空间分成与页大小相同的若干个存储块

17. 分页存储：将进程中的若干页分别装入多个可不相邻的页框中

18. 页内碎片：进程最后一页一般装不满一个页框，形成页内碎片

19. 页表：实现从页号到页框号的映射

20. 分页地址结构：页号P、页内偏移量（页内地址）W

 

b、kb、mb、gb、tb

1024b=1kb,1024kb=1mb,1024mb=1gb

 

 

21. 分页地址变换（简答题）：

进程执行，pcb中页表起始地址和页表长度送cpu的页表寄存器

Cpu访问某个逻辑单元A

由分页地址变换硬件自动将A分为页号和页内偏移两部分

由硬件检索页表，得到A所在的页对应的页框号

页框号和页内偏移地址送物理地址寄存器，计算物理地址。物理地址=页框大小*页框号+页内偏移量

（计算题）

 

求页号，根据题目给出的页表找出页框号，然后计算页内偏移量，然后在计算出物理地址，页框号*页面大小+页内偏移量（坑1：页内大小需要转换单位要转成B，坑2：0~1025有1026个，因为从0开始所以不需要使用1026计算）

22. 页的大小：512B~4KB

23. 快表：也称为转换后援缓冲（TLB），是为了提高cpu访存速度而使用的专用缓存，用来存放最近被访问过的内容，快表包含两个部分，键和值，键存放的是页号，值存放的是页框号

24. 引入快表后的地址变换过程（简答题）：去快表查询，查到就用，查不到就去内存找，找到后使用完就插入快表中

cpu产生对应信息后，将页号提交给快表

查找快表，如果找到页号，达到该页号对应的页框号，否则继续查找内容页表表得到页框号

如果查找的页号不在快表里，访问内存页表后，将页表项写入快表

25. TLB命中率：在TLB中找到某一个页号对应的页表项的百分比称为TLB命中率

 

26. 二级分页系统：页号访问页框号

第五小节 基本分页的虚拟存储系统

27.  虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种储器系统

28. 请求调入：先将进程的一部分装入内存，其余的什么时候需要什么时候请求系统调入

29. 置换：如果请求调入时没有足够的空间，则选择一部分内存中进程内容移到外存，腾出空间把当前需要转入的内存调入

30. 使用虚拟存储技术的优点：提高内存利用率、提高多道程序度、把逻辑地址和物理地址空间分开

31. 使用虚拟存储的特征：离散性（基础）、多次性、对换性、虚拟性（最重要的目标）

32. 请求分页：是系统最基本、最常用的虚拟存储系统的实现方式

33. 请求分页中的硬件支持：特殊的页表、缺页异常机构、和支持请求分页的地址变换机构

地址变换：分页地址变换机构计算出页号和页内偏移地址

    查找快表，如果找到了就读出这个页的页框号，并计算物理地址

如果快表里没有这个信息，转到内存页表进行查找页表，如果这个页已经调入，读出页框号并计算物理地址

如果这个页没有调入，则产生缺页异常，请求调度该页，修改页表重新执行

34. 页分配策略：

最小页框数：保证进程正常运行的所需要的最少页框数，最少页框数 与进程的大小没有关系，它与计算机的硬件有关，取决于指令的格式、功能和寻址方式（我有1025个单位，那么就需要2个（1024、1））

 分页存储系统中两种置换策略：局部置换和全局置换

按照页框数量的分配：固定分配和可变分配

分配页框的算法：平均分配算法（多出的放入候补区）、按比例分配算法、考虑优先权的分配算法

35. 页置换算法：最佳置换算法（主要用于研究）、先进先出置换算法FIFO(最简单的页置换算法）、最近最久未使用置换算法LRU(实现最佳算法的近似算法）

36. 最佳置换算法ORA：选择以后永远不会被访问的页或者在未来最长时间不被访问的页作为换出页

37. 先进先出置换算法FIFO：记录每个页调入内存的时间，选择进入内存时间最早的页作为换出页

 

产生多少次缺页中断？6次

缺页率=缺页/所有要访问的页 6/7=85%

产生多少次页面置换？3次

38. 最近最久未使用置换算法LRU：选择最近最久没有使用的页换出

 

产生多少次缺页中断？6次

缺页率=缺页/所有要访问的页 6/7=85%

产生多少次页面置换？3次

 

39. 缺页率对有效访问时间的影响：

有效访问时间=0.1+24999.9*P(缺页率）

有效访问时间与缺页率成正比，缺页率越高，有效访问时间越长，访问效率低

40. 工作集：某段时间间隔里，进程要访问的页的集合，目的是降低缺页率，提高访问内存效率

41. 抖动：运行进程大部分时间都用于换入换出几乎不能完成任何有效工作的状态，产生抖动原因是因为进程数量太多、分配页框太小，预防方法是引入工作集

第六小节 分段存储管理（易于实现共享）

-------------------------------------分段存储管理------------------------------------

42. 分段机制的引入：在分段存储管理的系统中，程序员使用二维的逻辑地址，一个数用来表示段，另一个数用来表示段内偏移量，题目会给出几号段+100偏移量

43. 分段存储的目的：部分存储空间动态增长、信息共享、信息保护的问题

44. 分段：进程的地址空间被划分成若干个段，每个段的大小不一样，每个段的逻辑地址从0开始，采用一段连续的地址空间，系统为每个段分配一个连续的物理内存区域，各个不同段可以离散的放入物理内存不同的区域，系统为进程建立一个段表，段表包括段号、段长和该段的基址，段表存放在内存里

45. 分段的逻辑地址结构：段号、段内偏移

46. 段表：是用于支持分段存储管理地址映射的数据结构，包括段号、段长（段大小）、段基址（段的起始地址）

47. 分段系统的地址变换：使用段号从段表中找到段号作为s的段表项；从找到的段表项中读出S段的基地址和段大小；如果d<=段大小，则将段基址与段内偏移d相加，得到物理单元地址

48. 分页和分段的主要区别：分页和分段都属于离散分配方式，都要通过数据结构与硬件的配合来实现逻辑地址到物理地址的映射

区别1：页是按物理单位划分的，分页的引入是为了支持虚拟存储，而段是按逻辑单位划分的，分段的引入是为了方便程序员编程

区别2：页的大小是固定的，而段的大小取决于用户编写的程序

区别3：分页的地址空间是一维的，分段的地址空间是二维的

49. 分段机制的优点：一个方便、两个动态、两个分段

-------------------------------------段页式存储管理-----------------------------------

也就是分页和分段结合的存储管理，先分段在分页

50. 段页式存储管理的基本原理：将用户进程的逻辑空间先划分成若干个段，每个段在划分成若干个页

第七小节 linux的伙伴系统

51. 满足以下条件的两个块称为伙伴：两个块具有相同的大小，记作b，他们的物理地址是连续的，起始地址是2b的整数倍

第五章 文件系统

第一小节 文件

1. 文件系统的用户接口：包括命名、类型、属性和对文件的操作

文件命名：所有操作系统都允许用1~8个字母组成的字符串，以圆点分开

文件结构：无结构字节序列（流式文件）、固定长度记录序列、树形结构（关键字）

文件类型：正规文件（ASCII文件、二进制文件）、目录文件、字符设备文件、块设备文件

文件存取：顺序存取、随机存取

文件属性：就是文件的详细信息，比如创建日期、文件大小啥的

文件操作：seek找到读取位置

第二小节 目录

2. 目录：是文件系统中实现按名访问的重要数据结构

3. 目录文件中两种常用结构：属性放在目录项中和放在i结点（属性和地址存放在i结点）中

4. 目录结构：

单层目录（一级目录）：缺点是文件命名和搜索效低

两级目录：主目录下存放用户目录，然后存放文件，优点是解决重名问题，查找快，缺点是增加系统开销

树形目录：优点是便于文件分类、层次结构清晰、便于管理和保护、解决了重名问题、查找速度加快，缺点是结构相对复杂

5. 树形目录的路径名：绝对路径名和相对路径名

第三小节文件系统的实现

-------------------------------------实现文件--------------------------------------------

6. 实现文件：文件系统通常是以2的n次方个连续的扇区为单位对文件进行磁盘空间的分配，把分配给文件的连续扇区构成的磁盘块称为簇，（每个簇使用二进制标识，一个簇号都要32位）

7. 文件存储4中常用方式：连续分配、磁盘链接表、内存的链接分配表、i-结点

8. 连续分配：把文件作为一连串的数据块放在磁盘上，优点是实现简单、读操作性能好，缺点是磁盘变得零碎，空闲的连续簇形成空洞

9. 使用磁盘链接表分配：为每个文件构造簇的链接表，优点是充分利用每个簇，缺点是随机存取相当缓慢

10. 使用内存的链接分配表分配：将文件所在的磁盘的簇号放在内存的表中，例如MS-DOS，缺点是把整个表都存放在内存中

11. i-结点：为每个文件赋予一个被称为i-结点的数据结构，其中列出了文件属性和文件的磁盘地址

算出数量

-------------------------------------实现目录--------------------------------------------

12. Cp/M中的目录：只有一层目录，存储以簇为单位

13. MS-DOS中的目录：使用文件分配表Fat存放

14. Unix中的目录：所有东西都存放I-结点，每个目录包含一个文件名和他的i结点号

-------------------------------------磁盘空间管理--------------------------------------------

15. 簇大小：太大造成空间浪费，太小会跨越簇，访问时间延长，一个簇大小是2的整数次幂个连续的扇区

16. 记录空闲块：空闲簇链接表、位图

第六章 I/O设备管理

第一小节I/O系统的组成

----------------------------------------I/O系统的结构-------------------------------------

1. I/O系系统的结构分为两大类：微机I/O系统、主机I/O系统

微机I/O系统：CPU与内存之间可以直接进行信息交换，但是不能与设备直接进行信息交换必须经过设备控制器

主机I/O系统：采用四级结构，包括主机、通道（用通道控制设备）、控制器（控制器也可以控制设备）和设备

----------------------------------------I/O设备的分类-------------------------------------

2. I/O设备的分类：按传输速率分类、按信息交换单位分类、按设备的共享属性分类

按传输速率分类：低速设备（鼠标、键盘）、中速设备、高速设备

按信息交换单位分类：块设备（数据存取以数据块为单位）、字符设备（传送字节流）

按设备的共享属性分类：独占设备、共享设备、虚拟设备

----------------------------------------设备控制器----------------------------------------

3. 设备控制器：是cpu与I/O设备之间的接口，接受I/O的命令并控制设备完成工作，也是一个可编址设备，链接多个设备时可有多个设备地址

4. 设备控制器的功能（简答题）：接收和识别命令、数据交换（通过数据寄存器进行数据交换）、设备状态的了解和报告、地址识别、数据缓冲、差错控制

5. 设备控制器的组成：设备控制器与处理机的接口、设备控制器与设备的接口、I/O逻辑

设备控制器与处理机的接口：数据线、控制器、地址线

设备控制器与设备的接口：接口中3类信号为数据、状态、控制信号

I/O逻辑：由指令译码器和地址译码器两部分功能部件构成

----------------------------------------I/O通道-------------------------------------

6. I/O通道：是一种特殊的处理机，大型主机系统中专门用于I/O的专用计算机，引入通道能够使cpu与I/O并行工作，提高Cpu利用率和系统吞吐量

第二小节I/O控制方式

7. 轮询控制方式：反复检测设备控制器状态寄存器的忙/闲标志位，缺点时使cpu经常处于循环测试状态、造成cpu的浪费，影响进程的吞吐量

8. 中断控制方式：

cpu执行过程中，发出输入/输出请求，如果I/O设备忙，则进程阻塞等待

当I/O设备工作完毕，通过中断控制器发出中断请求信号，Cpu响应中断，执行对应设备的中断处理程序，然后唤醒因等待该设备而阻塞的进程

Cpu继续执行这个进程时，向设备控制器发送I/o指令，然后cpu被调度程序分配给某个进程，继续执行某个进程

本次I/O结束后，设备控制器通过向CPU发送中断请求信号告知CPU本次数据传输结束

9. 中断控制的优点：时cpu和I/o设备并行工作，提高cpu的利用率和系统的吞吐量

10. DMA控制方式：

DMA控制器的组成部分：DMA与主机的接口、DMA与设备的接口以及I/O控制逻辑

DMA控制器中的寄存器：命令/状态寄存器CR、内存地址寄存器MAR、数据寄存器DR、数据计数器DC

DMA工作方式流程（简答题）：cpu要读取一个数据块时，向磁盘控制器发送一条读命令

该被送到命令寄存器CR中，同时CPU将本次读入数据放在内存中的起始地址送入MAR寄存器，将本次要读的字节送入DC寄存器

然后启动DMA控制器进行数据传输，传输完毕后，DMA向CPU发送中断请求

第三小节缓冲管理

11. 缓冲区：用来保存两个设备之间或设备与应用程序之间传输数据的内存区域，引入原因是处理数据流的生产者与消费者之间的速度差异、协调传输数据大小不一致的设备，引入作用是缓和CPU与I/O设备之间速度不匹配的矛盾，还能提高CPU和I/O设备的并行性

12. 单缓冲区：分配于内存，只有一个缓冲区

13. 双缓冲区：两个缓冲区，缓冲交换

14. 循环缓冲区：多个缓冲区彼此之间构成了圆，缓冲区的类型包括空缓冲区R、已装满数据的缓冲区G、现行工作缓冲区C，多个指针nextg(下一个装满数据的缓冲区)、nexti(下一个可用的空缓冲区)、current(正在使用的缓冲区)，getbuf使用缓冲区、releasebuf释放缓冲区

第四小节设备分配

15. 设备分配中的数据结构（用什么数据结构控制数据结构分配）：设备控制表DCT、控制器控制表COCT、通道控制报表CHCT、系统设备表SDT(把其他的都表都存起来)

16. 设备分配考虑的3个因素：设备的固有属性（独占性、共享性、可虚拟性）、设备分配算法（先来先服务、基于优先权的分配算法）、设备分配方式（安全分配方式、不安全区分配方式）

17. 设备独立性（设备无关性，现代操作系统都支持设备独立性）：应用程序独立于具体使用的物理设备，应用程序中，使用逻辑设备名称来请求各类设备、实际执行时，必须使用物理设备名称

18. 实现设备独立性的好处（简答题）：应用程序与物理设备无关（系统增减外围设备时，不需要修改应用程序）、易于处理输入/输出设备的故障（替换设备不需要修改应用程序）、提高系统的可靠性，增加设备分配的灵活性

19. 设备独立软件的功能：执行所有设备的公有操作（逻辑设备表LUT），向用户层软件提供统一的接口

20. 独立设备的分配程序（对于有通道的系统）：分配设备、分配控制器、分配通道

21. SPOOLing技术（假脱机技术）：通过虚拟化技术欺骗进程（只有一个打印机，使用spooling技术让进程以为自己拥有一个完整的打印机）

22. Spooling的组成：输入\输出井（在磁盘里）、输入/输出缓冲区、输入/输出进程、请求I/O队列

23. spooling的特点：提高i/o速度、将独占设备改为共享设备、实现虚拟设备功能

第五小节I/O软件原理

24. I/O软件原理：将软件组织成一种层次结构，低层软件用来屏蔽硬件具体细节、高层软件为用户提供界面

25. 设备管理的4个层次：用户层软件（我们发送的请求）、与设备无关的软件层（和操作系统相关的）、设备驱动程序、中断处理程序（底层）

26. 设备管理软件功能：实现输出I/O设备的独立性、错误处理、异步传输、缓冲管理、设备的分配和释放、实现I/O设备控制方式

27. I/O中断处理程序的作用：将发出i/o请求而被阻塞的进程唤醒

28. 设备驱动程序：I/O进程与设备控制器之间的通信程序（就是U盘连接电脑时，会弹出一个正在安装驱动）

29. 与硬件无关的I/o软件：无

第六小节磁盘管理

30. 磁盘存储器：是一个它容量大、存取速度快、可以实现随机存取的比较理想的外存设备，目标是提高磁盘空间利用率和磁盘访问速度

31. 磁盘结构：一个物理记录记录在一个扇区上，磁盘存储的物理记录数目由扇区数、磁道数、磁盘面数决定的

32. 磁盘访问时间：寻道时间（磁头移动到指定磁道时间，移动的是磁头）、旋转延迟时间（扇区移动到磁头下面的时间，移动的是扇区）、传输时间（磁盘数据读出或写入的时间）

33. 磁盘调度：最重要的目标是使磁盘的平均寻道时间最少，使用的算法有先来先服务、最短寻道时间优先、扫描算法、循环扫描算法

34. 先来先服务FCFS：最简单的磁盘调度算法，根据进程请求访问磁盘的先后顺序进行调度，优点公平、简单、缺点平均寻道时间较长

 

35. 最短寻道时间优先SSTF：要求访问的磁道与当前磁头所在的磁道距离最近，优点是寻道时间短，缺点是导致某个进程发生“饥饿”现象

36. 扫描算法SCAN（电梯调度算法）：不仅考虑到要访问的磁道与当前磁道的距离，更优先考虑到磁头当前移动的方向，优点是防止饥饿现象，缺点是有时候进程请求被大大推迟

37. 循环扫描算法CSCAN：一直往外边走

38. NStepSCAN和FSAN调度算法区别：NStepSCAN分为N个，FSAN分为2个

 

FCFS直接按照它给出的次序走

 

SSTF选择里当前数最近的

 

 

（增加的方向移动，就是向外走）

 

 

向外走也就是从100-->150然后直到最大的后面没有了，再从最小的开始（不会掉头，一直向外走）