操作系统复习笔记（自用版）-526互联

第一章：操作系统概述

操作系统的定义：是计算机系统中最基本、最重要的系统软件，是其他软件的支撑软件。
计算机系统的组成：计算器，控制器，存储器，输入设备，输出设备

单道批处理系统

多道批处理系统

特点：多道性，宏观上的并行性，微观上的串行性。

分时系统

多个用户分享了CPU的时间，所以称为分时系统。在分时系统中，多个用户何以通过终端同时访问系统。

分时系统与多道批处理系统相比，具有明显的特点：

交互性，及时性，独立性，多路性

批处理系统、分时系统的出现标志着操作系统的形成

实时系统

要求系统对特殊输入做出反应的速度足以控制发出实时信号的对象。

特点：

及时性，交互性，独立性，多路性，高可靠性

操作系统主要功能

处理机管理

进程控制，进程同步，进程通信，进程调度

存储管理

内存分配，存储保护，地址映射，内存扩充

设备管理

缓冲区管理，设备分配，设备处理，虚拟设备管理

文件管理

存储空间管理，目录管理，读写管理，文件保护，文件系统安全性

用户接口

命令接口，程序接口，图形接口

操作系统的基本特征：

并发性：并发和多道是同一事物的两个方面。

共享性：多道必然带来共享。互斥共享和同时共享

虚拟性：将物理上的一个资源或设备变成逻辑上的多个资源和设备。

异步性：又称不确定性，指多个作业的执行顺序和作业的执行时间不确定。

第二章：中断

中断信号：发生某事件时发出的信号。

中断源或中断事件：引起中断的事件。

程序状态字（PWS）

指令地址，条件码，目态/管态，中断屏蔽位，寻址方式、编址、保护键，

响应中断的内容

中断的特点：

随机性，可恢复性，自动性。

中断的作用：

实现CPU与I/O设备的并行工作，实现硬件故障处理，实现人机通信，实现多道程序和分时操作，实现实时处理，

中断的类型：

按功能分类，按方式分类，按来源分类

中断优先级：

由硬件规定，

一般情况是：硬件故障中断>自愿中断>程序性中断>外部中断>I/O中断

中断屏蔽：

自愿中断不能被屏蔽

中断处理过程：***

保护现场和传递参数--->执行响应的中断服务程序--->恢复现场并退出中断

操作系统由中断驱动

关中断：使系统不再响应任何中断， 在保护现场和恢复现场之前都要关中断。

中断是异步事件 ----在任何时候都可能发生

中断的响应过程：

发现中断源——>保护和恢复现象——>中断响应

第三章：进程和线程

虽然并发和并行都是在同一时间内执行多个任务，但并发通常是在一个或多个CPU核心上轮流处理多个任务，主要目的是提高系统资源的利用效率；而并行则是同时使用多个CPU核心或计算节点处理多个任务，主要目的是提高计算速度和处理能力。

程序顺序执行特征

顺序性、封闭性、可再现性。

~~单道程序顺序执行方式不利于系统资源的充分利用，但其特征却为程序员检查和校正程序错误带来极大方便~~

程序间能并发执行的条件

———Bernstein条件。

R(p1 )交 W(p2 )并 R(p2) 交 W(p1) 并 W(p1) 交 W(ap2) = {}。

成立则能并发，不成立则不能并发。

程序并发执行特征：

间断(异步)性、失去封闭性、不可再现性

进程的定义：

(1)程序的一次执行；

(2)可以和别的计算并发执行的计算；

(3)定义在一个数据结构上，并能够在其上进行操作的一个程序；

(4)是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位。

总结就是： 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

进程与程序之间的关系

一个进程可以包含多个程序，一个程序也可以被多个进程执行

进程状态：

两状态模型：运行态和非运行态

五状态模型：新建态，就绪态，运行态，阻塞态，终止态。

挂起：

当内存中没有就绪的进程时，把内存中阻塞的进程换出到外存中的挂起队列。而将外存中的就绪进程激活，存入内存。

有 挂起就绪态 和 挂起阻塞态 ，两种

PCB

进程控制块（PCB）-------- 进程的唯一标识符

进程、线程

进程由线程组成，线程是能够独立运行的实体，即控制流，使处理机进行调度和分派的基本单位。

线程简介：

操作系统中引入进程的目的是使多个程序能并发执行，以提高资源利用率和系统吞吐量；再引入线程，是为了减少程序再并发执行时所付出的时空开销，使操作系统具有更好的并发性。

进程的两方面特点：

资源所有权，调度

引入线程后：

进程 --> 资源分配的基本单位。线程 --> 调度和分派的基本单位

线程的主要特征：

并发性；共享性；动态性；结构性。

线程的关键状态：

运行态，就绪态，阻塞态

并发：

// 并发是指在一段时间内，多个任务或线程同时执行或者交替执行，以实现更高的计算效率。在计算机科学中，通常将并发定义为程序结构的一种形式，它使用独立的控制流来处理不同的任务，这些任务可能会相互依赖或协作完成某个目标。

// 在现代计算机系统中，常常会有多个任务需要同时进行，如打印文件、接收网络数据、响应用户输入等等，这些任务需要同时被处理，以提供良好的响应性能和操作效率。同时，多核计算机的普及也推动了并发编程技术的发展，以便更好地利用多核处理器的处理能力。

// 并发可以通过线程、进程、协程以及异步编程等方式来实现，并发的实现需要关注以下几个方面：

1. 任务的调度和控制：并发的任务需要有一个机制来管理和调度它们的执行，以确保它们能够按照一定的次序完成。常见的调度方式包括线程池、协程调度等等。

2. 共享资源的访问控制：并发是多个任务或线程同时执行或者交替执行，因此它们可能存在竞态条件。需要使用加锁、信号量、原子操作等方式来保护共享资源的访问，避免数据不一致问题的发生。

3. 数据同步和通信：并发的任务之间需要互相通信和同步，这需要使用一些同步机制来确保任务之间信息的可靠传输和正确处理。常见的同步和通信方式包括管道、消息队列、锁、条件变量等等。

需要注意的是，/*并发并不等于并行。*/并发是任务的智能调度，通过将不同的任务交替执行来提高系统的效率。而并行则是将不同的任务划分为多个子任务，并行执行，以便更充分地利用多核系统的处理能力。

并发与互斥、并行与互斥、并行与并发

//   并发与互斥
并发和互斥不是矛盾的，它们实际上是相对的概念，用来描述不同的计算模型。在实际的计算机系统中，一些任务需要同时或者交替执行，这就需要用到并发模型。同时，由于多个任务间需要访问同一共享资源的情况很常见，因此需要使用互斥机制来保证存取该共享资源的原子性，以避免竞争条件的出现。所以，在实际应用中，并发和互斥是一起使用的，彼此相得益彰，而不是矛盾的关系。

例如，操作系统中的进程或线程可以并发地访问同一共享资源，但同时需要使用一些锁或信号量等机制来确保对共享资源的互斥访问，避免数据的不一致性。

另外，互斥的实现通常也需要使用同步机制，如信号量、条件变量等，而这些机制本身也是支持并发性的。因此，并发和互斥是相辅相成的，既需要实现互斥保证数据的一致性，同时又需要通过并发来提高系统的性能和响应性。

//   并行与互斥
并行和互斥在某些情况下可能存在矛盾。并行是指系统可以同时处理多个任务，通过在多个处理器上并行运行任务来提高系统的处理能力。而互斥机制则是用来保证共享资源访问的原子性，避免多个线程或进程同时访问导致的数据不一致性问题。

当多个线程或进程需要同时访问共享资源时，为了保证数据的一致性，一个线程或进程可能需要获取到一个锁或者信号量，从而会阻塞其它并发运行的线程或进程。这就可能会导致并行性下降，从而影响系统的性能。

//   并发与并行
并行和并发是计算机领域中非常常见的概念，虽然它们的概念相似，但其本质不同。

并行：指在同一时刻同时执行多个任务，实现可同时高效地执行多个任务。在多核处理器、GPU等硬件层面上，能够更高效地利用硬件资源，提高计算机处理任务的并行能力。

并发：指在同一时间段内，同时有多个任务执行，但不一定是同时执行，可能是交替地执行。并发提高了资源的利用率、响应度和处理能力，尽可能的将多个任务并行的进行，达到尽可能高的处理效率。 

在一些情况下，并行和并发可以相互转换，但它们侧重点不同。并行主要强调任务的同时执行，通常需要更强的硬件支持，可同时完成多项任务，提高计算机效率和性能；而并发主要强调任务的并行处理，注重解决业务瓶颈，最大限度的提高业务问题的解决效率，也更加注重提高用户的体验。

需要注意的是，并发和并行不是绝对的二元对立概念，它们经常同时存在于各种计算机系统和应用场景中。例如，任务划分成多个子任务进行并行处理，同时允许多个线程和进程并发地访问共享资源，以达到更高的系统效率，更好的用户体验。

用户级线程的缺点

第（1）点：阻塞所有线程答疑。操作系统书 P55

用户级线程和内核级线程是两种不同的线程实现方式。用户级线程是由用户程序库管理的线程，它们只能在用户空间运行，内核并不知道它们的存在。而内核级线程则是由操作系统内核直接管理的线程，可以在内核态和用户态切换。当用户级线程执行系统调用时，会触发一个陷入内核的过程，这时候用户程序需要向内核发起调用，从而将控制权交给内核进程处理，内核会为该线程进行必要的服务或操作。在这个过程中，用户级线程所在的进程会被阻塞，因为内核是单核资源，同一时间只能处理一个请求，当某个线程正在被内核服务时，该进程中的其他用户级线程便无法继续执行。

这种现象称为“多个用户级线程共享一个内核级线程”，也称为“内核级线程抢占”或“内核级多任务”。在此情况下，虽然所有的用户级线程存在于同一个进程中，但它们是互相独立的，只要内核已经将一个用户级线程离开 CPU 并开始执行，那么就需要进行“上下文切换”，切换到另一个用户级线程中执行。

因此，如果一个用户级线程由于某种原因被内核挂起，那么进程内的所有用户级线程就会被阻塞，直到该用户级线程被内核重新调度为止。这也是用户级线程存在并发性问题的原因之一，需要谨慎地使用多线程编程技术。

临界区和临界资源

使用临界资源的 程序代码 成为临界区

临界资源就是进程要访问的资源，如打印机，磁带机等。

多个进程共享临界区，需遵循的调度原则

(1). 空闲让进 (2). 忙则等待第58页

(3). 有限等待 (4). 让权等待

管程的定义

对分散在各进程中的临界区集中进行管理，并将系统中的共享资源用数据结构抽象地表示出来。

既便于系统对共享资源的管理，有实现了进程间对资源的互斥访问。

管程的特点

共享性，安全性，互斥性。

第四章：调度与死锁

系统性能的好坏很大程度上取决于处理机调度性能的好坏。

调度

1. 高级调度（也称为作业调度）：负责从系统的所有作业中选择一部分进程或任务，将其调入内存，并为其分配操作系统资源（如 CPU、内存等），以便进程的执行。高级调度的目的是使系统的资源利用率更加高效，并确保系统的负载适度均衡，避免系统过度拥塞或过度空闲。

2. 中级调度（也称为进程调度或重定位调度）：负责选择在内存中的进程，通过将进程从一个 CPU 切换到另一个 CPU，更准确地分配 CPU 的使用权。中级调度的目的是提高系统的响应性和吞吐量，并确保每个进程都可合理地利用系统资源，从而最大限度地提高系统的效率和性能。

3. 低级调度（也称为线程调度或时间片调度）：负责选择正在执行的线程，并为其分配 CPU 的运行时间，通过时间片轮转的方式，以保证每个线程都有机会得到执行。低级调度的目的是提高系统的实时性、公平性和稳定性，避免线程或进程因执行时间过长而导致系统卡顿或崩溃的情况发生。

三个级别的调度目的不同，采用的调度算法和策略也不同。高级调度需要考虑资源的利用率和负载均衡；中级调度需要提高响应性和吞吐量；低级调度需要保证实时性和公平性。综合它们的层次、规律和特点，并应用于操作系统的设计与实现，可以最大限度地提高操作系统的性能和效率。

低级调度是操作系统最核心的部分，运行的频率最高，也称其为短程调度。

三种调度队列图

调度原则（调度算法设计考虑因素）

周转时间 = 后备队列等待时间+就绪队列等待时间*+CPU执行时间

+等待I/O完成时间* （带*说明可能执行多次）

平均周转时间：用于衡量不同调度算法对同一个作业流的调度性能。

平均带权周转时间：反映作业在整个处理过程中，想要获得一个单位的服务时间所要花费的等待时间，用于衡量同一个调度算法对不同作业流的调度性能。

响应时间 = 请求信息传送到处理机的时间+处理机处理信息的时间+响应信息回送到终端的时间
截止时间
优先权
吞吐量
处理机利用率
公平性

调度算法***

周转时间 = 完成时间 - 到达时间

带权周转时间 = 周转时间 / 服务时间

先来先服务算法

顾名思义，先到达先运行。比较有利于长作业（进程），不利于短作业（进程）。并且它的平均周转时间和平均带权周转时间与作业，到达顺序和调度顺序有关。

短作业优先调度算法

优先挑选所需服务时间最短的作业进行调度，照顾了短进程而忽略了长进程，甚至可能使长进程无法获得处理机。

优先级调度算法

根据事先设定好的进程优先级来选取优先运行的算法，当出现更高优先级的进程时，会根据

抢占式（立即剥夺当前进程所占机会，不管完成与否都要立即停止）

非抢占式（等当前进程执行完之后再开始运行）

两种策略来进行调度。

优先级两种划分方式：静态优先级，创建进程时确定后就不会再变

动态优先级，随着时间的推移而进行调整

时间片轮转调度算法

在先来先服务基础上，加了一个时间片，每个进程执行一个规定的时间片后，继续排到队伍末尾，进行下一轮循环。所以时间片的大小对系统性能有很大的影响。

太小利于短作业，但增加系统开销，太大退化为先到先服务算法。

最高响应比优先调度算法

响应比 = 周转时间/服务时间 = （等待时间+服务时间）/ 服务时间 = 1 + 等待时间/服务时间

所以长作业在等待一定时间后，必然会随着优先级的提高而分配到处理机，这是一个折中的调度算法。

不足的是每次调度之前都要计算每个作业的响应比，所以需要耗费一定的时间，其性能比短作业优先算法略差。性能介于先来先服务调度算法和短作业优先调度算法之间。

多级反馈队列调度算法

目前公认的一种较好的进程调度算法

多级反馈队列调度算法是一种常用的操作系统进程调度算法。它使用多个队列结构，将进程按照优先级进行分类，并根据进程的执行情况动态调整其优先级，从而实现更加高效的进程调度。

该调度算法的基本思想是将进程划分为多个优先级不同的队列，按照优先级的高低依次定时调度进程。当进程在某个队列中等待执行时间过长时，则自动将其降至较低的优先级队列进行等待，以便更加高优先级的进程可以得到更快的执行。此外，多级反馈队列调度算法还可以根据进程的执行情况动态地调整其优先级，以适应系统负载的变化和不同时段的需求。
    
多级反馈队列调度算法可以很好地平衡进程之间的优先级和相互竞争的情况，具有较高的执行效率和响应速度。但是调度算法也存在一定的缺陷，/*如容易出现饥饿问题*/，即低优先级进程在长时间内无法被执行。因此，在实际系统中，需要根据具体的需求来选择合适的进程调度算法。
    
//  有多个就绪队列，每个队列有不同的优先级，如第1队列优先级最高，第2队列次之，之后队列优先级逐个降低。   优先级越高的队列，所安排的时间片就越小。
//  一个新进程进入内存，先放入第1队列末尾，按先来先服务算法进行调度，若没在规定时间片内运行完成，则放入第2队列末尾，再等待调度执行，以此类推。
//  只有当第1~(i-1)个队列为空时，第i个队列才能运行，若低队列中进程在执行是，高队列新进进程，则要抢占正在运行进程的处理机。并把它重新放回第i个队列的末尾。

实时调度算法

最早截止时间优先调度算法：

根据任务的开始截止时间来确定任务优先级。

非抢占式~~：可获得数百毫秒至几秒的响应时间。

抢占式~~：可获得几毫秒至100毫秒的响应时间，甚至更低。

最低松弛度优先调度算法：

根据任务紧急程度来确定任务优先级，越紧急优先级越高。系统安排一个就绪队列，松弛度最低的任务排最前面（实时更新），采用抢占式调度方式。

例：一个任务必须在200ms时完成，而本身所需的运行时间为100ms，则该任务的松弛度为100ms。

另一个任务在400ms时必须完成，本身需要运行150ms，则松弛度为2 50ms。

死锁

资源

可剥夺性资源：在被进程获得后，可以被其他进程或系统剥夺的资源。

如 处理机和内存

不可剥夺性资源：分配后就不能被强制回收，只能由进程用完后自行释放。

如 磁带机和打印机

死锁的产生原因：

指多个进程因竞争资源而造成的一种僵局，如果没有外力作用，则这些进程永远不会再向前推进了。且与资源竞争及进程的推进顺序不当有关

死锁产生的必要条件：

(1) 互斥，(2)请求和保持，(3)不可剥夺，(4)循环等待

死锁预防

破坏”请求和保持“条件：简单、安全易实现，但资源浪费严重。

破坏”不可剥夺“条件：比较复杂且要付出很大代价。

破坏"环路等待"条件

死锁避免***

不安全状态 不意味着 死锁，但系统进入不安全状态后，有可能转变为死锁

死锁检测和恢复

~检测不限制资源的访问和约束进程行为。

死锁检测: 系统要做到，保存有关资源的请求和分配信息；提供算法，检测是否进入死锁

死锁恢复：可从爆多资源和撤销进程两个方面恢复

第五章：内存管理

内存：保存进程运行时的程序和数据，可读可写，内存的访问速度远低于CPU 的执行速度。

寄存器：与CPU协调工作，长度一般以字（word）为单位，用于加速存储器的访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。

高速缓冲存储器：容量远大于寄存器，但又比内存小几十个数量级。访问速度快于内存。主存中一些经常访问的信息存放在高速缓冲存储器中，减少访问内存的次数，可大幅度提高程序的执行速度。

把逻辑地址转换成物理地址的工作成为地址映射

内存共享:

一方面指共享内存资源，共同使用一个内存，另一方面指若干个作业有共同的程序段或者数据段时，可以同意放在某个存储区域，这样各作业执行时都可以访问，即共享内存的某些区域。

内存扩充：

不是扩充物理存储容量，而是利用存储管理技术提供一个比实际内存更大的逻辑存储空间这技术被称为虚拟存储管理技术。 原理就是： 通过软硬件协作，把磁盘等外存作为内存的扩充部分来使用。

地址重定位

以0为基址顺序进行编址的，称为相对地址，也称为逻辑地址或者虚地址，而相对地址的集合称为相对地址空间，也称地址空间，地址空间通过地址重定位转换到绝对地址空间，绝对地址空间也称 物理地址空间，存储空间。

常用重定位技术

静态重定位：一次性将指令地址和数据地址全部转换成物理地址。它是在程序执行之前进行的，通常由装配程序完成。

优点：容易实现，无需硬件支持。

缺点：程序经地址重定位之后不能再在内存中移动，不利于内存有效用，二是要求程序的存储空间是连续的，不能把程序放在若干个布莱纳许的区域内。

动态重定位：在程序执行的过程中进行地址重定位。

one 分区存储管理

单一连续分区存储管理

单纯的划分系统区和用户区两个区域

固定分区管理

一种简单的可运行多道程序的存储管理方式，是将内存用户空间划分为若干个固定大小的区域。(分区大小可不相等)

可变分区管理

可以根据作业对内存的实际需要，动态地分配内存空间大小。可使分区的大小和作业的大小相等。

解决了固定分区式的严重浪费内存问题，提高内存利用率。较灵活、实用

分区分配算法

针对于可变分区式分配~

首次适应算法

总是顺序查找未分分区的状态表，直至找到第一个能够满足长度要求的空闲分区，然后划分该分区，一部分分配给作业，一部分仍作为空闲区。

可能将大空间划分为许多小的空闲区，造成较多的空间碎片。

具体改进方案且其缺点在 P107

最优适应算法

总是从空闲区挑选能够满足作业需要的最小分区分配给作业的算法。

可能使得存储器中留下许多难以利用的”碎片“。

最差适应算法

总是挑选一个最大的未分分区分配给作业的算法。使得剩下的未分分区不至于太小，这样还能满足一般作业的需求。

该算法对中、小作业有利，缺点是各空闲区比较均匀的减小，工作一段时间后就不能满足较大作业空间的分配要求。

循环首次适应算法

从上一次找到的空闲区的下一个空闲区开始查找，直到找到一个能满足要求的空闲区为止。

该算法使内存中的空闲区分配的更加均匀，从而减少查找空闲分区的开销。但也会使得内存空间缺乏较大的空闲分区。

快速适应算法

这个有点难懂，要仔细理解就是：

将空闲区根据容量的大小进行分类，在每一类中，有相同容量的所以空闲区，单独设立一个空闲区链表。

优点是：查找效率高，只需要根据进程的长度，就可以寻找到能容纳它的最小空闲区链表，然后取下第一块进行分配就行。并且不会产生内存碎片（因为是直接把一块整个空闲区分配给了进程）。

缺点是：分区归还时算法比较复杂，系统开销较大。且算法分配是以进程为单位的，一个分区只属于一个进程，所以在为进程分配的一个分区中，总存在一下浪费，空闲区划分的越细，浪费越严重。

典型以空间换时间的做法。

分区管理的一系列问题

一、作业的分配受空闲区大小的限制。

二、存在内存碎片问题，内存利用率不高，合并内存也要消耗CPU时间。

三、各作业对应不同的分区，不利于程序段和数据段的共享。

two 页式存储管理

页式存储管理不存在存储分配连续性的要求，它使一个作业的地址空间在内存中可以是若干个不连续的区域。（离散分配方式）

把作业平分成相同大小的页面，每个页面对应一个编号，称为页号

把内存等分成相同大小的物理块，再依次进行编号，称为块号

逻辑地址

逻辑地址由两部分组成，分别是页号P 和页内地址W（位移量）

对于计算机，地址结构是固定的，所以有给定的A(最大地址数)和L(页面大小)

则页号P = int(A/L) W = (A) mod L

理解：页号P；页内地址：偏移量（为找到目标，起始地址要加上的地址数）

页表

进程执行时，通过查找页表，即可找到每页在内存中的物理块号。

页表的作用是实现从页号到物理号的地址映射

页表包含：

页号：是指内存分页中的页号索引，它用于表示所请求的页在物理内存中的位置。

物理块号：

快表

存放当前最活跃进程的少数几页，随着进程推进，要动态更新快表内容。

多级页表

两级页表结构：³¹ 外层页号P₁ ²² + ²¹ 外层页内地址P₂ ¹² + ¹¹ 页内地址W ⁰

外层页表每一页表项存放的是页表分页的首地址，页表的每个表项存放进程的某页在内存中的物理块号。 P113

three 段(页)式存储管理

段式存储管理：使用户把程序划分成若干段，每段具有独立的逻辑含义。

基本原理

以段位单位分配内存，每段分配一个连续的内存区域，但各段之间不要求连续。

分段）

结构地址： ³¹ 段号S ¹⁶ + ¹⁵ 段内地址W ⁰

段表）

存放在寄存器中，可以提高地址转换速度，但常见的存放在内存中。

包含信息：段号，段长，段的起始地址。

地址变换机构）

P 115

分段和分页的主要区别

1）页是信息的物理地址，与源程序的逻辑结构无关，且对用户不可见。分页的目的是 提高内存的利用率。

段是信息的逻辑单位，由源程序的逻辑结构决定，对用户可见，分段是为了更好地 满足用户地需求。

2）页的大小固定且由系统所决定，段的长度却不固定，可根据用户需求划分。

3）分页的作业空间是一维的，分段是二维的。

4）分段的段内空间比分页的页面空间大，则段表会比页表短，查询时间也就少

段页式存储管理：分页和分段两种存储管理方式的结合，具有两者互有的优点。

把用户程序分成 若干段，然后把每个段分成 固定大小的若干页。

³¹ 段号S ²² + ²¹ 段内页号P ¹² + ¹¹ 页内地址W ⁰

页表不再属于进程而是属于段。

虚拟存储管理

局部性原理：被执行/访问，在不久将来很可能被再次执行/附近空间很可能被再次访问

时间局限性：是因为程序中存在大量的循环操作

空间局限性：是因为程序的顺序执行

请求分页存储管理

请求分页原理：

不把作业或进程一次性放入内存，只装入经常使用的一部分，其余的执行过程中动态装入，需要通过页面置换，把外存中相应页调入内存。

必然会出现缺页的现象。

缺页中断机构：用于处理缺页中断、换入/换出页等功能。

每当要访问的页不在内存中时，就会产生一次缺页中断。

页面置换算法*** P₁₂₄

最佳置换算法
先进先出算法
最久未使用算法
第二次机会置换算法

在先进先出基础上，再加上最久未使用算法。在先进先出队列中的页面，且在其中时，被再次使用，则置1，替换访问到时，如果置1的，则置0，再重新放到队列末尾，如果是置0的，则被替换。
时钟页面置换算法

把第二次····的单向链表换出环形链表，就成了时钟页面置换算法。

抖动现象

当程序达到一定数量时，随着数量的进一步增加，CPU的利用率会急剧下降，这现象被称为抖动。是因为页面置换活动的增多，会让内外存访问次数过多，所以会造成系统效率大大降低的现象。

请求分段：先把大部分放入外存，要用的时候再放入内存。所以要再段表中增加一些干预项，说明哪些段已经存在内存，存放的位置，段长。等待。

缺段中断机构，和缺页终端机构类似。理解他的意思就行 P₁₃₀

第六章：设备管理

设备管理的目标：提高I/O设备的利用率，提供一个便利，统一的管理模式，满足用户的各种I/O需求。

设备管理的任务：状态跟踪，设备分配，设备控制，提高处理器和I/O设备利用率，共享，差错处理

有单总线模型，多通道I/O系统两种，在多通道I/O系统中，从主机到设备有多条通路，所以大大降低了某一设备因被占用而产生阻塞的概率。

I/O设备分类

按特性分类：存储设备，I/O设备

按数据组织分类：块设备，字符设备

按资源分配分类：独占设备，共享设备，虚拟设备

按数据传输率分类：低速设备，中速设备，高速设备

按从属关系分类：系统设备，用户设备

I/O系统控制方式***

程序直接控制方式

又称程序查询方式，是由CPU通过程序来直接控制处理器和外设之间的信息传送的。

在该方式中，CPU处理数据的高速性和I/O设备的低速性不匹配，导致CPU大部分时间浪费在等待I/O设备完成数据传送的循环测试中，可见这种方式下，CPU和I/O设备处于串行工作状态，CPU工作效率不高

中断控制方式

在I/O设备输入数据的过程中，无需CPU的参与，可使CPU和I/O设备并行工作。

只有在I/O设备准备就绪时，才需要CPU花费时间去处理中断请求。提高了CPU的利用率。但也存在一些问题，这些问题被DMA控制方式解决。 P138

DMA控制方式

特点：数据传输的基本单位是数据块，不是字，在CPU和I/O设备之间，每次至少传输一个数据块。

传输数据从I/O设备直接进入主存，或从主存直接到I/O设备。

只有在一次传输操作的开始或结束时，才需要CPU干预，在过程中不需要，都是由MDA控制器控制的。

组成：处理器与MDA控制器的接口、MDA控制器与块设备的接口、I/O控制逻辑。

工作流程：

通道控制方式 P₁₄₀

DMA控制方式显著减少了CPU的干预，但当系统需要一次读多个数据块且将他们分别传入到不同的内存区域，或者相反时，就需要CPU发出多条I/O指令及进行多次中断处理才能完成。

通道控制方式，可以实现CPU、通道和I/O设备三者的并行操作，更有效地提高了系统

I/O软件的组成

设计和原则

I/O软件结构

用户层I/O软件

与设备无关的系统软件

设备驱动程序

中断处理程序

具有通道的设备管理

引入通道的主要目的时建立独立的I/O操作。让I/O操作尽量独立，保证处理器有更多时间去处理数据。

字节多路通道

是一种字节交叉方式工作的通道，通常含有许多非分配型的子通道，还有一个主通道，采用时间片轮转方法，轮流为子通道服务。通常连接低速I/O设备，如行式打印机

数组选择通道

以数组方式进行数据传送，它传输速率高，可以连接多台高速设备，但是它有明显缺陷是：通道利用率低。

数组多路通道

结合了上面两种的优点而形成的新通道，有很高的数据传输速率和令人满意的通道利用率。适合用于连接高、中速的I/O设备。

设备管理相关技术

DMA

直接存储访问方式

有单总线、分离的DMA，单总线、集成的DMA-I/O，I/O总线的DMA配置

缓冲技术

有硬件缓冲器和 n个存储单元的专用缓冲区（软件）。

单缓冲区

双缓冲区

循环缓冲区

磁盘存储管理

磁盘是一种可以直接存取的存储设备，又称随机存取存储设备。它的每一个物理记录都有确定的位置和唯一的地址。

存储容量 = 磁头数×磁道（柱面）数×每道扇区数×每扇区字节数

磁盘调度

先来先服务调度算法

根据进程请求访问磁盘的先后顺序进行调度，适合进程数据少的情况

最短寻道时间优先调度算法

要求访问的磁道与当前所在磁道距离最近，以便寻道时间最短。比先来先服务有更好的寻道性能，但是可能导致某进程饥饿。

扫描调度算法

为避免最短寻道···出现饥饿，采用扫描···，扫描调度算法不仅考虑欲访问的磁道与当前磁道的距离，更优先考虑磁头的移动方向。 相同方向的优先级更高

循环扫描调度算法

有较好的寻道性能，又能防止饥饿，扫描调度算法可能出现，当刚刚越过某磁道时，该磁道恰好有进程请求访问，此时进程只能等待，等到掉头回来的时候才能处理。 循环扫描调度算法规定磁头单向移动，不准掉头。访问到最后的时候又直接返回开始的地方。

N步扫描调度算法

把磁盘请求队列分成产犊为N的子队列，每次用扫描调度算法处理一个子队列。

F-SCAN调度算法

对上面的简化，只将磁盘请求队列分成两个子队列，其中一个由当前所有请求磁盘I/O的进程形成的对列，由扫描调度算法处理。另一个是存放扫描期间请求访问的进程，等上一个队列扫描完后，才扫描该队列。

第七章：文件管理

大量数据和程序都以文件的形式保存再外存中，需要时才将其调入内存。操作系统是文件管理的承担着。

文件系统由三部分组成：与文件管理相关的软件、被管理文件、实施文件管理所需数据结构。

操作系统对信息的管理就是将他们组成一个个文件，文件就是具有符号名的数据项集合。

文件系统优点

使用方便，较强的数据安全性，接口统一性

文件结构之物理结构

逻辑结构：从用户的观点出发所观察到的文件组织形式，这种数据和结构用户可以直接处理。

物理结构：又称存储结构，是文件在存储器上的存储组织形式，与存储介质和存储特性有关。

顺序结构

优点：知道文件存储的起始物理块号和文件长度，可以立即找到信息，访问容易，访问速度快，但是文件的长度大小在随时变化，所以要预留很大的空间，容易造成空间浪费。其次不利于文件内容的修改，（在中间修改时要随之改变后面一系列的东西）

链接结构

就相当于链表。优点是可以动态的增加或者删除文件，新建文件时不必考虑最大长度，因为不是连续的，所以几乎不会造成空间浪费。缺点就是只适合顺序存取，不能直接存取。（因为链表不能直接定位，只能从头开始往后找），从而降低了信息的查找速度。

索引结构

把一个文件的信息存放在若干个不连续的物理块中，并为每个文件建立一个专用数据结构---索引表。

它既保持了链接结构访问访问快速的优点，又解决了串联结构要求的空间连续的缺点，表现在既能顺序存取，又能随机存取，且能充分利用存储空间。缺点就是索引表本身带来的系统开销（但应该是好处更过吧）

文件存取方法

顺序存取法

随机存取法

每次存取操作前要确存取的位置，允许用户根据记录的编号来存取文件中的任一记录。

按键存取法

P 172

文件控制块

通常包含三类信息：基本信息，存取控制信息和使用信息

基本信息：文件名，文件物理地址，文件逻辑结构，文件物理结构

存取控制信息类：包括文件主的存取权限、核准用户的存取权限、一般用户的存取权限。

使用信息类：包括文件的建立日期和时间、文件上一次修改的日期和时间、当前使用信息。

索引节点

索引节点是一个结构，它包含了一个文件的长度、创建及修改时间、权限、所属关系、磁盘中的位置等信息。一个文件系统维护了一个索引节点的数组，每个文件或目录都与索引节点数组中的唯一一个元素相对应。

第十章：系统安全

程序安全

逻辑炸弹

P 233

缓冲区溢出

P 234

SQL注入