2023春季操作系统复习
目录- 2023春季操作系统复习
ch1 操作系统概述
1.2 计算机系统组成
系统总线：提供CPU、主存与I/O模块之间的通信通道。
设备控制器通过引起中断来通知CPU它已完成其操作。
中断为了解决CPU与外设之间的速度不匹配，通常通过包含所有服务例程地址的中断向量将控制转移到中断服务例程，分为软中断（系统调用）和硬件中断（设备中断）。中断体系结构必须保存中断指令的地址。陷阱或异常时由错误或用户请求引起的软件生成的中断。操作系统是中断驱动的。
1.2.3 I/O结构
中断I/O的周期：？
I/O结构：操作系统为每一个设备控制器提供一个设备驱动程序。处理I/O的两种方式：
1、I/O启动后，设备控制器仅在I/O完成后返回到用户程序。（同步I/O）
等待指令使CPU空闲，直到下一个中断；等待循环（内存访问争用）；一次最多有一个I/O请求未完成，没有同步的I/O处理。
2、I/O启动后，设备控制器返回到用户程序，而无需等待I/O完成（异步I/O）
系统调用，请求操作系统允许用户等待I/O完成；设备状态表包含每个I/O设备的条目，指示其类型、地址和状态；操作系统索引到I/O设备表，以确定设备状态并修改表项以包含中断。
I/O技术：可编程I/O，中断驱动，DMA方式
DMA方式：I/O设备速度接近内存传输信息，每个块只生成一个中断，设备控制器将数据块从缓冲存储器直接传输到主存储器，无需CPU干预。
完整表述：在为这种I/O设备设置好缓冲、指针和计数器之后，设备控制器可在本地缓冲和内存之间传送整块的数据，而无需CPU的干预。每块只产生一个中断，来告知设备驱动程序操作已完成，而不是像低速设备那样每个字节产生一个中断。当设备控制器执行这些操作时，CPU可以进行其他工作。
1.3 计算机系统的体系结构
高速缓存对操作系统不可见，CPU中
主存——cache（多级）——内存
1.3.2 多处理器系统
多处理器系统（并行系统、多核系统），增加吞吐量，规模经济，增加可靠性。
非对称处理器：每个处理器都有各自特定的任务，一个主处理器控制系统，其他处理器或者向主处理器要任务或做预先规定的任务。
对称多处理器（SMP）：每个处理器都参与完成操作系统的所有任务。没有主从关系。每个处理器都有自己的寄存器集，有本地缓存，但是都共享物理内存。
多处理可使系统的内存访问模型，从均匀内存访问改成非均匀内存访问。
CPU集成多个计算核到单个芯片。这种多处理器系统为多核。
1.3.3 集群系统
集群系统：这种系统将多个CPU组合在一起。由两个或多个独立系统组成，这种系统称为松耦合的。
集群通常用于提供高可用性服务。集群可以是对称的，也可以是非对称的。
为提供共享访问，系统应该针对文件访问加以控制与加锁，以便确保没有冲突操作，这种技术称为分布锁管理器。
1.4 操作系统的结构
多道程序设计：通过安排作业使得CPU总有一个执行作业，从而提高CPU利用率。
分时系统（多任务）：CPU通过切换作业来执行多个作业，用户可以在程序运行时与其交互。允许许多用户同时共享一台计算机。采用CPU调度和多道程序设计。加载到内存并执行的程序，称为进程。
Q：作业调度和CPU调度的区别：有多个作业可以加载到内存中，但是内存太小不能容纳所有作业。有多个任务同时等待执行，系统应该做出选择。
交换：将进程从磁盘调入内存，也可将进程从内存调到磁盘。
1.5 操作系统的执行
操作系统是中断驱动的。事件总是由中断或陷阱引起的。陷阱（或异常）是一种软件生成的中断，除0，用户程序的特定请求。中断服务程序用于处理中断。
1.5.1 双重模式与多重模式
计算机系统采用硬件支持，以便区分各种执行模式。至少需要两种单独运行模式：用户模式和内核模式，计算机硬件通过一个模式位来表示当前模式。
Q：描述用户如何在内核态和内核态切换？
A：当系统引导时，硬件从内核模式开始。操作系统开始在用户模式下执行用户程序。一旦有陷阱或中断，硬件会从用户模式切换到内核模式。在将控制交给用户程序前，系统会切换到用户模式。
双重模式执行提供保护手段：将可能引起损害的机器指令作为特权指令，并且硬件只有在内核模式下才允许执行特权指令。
支持虚拟化技术的CPU有一种单独模式，用于表示虚拟机管理器。特权介于内核态与用户态之间。
系统调用为用户程序提供手段，以便请求操作系统完成某些特权任务，是进程请求操作系统执行功能的方法，系统调用通常会陷入中断向量的某个指定位置。一般由通用trap指令完成。
当要执行系统调用时，硬件将它作为软中断。控制通过中断转到操作系统的中断服务程序，模式位设置为内核模式。系统调用服务程序是操作系统的一部分。内核检查中断指令，确定系统调用类型，参数表示用户程序请求何种服务。请求所需的其他信息可以通过寄存器、堆栈或内存来传递。
1.5.2 定时器
防止用户程序陷入死循环，或不调用系统服务并且不将控制返给操作操作系统。定时器可设置为在指定周期后中断计算机。
1.6 进程管理
进程是正在执行的程序，它是操作系统中的一个工作单元，是操作系统分配资源的最小单位。
Q：程序与进程的区别？
A：程序是一个被动的实体，进程是一个活跃的实体。
进程需要资源来完成任务：CPU、内存、I/O、文件，进程结束后可回收资源。
单线程进程有一个程序计数器，多线程进程中每个线程有一个程序计数器。
进程分为操作系统进程和用户进程，所有进程都会并发执行。
操作系统负责进程管理的以下活动：1、在CPU上调度进程和线程。2、创建和删除用户进程和系统进程。3、挂起和重启进程。4、提供进程同步机制。5、提供进程通信机制。
1.7 内存管理
内存为CPU和I/O设备所共享。要执行程序，所有（或部分）指令必须在内存中，程序所需的全部（或部分）数据必须在内存中。
内存管理活动：1、记录内存的哪部分在被使用及被谁使用。2、决定哪些进程会调入或调出内存。3、根据需要分配和释放内存空间。
1.8 存储管理
操作系统对存储设备的物理属性进行抽象，定义了逻辑存储单元文件。
文件内容为程序和数据，数据文件可以是数值、字符或二进制。
操作系统负责文件管理：1、创建和删除文件。2、创建和删除目录。3、提供文件和目录的操作原语。4、映射文件到外存。5、备份文件。
1.8.2 大容量存储器管理
操作系统负责有关硬盘管理的以下活动：1、空闲空间管理。2、存储空间分配。3、硬盘调度。
1.8.3 高速缓存
检查缓存是否存在信息，如果是，直接从缓存使用信息；否则，将数据复制到缓存并使用。
1.8.4 I/O系统
I/O子系统为操作系统本身隐藏了I/O设备的特性，包括：1、缓冲、高速缓存和假脱机（一个作业的输出与其他作业的输入重叠）的内存管理组件。2、设备驱动器的通用接口。3、特定硬件设备的驱动程序。
1.9 保护与安全
保护是一种机制，用于控制进程或用户访问计算机系统的资源。
防止系统不受外部或内部的攻击是安全的工作。
1.10 内核数据结构
略
1.11 计算环境
1.11.1 传统计算
1.11.2 移动计算
苹果、安卓
1.11.3 分布计算
分布式系统是物理上分开、可能异构的、通过网络相联的一组计算机系统，可供用户访问系统维护的各个资源。
传输控制协议/网间协议是最常用的网络协议。
网络根据节点之间的距离划分：局域网，广域网，城域网，个人局域网
1.11.7 云计算
云计算通过网络提供计算、存储甚至应用程序等服务。
1.11.8 实时嵌入式系统
要求有定义良好的固定时间约束。
ch2 操作系统结构
2.1 操作系统的服务
ch3 进程
3.1 进程概念
3.1.1 进程
程序代码称为文本段，进程包括程序计数器，寄存器，还包括堆栈，数据段，堆内存。
3.1.2 进程状态
进程的五个状态：创建态、就绪态、运行态、阻塞态、终止态。
就绪态可以从创建态，运行态和阻塞态切换得到。
运行能切换成阻塞态，就绪态（中断）和终止态。
补充：阻塞态可以转换到挂起态suspend（内存就绪队列为空），特点是进程不能执行，有也可能没有等待事件，由父进程代理，无显示命令状态不转换。
3.1.3 进程控制块
PCB，保存了进程状态，程序计数器，CPU寄存器等，包含了进程控制信息。注意进程间的CPU切换，会先保存PCB状态到操作系统中，再进行切换。
3.1.4 GetPid系统调用
GetPid函数是一个系统调用，从PCB获取，所以会发生用户态到内核态的切换。
3.2 进程调度
进程调度器选择一个可用进程到CPU上执行。
3.2.1 调度队列
进程进入系统时，会加到作业队列（包含所有进程），驻留在内存中，就绪，等待运行的进程保存在就绪队列中。
最初，新进程被加到就绪队列；它在就绪队列中等待，直到被选中执行或被分派，当进程分配到CPU并执行时，可能发生以下事件：
1、进程发送I/O请求，并被放到I/O队列。
2、进程可能创建一个新的子进程，并等待其终止。
3、进程可能由于中断而被强制释放CPU，并被放回到就绪队列。
前两种情况，进程可能从等待状态切换到就绪状态，然后加入到就绪队列中。
3.2.2 调度程序
进程选择通过适当调度器或调度程序来执行。
批处理系统中，提交的进程多于可以立即执行的，所以这些进程会被保存到大容量存储设备的缓冲池中。长期调度程序或作业调度程序从该池中选择进程。短期调度程序或CPU调度程序从准备执行的进程中选择进程，并分配CPU。
大多数进程可分为：I/O为主或CPU为主。I/O密集型进程执行I/O比执行计算花费更多时间，CPU密集型进程则相反。
3.2.3 上下文切换
当中断发生时，系统要保存当前运行在CPU上的进程的上下文（采用进程PCB表示，包括CPU寄存器值、进程状态和内存管理信息）。
切换CPU到另一个进程需要保存当前进程状态和恢复另一个进程的状态，这个任务称为上下文切换。
3.3 进程运行
基本的系统调用：getpid(),fork(),exec*(),wait(),exit(),vfork()。
3.3.1 进程创建
每个新进程可以再创建其他进程，形成进程树。
对进程的识别采用的是唯一的进程标识符。
当进程创建新进程时，可有两种执行可能：1、父进程与子进程并发执行。2、父进程等待，直到某个或全部子进程执行完。
新进程的地址空间也有两种可能：1、子进程是父进程的复制品。2、子进程加载另一个新程序。
通过系统调用fork()，可创建新进程。新进程的地址空间复制了原来进程的地址空间。这种机制允许父子进程轻松通信。对于子进程，fork()的返回值为0；父进程fork()的返回值是子进程的pid。子进程和父进程在执行结束时都会隐式调用exit函数。
调用fork之后，有个进程使用系统调用exec，以用新程序来取代进程的内存空间。
vfork()创建的是共享进程。
3.3.2 进程终止
当进程完成执行最后语句并且通过系统调用exit()请求操作系统删除自身时，进程终止。
如果一个进程终止，那么它的所有子进程也应终止，这种现象称为级联终止。
当一个进程终止时，操作系统会释放其资源。但是，它位于进程表中的条目还是存在，直到它的父进程调用wait；这是因为进程表包含了进程的退出状态。当进程已经终止，但是其父进程尚未调用wait()，这样的进程称为僵尸进程。在父进程调用wait()函数之后，僵尸进程的进程标识符和在进程表里的条目就会释放。子进程终止时，可以发生SIGCHLD信号通知父进程，自己已经结束了。
如果父进程没有调用wait()就终止，以至于子进程称为孤儿进程。
3.4 进程间通信
协作进程需要有一种进程间通信（IPC）机制，以允许进程相互交换数据与信息。进程间通信有两种基本模型：共享内存和消息传递。
共享内存模型会建立起一块供协作进程共享的内存区域，进程通过向此共享区域读出或写入数据来交换信息。
消息传递模型通过在协作进程间交换消息来实现通信。
3.4.1 共享内存系统
采用共享内存的进程间通信，需要通信进程建立共享内存区域。通常，一片共享内存区域驻留在创建共享内存段的进程地址空间内。生产者进程生成信息，以供消费者进程消费。
缓冲区分为有界缓冲区和无界缓冲区两种。对于无界缓冲区，生产者可随时产生新内容，但是消费者只能在有东西时读取。对于有界缓冲区，如果缓冲区空，那么消费者必须等待；如果缓冲区满，则生产者必须等待。
3.4.2 消息传递系统
通过发送信息相互通信，无需借助共享变量。
P和Q需要通信，则必须互相发送消息和接受消息：它们之间必须要有通信链路，消息的大小是固定的或可变的。用于逻辑实现链路和操作send()/receive()。
- 直接或间接的通信
- 同步或异步的通信
- 自动或显式的缓冲
3.4.2.1 命名
对于直接通信，通信的每个进程必须明确指定通信的接受者或发送者，原语send()和receive()必须指明发送或接收对象和消息。
通信链路特性：1、链接是自动建立的。2、链路仅与一对通信进程相关联。3、每对之间只存在一个链接。4、通常双向，也可单向。该方案展示了寻址的对称性。
在间接通信中，通过邮箱或端口来发送和接收信息。邮箱可抽象成一个对象，进程可向其中存放信息，也可从中删除消息。每个邮箱都有一个唯一的标识符。
问题：$P_1、P_2、P_3$共享邮箱A，$P_1$发送，$P2,P3$接收，谁得到消息？
解决：1、允许链接最多与两个进程关联。2、一次只允许一个进程执行接收操作。3、允许系统任意选择接收器。
邮箱所有者：邮箱可以被进程拥有；邮箱被操作系统拥有；邮箱可以转移。
3.4.2.2 同步
消息传递可以是阻塞或非阻塞，也称为同步或异步。
- 阻塞发送：发送进程阻塞，直到消息由接受进程或邮箱所接收。
- 非阻塞发送：发送进程发送信息，并恢复操作。
- 阻塞接收：接收进程阻塞，直到有消息可用。
- 非阻塞接收：接收进程收到一个有效消息或空消息。
3.4.2.3 缓存
不管通信是直接的还是间接的，通信进程交换的信息都是驻留在临时队列中，队列实现有三种方法：
- 零容量：等价于发送者阻塞，直到接收者接收消息。
- 有限容量：最多只能有n个消息驻留其中。发送信息时，如果队列未满，则可以把消息放到队列中；否则需要阻塞。
- 无限容量：队列长度无限，随便放。
3.6 客户机/服务器通信
3.6.1 套接字
套接字为通信的端点，通信进程需要一对套接字，每个进程各一个，由IP+端口号。
3.6.3 管道
管道允许两个进程进行通信，分普通管道和命名管道。
普通管道——无法从创建它的进程外部访问，通常在父子进程之间创建。
命名管道——可以在没有父子关系的情况下访问。
3.6.3.1 普通管道（匿名管道）
普通管道允许两个进程按生产者—消费者方式进行通信；生产者向管道一端写，消费者从管道另一端读。普通管道是单向的，只允许单向通信。如果想要双向通信，就需要两个管道。普通管道只能由创建进程所访问。
3.6.3.2 命名管道
命名管道的通信是双向的，通信进程不需要父子关系，有几个进程可以使用命名管道进行通信。
ch4 多线程编程
4.1 概述
每个线程是CPU使用的一个基本单元；包括线程ID、程序计数器、寄存器组和堆栈。与同一进程的其他线程共享代码段，数据段（全局、局部），动态分区和其他操作系统资源。如果一个进程具有多个控制线程，那么它能执行多个任务。
每个线程共享同一地址空间，目的是方便数据共享和交互；允许线程在进程内并行。
一个进程的多线程可以在不同处理器上同时执行：调度的基本单元从进程变成了线程；每个线程都有状态；上下文切换的单位变成了线程。
进程与线程：进程具有资源所有权和调度/执行两个特点。
资源所有权：进程包括存放进程映像的虚拟机地址空间。
调度/执行：进程执行时采用一个多程序的执行路径，不同进程的执行过程会交替进行；进程具有执行态等和分配给其的优先级，是可被操作系统调度和分派的实体。
通常将分派的单位称为线程或轻量级进程（LWP），将拥有资源所有权的单位称为进程或任务。
多线程：多线程是指操作系统在单个进程内支持多个并发执行路径的能力。
4.1.2 进程在内存中的映像
进程的内存空间从高地址到低地址包括：栈、堆、数据、文本（代码）。全局变量、局部变量、动态分区、代码段。
4.1.3 线程在内存中的分布
线程通过特定的函数驱动，线程函数可以调用其他函数或者系统调用，但是绝不会返回调用线程。
4.1.4 动机
从系统角度看：现代计算机通常多核，每个处理器一次只能运行一个进程，CPU资源没有充分利用，为提高效率，一个核心一个任务。
多线程的优点：1、响应性：部分线程被阻塞，仍可以继续执行。 2、资源共享：比进程共享内存或消息传递方便。 3、线程切换比上下文切换开销低。 4、可扩展性：线程可以利用多核体系结构。
并发与并行（超级重点）：
并发指在单核系统上，通过快速的CPU调度进程，支持多个任务，提供并行的假象，任意时刻只能执行一个任务。
并行指在多核系统上，可以同时执行多个任务。
4.2 多核编程
多核：多个处理器
4.2.2 并行类型
数据并行（分段求和）和任务并行（执行不同任务）。
4.3 多线程模型
概述：有两种不同方法来提供线程支持：用户线程或内核线程。用户线程的管理无需内核，内核线程由操作系统直接管理。用户线程和内核线程之间必然存在某种关系。
4.3.1 多对一模型
将多个用户级线程映射到一个内核级线程中。这些用户线程一般属于一个进程，线程的调度和管理在用户空间完成。仅当用户线程需要访问内核时，才将其映射到一个内核级线程上。每次只允许一个线程映射。
优点：线程管理是在用户空间进行的，效率高
缺点：一个线程访问内核时发生阻塞，则全部阻塞；任何时刻，只有一个用户线程能与内核线程建立映射；多线程不能在多处理机上并发执行。
4.3.2 一对一模型
将每个用户级线程映射到一个内核级线程。
优点：当一个线程被阻塞后，允许调度另一个线程运行，并发能力强。
缺点：创建一个用户线程需要对应创建一个内核线程，开销大。
4.3.3 多对多模型
将n个用户线程映射到m个内核级线程上，要求n>m。
优点：既克服了多对一模型并发度不高的缺点，又克服了一对一模型开销太大的特点。
4.4 线程的实现方式
线程控制块（TCB），类似于PCB，在上下文切换中会使用到。
Q：如何控制和管理线程在用户空间的内存？
A：线程包括了用户空间的数据和资源，内核中的数据结构（TCB），线程分成用户线程和内核线程，线程模型即用户线程（ULT）与内核线程（KLT）的对应关系。
4.4.1 用户级线程
在用户级线程中，有关线程管理的所有工作都由应用程序在用户空间中完成，内核意识不到线程的存在。这种方式的优点：1、线程的切换不需要转换到内核空间，节省了模式切换的开销。缺点：1、系统调用的阻塞问题，当线程执行一个系统调用时，不仅该线程被阻塞，而且进程内的所有线程都被阻塞。2、不能发挥多处理机的优势，内核每次分配给一个进程仅有一个CPU，因此进程中仅有一个线程能执行。
4.4.2 内核级线程
内核级线程在内核的支持下运行。线程管理工作在内核空间内实现的。优点：1、能发挥多处理机的优势，内核能同时调度同一进程中的多个线程并发执行。2、如果进程中的一个线程被阻塞，内核可以调度该进程中的其他线程占用处理机，也可运行其他进程中的线程。3、内核支持线程具有很小的数据结构和堆栈，线程切换比较快，开销小。4、内核本身也采用多线程技术，可以提高系统的执行速度和效率。
总结来说：1、能发挥多处理机优势，内核线程并发执行。
2、不会因一个线程阻塞而导致所有线程阻塞。
3、上下文切换效率高，开销小
4、内核线程自身也可以是多线程
缺点：1、同一进程中的线程切换，需要从用户态切换到核心态，系统开销大。因为用户进程的线程在用户态进行，而线程调度和管理在内核实现。
4.4.3 混合方法
同一进程中的多个线程可以同时在多处理机上并行执行，且在阻塞一个线程时不需要将整个进程阻塞。
特点：1、线程的创建完全在用户空间中完成。2、线程的调度和同步也在应用程序中进行。3、多个用户线程会映射到一些内核线程上。
4.4.4 线程库
是为程序员提供创建和管理线程的API。
实现方法：1、在用户空间中提供一个没有内核支持的库。2、实现由操作系统直接支持的内核级的一个库。
ch5 进程调度
处理器调度：通过多道程序设计获得的最大CPU利用率。
5.1 基本概念
5.1.1 CPU—I/O执行周期
进程执行包括周期进行CPU执行和I/O等待，进程在这两个状态之间不断交换。
5.1.2 CPU调度程序
每当CPU空闲时，操作系统就应从就绪队列中选择一个进程来执行。进程选择采用短期调度程序或CPU调度程序。短期调度程序主要是关于如何对已经就绪的进程进行调度，从使得能在处理机上运行。
| schedule type | process |
|---|---|
| 长期调度 | new->ready |
| 中期调度 | suspend->ready（一部分从磁盘调度到内存中） |
| 短期调度 | ready->run（修改寄存器值） |
| I/O调度 | ？ |
长程调度：确定哪一个程序进入系统中处理。
中期调度：中程调度时交换功能的一部分。换入决定取决于管理系统并发度的需求。
短期调度：分派程序，执行频率高。执行频繁程度：长程<中程<短程。
导致当前进程阻塞或抢占当前运行进程的事件发生时，调用短程调度程序。例如：时钟中断，I/O中断，操作系统调用。
简单题出法：
1、如何使一个处于就绪态的进程调度上处理机运行？
上下文切换。切换CPU到另一个进程需要保存当前进程状态和恢复另一个进程的状态。
5.1.3 抢占调度
Q：阐述需要进行CPU调度的四种情况？
- 当一个进程从运行状态切换到等待状态时（例如，I/O请求，wait系统调用）
- 当一个进程从运行状态切换到就绪状态时（中断）
- 当一个进程从等待状态切换到就绪状态（I/O完成）
- 当一个进程终止时
在上述情况中，调度发生在1和4下，称为非抢占式调度；发生在2和3下，称为抢占式调度。
5.1.4 调度程序
调度程序是一个模块，用来将CPU控制交给由短期调度程序选择的进程。这个功能包括：
- 上下文切换
- 切换到用户模式
- 跳转到用户程序的合适位置，以便重新启动程序
5.2 调度准则
CPU调度算法的准则包括：
- CPU使用率：应该使CPU尽可能忙碌。
- 吞吐量：在一个时间单位内进程完成的数量。
- 周转时间：从进程提交到进程完成的事件段称为周转时间。
- 等待时间：在就绪队列中等待所花时间之和。
- 响应时间：是开始响应所需的时间。
最大化CPU使用率和吞吐量，最小化周转时间、等待时间和响应时间。
5.3 调度算法
5.3.1 先到先服务调度（FCFS）
先请求的进程先分配CPU，非抢占的。
缺点：1、平均等待时间长。2、在动态情况下FCFS的调度性能差（出现护航效应）。
护航效应：所有其他进程都等待一个大进程释放CPU。
5.3.2 最短作业优先调度（SJF)
当CPU空闲时，它会被赋给具有最短CPU执行的进程。既可抢占，也可非抢占。经常用于长期调度。
特点：平均等待时间和平均周转时间降低，但是代价是增加了上下文切换的成本。
预测下一个CPU执行长度：$\tau_{n+1}=\alpha t_n+(1-\alpha)\tau_n$，$t_n$是第n个CPU执行长度，$\tau_{n+1}$为下一次CPU执行预测值。
最短剩余时间优先调度算法：也被称为抢占式最短作业优先调度。
5.3.3 优先级调度
SJF是优先级调度算法的特例。
优先级调度算法的主要问题是无穷阻塞或饥饿。饥饿：就绪运行的低优先级进程无穷等待CPU。
解决饥饿的方案：老化：逐渐增加在系统中等待长时间的进程的优先级。
5.3.4 轮转调度
定义时间片，时间片轮转完进行调度。平均等待时间较长。
在RR调度算法中，没有进程被连续分配超过一个时间片的CPU（除非是就绪队列中唯一的进程），RR调度算法是抢占的。
RR算法的性能很大程度取决于时间片的大小。如果时间片很大，那么RR算法退化成FCFS，如果时间片很小，则RR算法会导致大量的上下文切换。
时间片要远大于上下文切换时间，否则会有大量时间浪费在上下文切换上。
5.3.5 多级队列调度
该算法设置多个就绪队列，将不同类型或性质的进程固定分配到不同的就绪队列。每个队列可实施不同的调度算法。在多次处理机系统中，可以为每个处理机设置一个单独的就绪队列，每个处理机可实施各自的调度策略。分成前台进程（RR）和后台进程（FCFS）。
5.3.6 多级反馈队列调度
堆积反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合。通过动态调整进程优先级和时间片大小。实现思路：1、设置多个就绪队列，并给每个队列赋予不同的优先级。2、赋予每个队列的进程运行时间片的大小各不相同。3、每个队列采用FCFS算法。新进程进入内存后，把它放入第1级队列末尾，按FCFS调度。如果能在时间片内完成最好，否则进入下一级队列末尾进行调度……直到第n级队列，采用时间片轮转方式运行。
调度算法的比较
| 先来先服务 | 短作业优先 | 高响应比优先 | 时间片轮转 | 多级反馈队列 | |
|---|---|---|---|---|---|
| 能否是可抢占 | 否 | 是 | 能 | 能 | 队列内算法不一定 |
| 能否是不可抢占 | 能 | 能 | 能 | 否 | 队列内算法不一定 |
| 优点 | 公平，实现简单 | 平均等待时间最少，效率最高 | 兼顾长短作业 | 兼顾长短作业 | 兼顾长短作业 |
| 缺点 | 不利于短作业 | 长作业会饥饿 | 计算响应比的开销大 | 平均等待时间较长，上下文切换浪费时间 | 无 |
| 适用于 | 无 | 作业调度，批处理系统 | 无 | 分时系统 | 相当通用 |
| 默认决策模式 | 非抢占 | 非抢占 | 非抢占 | 抢占 | 抢占 |
5.4 线程调度
在支持线程的操作系统上，内核级线程才是操作系统所调度的。用户级线程为了运行在CPU上，最终应映射到相关的内核级线程，可能采用轻量级进程LWP。
5.4.1 竞争范围
对于实现多对一和多对多模型的系统线程库会调度用户级线程，以便在可用LWP上运行，这种方案称为进程竞争范围。为了决定哪个内核级线程调度到一个处理器上，内核采用系统竞争范围。采用SCS调度来竞争CPU，发生在系统内的所有线程之间。采用一对一模型的系统，只采用SCS调度。
5.5 处理器调度
5.5.1 多处理器调度的方法
让一个处理器处理所有调度决定、I/O处理以及其他系统活动，其他处理器只执行用户代码，这种称为非对称多处理。对称多处理事指每个处理自我调度。
5.5.2 处理器亲和性
处理器亲和性：避免进程从一个处理器转移到另一个处理器，试图让一个进程运行在同一处理器上。
亲和性分类：软亲和性和硬亲和性。
软亲和性：一个操作系统试图保持进程运行在同一处理器上时。
5.5.4 多核处理器
多个处理器放置在同一个物理芯片上，从而产生多核处理器。
5.6 实时CPU调度
软实时系统：不保证会调度关键实时进程；而只保证这类进程会有优先于非关键进程。
硬实时系统：一个任务应在它的截止期限之前完成。
5.6.1 最小化延迟
当一个事件发生时，系统应尽快地响应和服务它。从事件发生到事件得到服务的这段时间称为事件延迟。
两类的延迟影响实时系统的性能：中断延迟和调度延迟。
中断延迟是从CPU收到中断到中断处理程序开始的时间。调度延迟是指从停止一个进程到启动另一进程所需的时间量。
5.6.2 优先权调度
进程是周期性的，定期需要CPU，一旦周期性进程获得CPU，具有固定的处理时间$t$、CPU应处理的截止期限$d$和周期$p$，三者关系为：$0\leq t\leq d\leq p$。周期任务的速率为$\frac{1}{p}$。
5.6.3 单调速率调度
单调速率调度算法采用抢占的，静态优先级的策略。进入系统时，每个周期性任务会分配一个优先级，它与周期成反比。周期越短，优先级越高。
单调速率调度可认为是最优，如果一组进程不能由此算法调度，它不能由任何其他分配静态优先级算法调度。调度N个进程的最坏情况下的CPU利用率为$N(2^{1/N}-1)$。
5.6.4 最早截止期限优先调度
最早截止期限优先调度根据截止期限动态分配优先级。截止期限越早，优先级越高。
ch6 同步
Q：shell中的“|”是匿名管道还是命名管道？ A：匿名管道
6.1 背景
操作系统设计的核心问题是进程和线程的管理。进程可以并发甚至并行执行，对共享数据的并发访问可能导致数据不一致。由生产者和消费者同时更新的计数器的有界缓冲区问题导致的竞争状态。
竞争条件：多个进程并发访问和操作同一数据并且执行结果与特定访问顺序有关。
为了防止竞争条件，需要确保一次只有一个进程访问关键数据。
6.2 临界区问题
将一次进允许一个进程使用的资源称为临界资源。每个进程中访问临界资源的代码，称为临界区。
实现访问临界请求的代码区称为进入区，临界区后有退出区，其他代码为剩余区。
临界区问题的解决方案应满足如下三条要求：
- 互斥：如果进程在其临界区内执行，那么其他进程都不能在其临界区内执行。
- 推进：如果没有进程在其临界区执行，并且存在一些希望进入其临界区的进程，则不能无期限推迟选择下一个将进入临界区的进程。
- 有限等待：在进程发出进入其临界区的请求后，以及该请求被批准之前，其他进程允许进入其临界区的次数必须存在上限。
实现互斥条件的方法：
- 软件方法：让并发执行的进程承担
- 专用机器指令
- 操作系统或程序设计语言
6.3 Peterson解决方案
Peterson解决方案适用于两个进程交错执行临界区与剩余区，是一个很好的算法，并能说明满足互斥、进步、有限等待等要求的软件设计的复杂性。
要求两个进程共享两个数据项：
int turn;
boolean flag[2];
这个方案中的进程像一个绅士，如果你想进入，它会先让你进。
变量turn表示哪个进程可以进入临界区。如果turn == i，那么进程$P_i$允许在临界区内执行。数组flag表示哪个进程准备进入临界区。如果flag[i]为true，那么进程$P_i$准备进入临界区。
int turn;
int interested[2] = {FALSE, FALSE};
void enter_region(int process)
{
int other;
other = 1-process;
interested[process] = TRUE;
turn = other;
while(turn == other && interested[other] == TRUE)
{
/* busy waiting */
}
}
void leave_region(int process)
{
interested[process] = FALSE;
}
Peterson解决方案的明显缺点：busy waiting会消耗大量CPU时间。隐秘的缺点：优先级反转的问题。
6.4 硬件同步
中断禁用：单处理器系统通过禁用中断保障互斥。代价很高，效率低，不能使用于多处理系统。
特殊的硬件指令，允许测试和修改一个字的内容，或以原子方式（不间断）交换两个字的内容
- 测试和设置指令（test_and_set())
boolean test_and_set(boolean *target){
boolean rv = *target;
*target = true;
// 返回的是target的初始值
return rv;
}
实现互斥：
while(test_and_set(&lock))
{
/* critical section */
lock = false;
/* remainder section */
}
仅当lock被设置为false，会跳出while循环，在次之后，其他进程才能访问临界区。执行过程是原子的。
- 比较和交换指令(compare_and_swap())
// compare_and_set()函数定义，执行是原子的
int compare_and_swap(int *value, int expected, int new_value)
{
int temp = *value;
// 有锁我就用，马上上锁，不给机会
if(*value == expected)
*value = new_value;
return temp;
}
while(true)
{
while(compare_and_swap(&lock, 0, 1) != 0)
/* do nothing */
/* critical section */
// 退出临界区，将lock设置回0
lock = 0;
/* ramainder section */
}
上述两种方法能够满足互斥的要求，但是还不能作为临界区问题的解决方案，因为不满足有限等待的要求。
下面是基于test_and_set()的解决方案，实现有限等待。共用数据结构：
boolean waiting[n];
boolean lock;
这些数据结构初始化为false，只有waiting[i] == false或key == false时，进程P1才能进入临界区。只有执行test_and_set()时，key的值才变成false。类似于唤醒操作。
do{
waiting[i] = true;
key = true;
while(waiting[i] && key)
key = test_and_set(&lock);
// 获得锁，将等待设置为false
waiting[i] = false;
/* critical section */
j = (i + 1) % n;
while((j != i) && !waiting[j])
j = (j + 1) % n;
if(j == i)
// 如果没人想要锁，就设置成false就行
lock = false;
else
// 有人要的话就给他，而且还不用设置lock为false
waiting[j] = false;
/* remainder section */
}while(true)
特殊机器指令的优势：1、不管是单道还是多道程序中，可以使任意数量的进程共享主存。2、实现简单。3、支持多重临界区。
劣势：1、可能出现忙等，消耗进程时间。2、可能产生饥饿。3、可能死锁。
6.5 互斥锁
最简单的是互斥锁，每一个互斥锁是表示锁是否可用的布尔变量。
可通过以下方式保护临界区：
- 首先获取一个锁
acquire()； - 然后释放锁
release()；
对acquire()和release()的调用必须是原子的。
while(true)
{
/* acquire lock */
/* critical section */
/* release lock */
/* remainder section */
}
acquire(){
while(!available)
/* busy wait */
available = false;
}
但是这个解决方案需要繁忙的等待，因此，该锁称为自旋锁。
存在优点：当进程在等待锁时，没有上下文切换，在使用锁的时间较短时，常用于多处理器系统。
补充：严格备选
目的：确定哪一个进程进入临界区
核心问题：1、检测进程状态。2、进入和退出需要是原子操作。
方法：使用一个共享变量检测进程状态。
缺点：1、很低效率，因为busy waiting很消耗CPU时间。2、同一进程不能连续访问临界区。
6.6 信号量
一个信号量S是个整型变量，只能通过两个标准原子操作：wait()和signal()来访问。在PV操作中，信号量整数值的修改过程中，其他任何进程不同修改信号量的值。
6.6.1 信号量的使用
信号量分为计数信号量（不受限制）和二进制信号量（0和1值）。
对于计数信号量，初值为可用资源数量。当进程需要使用资源时，对信号量执行wait()操作（减少信号量的计数），当进程释放资源时，需要对该信号量执行signal()操作（增加信号量的计数）。当信号量的计数为0时，所有资源都在使用中，之后，需要使用资源的进程将会阻塞，直到计数大于0。
6.6.2 信号量的实现
PPT：（a）compare and swap 指令 （b）中断
为了克服忙等的问题，可以修改wait()和signal()的实现，当一个进程执行wait()操作时并且信号量不为正时，它阻塞自己并加入到与信号量相关的等待队列中，并且将进程状态切换成等待状态。
在这种情况下，信号量的值可以为负，绝对值为等待它的进程数。但是在经典忙等的情况下，不能为负。
6.6.3 死锁
当两个或多个进程无限等待一个事件，而该事件只能由这些等待进程之一产生，称为死锁。
6.6.4 优先级的反转
假设有三个进程ABC，优先级顺序：A<B<C，AC都需要操作共享变量，而B只需要占有CPU。假如在$t_0$时刻，A获得互斥锁，并对变量进行操作，在$t_1$时刻到来时，C也被唤醒，但是由于现锁被A占有，所以不得不进入到阻塞队列中。在$t_2$时刻，B进程到来，由于优先级B>A，所以B会抢占CPU，A则是转化为就绪态退出临界区。在$t_3$时刻，B进程执行结束，释放CPU，此时只有A进程是就绪态，所以A获得CPU，并在执行结束后，唤醒C进程，最后C进程获得锁并进入临界区对变量进行操作。
这个过程中B的优先级低于C，但是却比C先执行，产生了优先级的反转。
6.7 经典同步问题
6.7.1 生产者—消费者问题
生产者和消费者共享以下数据结构：
int n = 0;
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;
生产者的进程结构：
do{
wait(mutex);
wait(empty);
/* do something */
signal(empty);
signal(mutex);
}while(true)
消费者结构：
do{
wait(mutex);
wait(full);
/* do something */
signal(full);
signal(mutex);
}while(true)
无界缓冲区生产者—消费者问题
// s维护缓冲区的互斥访问，n维护对物品数量的同步访问。
semaphore n = 0, s = 1;
void producer()
{
while(true){
semwait(s);
append();
semsignal(s);
semsignal(n);
}
}
void consumer()
{
while(true){
semwait(n);
semwait(s);
take();
semsignal(s);
}
}
有界缓冲区生产者—消费者问题
// s控制缓冲区的互斥访问，e控制缓冲区的空闲块数量，n控制缓冲区的物品数量。
semaphore s = 1, n = 0, e = sizeofbuffer;
void producer(){
while(true){
semwait(e);
semwait(s);
append();
semsignal(s);
semsignal()
}
}
void consumer(){
while(true){
semwait(s);
n--;
take();
semsignal(s);
semsignal(e);
}
}
void main(){
parbegin(producer, consumer);
}
6.7.2 读者—写者问题
读者—写者有多个变种，与优先级有关。最为简单的问题，通常成为第一读者—作者问题，要求读者不应保持等待，除非作业已获得权限使用共享对象。即没有读者，由于某个作者等待，而等待其他读者的完成。第二读者—写者问题，一旦作业就绪，那么作者就会尽可能快地执行，如果有一个作者访问等待访问对象，那么不会有新的读者可以开始读。
这两个问题都可能产生饥饿，第一个问题写者可能饥饿，第二个问题读者可能饥饿。
读者优先代码
int readcount = 0;
semaphore x = 1, wsem = 1;
void reader()
{
while(true)
{
semwait(x);
readcount++;
if(readcount == 1)
// 阻塞写者
semwait(wsem);
semsignal(x);
READUNIT();
semwait(x);
readcount--;
if(readcount == 0)
// 没有读者，才允许写者写
semsignal(wsem);
semsignal(x);
}
}
void writer(){
while(true){
semwait(wsem);
WRITEUNIT();
semsignal(wsem);
}
}
void main(){
readcount = 0;
parbegin(writer, reader);
}
写者优先代码
// x控制readcount，y控制writecount，z控制读者排队
int readcount = 0, writercount = 0;
semaphore x = 1, y = 1, z = 1, wsem = 1, rsem = 1;
void reader(){
while(true){
semwait(z);
semwait(rsem);
semwait(x);
readcount++;
if(readcount == 1)
semwait(wsem);
semsignal(x);
semsignal(rsem);
semsignal(z);
READUNIT();
semwait(x);
readcount--;
if(readcount == 0)
semsignal(wsem);
semsignal(x);
}
}
void writer(){
while(true){
semwait(y);
writecount++;
if(writecount == 1)
semwait(rsem);
semsignal(y);
semwait(wsem);
WRITEUNIT();
semsignal(wsem);
semwait(y);
writecount--;
if(writecount == 0)
semsignal(rsem);
semsignal(y);
}
}
void main(){
readcount = 0;
writecount = 0;
parbegin(writer, reader);
}
6.7.3 哲学家就餐问题
对于5位哲学家，共享数据。需要互斥。
- 允许4个哲学家同时坐在桌子上
- 只有一个哲学家的两根筷子都可用时，才能拿起它们
- 使用非对称解决方案，单号哲学家先拿起左边的筷子，再拿起右边的筷子；而双号的哲学家先拿起右边的筷子，再拿起左边的筷子。
void philosopher(int i){
while(true){
think();
take(i);
take((i+1)%N);
eat();
put(i);
put((i+1)%N);
}
}
6.8 管程
信号量的错误使用可能导致难以检测的时序错误，这些错误只在特定执行顺序时才会出现。
- 管程类型属于抽象数据类型，封装了数据及对其操作的一组函数，内部变量只能由过程中的代码访问。
- 提供一组由程序员定义的管程内互斥的操作。
- 管程中一次只能有一个进程处于活跃状态。
条件变量：定义附加的同步机制，可以定义一个或者多个类型为condition的变量，对于条件变量，只有操作wait和signal可以调用。
条件变量和信号量的比较：
- 相同点：条件变量wait和signal操作类似于信号量的PV操作，可以实现进程的阻塞和唤醒。
- 不同点：条件变量是没有值的，仅实现了排队等待功能；而信号量是有值的，信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。
使用条件变量实现管程：
semaphore x_sem;
int x_count = 0;
x.wait()等价于下面代码
x_count++;
if(next_count > 0)
signal(next);
else
signal(mutex);
wait(sem_x);
x_count--;
对于条件变量，只有操作wait()和signal()可以调用。操作x.wait()意味着调用这一操作的进程会被挂起，直到另一进程调用x.signal()。操作x.signal()重新恢复正好一个挂起进程。如果没有挂起进程，那么操作signal()就没有作用。
ch 7 死锁
7.1 系统模型
当一组进程中的每一个进程都在等待某个时间，而仅有这组进程中被阻塞的其他进程才可触发该事件。死锁是永久性的。死锁问题并没有有效而通用的解决方案。
进程使用资源的正确顺序：申请，使用，释放。
7.2 死锁特征
7.2.1 必要条件
- 互斥：至少有一个资源必须处于非共享模式。
- 占有并等待：一个进程应占有至少一个资源，并等待另一个资源。
- 非抢占：不能强行抢占进程已占有的资源。
- 循环等待：存在一个闭合的进程链，每个进程至少占有此链中下一个进程所需的资源。
7.2.2 资源分配图
系统资源分配图的有向图可以精确描述死锁。
圆形代表进程，方块代表资源，圆形指向方块表示请求边，方块指向圆形表示分配边。
如果资源分配图中没有环，那么系统就没有进程死锁，如果有环，可能存在死锁。
如果每个资源类型刚好有一个实例，则有环意味着已经出现死锁。如果每个资源类型有多个实例，则有环不一定意味着死锁。
内存死锁处理方法
处理死锁有三种方法：
- 通过协议来预防或避免死锁，确保系统不会进入死锁状态。
- 可以允许系统进入死锁状态，然后检测它，并加以修复。
- 可以忽略这个问题，认为死锁不可能在系统内发生。
为了确保死锁不会发生，系统可以采用死锁预防或死锁避免方案。死锁预防方法确保至少有一个必要条件被破坏。死锁避免要求操作系统得到有关进程申请资源和使用资源的额外信息。
简单来说，死锁预防是永远不会出现死锁（开始前），死锁避免是行进间判断（调度和资源分配解决）。
7.4 死锁预防
- 互斥——可共享资源（只读文件）不需要互斥；
- 持有且等待——必须保证当前进程请求资源时，它不会保持任何其他资源；一种实现是在开始执行之前请求并分配其所有资源；另一种实现是仅当进程未分配任何资源时。这种方法资源利用率低，资源已分配，但是长时间不同；发生饥饿，长久等待需要的资源。
- 无抢占——如果持有某些资源的进程请求另一个无法立即分配给它的资源，那么当前持有的所有资源都将被释放。被抢占资源被添加到进程正在等待的资源列表中；只有当进程能够恢复其原有的资源以及它所请求的新资源时，才会重新启动进程。
- 循环等待——强制所有类型的资源进行完全排序，并要求每个进程以递增的顺序请求资源。
如果能够动态获得锁，那么制定一个加锁的顺序并不保证死锁预防。
7.5 死锁避免
死锁预防的副作用是系统吞吐率低。死锁避免算法动态检查资源分配状态，以确保不存在循环等待条件。
7.5.1 安全状态
如果系统按一定顺序为每个进程分配资源，仍然避免死锁，那么系统的状态就是安全的。只要存在一个安全序列，系统就是安全状态。安全状态不是死锁状态，相反，死锁状态是非安全状态，不是所有的非安全状态都能导致死锁状态；非安全状态可能导致死锁。
7.5.2 资源分配图算法
需求边$P_i\Rightarrow R_j$，表示进程$P_i$可以请求资源$R_j$，用虚线表示，当进程请求资源时，需求边转换为请求边；将资源分配给进程时，请求边转换为分配边，当流程释放资源时，分配边重新转换为需求边，只有当进程$P_i$的所有边都为需求边时，才能允许将需求边增加到图中。每种资源只有一个实例。
仅当将申请边转换为分配边不会导致资源分配图中形成循环时，才能授予请求，利用环检测算法，检查安全性。
7.5.3 银行家算法
太熟悉了，不赘述了……O^O
7.6 死锁检测
- 允许系统进入死锁状态
- 检测算法
- 回收计划
如果系统不采取死锁预防也不采用死锁避免算法，那么死锁可能出现。
- 系统检查系统状态，确定是否出现死锁
- 从死锁状态中恢复的算法
讨论两个状态：每个资源只有单个实例和多个实例。
7.6.1 每种资源类型只有单个实例
定义等待图（资源分配图的变形），删除资源，如果有有向边则连边。如果存在环，则出现死锁。
7.6.2 每种资源类型可有多个实例
类似银行家算法。
7.6.3 应用检测算法
- 周期性检测死锁
- CPU利用率低于一个阈值
7.7 死锁恢复
7.7.1 进程终止
- 中止所有死锁进程。
- 一次中止一个进程，直到清除所有死锁为止。
7.7.2 资源抢占
通过资源抢占来消除死锁，不断抢占一些进程的资源以给其他进程使用，直到打破死循环。
- 选择牺牲进程：确定抢占顺序，使得代价最小。
- 回滚：回到某个安全状态，重新启动进程。
- 饥饿：一个进程只能有限次被选择为牺牲进程。
ch 8 内存管理策略
8.1 背景
8.1.1 基本硬件
增加更快的内存，称为高速缓存。
确定一个进程访问的合法地址范围，通过基地址寄存器和界限地址寄存器两个寄存器制定范围的大小。
操作系统通过特权指令，才能加载基地址寄存器和界限地址寄存器。
8.1.2 地址绑定
根据采用的内存管理，进程在执行时可以在磁盘和内存之间移动。在磁盘上等待调到内存以便执行的进程形成了输入队列。
通常，指令和数据绑定到存储器地址可在沿途的任何一步中进行：
- 编译时：如果编译时就已知道进程在内存中的驻留地址，那么就绝对代码。
- 加载时：如果在编译时并不知道进程将驻留何处，那么编译器就应生成可重定位代码。
- 执行时：如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定应延迟到执行时才进行。
8.1.3 逻辑地址空间与物理地址空间
CPU生成的地址称为逻辑地址，而内存单元看到的地址称为物理地址。
编译时和加载时的地址绑定方法生成相同的逻辑地址和物理地址。然而，执行时的地址绑定方案生成不同的逻辑地址和物理地址。我们将逻辑地址称为虚拟地址。由程序所生成的逻辑地址集合称为逻辑地址空间，对逻辑地址对应的所有物理地址称为物理地址空间。
从虚拟地址到物理地址的运行时映射是由内存管理单元（MMU）。基地址寄存器被称为重定位寄存器。
8.1.4 动态加载
为了获取更好地内存空间利用率，可以使用动态加载。一个程序只有在调用时才会加载。当一个程序需要调用另一个程序时，调用程序首先检查另一个程序是否已加载。
8.1.5 动态链接与共享库
动态链接库整个程序需要在内存中才能执行，在调用程序之前，不会加载程序。
8.3 连续内存分配
连续内存分配，每个进程位于一个连续的内存区域，与包含下一个进程的内存相连。
8.3.1 内存保护
每个逻辑地址应在界限寄存器规定的范围内。MMU通过动态地将逻辑地址加上重定位寄存器的值，来进行映射，映射后的地址再发送内存。
8.3.2 内存分配
固定分区方案，将内存分为多个固定大小的分区。
可变分区方案，操作系统有一个表，用于记录哪些内存可用和哪些内存已用，一大块的可用内存，称为孔。
动态存储分配问题：一块分配给新进程，另一块还回到孔的集合。
常见的算法：首次适应，最优适应，最差适应。
8.3.3 碎片
首次适应和最优适应算法都有外部碎片。按固定大小的块为单位来分配内存，进程分配的内存可能比所需的要大，两个数字之差称为内部碎片。
8.4 分段
8.4.1 基本方法
分段：程序和其相关的数据划分到几个段，所有段长度不一定相等，段有最大长度。
逻辑地址由段号和偏移量构成，分段类似于动态分区，消除了内部碎片，但是会产生外部碎片。一个程序占据多个分区，并且这些分区不要求是连续的。对程序员可见。
8.4.2 分段硬件
地址通过段表实现，以映射用户定义的二维地址到一维物理地址。段表的每个条目都有段基地址和段界限。
8.5 分页
8.5.1 基本方法
将物理内存分为固定大小的块，称为帧或页帧。而将逻辑内存也分为同样大小的块，称为页或页面。由CPU生成的每个地址分为两部分：页码和页偏移。
设置页表将逻辑地址转换为物理地址。仍有内部碎片。
访问一个字节需要两次内存访问。
8.5.2 硬件支持
内表保存在主存中，为每一个进程分配，页表基地址寄存器指向页表，页表长度寄存器指示页表的大小，特权指令。
转换表缓冲区（TLB）：关联的高速内存。解决两次内存访问问题。
TLB未命中时，值将加载到TLB中，以便下次快速访问。键值存储，给定值查找时，同时与所有的键进行比较。
实现：联想记忆——并行搜索，地址转换。
8.5.3 保护
通过将保护位与每个帧关联以指示是否允许只读或读写访问来实现内存保护，附加到页表总每个条目的有效—无效位。
8.6 页表结构
8.6.1 分层页表
两层分页算法：前向映射页表。
8.6.2 哈希页表
公共地址空间大于32位，虚拟页码散列到页表中，虚拟页码作为哈希值，此页表包含散列到同一位置的元素链。链表上的每个元素包含三个字段：1）虚拟页码 2）映射的帧码 3）指向链表内下一个元素的指针。
8.6.3 倒排页表
通过物理帧号找对应虚拟页码。
ch9 虚拟内存管理
9.1 背景
虚拟内存将用户逻辑内存与物理内存分开。虚拟地址空间：进程如何存储在内存中的逻辑视图。可以通过请求分页和按需分段实现。
9.2 请求调页
静态调页加载整个程序到内存当中。请求调页是仅在需要时才加载页面。
有效—无效位？
在MMU地址转换期间，页表条目中如果有效无效位为i，发生页面错误。
处理缺页：
- 如果无效，终止进程。若引用有效但未调入页面，那么发生缺页中断。
- 找到空闲帧。
- 通过磁盘调度操作将页面交换到刚分配的帧中。
- 当磁盘操作读取完成后，重置页表和快表，以表示当前页面在内存中。
- 重新启动导致缺页的指令，该进程能够访问所需的页。
9.4 页面置换
如果没有空闲帧，就查找当前不在使用的一个帧，并释放它。
9.4.2 FIFO置换算法
只有你会出现Belady异常。
9.4.3 最优页面置换
最好的算法
9.4.4 LRU置换算法
一般般吧~
9.4.5 近似LRU页面置换
clock算法。
循环队列，维护一个数组，页面进来，对应位设置为1。淘汰策略，指针循环遍历，淘汰第一个值为0的页面，并将指针指向下一位；如果当前位为1，则设置为0，继续遍历。
ch10 文件系统
10.1 文件概念
操作系统对存储设备的物理属性加以抽象，从而定义逻辑存储单位，即文件。
类型：数据文件（数字，字符，二进制），程序代码
文本文件：源文件，可执行文件。
10.1.1 文件属性
- 名称
- 标识符
- 类型
- 位置
- 尺寸
- 保护
- 时间、日期和用户标识
10.1.2 文件操作
- 创建文件
- 读文件
- 写文件
- 重新定位文件
- 删除文件
- 截断文件
在首次使用文件之前进行系统调用open()，操作系统有一个打开文件表以用于维护所有打开文件的信息。当请求文件操作时，可通过该表的索引指定文件。
系统打开文件表为每个文件关联一个打开计数，表示多少进程打开了这个文件。
每个打开文件有如下关联信息：
- 文件指针：上次读写的位置。
- 文件打开计数：多少个进程打开这个文件。
- 文件的磁盘位置：查找磁盘上的文件所需的信息保存在内存中。
- 访问权限：每个进程采用访问模式打开文件。
文件锁包括共享锁和独占锁。共享锁类似于读者锁，以便多个进程可以并发获取它。独占锁类似于写者锁，一次只有一个进程获取这样的锁。
10.1.3 文件类型
操作系统使用扩展名来指示文件类型和可用于文件的操作类型。
10.1.4 文件结构
文件类型也可用于指示文件的内部结构。
10.1.5 内部文件结构
由于磁盘空间总是以块为单位来分配的，因此每个文件的最后一块的某些部分通常会被浪费。块大小越大，内部碎片也越大。所有文件系统都有内部碎片。
10.2 访问方法
文件存储信息，当要使用时，必须读到内存中。
10.2.1 顺序访问
文件信息按顺序加以处理。读和写构成大部分操作。读操作，read_next()读取文件的下一部分，并且自动前移文件指针以跟踪I/O位置。写操作，write_next()会对文件的结尾附加内容，并移动到文件的新末尾。
10.2.2 直接访问
直接访问或相对访问。文件由特定长度的逻辑记录组成，以允许程序按任意顺序进行快读读取和写入记录。
使用块号作为参数传递read()或write()，很方便。相对访问就是用户先提供一个基准块号，接下来就是偏移的问题。
10.2.3 其他访问方法
索引访问：先搜索索引，然后根据指针直接访问文件并且找到相应记录。
10.3 目录与磁盘的结构
包含文件系统的分区称为卷。文件信息保存在设备目录或卷目录表中。
10.3.1 存储结构
分区可用于限制单个文件系统的大小。
10.3.2 目录概述
目录可视为符号表，可将文件名称转成目录条目。常见的目录操作如下：
- 搜索文件
- 创建文件
- 删除文件
- 遍历目录
- 重命名文件
- 遍历文件系统：可能希望访问每个目录和目录结构内的每个文件。
10.3.3 单级目录
最简单的目录结构是单级目录。所有文件都包含在同一目录中。就是把所有文件都堆在你的C盘上，没有任何文件夹。不支持重名。
10.3.4 两级目录
对于两级目录结构，每个用户都有自己的用户文件目录（UFD）。主文件目录（MFD）包含了所有UFD，用户可以进入其对应的UFD中。在不同用户目录内支持重名。搜索高效。
系统内的每个文件都有一个路径名。
10.3.5 树形目录
在根目录中，系统内的每个文件都有唯一的路径名。
绝对路径名和相对路径名。
10.3.6 无环图目录
文件或子目录可被不同目录共享。这里需要区别一下共享和副本，注意，这里是共享。
硬链接和软链接：实际上是另一文件或子目录的指针。绝对路径或相对路径。硬链接维护引用计数，每次删除-1，直到为0，删除文件。软链接给的是相对路径。
10.3.7 通用图目录
由于存在自我引用的缘故，需要使用垃圾收集的方案，以确定何时最后引用已被删除并重新分配磁盘空间。
10.6 保护
10.6.1 访问类型
通过限制可以进行的文件访问类型，保护机制提供受控访问。可以控制多个不同的操作类型：
- 读
- 写
- 执行
- 附加：在文件末尾写入新的信息。
- 删除：删除文件，并释放空间以便重复使用。
- 列表：列出文件的名称和属性。
10.6.2 访问控制
不同用户可以需要不同类型的文件或目录访问。访问控制列表指定每个用户的名称及其允许的访问类型。每个文件采用三种用户类型：所有者+组+其他。分别有RWX属性。
ch11 文件系统（磁盘）实现
11.1 文件系统结构
为了提高I/O效率，内存和磁盘之间的I/O传输以块为单位执行。每个块具有一个或多个扇区，一般一扇区为512字节。
块是存储设备上与 RAID 组相关的概念，而簇是主机上与文件系统相关的概念。
扇区是硬盘生产时就形成的，不可变更的。分区是根据自己需要来调节划分硬盘区域对应不同应用的方法。
文件系统提供高效和便捷的磁盘访问。分层设计的文件系统结构，从底层到上层依次为：设备，I/O控制，基本文件系统，文件组织模块，逻辑文件系统，用户程序。
- I/O控制：包括设备驱动程序和中断处理程序，以在主内存和磁盘系统之间传输信息。
- 基本文件系统：向适当设备驱动程序发送通用命令，以读取和写入磁盘的物理块。
- 文件组织模块：知道文件及其逻辑块以及物理块。
- 逻辑文件系统：管理元数据信息。
11.2 文件系统实现
11.2.1 概述
在磁盘上，文件系统可能包括以下信息：如何启动存储在那里的操作系统、总的块数、空闲块的数量和位置、目录结构以及各个具体文件等。
- 引导控制块可以包含从该卷引导操作系统的所需信息。
- 卷控制块包含卷的详细信息。
- 目录结构用于组织文件。
- 每个文件的FCB包含文件的详细信息。
内存信息用于管理文件系统并通过缓存来提高性能。这些数据在安装文件系统时被加载，在文件系统使用期间被更新，在卸载时被丢弃。包括：
- 内存中的安装表
- 内存中的目录结构的缓存含有最近访问目录的信息
- 整个系统的打开文件表：每个打开文件的FCB的副本。注意是副本。
- 每个进程的打开文件表：指向整个系统打开文件表中的适当条目的指针。
文件描述符（文件句柄）：打开文件表的条目。
请描述文件被创建和被删除的过程。
系统调用open()将文件名传递到逻辑文件系统，系统调用open()首先搜索整个系统打开文件表，如果文件在打开表中，则在单个进程的打开文件表中创建一个条目，并指向现有整个系统的文件打开表。如果这个文件未被打开过，则根据给定文件名搜索文件目录结构。部分的目录结构缓存在内存中，找到文件后，它的FCB会复制到内存的整个系统的开放文件表中。
当进程关闭文件时，它的单个进程表的条目会被删除，并且整个系统的条目的打开数量会递减。当所有打开该文件的用户关闭它时，任何更新的元数据会被复制到基于磁盘的目录结构，并且整个系统的打开文件表的条目会被删除。
11.4 分配方法
问题：如何为文件分配空间，以便高效使用磁盘空间和快速访问文件。磁盘空间分配的三种常见方式：连续、链接和索引。
11.4.1 连续分配
连续分配要求每个文件在磁盘上占有一组连续的块。因此，用于访问连续分配文件的所需寻道数量最小。
11.4.2 链接分配
链接分配解决了连续分配的所有问题，每块都有下一块的指针，用户不能使用这些指针。
要创建一个新文件，只需在目录中增加一个新的条目。采用链接分配，每个目录条目都有文件首个磁盘块的一个指针。主要磁盘有可用的空闲块，文件就可以继续增长。因此，无需合并磁盘空间。
链接分配主要问题是只能应用于顺序访问文件，不能支持文件的直接访问。
问题：指针占据的空间大
解决方法：将多个块组成簇，按簇分配代替按块分配。缺点：增加了磁盘吞吐量，但是会产生内部碎片。
问题：指针出错
解决方法：双向链表，每块存储文件名和相对块号
链接分配的一个重要变种文件分配表（FAT）。在该表中，每个磁盘块都有一个条目，可按块号来索引。目录条目包含文件首块的块号。通过这个块号索引的表条目包含文件的下一块的块号。未使用的块号用0作为表条目的值来表示。为文件分配一个新块只要简单找到第一个值为0的FAT条目。
需要对FAT进行缓存，否则会导致大量的磁头寻道时间。
11.4.3 索引分配
索引分配通过将所有指针放在一起，即索引块。每个文件都有自己的索引块，是一个磁盘块地址的数组，索引块的第i个条目指向文件的第i个块。当首次写入第i块时，先从空闲空间管理器中获得一块，再将其地址写到索引块的第i个条目。
索引分配支持直接访问，并且没有外部碎片问题，因为磁盘的任何空闲块可以满足更多空间的请求。
问题：索引块太小，不能为大文件存储足够多的指针；索引块太大，浪费空间。
解决方案：TBD
11.4.4 性能
最佳方法取决于文件访问类型：连续还是随机
链接适用于顺序，不是随机
在创建时声明访问类型：连续分配还是链接分配
索引分配更复杂：取决于索引的结构、文件的大小以及所需块的位置。
11.5 空闲空间管理
为了跟踪空闲磁盘空间，系统需要维护一个空闲空间列表。
11.5.1 位向量
01串表示
11.5.2 链表
将所有空闲磁盘块用链表链接起来，将指向第一空闲块的指针保存在磁盘的特殊位置上，同时也缓存在内存中。
11.5.3 组
在第一个空闲块存储n个空闲块的地址。
11.5.4 计数
ch12 大容量存储结构
12.1 大容量存储结构概述
12.1.1 磁盘
磁盘或硬盘称为外存。
读取或写入时，磁头必须被定为在期望的磁道，并从所期望的柱面和扇区的开始。寻道时间为定位到期望的磁道所花费的时间。旋转延迟为从零扇区开始处到达目的地花费的事件。访问延迟=寻道时间+旋转延迟。
12.2 磁盘结构
逻辑块的一维数组。
12.4 磁盘调度
12.4.1 FCFS调度
12.4.2 SSTF调度
最短寻道时间优先，并非最优
12.4.3 SCAN调度
对于扫描算法，磁臂从磁盘的一端开始，向另一端移动，遇到请求就处理请求。当到达磁盘的另一端时，磁盘移动方向翻转，并继续处理，称为电梯算法。
12.4.4 C-SCAN调度
循环扫描调度是SCAN的一个变种。视磁盘为环。
12.4.5 LOOK调度
SCAN算法寻到最远端即可，不必到达两端。
12.4.6 C-LOOK调度
C-SCAN调度寻到最远端即可，不必到达两端。
ch13 I/O系统
13.1 概述
设备驱动程序为I/O子系统提供了统一的设备访问接口。
- CPU和I/O设备间的接口
- 向CPU提供特殊指令和寄存器
I/O设备的要素：端口，总线，设备控制器。
I/O地址：
- CPU用来控制I/O硬件
- 内存地址或端口号：I/O指令或内存映射I/O
I/O指令是指通过I/O端口号访问设备寄存器，需要使用特殊的CPU指令。
内存映射I/O：设备的寄存器/存储被映射到内存物理地址空间中；通过内存load/store指令完成I/O操作；MMU设置映射，硬件跳线或程序在启动时设置地址。
课本表述：通过I/O指令完成I/O传输：通过特殊的I/O指令针对I/O端口地址传输一个字节或字。I/O指令触发总线线路，选择适当设备，并将位移入或移出设备寄存器。
内存映射I/O：设备控制寄存器被映射到处理器的地址空间。处理器执行I/O请求是通过标准数据传输指令读写映射到物理内存的设备控制器。
13.2 I/O硬件
I/O控制器是可以操作端口、总线或设备的一组电子器件。
CPU与设备的通信方式：轮询、设备中断和DMA
13.2.1 轮询
对于I/O的每个字节，从状态寄存器读忙位，直到该位为零；主机设置读或写位，如果写入，则将数据复制到数据输出寄存器中；主机设置命令就绪位；控制器设置忙位；控制器读取命令寄存器，并看到命令。从数据输出寄存器中读取一个字节，并向设备执行I/O操作；传输完成后，控制器清楚忙位、错误位和命令准备位。
功能+数据$\Rightarrow$状态
这种方式最开始主机处于忙等待或轮询。设备快，合理；慢就效率低；切换到其他任务，错过了就没有了。
可以在3个指令周期内发生。
13.2.2 中断
CPU每当执行完一条指令都会检查IRL是否有中断信号，若检查到，则CPU状态保存并跳到内存固定位置中断处理程序（上下文切换）。
中断处理程序确定中断原因，执行必要处理，执行状态回复，并且执行返回中断指令以便CPU回到中断前的执行状态。
设备控制器通过中断请求线发送信号而引起中断，CPU捕获中断并分派到中断处理程序。
中断I/O过程
中断其他用处：异常，缺页错误，系统调用（陷阱），多核系统实现多优先级中断，时间敏感处理。
13.2.3 直接内存访问（DMA）
目的：为了避免programmed I/O增加CPU负担，将任务交给专用的处理器（直接内存访问控制器）。
在启动DMA传输时，主机将DMA命令块写到内存。CPU将这个命令块的地址写到DMA控制器.DMA控制器继续直接操作内存总线，将地址放到总线。
DMA过程：
DMA控制器与设备控制器之间的握手，通过一对称为DMA请求和DMA确认的线路进行。
周期窃取：DMA控制器占用内存总线时，CPU被暂时阻止访问内存，但仍可以访问住缓存或辅助缓存内的数据项。
13.3 应用程序I/O接口
I/O设备的特点：
- 块I/O
- 字符I/O
- 内存映射文件访问
- 网络套接字
对I/O设备特定特性的直接操作，称为逃生或后门。
13.3.4 非阻塞与异步I/O
阻塞I/O与非阻塞I/O
13.4 内核I/O子系统
13.4.2 缓冲（buffer）
缓冲区为了解决处理数据流的生产者与消费者之间速度不匹配的问题
13.4.3 缓存（cache）
缓存是保存数据副本的高速内存区域。
13.4.4 假脱机与设备预留
假脱机是保存设备输出的缓冲区。
设备预留提供了特殊的设备通道，通过系统调用进行分配，要避免死锁。
13.4.6 I/O保护
定义所有的I/O指令为特权指令。
内存保护系统保护任何内存映射和I/O端口内存位置。
13.4.8 总结
I/O子系统协调大量的服务组合，以便于应用程序和其他内核部件。
标签：操作系统,调度,死锁,线程,内存,2023,进程,CPU,复习 From： https://www.cnblogs.com/chickchick/p/17508401.html