计算机操作系统复习笔记（详细版）（重庆科技学院期末考点）

前言

本文旨在帮助我更好的复习，内容皆来自于其他博主的博客，以及课本，按科院操作系统老师划定的范围进行筛选总结。在我复习过程中内容还会有一定的删改

第一章：操作系统引论

什么是操作系统？

操作系统（OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境，它是计算机系统中最基本的系统软件。

1.1操作系统的目标和作用

总的来说：例如，用户是雇主，操作系统是工人（用来操作机器），计算机是机器（由处理机、存储器、设备、文件几个部件构成），工人有熟练的技能，能够控制和协调各个部件的工作，这就是操作系统对资源的管理；同时，工人必须接收雇主的命令， 这就是"接口"；有了工人，机器就能发挥更大的作用，因此工人就成了“扩充机器”。

1.1.1操作系统的目标

1.方便性 2.有效性 3.可扩充性 4.开放性

1.1.2操作系统的作用

1. OS的功能和目标：作为用户和计算机硬件之间的接口。（通过命令方式、系统调用方式等实现自身与OS的通信）
   

• 操作系统还提供了用户接口。操作系统提供的接口主要分为两类：

  命令接口，用户利用这些操作命令来组织和控制作业的执行；
  程序接口，编程人员可以使用它们来请求操作系统服务。

  (1) 命令接口

  命令接口进行作业控制的主要方式有两种，联机控制方式和脱机控制方式。按作业控制方式的不同，可将命令接口分为联机命令接口和脱机命令接口。

  (2) 程序接口

  程序接口由一组系统调用(也称广义指令)组成。用户通过在程序中使用这些系统调用来请求操作系统为其提供服务，如使用各种外部设备、申请分配和回收内存及其他各种要求。 当前最为流行的是图形用户界面(GUI),即图形接口。

2. OS作为计算机系统资源文件、处理机、存储器、I/O设备的管理者（硬+软=计算机系统资源）

   处理机管理、存储器管理、文件管理、设备管理

3. OS实现了对计算机资源的抽象（虚拟机)

1.1.3推动操作系统发展的主要动力

1. 不断提高计算机资源利用率
2. 方便用户
3. 器件的不断更新换代
4. 计算机体系结构的不断发展
5. 不断提出新的应用需求

1.2操作系统的发展过程

1.2.1单道批处理系统（操作系统开始出现）

单道批处理系统的处理过程

为实现对作业的连续处理，需要先把一批作业以脱机方式输入到磁带上，并在系统中配上监督程序(Monitor)，在它的控制下，使这批作业能一个接一个地连续处理。

• 目的：提高利用率和吞吐量
• 特点：1.单道性 2.顺序性 3.自动性
• 缺点：资源得不到充分利用

1.2.2多道批处理系统

多道程序设计的基本概念

在多道程序设计系统中，用户提交的作业先放在外存上，并排成一个队列，称为后备队列。然后由作业调度程序按照一定的算法，从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。计算机内存中加载多个程序，变成进程

• 特点：1.多道性 2.无序性 3.调度性 宏观上并行，微观上串行
• 优点：1.资源利用率高 2.资源吞吐量大
• 缺点：1.平均周转时间长 2.无交互能力

多道批处理系统需要解决的问题

• 处理机争用问题
• 内存分配和保护问题
• I/O设备分配问题
• 文件的组织和管理问题
• 作业管理问题
• 用户与系统的接口问题

1.2.4分时系统

分时系统的特征（最重要的是及时性）

1、多路性。 允许一台主机上联接多台终端，系统按分时原则为每个用户服务；
2、独立性。 每个用户各占一个终端，独立操作，互不干扰；
3、及时性。 用户的请求能在很短的时间内获得响应；
4、交互性。 用户可通过终端与系统进行广泛的人机对话。

• 缺点：不能有效处理紧急任务操作系统对各个用户 / 作业都是完全公平的，循环地为每个用户 /作业服务一个时间片，不区分任务的紧急性。

1.3操作系统的基本特性

并发，共享，虚拟，异步（友好性，安全性都不是基本特征）

1.3.1 并发

并行与并发

• 并行： 两个或多个事件在同一时刻发生

• 并发： 两个或多个事件在同一时间间隔内发生 注：宏观同时发生，微观交替发生

并发是提高系统资源利用率，增加系统的吞吐量的主要手段单处理机并发执行和多处理机的并发/并行执行

引入进程

• 进程是指 是计算机中的程序关于某数据集合上的一次运行活动，没引入线程之前是系统进行资源分配和调度的基本单位引入进程可实现并发执行

1.3.2 共享

定义：资源共享也称为资源复用，是指系统中的资源可供内存中多个并发执行的进程共同使用。

互斥共享方式

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

  例如：打印机，系统表格

同时访问方式

• 系统中还有另一类资源，允许在一段时间内由多个进程“同时”对它们进行访问。这里所谓的“同时”，在单处理机环境下是宏观意义上的，而在微观上，这些进程对该资源的访问是交替进行的。

  例如：磁盘、共享代码、共享库等

生活实例:

• 互斥共享方式:使用QQ和微信视频。同一时间段内摄像头只能分配给其中一个进程。

• 同时共享方式:使用QQ发送文件A，同时使用微信发送文件B。宏观上看，两边都在同时读取并发送文件，说明两个进程都在访问硬盘资源，从中读取数据。微观上看，两个进程是交替着访问硬盘的。

1.3.3 虚拟

在OS中，通过某种技术将一个物理实体变为若干个逻辑上的对应物的功能称为虚拟。

• 时分复用:虚拟处理机(多道程序)技术、虚拟设备技术

• 空分复用:多道程序共享内存，多文件共享磁盘, 用以提高存储空间的利用率
  

1.3.4 异步

在多道程序环境下，系统允许多个进程并发执行。在单处理机环境下，由于系统中只有一台处理机，因而每次只允许一个进程执行，其余进程只能等待。

由于资源等因素的限制，使进程的执行通常都不可能“一气呵成”，而是以"停停走走”的方式运行。

（补）操作系统的中断处理

中断机制的作用：为了在多道批处理系统中让用户进行交互；

中断产生：

• 发生中断时，CPU立马切换到管态，开展管理工作；（管态又叫特权态，系统态或核心态，是操作系统管理的程序执行时，机器所处的状态。）
• 发生中断后，当前运行的进程会暂停运行，由操作系统内核对中断进行处理；
• 对于不同的中断信号，会进行不同的处理。

中断的分类：

• 内中断（也叫“异常”、“例外”、“陷入”）------- 信号来源：CPU内部，与当前执行指令有关；
• 外中断（中断）----------信号来源：CPU外部，与当前执行指令无关。

外中断的处理过程：

• 每执行完一个指令后，CPU都需要检查当前是否有外部中断信号；
• 如果检查到外部中断信号，则需要保护被中断进程的CPU环境（如程序状态字PSW，程序计数器PC、各种通用寄存器）把他们存储在PCB（进程控制块中）；
• 根据中断信号类型转入相应的中断处理程序；
• 恢复原进程的CPU环境并退出中断，返回原进程继续执行。

1.4操作系统的主要功能

1.4.1处理机管理功能

• 主要任务：

  1. 进程控制：创建和撤销进程
  2. 进程同步：对进程的运行进行协调
  3. 进程通信：实现进程之间的信息交换
  4. 调度：按照一定算法把处理机分配给进程

1.4.2存储器管理功能

• 主要任务 ：为多道程序的运行提供良好的环境，提高存储器的利用率，方便用户使用，从逻辑上扩大内存。

  1. 内存分配和回收
  2. 内存保护
  3. 地址映射
  4. 内存扩充

1.4.3设备管理功能

• 主要任务：
  1. 完成用户进程提出的I/O请求，为用户进程分配所需的I/O设备，并完成指定的I/O操作；
  2. 提高CPU和I/O设备的利用率，提高I/O速度，方便用户使用I/O设备。

  • 缓冲管理
  • 设备分配
  • 设备处理

1.4.4文件管理功能

• 主要任务： 对用户文件和系统文件进行管理以方便用户使用，并保证文件的安全性。

  1. 文件存储空间的管理
  2. 目录管理
  3. 文件的读/写管理和保护

1.4.5接口管理功能

• 主要任务： 为了方便用户对OS的使用，OS向用户提供了“用户与OS之间的接口”。

  用户接口（命令接口）：

  联机用户接口
  脱机用户接口
  图形用户接口

  程序接口：
  程序接口是为用户程序在执行中访问系统资源而设置的，是用户程序取得操作系统服务的唯一途径。

1.5操作系统的结构

• 简单结构

• 模块化结构：
  优点:

  提高OS设计的正确性、可理解性、易维护性、可适应性，加速OS开发过程

  缺点：

  接口规定很难满足划分后模块对于接口的实际需求； B决定必须建立在A决定的基础上，没有可靠决定顺序，容易造成决定的无序性

• 分层结构：
  优点：

  能保证正确性、易维护性、可扩展性

  缺点：

  系统效率低

• 微内核结构：
  概念：

  足够小的内核、基于客户或服务器的模式、采用策略和机制分离的原则、采用面向对象技术。

  功能：

  进程（线程）管理、低级存储器管理、中断和陷入处理（在微内核OS中，将进程管理、存储器管理、I/O管理等功能一分为二，并将其中属于机制的、很小的一部分放入了微内核中，另外的绝大部分放在了微内核外的各种服务器中）

  优点：

  提高系统扩展性、可靠性、可移植性，提供了对分布式系统的支持，融入了面向对象技术。操作系统可仅通过调整策略来适应不同应用的需求

  存在的问题：

  因为客户和服务器间有消息传递，因此相比于早期的OS，微内核OS的运行效率有所降低（内核大则效率高但占用空间也大，反之效率低但是占用空间小）

• 外核结构：
  概念：

  内核不提供传统OS的进程、虚拟存储器等抽象事物，而是专注于物理资源的隔离（保护）和复用，即非常小的内核负责保护系统资源，而硬件资源的管理职责则委托给应用程序。将原本属于OS内核的功能以库的形式提供给用户

1.6系统调用

• 概念：

  使应用程序可以通过系统调用来间接调用OS中的相关过程，进而取得相应的服务。

• 系统调用是通过中断机制实现的
• 系统调用区别于一般的过程调用

  • 运行在不同的系统状态：系统调用的调用程序运行在用户态，而被调用程序运行在内核态

  • 状态转换 ：因为调用和运行的系统状态不同（一个是用户态，一个是内核态），因此不允许由调用过程直接转向被调用过程，需要通过软中断机制先由用户态转为内核态，经内核分析后才能转向相应的系统调用处理子程序

  • 返回问题：每次调用需要判断优先级

  • 嵌套调用：系统调用对于嵌套调用的深度有一定限制，但是一般的过程调用则没有

• 系统调用的类型：
  • 1. 进程控制类系统调用
  • 2. 文件操纵类系统调用
  • 3. 进程通信类系统调用

第二章 进程的描述与控制

2.1前趋图

有向无环图（DAG），用于描述进程之间执行的先后顺序。节点表示一个进程、一段程序 或 一条语句；节点间有向边表示节点间存在的偏序或前趋关系。

1. 如果进程 Pi 和 Pj 存在前趋关系，可表示为( Pi , Pj )∈→，也可写成 Pi → Pj ，表示 Pj 开始执行之前 Pi 必须完成。 Pi 是 Pj 的直接前趋， Pj 是 Pi 的直接后继。

2. 没有前趋的节点称为初始节点，没有后继的节点称为终止节点。

3. 每个节点还具有一个重量，用于表示该节点所含有的程序量或程序的执行时间。

4. 前趋图中不允许存在循环，否则会产生不可实现的前趋关系

图 2-1 （b）的关系是不可实现的

2.2进程的描述

2.2.1进程的定义与特征

为了使参与并发执行的每个程序都能独立运行，设置了专门的数据结构，称为进程控制块PCB。利用进程控制块来描述进程的基本情况和活动过程，进而控制和管理进程。

• 进程实体，由程序段、相关数据段和进程控制块组成。简称为进程
• 创建、撤销 进程实际上是在 创建、撤销 进程实体的进程控制块（PCB）。
• 进程的定义：
  • 进程是程序的执行过程，是系统进行资源分配和调度的独立单位。

特征：

• 动态性

  • 进程的实质是进程实体的执行过程，动态性是进程最基本的特征。
  • 进程与程序的区别： 进程实体具有一定的生命周期，程序是静态的。

• 并发性

  • 多个进程实体同存于内存中，且能在一段时间内同时运行。
  • 引入进程的目的也是为了使进程实体能和其他进程实体并发执行。

• 独立性
  独立性是指进程实体是一个能独立运行，独立获得资源和独立接受调度的基本单位。

• 异步性

  • 进程是按异步方式运行的，按各自独立，不可预知的速度向前推进。
  • 并发执行的程序运行过程总是走走停停。会产生结果的不可再现性。

2.2.2进程的基本状态与转换

• 进程的三种基本状态：
  • 就绪状态
    • 进程已处于准备好运行的状态，进程已分配到除CPU以外的所有必要资源后，只要再获得CPU便可立即执行。
  • 执行状态
    • 进程已获得CPU，其程序正在执行的状态。
  • 阻塞状态
    • 正在执行的进程，由于发生某事件暂时无法继续执行时的状态。进程的执行受到阻塞。

• 创建状态和终止状态
  • 创建状态
    • 创建进程时，所需资源不能完全被满足。如果可以完全被满足，则直接进入就绪状态。
    • 创建进程：
      1. 首先由进程申请一个空白的PCB，向PCB中填写用于控制和管理进程的信息，然后为该进程分配运行时所需的资源，最好把进程转入就绪状态并插入就绪队列中。
      2. 如果进程所需的资源不能得到满足，创建进程的工作未完成，进程不能被调度运行，此时进程所处的状态为创建状态。
      3. 当进程获得了所需的资源以及对其PCB的初始工作完成后，便可由创建状态转入就绪状态。
  • 终止状态
    • 进程的终止：

    等待操作系统进行善后处理，然后将PCB清零，并将PCB空间归还系统。

    • 进入终止状态的情况

    1. 进程到达自然结束点。
    2. 进程出现无法克服的错误。
    3. 进程被操作系统终结。
    4. 进程被其他有终止权的进程终结。

2.2.3挂起操作和进程状态的转换（理解）

• 为了系统和用户分析进程的需要，引入了一个针对进程的重要操作，挂起操作。
• 与挂起操作对应的操作为——激活操作。
• 引入挂起操作的原因是基于操作系统和用户的需要：
  • 终端用户在自己的程序运行期间发现有可疑的问题，希望暂停程序的运行。
  • 父进程需要挂起自己的某个子进程，以便考察和修改子进程或协调各子进程间的活动。
  • 系统需要把一些不重要的进程挂起。实现负荷调节，保证系统的正常运行。
  • 操作系统挂起某些进程，以便检查运行中的资源使用情况或进行记账。
• 引入挂起原语操作后的三个进程状态的转换
  • 当进程未处于被挂起的就绪状态，为活动就绪状态。此进程可以接受调度。
  • 当进程被挂起后，该进程处于静止就绪状态。此进程不可被调度。
  • 当进程处于未被挂起的阻塞状态为活动阻塞状态。
  • 当进程处于被挂起的阻塞状态为静止阻塞状态。处于该状态的进程在其所期待的事件出现后，从静止阻塞变为静止就绪。
  • 创建进程时，进程所需的资源不满足，进入静止就绪状态。
  • 创建进程时，进程所需的资源能够被满足进入活动就绪状态。

2.2.4进程管理中的数据结构（理解）

• 操作系统中用于管理资源和控制进程的数据结构
  • 在计算机操作系统中，对于每个资源和每个进程都设置了一个数据结构用于表征其实体，称之为资源信息表或进程信息表。其中包含了资源或进程的标识，描述状态等信息，以及一批指针。
  • 主要分为四类。
    • 内存表
    • 设备表
    • 文件表
    • 进程表：又称为PCB，用于进程管理。

• 进程控制块（PCB）作为进程实体的一部分，记录了操作系统所需的用于描述进程当前情况以及管理进程运行的全部信息，是操作系统（OS）中最重要的记录型数据结构。
• 进程控制块（PCB）的作用
  • 作为独立运行基本单位的标志。系统通过PCB（进程控制块）感知进程的存在与进程状态的改变。
  • 能实现间断运行方式。程序阻塞时，系统可以将程序运行的现场信息保存在PCB（进程控制块）中，当阻塞结束后，通过PCB（进程控制块）恢复现场，以便程序继续运行。
  • 提供进程管理所需要的信息。根据PCB（进程控制块）中记录程序和数据在内存或外存中的起始地址指针，可以找到相应的程序和数据。
  • 提供进程调度所需的信息。在PCB（进程控制块）中计入了进程处于何种状态，以及进程的优先级，进程的等待时间和已执行时间等。
  • 实现与其他进程的同步和通信。在PCB（进程控制块）中记录了用于实现进程通信的区域或通信队列指针。
• PCB（进程控制块）中的信息。
  • 进程标识符
    • 外部标识符方便用户对进程的访问。
    • 内部标识符方便系统对进程的使用。
  • 处理机状态。
    • 处理机状态信息也称为处理机的上下文，主要是由处理机的各种寄存器中的内容组成。
    • 当进程被切换时，处理机状态信息都保存在PCB（进程控制块）中，以便在进程重新执行时能从断点继续执行。
  • 进程调度信息
  • 进程状态，进程优先级等。
  • 进程控制信息
    • 用于进程控制所必须的信息。
      包括：
      • 程序和数据的地址
      • 进程同步和通信机制
      • 资源清单
      • 链接指针
• PCB（进程控制块）的组织方式
  • 线性方式
    • 所有的PCB（进程控制块）都组织在一张线性表中，将该表的首地址存放在内存的一块专用区域中，每次查找都需要扫描整张表。
  • 链接方式
    • 把具有相同状态的PCB（进程控制块）分别通过PCB（进程控制块）中的链接字链接成一个队列。
    • 按照进程的优先级，将PCB（进程控制块），从高到低进行排列。

2.3进程控制（理解）

• 进程控制是进程管理中最基本的功能，主要包括创建新进程、终止已完成的进程、将因发生异常情况而无法继续运行的进程置于阻塞状态，负责进程运行中状态转换。
• 进程控制一般是通过操作系统内核中的原语来实现。

2.3.1进程的创建

• 在操作系统中允许一个进程创建另一个进程，通常把创建进程的进程称为父进程，而把被创建的进程称为子进程。
• 子进程可以继续创建自己的子进程（即父进程的孙进程），由此便形成了一个进程的层次结构。
• 进程与其子孙进程共同组成进程家族。
• 子进程可以继承父进程所拥有的资源。当子进程被撤销时，应将从父进程那里获得的资源归还父进程，在撤销父进程时，必须同时撤销其所有子进程。
• 进程图
  • 为了形象的描述一个进程的家族关系，引入了进程图。
  • 进程图就是用于描述进程间关系的一颗有向树。
    
  • 进程图中的节点代表进程。
  • 创建父进程的进程称为祖先进程，把树的根节点作为进程家族的祖先。
• 引起创建进程的事件。
  • 用户登录
  • 作业调度
  • 提供服务
  • 应用请求：用户进程自己创建新进程
• 进程的创建
  • 申请空白PCB（进程控制块）。
  • 为新进程分配其运行所需的资源，包括各种物理和逻辑资源。
  • 初始化PCB（进程控制块）。
  • 如果进程就绪，队列能够接纳新进程，便将新进程插入就绪队列。

2.3.2进程的终止

• 引起进程终止的事件
  • 正常结束，表示进程任务已完成，准备退出运行。
  • 异常结束是指进程运行时发生某种异常事件使程序无法继续运行。
    • 越界错
    • 保护错：访问一个不允许访问的资源文件。
    • 非法指令。
    • 特权指令错。
    • 运行超时
    • 等待超时
    • 算数运算错
    • I/O故障
  • 外界干预是指进程因外界的请求而终止运行
• 进程的终止过程
  • 根据被终止的进程标识符从PCB（进程控制块）集合中检索出该PCB（进程控制块），读出该进程的状态。
  • 被终止进程正处于执行状态，立即终止该进程的执行，并设置调度标志位真，用于指示该进程被终止后应重新进行调度。
  • 如果该进程还有子孙进程，将所有子孙进程终止。
  • 将被终止的进程所拥有的全部资源归还给父进程或者归还给系统。
  • 将被终止进程从所在队列中移出，等待其他程序来搜索信息。搜集完才回收。

2.3.3进程的阻塞与唤醒

• 引起进程阻塞或被唤醒的事件
  • 向系统请求共享资源失败。
  • 等待某种操作的完成。
  • 新数据未达到。
  • 等待新任务到达。
• 阻塞是进程自身的一种主动行为。
• 进程的阻塞过程
  • 通过调用阻塞原语将自己阻塞，如果进程处于执行状态，立即停止执行，把PCB（进程控制块）中的现行状态改为阻塞，并将PCB（进程控制块）插入阻塞队列。保存当前进程的处理机状态。将处理机分配给另一个就绪进程。
• 进程唤醒过程
  • 阻塞进程所期待的事件发生，由相关进程调用唤醒原语将等待该事件的进程唤醒。
  • 把阻塞进程从阻塞队列中移出。将PCB（进程控制块）的状态改为就绪状态，将PCB（进程控制块）插入就绪队列中。

2.3.4进程的挂起与激活

• 进程的挂起
  • 操作系统利用挂起原语将指定进程或处于阻塞状态的进程挂起
• 进程的激活
  • 操作系统利用激活原语将指定进程激活

2.4消息传递通信的实现方式

• 直接消息传递系统

  • 直接通信原语

    发送原语：send(receiver, message) 、接收原语：receive(sender, message)

    • 对称寻址方式，发送进程和接收进程必须以显示方式提供对方的标识符。
    • 非对称寻址方式，发送进程不用显示提供对方的标识符。

  • 在直接消息传递系统中采用直接通信方式发送进程，利用操作系统提供的发送命令直接把消息发给目标进程。

• 信箱通信（间接通信）

  • 发送原语：send(mailbox, message) 、接收原语：receive(mailbox, message)

  • 信箱通信属于间接通信方式及进程之间的通信，需要通过中间实体来完成。
  • 通常把中间实体称为邮箱，每个邮箱都有一个唯一标识符。
  • 邮箱只允许核准的目标用户随时读取。
  • 利用邮箱通信方式可实现实时通信，也可实现非实时通信。
  • 信箱结构
    • 信箱头用于存放有关信箱的描述信息。
    • 信箱体，由若干个可以存放信息的信箱格组成，信箱格的数目以及每格的大小是在创建信箱时确定。
      
  • 信箱的类型
    • 私用信箱，用户进程为自己创建的信箱。
    • 公用信箱，由操作系统创建。被允许的进程才可以使用该信箱。
    • 共享信箱，由进程创建所有共享进程都可以使用。

2.5线程与进程的比较

• 由于线程具有许多传统进程所具有的特征，所以又称之为轻型进程或进程元
• 传统进程被称为重型进程
• 线程和进程都能作为调度的基本单位。线程的切换代价低于进程。
• 线程的并发性更好
• 进程可以拥有资源，并作为系统中拥有资源的一个基本单位，线程本身并不拥有资源。
• 进程的独立性高于线程。同一进程中的不同线程共享进程中的内存空间和资源
• 线程切换的系统开销小
• 线程更适合多处理机

第三章处理机调度与死锁

3.1处理机调度的层次

• 高级调度（长程调度/作业调度）将外存上处于后备队列中的作业调入内存，主要用于多道批处理系统中
• 低级调度（中程调度/进程调度）根据某种调度算法，决定就绪队列中的哪个进程应获得处理机
• 中级调度（短程调度/内存调度）内存调度，将暂不运行的进程，调至外存等待；将处于外存上的急需运行的进程，调入内存运行

3.2调度算法

• 先来先服务（FCFS）：

  介绍：按照作业到达的先后次序来进行调度

• 短作业优先（SJF）：

  分类：抢占式，非抢占式

  优点：比FCFS算法有明显改进，SJF是最优的（对一组指定的进程而言），它给出了最短的平均等待时间

  缺点：对长作业不利、无法实现人机交互、通常用于作业调度

  介绍：

  • 对作业：从后备队列中选择若干个估计运行时间最短的作业;
  • 对进程：关联到每个进程下次运行的CPU区间长度，调度最短的进程

• 优先级调度（PR）：

  介绍：基于作业/进程的紧迫程度，由外部赋予作业相应的优先级，调度算法根据优先级进行调度

  分类：抢占式、非抢占式；动态优先级、静态优先级。

  缺点：饥饿，低优先级的进程可能永远得不到运行

  高响应比优先级调度算法是一种优先级调度算法，用于作业调度

• 时间片轮转（RR）：

  介绍：专为分时系统设计，类似于FCFS，但增加了抢占。为每个进程分配不超过一个时间片的CPU。时间片用完后，该进程将被抢占并插入就绪队列末尾，循环执行

3.3实时调度（理解）

• 实时调度是针对实时任务的调度，分为硬实时任务HRT和软实时任务SRT

• 实时调度所需的条件

  必要信息：就绪时间、开始截止时间、处理时间、资源要求、优先级

  处理能力强：
  Σ（处理时间i / 周期时间i）≤ N（N为CPU的个数）

  采用抢占式调度机制

  采用快速切换机制

• 实时调度算法的分类：

  HRT、SRT；抢占式（基于时钟中断的抢占式优先级调度算法、立即抢占的优先级调度算法）、非抢占式（非抢占式轮转调度算法、非抢占式优先级调度算法）

• 常见的实时调度算法：

  最早截止时间优先（EDF）、最低松弛度优先（不考）

3.4死锁概述

3.4.1死锁的定义、必要条件与处理方法

• 死锁的定义：

  如果一组进程中的每个进程都在等待仅由该组进程中的其他进程才能引发的事件发生，那么该进程是死锁的

• 产生死锁的必要条件：

  互斥、请求和保持、不可抢占、循环等待

• 处理方法：
  • 系统层面处理死锁：

    确保系统永远不会进入死锁状态；允许系统进入死锁状态然后恢复系统、忽略这个问题假装系统从未出现过死锁

  • 理论层面处理死锁：

    预防、避免、检测、解除

3.4.2资源分配图（理解）

• 资源分配图：进程用⚪表示，资源用 口 表示。 进程指向资源表示【申请】，资源指向进程表示【占用】

  由于一类资源可以包含多个资源实例， 我们用方框中的一个圆点来代表一类资源中的一个资源实例

  请求边由进程指向方框中的R，而分配边则始于方框中的一个圆点。
  

• 每一个进程通过如下方法来使用资源：申请、使用、释放

• 死锁资源分配图如下：

  • 如果图没有环，那么不会有死锁！
  • 如果图有环，那么： 如果每一种资源类型只有一个实例，那么死锁发生； 如果一种资源类型有多个实例，那么可能死锁。

• 当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和 解除死锁的手段。为此，系统必须：
  • 保存有关资源的请求和分配信息；
  • 提供一种算法，以利用这些信息来检测系统是否已进入死锁状态
• 通过资源分配图的简化，判断是否死锁 的算法：
  • 在资源分配图中，找出一个既不阻塞又非独立的进程结点pi 。
  • p1释放资源后，便可使p2获得资源而继续运行，直到p2完成后又释放出 它所占有的全部资源；
  • 在进行一系列的简化后，若能消去图中所有的边，使所有进程都成为孤 立结点，则称该图是可完全简化的，即没有死锁
    
• 有关文献已经证明，所有 的简化顺序，都将得到相同的不可简化图
• 死锁定理：当且仅当S状态的资源分配图是不可完全 简化的。

3.5死锁预防（理解）

通过破坏成圣死锁的4个必要条件中的一个或几个来实现

• 互斥：互斥条件是非共享设备锁必须具备的条件，不仅不能改变，还应加以保证
• 请求和保持：必须保证进程申请资源的时候没有占有其他资源
• 非抢占：如果一个进程的申请没有实现，它要释放所有占有的资源
• 循环等待：对所有的资源类型排序进行线性排序，并赋予不同的序号，要求进程按照递增顺序申请资源。（可防止出现环路）

3.6用银行家算法避免死锁

• 死锁避免算法动态检查资源分配状态，以确保不会出现循环等待的情况
• 当进程申请一个有效的资源的时候，系统必须确定分配后是安全的
• 如果存在一个安全序列，则系统处于安全态

所需变量

• Available: 长度为 m的向量。如果available[ j ]=k,那么资源Rj 有k个实例有效
• Max: n x m 矩阵。 如果Max[ i, j ]=k,那么进程Pi可以最多请求资源Rj 的k个实例
• Allocation: n x m 矩阵。 如果Allocation[ i, j ]=k,那么进程Pi当前分配了k个资 源Rj的实例
• Need: n x m 矩阵。如果Need[ i, j ]=k,那么进程Pi还需要k个资源Rj的实例

算法流程图
例：

例题：
由5个进程组成进程集合P={P0,P1,P2,P3,P4}，且系统中有3类资源A,B,C，假设在某时刻有表3-4的进程资源分配情况。请问当x,y,z取下列值时，系统是否处于安全状态？

3.7死锁的检测与解除（理解）

• 死锁检测算法：

  用于检测系统状态，以确定系统中是否发生了死锁

• 死锁解除算法：

  当确定系统中发生了死锁时，利用该算法将系统从死锁状态解脱出来

第四章进程同步

4.1临界区问题

进程中涉及临界资源的代码段

item nextConsumed;
while (1) {//进入区while (counter == 0)/* do nothing */nextConsumed = buffer[out];out = (out + 1) % BUFFER_SIZE;counter--; //临界区//退出区break;//其它区
}

• 解决临界区问题的同步机制，需要遵循下列4条准则：空闲让进、忙则等待、有限等待、让权等待（当进程不能进入自己的临界区时，应该立即释放处理机，避免进程陷入忙等）

4.2信号量机制

• 软件同步机制和硬件同步机制，都无法实现“让权等待”
• 原语：只能一气呵成，不能被中断。原语是由关/开中断指令实现的。 因此若能把进入区、退出区的操作用原语来实现，则可避免同时访问临界区的问题
• wait（S）原语和Signal（S）原语，可以理解为一个名为wait/signal的方法（函数），S即为我们传入的参数——信号量
• PV操作：
  • 常常把wait（S）写成P操作，signal（S）写成V操作。即：wait（S）又称为P（S），为进入操作；signal（S）又称为V（S），V为退出操作
  • P.V操作必须成对出现，有一个P操作就一定有一个V操作
  • 当为互斥操作时，它们同处于同一进程；当为同步操作时，则不在同一进程中出现
• 信号量机制缺点：同步操作分散、易读性差、不利于修改和维护、正确性难以保证

常见信号量：

• 整型信号量：S为整型变量。缺点：进程忙等

wait(S)：while s<=0 ; /*do no-op*/s:=s-1;signal(S)：s:=s+1;

• 记录型信号量：去除忙等的信号量
  • 每个信号量S除一个整数值S.value外，还有一个进程等待队列S.list，存放阻塞在该信号量的各个进程PCB
  • 信号量只能通过初始化和两个标准的原语PV来访问，作为OS核心代码执行，不受进程调度的打断
  • 初始化指定一个非负整数值，表示空闲资源总数（又称为“资源信号量”），若为正值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数

wait(semaphores *S) { //请求一个单位的资源S->value --; //资源减少一个if (S->value<0) block(S->list) //进程自我阻塞
}
signal(semaphores *S) //释放一个单位资源
{S->value++; //资源增加一个if (S->value<=0) wakeup(S->list); //唤醒等待队列中的一个进程
}

• AND型信号量：
  • 基本思想：将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。
  • 对若干个临界资源的分配，采用原子操作。
  • 在wait（S）操作中增加了一个“AND”条件，故称之为AND同步

Swait(S1，S2，…，Sn) {while (TRUE) {if (Si>=1 && … && Sn>=1) {for (i =1;i<=n;i++) Si--){break;}}}}else {//......}
}}

信号量集——扩充AND信号量：对进程所申请的所有资源以及每类资源不同的资源需求量，在一次P、V原语操作中完成申请或释放

• 信号量的应用：信号量必须置一次且只能置一次初值，初值不能为负数；除了初始化，只能通过执行P、V操作来访问信号量
  • 利用信号量实现进程互斥：设置互斥信号量
  • 利用信号量实现前趋关系
  • 利用信号量实现进程同步：设置同步信号量

//信号量实现互斥
semaphore mutex; 
mutex=1; // 初始化为1
while(1)
{wait(mutex);临界区；signal(mutex);剩余区；
}

//信号量实现进程同步
P1(){C1;signal(s);…
}P2(){…wait(s); C2;
}

4.3管程机制

• 由编程语言解决同步互斥问题
• 一个管程定义了一个数据结构和能为并发进程执行（在该数据结构上）的一组操作
• 管程的功能：互斥（管程中的变量只能被管程中的操作访问、任何时候只有一个进程在管程中操作、类似临界区、由编译器完成）、同步

4.4经典的进程同步问题

4.4.1生产者-消费者问题

• 需要注意的地方
  • 用于实现互斥的wait（mutex）和signal（mutex）必须成对出现
  • 每个程序的多个wait操作的顺序不能颠倒，应先执行对资源信号量的wait操作，再执行对互斥信号量的wait操作，否则可能会引起进程死锁。
• 具体代码实现请参考：生产者消费者模型

//生产者-消费者 伪代码var items = 0, space = 10, mutex = 1;
var in = 0, out = 0;
item buf[10] = { NULL };producer {while( true ) {wait( space );  // 等待缓冲区有空闲位置， 在使用PV操作时，条件变量需要在互斥锁之前wait( mutex );  // 保证在product时不会有其他线程访问缓冲区// productbuf.push( item, in );  // 将新资源放到buf[in]位置 in = ( in + 1 ) % 10;signal( mutex );  // 唤醒的顺序可以不同signal( items );  // 通知consumer缓冲区有资源可以取走}
}consumer {while( true ) {wait( items );  // 等待缓冲区有资源可以使用wait( mutex );  // 保证在consume时不会有其他线程访问缓冲区// consumebuf.pop( out );  // 将buf[out]位置的的资源取走out = ( out + 1 ) % 10;signal( mutex );  // 唤醒的顺序可以不同signal( space );  // 通知缓冲区有空闲位置}
}

4.4.2读者-写者问题

• 有两组并发进程：读者和写者，共享一组数据区
• 要求：允许多个读者同时执行读操作；不允许读者、写者同时操作；不允许多个写者同时操作。
• 分类：读者优先（第一类 读者写者问题）；写者优先（第二类 读者写者问题）
• 具体代码实现请参考：读者写者问题三种情况详细解释(通俗易懂)

//读者优先（伪代码）// 互斥读者与读者
semaphore rmutex = 1;
// 互斥读者与写者，写者与写者
semaphore mutex = 1;
// 表示读者数量，需看成临界资源，即进来一个读者就+1操作
int readcount = 0;// 读者进程
void reader()
{while(TRUE){// 互斥其他读者，只允许一个读者进入P(rmutex);if(readcount == 0)// 如果读者数目为0，所以就必须互斥写者P(mutex);// 读者数+1readcount++;// 释放，让其他读者进来修改readcountV(rmutex);/* 读操作 */// 读者离开，需要访问readcountP(rmutex);readcount--;// 如果此时没有读者了，表示写者可以进行写了if(readcount == 0)V(mutex);// 释放readcount资源V(rmutex);}
}void writer()
{while(TRUE){// 写者和一般消费者进程一样，获取信号量值P(mutex);/* 写操作 */// 让文件可读和可写V(mutex);}
}void main()
{reader();writer();reader();/*.......*/
}

//写者优先（伪代码）// 互斥读者与写者
semaphore mutex = 1;
// 互斥读者
semaphore rmutex = 1;
// 互斥写者
semaphore wmutex = 1;
// 表示是否还有写者
semaphore readable = 1;// 读者数量，写者数量
int readcount = 0, writecount = 0;void reader()
{// 先看是否可读P(readable);// 互斥其他读者修改readcountP(rmutex);if(readcount == 0)// 如果没有读者，需要互斥写者P(mutex);readcount++;V(rmutex);V(readable);/* 读取中 */P(rmutex);readcount--;if(readcount == 0)V(mutex);V(rmutex);
}void writer()
{// 互斥其他写者，写入writecountP(wmutex);if(writecount == 0)// 此时不能让写者以后的读者进去P(readable)writecount++;V(wmutex);// 互斥在写者之前的读者P(mutex);/* 写入中 */// 写入完成离开V(mutex);P(wmutex);writecount--;if(writecount == 0)// 让写者以后的读者可读V(readable);V(wmutex);}void main()
{reader();writer();reader();/* ... */
}

第五章存储器管理

5.1存储器的层次结构

• 存储层次：CPU寄存器；主存：高速缓存、主存储器、磁盘缓存；辅存：固定磁盘、可移动介质
  • 寄存器：访问速度最快，与CPU协调工作，加个贵
  • 主存储器：内存或主存
  • 高速缓存：介于寄存器和春初期之间；主要用于备份内存中较常用的数据，以减少处理机对内存的访问次数。缓和内存与处理机速度之间的矛盾。
  • 磁盘缓存：暂时存放频繁使用的一部分磁盘数据和信息；缓和主存的访问速度和磁盘的I/O速度的不匹配；利用主存的部分空间，主存可看成辅存的高速缓存。
  • 层次越高，访问速度越快，价格也越高，存储容量也最小
  • 寄存器和主存掉电后存储的信息不再存在，辅存的信息长期保存

5.2程序的装入与连接（理解）

• 程序的运行步骤

  • 编译：由编译程序（Compiler）对源程序进行编译，形成若干个目标模块
  • 链接：由链接程序（Linker）将目标模块和它们所需要的库函数链接在一起，形成一个完整的装入模块
  • 装入：由装入程序（Loader）将装入模块装入内存

• 物理地址和逻辑地址

  • 物理地址（绝对地址）：内存以子节为单位编址
  • 物理地址空间：所有物理地址的集合
  • 逻辑地址（虚拟地址、相对地址）：由CPU产生的地址，即程序编译后使用的相对于0子节的地址
  • 逻辑地址空间：由程序所生成的所有逻辑地址的集合

• 地址的翻译：翻译规则取决于虚拟内存采用的组织机制，包括：分段机制和分页机制
  
• 内存保护

  • 目的：保护OS不被用户访问，保护用户进程不会相互影响
  • 实现：硬件判断 “基地址<物理地址<=（基地址+界限地址）” 是否成立。

• 程序的装入

  • 绝对装入方式： 编译时产生的地址使用绝对地址，程序或数据呗修改时，需要重新编译程序
  • 可重定位装入方式： 编译后的目标模块使用相对地址、在装入时完成重定位（静态重定位）、需硬件支持
  • ==动态运行时装入方式：==编译后目标模块使用 相对地址 、在运行时程序在 内存中的位置不固定，需要完成重定位；地址变换推迟到程序真正要执行时才进行

• 程序的链接

  • == 静态链接== ：在程序运行前，将目标模块及它们所需的库函数 链接成一个完整的装配模块，以后不再拆开；对相对地址进行修改； 变换外部调用符号
  • == 装入时动态链接== ：在装入内存时，采用 边装入边链接的链接方式；便于修改和更新、实现时目标模块的共享
  • 运行时动态链接： ：将某些目标模块的 链接推迟到执行时才执行，加快装入过程，节省大量的内存空间

5.3对换与覆盖（理解）

• 为什么要有对换？

  • 内存中 某些进程由于某事件尚未发生而被阻塞运行，却占用了大量的内存空间 ，甚至可能出现在内存中所有进程都被阻塞而迫使CPU停止下来等待的情况
  • 另一方面，却又有着 许多作业在外存上等待，因无内存而不能进入内存运行 的情况。
  • 浪费资源，降低系统吞吐量

• 什么是对换？

  • 首先，把 内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间。
  • 然后，再 把已具备运行条件的进程或进程所需的程序或数据，调入内存。
  • 对换是 提高内存利用率 的有效措施，广泛应用于OS中

• 对换的类型

  • 整体对换 ：对换以整个进程为单位，也称为 进程对换 。被广泛应用于多道程序系统，并作为处理机中级调度;
  • 为了实现进程对换，系统必须能实现三方面的功能：对换空间的管理、 进程的换出、进程的换入
  • 页面(分段)对换 ：对换是以“页”或“段”为单位进行的，又统称为 “部分对换”。目的是为了支持虚拟存储系统

• 对换区的管理

  • 主要目标 ：提高进程换入和换出的速度、提高文件存储空间的利用率、应采用 连续分配方式 ，很少考虑碎片问题
  • 盘块管理中的数据结构：记录外存对换区中的空闲盘块的使用情况

• 进程的换出

  • 对换进程在实现进程换出时，是将内存中的某些进程调出至对换区，以便腾出内存空间
  • 分为两步：选择被换出的进程（阻塞状态或睡眠状态的进程，低优先级的进程）、进程换出过程（先申请兑换区 → 启动磁盘 → 直到无阻塞进程）

• 进程的换入

  • 首先查看PCB集合中所有进程的状态， 从中找出“就绪”状态但已换出的进程
  • 有许多这样的进程时，它将选择 其中已换出到磁盘上时间最久的进程作为换入进 程，为它申请内存
  • 如果申请成功，可直接将进程从外存调入内存；
  • 如果失败，则需先将内存中的某些进程换出，腾出足够的内存空间后，再将进程调 入

• 覆盖
  • 解决的问题：程序大小超过物理内存总和
  • 程序执行时：只在内存中保留那些在任何时间都需要的指令和数据；程序的不同部分在内存中相互替换。
  • 由程序员声明覆盖结构，不需要操作系统的特别支持
  • 覆盖结构的程序设计很复杂
  • 应用于早期的操作系统

5.4动态分区分配

5.4.1动态分配——基于顺序搜索（掌握！）

• 依次搜索空闲分区链上的空闲分区，寻找一个其大小能够满足要求的分区
• 分类：首次适应算法（FF）、循环首次适应算法（NF）、最佳适应算法（BF）、最坏适应算法（WF）

5.4.2动态分配——基于索引搜索（理解）

• 提高搜索空闲分区的速度，在大、中系统中采用
• 快速适应算法、伙伴系统、哈希算法
• 快速适应算法：
  • 将空闲分区按其容量大小进行分类，具有相同容量的所有空闲分区设有一个空闲分区链表
  • 系统设有一张管理索引表，每一项对应一个空闲分区类型
  • 分配时，根据进程长度，从索引表中寻找到能容纳它的最小空闲分区链表；从链表中取下第一块进行分配
  • 优点：不分割分区，不产生碎片，查找效率高；缺点：分区归还主存时算法复杂，系统开销较大。存在浪费
• 伙伴系统
  • 内存按2的幂的大小来分配，即4KB、8KB等
  • 满足要求是以2的幂为单位的
  • 如果请求不为2的幂，则需要调整到下一个更大的2的幂，然后再判断
  • 当分配需求小于现在可用内存时，当前段就分为两个更小的2的幂段，然后再判断
• 哈希算法
  • 建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每个表项对应于一个空闲分区链表的头指针
  • 进行分配时，根据空闲区大小，通过计算哈希函数，得到在哈希表中的位置，找到对应的空闲分区链表
  • 优点：查找快速

5.5分页存储管理方式

• 把 物理内存 分成大小固定的块，称为 物理块 （frame）。（大小为2的幂，通常为1KB-8KB）
• 把 逻辑内存 也分成固定大小的块，称为 页 （page）
• 运行一个有N页大小的程序，需要找到N个空的页框来装入程序
• 存在 页内碎片 ：进程最后一页经常装不满，而形成不可利用的碎片
• 页的地址结构为：页号P、位移量W（页内地址）
• 页表：
  • 系统为每个进程建立了一张页表
  • 逻辑地址空间内的所有页，依次在页表中有一表项，记录相应页在内存中对应的物理块号
  • 页表的作用：实现从页号到块号的地址映射
    
• 页表结构：
  • 现代的大多数计算机系统，都支持非常大的逻辑地址空间。在这样的环境下，页表就变得非常大，要占用相当大的内存空间
  • 解决办法：对页表所需要的内存空间，采用 离散分配 方式，不分页表调入内存
  • 页表结构的类型：两级页表、多级页表、反置页表

第六章虚拟存储器

6.1常规存储器管理方式的特征和*局部性原理*

• 常规存储器管理方式的特征：
  1. 一次性：
     • 作业被一次性全部装入内存
  2. 驻留性：
     • 作业一直驻留在内存
• 局部性：

  一段较短的事件内，程序的执行仅局限于某个部分，它所访问的存储空间也局限于某个区域

  1. 时间局限性
     • 如果程序中的某条指令被执行、某数据被访问，则不久以后该指令、数据可能会被再次执行、访问
     • 产生原因：程序中存在着大量的循环操作
  2. 空间局限性
     • 一旦程序访问了某个存储单元，不久之后，其附近的存储单元也将会被访问，即程序在一段时间内所访问的地址可能集中在一定的范围之内
     • 典型情况：程序的顺序执行

6.2请求分页

• 最小物理块数的确定：保证进程正常运行所需的最小物理块数。取决于指令的格式、功能和寻址方式。
  • 平均分配算法；
  • 按比例分配算法； 各进程页面总和S = ΣSi 每个进程所能分到的物理块数 bi ＝ Si / S * m
  • 考虑优先权的分配算法；
• 页面调入策略：
  • 何时调入页面？预调页策略、请求调页策略
  • 从何处调入页面？
  • 如何调入页面？查找所需页在磁盘上的位置、查找一内存空闲块、将所需页读入新空闲块然后更新页表、重启用户进程
• 缺页率的计算：
  • S：访问页面成功次数
  • F：访问页面失败次数
  • A：总访问次数 = S+F
  • 缺页率 = F/A
• 缺页中断处理时间：
  • β：被置换的页面被修改的概率
  • ta：被置换页面被修改的缺页中断处理时间
  • tb：被置换页面没有被修改的缺页中断时间
  • 缺页中断处理的事件 = β * ta + （ 1 - β ）* tb

6.3页面置换算法

• 页面置换： 找到内存中没有使用的一些页，换出
• 性能的关键点：找出一个导致最小 缺页数的算法
• 同一个页可能会被装入内存多次（可能造成“抖动”）
• 页面置换完善了逻辑内存和物理内存的划分——在一个较小的物理内存基础之上可以提供一个大的虚拟内存
• 常见的页面置换算法： 最佳置换算法 OPT 、先进先出置换算法 FIFO 、最近最久未使用算法 LRU 、最少使用算法 LFU 、 Clock置换算法 、页面缓冲算法
• 目的：尽可能小的缺页率

6.4“抖动”与工作集（理解）

根本原因： 同时在系统中运行的进程太多，导致分配给每个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时会频繁地出现缺页，必须请求系统将所缺之页调入内存。

每个进程的大部分时间都用于页面的换入/换出，而几乎不能再去做任何有效的工作，从而导致发送处理机的利用率急剧下降而趋于0的情况。此时的进程处于“抖动”状态

第七章输入/输出系统

7.1磁盘性能概述和磁盘调度

• 磁盘的结构
  • 盘面（磁头） ：磁盘设备可 包含一或多个盘片，每个盘片分为一个或两个盘面 ，每个面上有一个读写磁头
  • 磁道（柱面） ：每个 盘面可分为若干条磁道
  • 扇区 ：每条 磁道逻辑上分成若干个大小相同的扇区 。每个扇区的大小相当于一个盘块（数据块）
  • 每条磁道上可存储相同数目的二进制位
  • 磁盘觅渡即每英寸中所存储的位数，显然内层磁道的密度较外层磁道的密度高。
    
• 数据的组织和格式
  • 为了在磁盘上存储数据，必须先将磁盘格式化
  • 每个扇区包括2个字段：标识符字段、数据字段
• 磁盘的类型
  • 硬盘、软盘；
  • 单片盘、多片盘；
  • 固定头磁盘：每个磁道上都有一个读写磁头。
  • 移动头磁盘：每个盘面仅配有一个磁头，能移动寻道

7.1.1磁盘容量计算

容量=柱面×磁头×扇区，每扇区存放512B数据

7.1.2磁盘访问时间的计算

• 磁盘在工作时是以恒定速率旋转
• 读写的过程： 磁头必须移动到所要求的磁道上→等待所指定的扇区的开始位置旋转到磁头下→开始读写数据
• 磁盘的访问时间计算公式： 寻道时间 + 旋转延迟时间（查询扇区平均时间） + 传输时间
• 寻道时间 = 启动磁臂的时间 + m * 磁头移动 n 条磁道所花费的时间 m是一个常数，一般是0.2.对于高速磁盘则小于0.1
• 旋转延迟时间（查询扇区平均时间）= 0.5 * 1 / 转速 （转速的单位： r/s，注意换算。本质：0.5 * 周期。T = 1 / f）
  

7.1.3磁盘调度算法与平均寻道时间的计算

• 磁盘调度的目标，是使磁盘的平均寻道时间最小。
• FCFS算法（先来先） ：根据进程请求访问磁盘的先后次序进行调度
• SSTF调度算法（最短） ：寻找当前距离最近的磁头所在的磁道，以使每次的寻道时间最短，但不保证平均寻道时间最短
• SCAN调度算法（反复循环扫描） ：
  1. 磁臂 从磁盘的一段向另一端移动，沿途响应服务请求。
  2. 到达另一端时，磁头改变移动方向，继续处理。磁头在磁盘上来回扫描
• CSCDN调度算法（单向循环扫描，但是以最远请求为断点）
  1. 磁头只移动到一个方向上最远的请求为止！然后马上返回另一端的最远请求（而非另一端！）
     
     

第八章文件管理

8.1文件保护

• 影响文件安全性的主要因素：
  1. 认为因素 ：人们有意或无意的行为会使文件系统中的数据遭到破坏或丢失
  2. 系统因素 ：系统的某部分出现异常情况会造成数据的破坏或丢失，特别是作为存储数据的主要介质——磁盘，其一但出现故障将会产生难以估量的影响
  3. 自然因素 ：随着时间的推移，存放在磁盘上的数据会逐渐消失
• 针对上述因素的措施：
  1. 通过存取控制机制，防止人为因素导致文件不安全
  2. 采取系统容错技术，防止系统某部分的故障导致文件不安全
  3. 建立后备系统，防止自然因素导致文件不安全

8.1.1保护域

每个进程仅能在保护域内执行操作，而且只允许进程访问它们具有“访问权”的对象

• 访问权：为了对系统中的对象加以保护，应由系统来控制进程对对象的访问。我们把一个进程能对某对象进行操作的权利称为访问权
• 保护域：为了对系统中的资源进行保护，引入了保护域的概念，简称“域”。是进程对一组对象的访问权的集合。进程只能在指定域内执行操作。

第九章磁盘存储器管理

9.1位示图法

• 位示图

  利用二进制的一位来表示磁盘中一个盘块的使用情况。当值为“0”时，表示对应的盘块空闲；当值为“1”时，表示对应的盘块已被分配。部分系统相反。