计算机操作系统

2024/3/27 Basic

字数统计: 24.9k字 | 阅读时长: 86分 | 总文章阅读量：次

前言

计算机408之操作系统

参考：上课的课件和《计算机操作系统（慕课版）》，以及b站大学，各路博客

引论

操作系统定义

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

是一种（系统）软件，是安装在计算机硬件上的第一层软件

shell：用户交互程序

主要功能

从人机交互、资源管理及资源抽象等不同方面来分析：

OS作为用户与计算机硬件系统之间的接口
OS作为计算机系统资源的管理者
OS实现了对计算机资源的抽象。

提供接口

资源管理

处理机管理：用于分配和控制处理机
存储器管理：负责内存的分配与回收
IO设备管理：负责IO设备的分配与操作
文件管理：用于实现对文件的存取、共享和保护

实现资源共享的方式——多路复用

资源抽象

抽象与现实，类似于类与实例

操作系统的抽象，是把硬件的具体细节隐藏了，而将一个清晰的、优雅的、一致的接口提供给用户。例如，CPU，鼠标等设备都被操作系统抽象成为了文件（数据结构），用户通过命令来操作它们

linux一切皆文件.jpg：

操作系统的发展过程

集成电路和多道批处理

CPU利用率

单位时间内CPU使用情况的统计，是除了空闲时间外的其他时间占总 CPU 时间的百分比

因为只有所有进程都处于阻塞态（如等待I/O）或者就绪队列中无进程时，CPU才会空闲下来，所以CPU利用率 = 1 - 进程等待I/O的概率 * 进程数

分时系统

满足用户对人机交互的需求，包括人机交互和共享主机

如Unix

特征：

多路性：多台终端同时联接到一台主机上
独立性：用户在各自的终端上操作
及时性：短时间响应
交互性：广泛的人机对话

应用程序可以交替执行

基本特征

并发和共享是多用户OS最基本的特征，并发和共享互为存在条件

并发

并发性（concurrency）是指两个或多个事件在同一时间间隔内发生。在宏观上是同时发生的，在微观上却仍是交替发生的
并行性（parallel）是指两个或多个事件在同一时刻发生（多处理器才可能真正实现）

共享

系统中的资源可供内存中多个并发执行的进程共同使用，这里既限定了时间（进程在内存中时），又限定了地点（内存）

主要的实现方式有两种：

互斥共享：规定一段时间内只允许一个进程访问该资源，仅当当前进程访问完并释放后，才允许另一进程对该资源进行访问

这种资源叫做临界资源，如系统中的大多数物理设备以及栈、变量和表格，都只能被互斥地共享
同时共享：允许一段时间内由多个进程“同时”对资源进行访问，这种资源比如有磁盘设备，允许若干个用户同时访问的文件

虚拟

在操作系统中，把通过某种技术将一个物理实体变为若干个逻辑上的对应物的功能称为“虚拟”

时分复用：
- 虚拟处理机技术：利用多道程序设计技术，为每道程序建立至少一个进程，使多道程序并发执行
- 虚拟设备技术：将一台物理上的 I/O 设备虚拟为多台逻辑上的 I/O 设备，并允许每个用户占用一台逻辑上的 I/O 设备，这样便可使临界资源变为允许多个用户“同时”访问的共享设备
空分复用：利用存储器的空闲空间（如某道程序阻塞时被换出到外存而空出来的内存空间）来存放其他程序以提高内存的利用率；还要引入虚拟存储技术（补充内存逻辑空间的技术），实现内存的分时复用，例如，100MB的程序在30MB的内存空间中可以运行是因为每次只把程序的一部分调入内存运行

异步

进程是以人们不可预知的速度向前推进的

让调用方法的主线程不需要同步等待另一线程的完成，从而可以让主线程干其它的事情

运行机制与体系结构

操作系统通过指令来运行处理器

特权指令：具有高级别权限，不允许用户程序使用
非特权指令：普通级别权限，如加减乘除等运算指令

状态转换

用户态：应用程序运行时所处的状态

内核态：操作系统内核运行时所处的状态

当应用程序需要访问操作系统提供的资源或执行一些特权操作时，需要切换到内核态，由操作系统内核来完成相应的操作。在内核态下，应用程序无法直接访问系统资源和硬件设备，需要通过操作系统提供的接口来进行操作

用户态->内核态：通过中断/异常/陷入机制实现，且中断是唯一途径
内核态->用户态：通过执行一个特权指令，将程序状态字（PSW）的标志位设置为“用户态”

内核程序：操作系统中，可以访问所有硬件设备，如网卡、内存设备等的一些特殊的高权限的系统程序

用户程序：只能有限的访问部分内存空间，对硬件设备没有访问权限的低权限的应用程序或系统程序

中断和异常

事件总是由中断或异常（陷阱）引起的，现代OS是由中断驱动的

中断：CPU对系统发生的某个事件做出的某种反应。当系统接收到一个中断信号时，CPU暂停正在执行的程序，保留现场后自动转去执行相应事件的处理程序，完成后返回断点，继续执行被打断的程序

中断的引入：为了支持CPU和设备间的并行操作（多道程序），即实现多道程序并发执行

异常：一种由软件引起的中断，或源于出错，或源于用户程序的特定请求（如执行OS的某个服务等）

异常的引入：表示CPU执行指令时本身出现的问题。如运算中遇到除零等错误，此时硬件改变了CPU当前的执行流程，自动转到相应的错误处理程序或异常处理程序或执行系统调用

分类：

内中断（也称异常、例外、陷入）：信号来源于CPU内部，与当前执行的指令有关
- 自愿中断：指令中断，如系统调用时使用的访管指令（又叫陷入指令、trap指令）
- 强迫中断：硬件故障（如缺页）、软件中断（如整数除以0）
外中断：信号来源于CPU外部，与当前执行的指令无关
- 外设要求：I/O操作完成发出的中断信号
- 人工干预：用户强行终止一个进程

中断/异常的作用：

及时处理设备发来的中断请求
使操作系统能捕获用户程序提出的服务请求
防止用户程序执行过程中的破坏活动等

发生中断就意味着需要操作系统介入，开展管理工作。由于操作系统的管理操作（如进程切换、分配IO设备等）需要使用特权指令，因此CPU要从用户态转为核心态

系统调用

应用程序通过系统调用（陷入机制，由用户态->内核态）请求操作系统的服务

系统中的各种共享资源都由操作系统统一掌管，因此在用户程序中，凡是与资源有关的操作（如存储分配、IO操作、文件管理等），都必须通过系统调用的方式向操作系统提出服务请求，由操作系统代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作

注：系统调用的处理是在核心态进行的

实例：C语言read函数的调用

count = read(fd, buffer, nbytes);
// fd：指定文件
// buffer：指向缓冲区
// nbytes：要读出的字节数

操作系统结构

单体系统（无结构系统）：整个操作系统在内核态以单一程序的方式运行。该结构中，系统中每个过程可以自由调用其他过程。整个系统以过程集合的方式编写，链接成一个大型可执行二进制程序
层次式系统：THE系统
微内核：将系统分成若干小的、良好定义的模块，且只有其中一个模块——微内核运行在内核态，其余模块则作为普通用户进程运行
客户端-服务器模式：微内核的一种变体，如Web服务器
虚拟机
外核

进程与线程

概述

定义&特征

进程是指在系统中能够独立运行并作为资源分配的基本单位，是由一组机器指令、数据和堆栈等组成的活动实体

进程实体（进程映像，可以认为是进程）：由程序段、相关的数据段和PCB三部分构成，是静态的；进程是进程实体的运行过程，是动态的

进程的特征：

动态性：进程的实质是程序的执行过程；而程序只是一组有序指令的集合，并存放在某种介质上
并发性：内存中有多个进程实体，各进程可并发执行
独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位
异步性：各进程按各自独立的、不可预知的速度向前推进，系统提供同步机制来解决异步问题

进程与程序的区别

进程也是一种程序，是专门负责处理其它程序如何在操作系统中运行的程序
进程能描述并发，而程序没有这个功能
进程是动态的，程序是静态的（根本区别）
进程有生命周期，是短暂的；而程序相对长（存在磁盘里）
一个程序可以对应多个进程（程序多开）
进程具有创建其它进程的功能

进程的组成

PCB

进程控制块（PCB）：操作系统配置的一个专门的数据结构。系统利用PCB来描述进程的基本情况和活动过程，进而控制和管理进程

PCB是进程存在的唯一标志。创建进程，实质上是创建进程实体中的PCB；而撤销进程，实质上是撤销进程实体中的PCB

PCB的构成：

标识符：与进程相关的唯一标识符，用来区分其他进程
状态：若进制正在执行，则进程处于运行态
优先级：相对于其他进程的优先顺序
程序计数器：程序中即将执行的下一条指令的地址
内存指针：包括程序代码和进程相关数据的指针，以及与其他进程共享内存块的指针
上下文数据：进程执行时处理器的寄存器中的数据
IO状态信息：包括显式IO请求，分配给进程的IO设备和被进程使用的文件列表等
记账信息：包括处理器时间总和，使用的时钟数总和，时间限制等

组织方式：

线性方式：把所有的PCB都组织在一张线性表中，表的首地址存放在内存专用区
链接方式：把具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列，如就绪队列。通常，将优先级高的进程排在前面

（图中最右边的指针表示队列中下一个优先级的PCB指针，0表示队列结束）

（注：单处理器系统中，同一时刻只有一个进程会处于运行状态）

如果系统中有许多处于就绪状态的进程，通常将它们按一定的策略（如优先级）排队，称为就绪队列

如果将处于阻塞状态的进程进行排队，称为阻塞队列。而为了减少队列操作的开销，系统会设置多个阻塞队列
索引方式：系统根据所有进程状态，建立几张索引表，并把索引表的首地址记录在内存的专用单元中。在每个索引表中，记录具有相应状态的PCB在PCB表中的首地址

操作系统会提供一个唯一仲裁程序例程来保护PCB，这里涉及到系统性能、软件信任度等问题

程序段

能被进程调度程序调度到CPU执行的程序代码段

程序可以被多个进程共享，即多个进程可以运行同一个程序

数据段

一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果

.data段：保存已初始化的全局变量和局部静态变量

.bss段：保存未初始化的全局变量和未初始化的局部静态变量

层次结构

父进程：创建进程的进程
子进程：被创建的进程，子进程又可以创建自己的子进程（即父进程的孙进程）。子进程可以继承父进程所拥有的资源，如父进程所打开的文件和分配到的缓冲区

Unix / Linux 系统为树型结构，可以共同组成一个进程家族（进程组）

Windows 系统没有进程层次的概念，所有进程都是地位相同的，进程之间的关系是获得句柄（作用相当于一个令牌，可以用来控制被创建的进程）与否、控制与被控制的关系

父进程使用句柄来控制子进程，然而，父进程可以把句柄传送给其它进程，这样就不存在进程层次了

进程状态

基本状态与转换

3种基本状态：

就绪态（ready）：进程已处于可运行的状态，只要获得CPU资源，就可立即运行
运行态（running）：该时刻进程实际占用CPU
阻塞/等待态（block/waiting）：正在执行的进程由于发生某事件（如I/O请求、申请缓冲区失败等）而暂时无法继续执行

基本状态转换：三状态模型

就绪->运行：调度程序选择一个新的进程运行
运行->就绪：运行进程用完了时间片且被换出；一个高优先级进程抢占正在运行的进程
运行->阻塞：当一个进程等待某个事件发生时，如I/O请求
阻塞->就绪：进程所等待的事件发生了，如I/O操作完成，产生中断

（不存在阻塞态 -> 运行态）

再认识两种状态：

创建态（或称新建态，new）：进程正在被创建，操作系统为进程分配资源、初始化PCB
终止态（或称结束态，terminated）：进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB

于是就有了五状态模型：

进程控制

是对系统中的所有进程实施有效的管理，具有进程创建、进程执行、进程切换以及进程终止（撤销）等功能

本质就是实现进程状态转换

一般由OS内核中的原语来实现：

原语处于系统最底层，是最接近硬件的部分，运行事件较短、调用频繁。其最大的特点是执行期间不允许中断（即操作的原子性）
原语采用“关中断”和“开中断”指令实现。开关中断指令的权限很大，是运行在核心态下的特权指令

创建

引起进程创建的事件：

用户登录：系统初始化
作业调度：一个批处理作业的初始化
提供服务：正在运行的程序执行了创建进程的系统调用
应用请求：用户请求创建一个新进程（上面3种都是由系统内核为用户创建一个新进程）

启动操作系统时会创建若干个进程，一些是前端交互进程，一些是后端守护进程（daemon）

进程的创建：

申请空白PCB
为新进程分配其运行所需的资源
初始化PCB
如果进程就绪队列能够接纳新进程，就将新进程插入就绪队列

通常，在系统调用fork()后，进程会使用另一个系统调用exec()，用新程序来取代进程的内存空间

创建的一般步骤：

为新进程分配一个唯一的进程标识符
为进程分配空间
初始化进程控制块
设置正确的链接：新进程进状态队列链表
创建或扩充其他数据结构：维护记账文件

执行

处理器至少支持两种执行模式：特权模式和用户模式

特权模式：也称为系统模式、控制模式或内核模式
用户模式：通常是用户程序运行的模式

设计两种模式是为了保护操作系统和重要的操作系统表不受用户程序的干扰

系统通过程序状态字PSW来判断当前模式

切换

进程的挂起：暂停运行

终端用户的需要
父进程的请求
负荷调节的需要
操作系统的需要

切换的时机：进程切换可在操作系统从当前正在运行进程中获得控制权的任何时刻发生，如一个进程从运行态切换为就绪态

上下文（context）：进程执行时处理器的寄存器中的数据

切换的成因：

系统中断，如时钟中断、IO中断或者内存失效
操作系统确定出现错误或异常条件
系统调用，正运行用户进程执行了一个请求IO操作的指令，此时该调用会转移到作为系统代码一部分的一个例程

切换的一般步骤：

决定是否作切换以及是否允许作切换
保存当前进程的进程上下文（包括CPU的所有寄存器中的值、进程的状态以及堆栈中的内容）
更新当前处于运行态进程的PCB以及其他相关字段的更新，如退出运行态的原因和记账信息
把该进程的PCB移到相应的队列
使用进程调度算法，选择某个就绪状态的进程
更新所选进程的PCB
更新内存管理数据结构（切换新的页表，然后使用新的虚拟地址空间）
载入程序计数器和其他寄存器先前的值，将进程上下文恢复为所选进程上次退出运行态时的上下文

终止

事件：

正常退出（自愿的）
出错退出（自愿的）：如打开不存在的文件，则系统会退出
严重错误（非自愿的）：指的是进程引起的错误，比如执行一条非法指令，引用不存在的内存或是除数为零等
被其他进程杀死（非自愿的）：Unix中的系统调用是kill，Windows中使用TerminateProcess函数

阻塞与唤醒

事件：

向系统请求共享资源失败
等待某种操作的完成
新数据尚未到达
等待新任务的到达

进程通信（IPC）

指进程之间的信息交换

进程是分配系统资源的单位（包括内存地址空间），因此各个进程拥有独立的内存地址空间，一个进程不能直接访问另一个进程的地址空间

概念

直接制约关系——相互合作

进程A通过缓冲区向进程B提供数据；当缓冲区空时，进程B不能获得数据而阻塞，一旦进程A将数据送入缓冲区，进程B被唤醒；反之，缓冲区满时，进程A被阻塞，仅当进程B取走数据时，才唤醒进程A（同步）

间接制约关系——共享资源

进程A进入临界区访问临界资源，此时进程B必须等待，当进程A退出临界区，进程B才能进入临界区访问临界资源（互斥）

临界资源

系统中某些资源一次只允许一个进程使用，如系统中的大多数物理设备以及栈、变量和表格等

临界区

各个进程中对某个临界资源实施操作的程序（代码）片段

使用原则：

空闲让进：没有进程在临界区时，想进入临界区的进程可以进入
忙则等待：不允许两个进程同时处于临界区中
让权等待：临界区外运行的进程不得阻塞其他进程进入临界区
有限等待：不得使进程无限期等待进入临界区

进程同步

是指为完成某种任务而建立的两个或多个进程，这些进程的执行存在某种时序关系，需要互相协作、合作

具体地，一个进程运行到某一个点时，要求另一个伙伴进程为它提供消息，在未获得消息之前，该进程进入睡眠（阻塞态），获得消息后被唤醒进入就绪态

进程互斥

进程互斥指的是当一个进程访问某临界资源时，其他进程必须等待其释放之后才能去访问该资源（即互斥访问）

进程互斥描述的是进程（对共享资源）的竞争关系；而进程同步描述的是进程（对共享资源）的合作关系

互斥是同步的一种特殊情况

对临界资源的互斥访问：

do {
	entry section; // 进入区，负责检查能否可进入的代码
	critical section; // 临界区，访问临界资源的代码
	exit section; // 退出区，负责解除对资源的占用的代码
	remainder section; // 剩余区，做其他处理的代码
} while(true)

进程通信方法

进程的高级通信机制共有以下四种：

共享存储

基于共享数据结构的通信方式：比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方法
基于共享存储区的通信方式：在内存中划出一块存储区，数据的形式、存放位置都由进程控制，而不是OS。相比之下，速度快，是一种高级通信方式

管道通信

管道：指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，即pipe文件，其实就是在内存中开辟一个固定的缓冲区

管道机制的协调能力：

互斥：防止进程进入竞争条件
同步
确定对方是否存在

消息传递

以格式化的消息为单位，将通信的数据封装在消息（队列）中，并利用系统提供的一组通信命令（原语）在进程间传递消息，完成进程间的数据交换。

例如：在计算机网络中，消息又被称为报文

该方法属于高级通信方式，主要方式：

直接通信方式：消息直接发送到接收进程的消息缓冲队列上
间接通信方式：也称为信箱通信方式，消息要先发送到中间实体（信箱）中

客户机－服务器

实现方法：

套接字：一个套接字就是一个通信标志类型的数据结构
- 基于文件型：一个套接字关联一个特殊的文件，通信双方通过对这个特殊文件进行读/写而实现通信，类似于前面的管道通信
- 基于网络型：通常是非对称方式通信，即发送者需要提供接收者的名称
远程过程调用（remote procedure call，RPC）和远程方法调用：RPC是一个通信协议，用于通过网络连接的系统，该协议允许运行于一台主机（本地）系统上的进程调用另一台主机（远程）系统上的进程

如果涉及的软件采用面向对象编程，那么远程过程调用也可以称作远程方法调用，例子：Java中的RMI

进程间的关系

感知程度	关系	一个进程对其他进程的影响	潜在的控制问题
进程间不知道对方的存在	竞争	一个进程的结果与另一个进程的活动无关；进程的执行时间可能会受到影响	互斥；死锁；饥饿
进程间接知道对方存在（共享对象）	共享合作	一个进程的结果可能取决于另一进程获得的信息；进程的执行时间可能会受到影响	互斥；死锁；饥饿；数据一致性
进程直接知道对方的存在（通信）	通信合作	一个进程的结果可能取决于另一进程获得的信息；进程的执行时间可能会受到影响	死锁；饥饿

术语

原子操作

原语：由若干条指令组成的，用于完成一定功能的一个过程，它们是原子操作；一个操作中的所有动作要么全做，要么全不做；原子性保证了并发进程的隔离

竞争条件：两个或多个进程读写某些共享数据，且最后的结果取决于这些进程运行的精确时序

互斥：由于各进程要求使用共享资源（变量、文件等），而这些资源需要排他性使用（独占），各进程之间竞争使用这些资源的关系

死锁

一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源。即大家都占用着对方想要的资源

活锁：拿到资源却又相互释放不执行

饥饿

一个可运行进程尽管能继续执行，但被调度程序无限期地忽视，而不能被调度执行的情形

例子：

如打印机分配案例。一种可能的方案是把打印机分配给打印最小文件的进程。
如果在一个繁忙的系统中，某个进程有一个很大的文件要打印，这个进程可能永远得不到打印机。

互斥访问的实现方法

软件解法

单标志法（严格轮换）

global boolean free = false // 临界区空闲标志，true为有进程在临界区，false反之

进程P、Q：

...
while(free); // 忙等待
free = true; // lock()
// 临界区
free = false; // unlock()
...

单标志轮换法

进程P：

...
while(not turn);
// 临界区
turn = false;
...

进程Q：

...
while(turn);
// 临界区
turn = false;
...

双标志法

进程P：

...
pturn = true;
while(qturn);
// 临界区
pturn = false;
...

进程Q：

...
qturn = true;
while(pturn);
// 临界区
qturn = false;
...

违反了有限等待

Dekker解法——三标志法

进程P：

...
pturn = true;
while(qturn){
    if(turn == 2){
        pturn = false;
        while(turn == 2);
        pturn = true;
    }}
    // 临界区
turn = 2;
pturn = false
...

进程Q：

...
qturn = true;
while(pturn){
    if(turn == 1){
        qturn = false;
        while(turn == 1);
        qturn = true;
    }}
    // 临界区
turn = 1;
pturn = false
...

Peterson解法

#define FALSE 0
#define TRUE 1
#define N 2
int turn;
    int interested[N];
    // 兴趣数组，初始值均为FALSE
    
void enter_region(int process)
{
    int other;
    other = 1 - process;
    interested[process] = TRUE;
    turn = process;
    while(turn == process && interested[other] == TRUE);
}

void leave_region(int process)
{
    interested[process] = FALSE;
}

进程i：

...
enter_region(i);
// 临界区
leave_region(i);
...

硬件解法

开关中断

TSL（Test and Set Lock）指令

XCHG指令（或Swap交换指令）

进程同步

允许多个进程从临界区里读数据，仅是读不写

同步机制：信号量机制和管程机制

信号量机制

两个或多个进程通过简单的信号进行合作，可以强迫一个进程在某个位置停止，直到它接收到一个特定的信号

信号量：可以是一个整数，也可以是更复杂的记录型变量

用户进程通过使用操作系统提供的一对原语（P、V操作）对信号量进行操作，从而实现进程的互斥、同步

对信号量S可以实施的操作：初始化、P操作和V操作

初始化完成后，只有P、V操作才能改变其值

P(s)/wait(s)：s–（申请），若 s<0 则等待，否则继续（这里的s是记录型变量）

P(s) // down, semWait
{
    s.count --;
    if(s.count < 0)
    {
        /*
        该进程状态置为阻塞状态;
        将该进程插入相应的等待队列s.quene末尾;
        重新调度;
        */
    }
}

V(s)/signal(s)：s++（释放），若 s<=0 ，唤醒一个等待的P

V(s) // up, semSignal
{
    s.count ++;
    if(s.count <= 0)
    {
        /*
        唤醒相应等待队列s.quene中等待的一个进程;
        改变其状态为就绪态，并将其插入就绪队列;
        */
    }
}

整型信号量：wait相当于P，signal相当于V，表示系统中某种资源的数量，如某系统中有一台打印机

int S = 1;

void wait (int S){ // wait 原语（不能被中断，比如下面的S<=0和S=S-1都不能被中断）相当于“进入区”
    while (S <= 0); // 如果资源数不够，就一直循环等待（问题：只要S<=0，就会发生“忙等”，违反“让权等待”原则）
    S=S-1; // 如果资源数够，则占用一个资源
}

void signal (int S){
    S=S+1;
}

记录型信号量：用记录型数据结构表示。先分资源，然后分不到的就阻塞，释放一个资源的时候如果对资源还有需求则唤醒一个阻塞的进程

typedef struct{
    int value;	// 代表资源数目
    struct process_control_block *list;	// 进程链表指针，用于链接上述所有等待进程
}semaphore;

相应地，wait(S) 和 signal(S) 操作为：

wait(semaphore *S){
    S->value--;
    if(S->value<0){	// 表示该类资源已分配完毕
        block(S->list);	// 阻塞，并将该进程插入信号量链表中
    }
}
signal(semaphore *S){
    S->value++;
    if(S->value<=0){	// 表示依然有进程在等待该类资源，因此调用wakeup原语唤醒等待队列中的第一个进程（由阻塞态进入就绪态）
        wakeup(S->list)
    }
}

如果 S->value 的初值为1，则表示只允许一个进程访问临界资源，此时的信号量是互斥信号量，用于进程互斥

AND型信号量：将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它可分配的资源也不分配给该进程。从而避免死锁

Swait(Dmutex, Emutex){
    while(TRUE){
        if(Dmutex >=1 and Emutex >=1){
            Dmutex--;
            Emutex--;
        }
    	else{
            // 将该进程置入等待队列
        }
	}
}
Ssignal(Dmutex, Emutex){
    while(TRUE){
        Dmutex++;
        Emutex++;
        // 将资源全部分给等待队列中的进程使其进入就绪态
    }
}

信号量集：对AND信号量加以扩充，在每次分配前，都必须测试资源的数量，看是否大于其下限值，并可按要求一次性分配多个资源

应用

实现进程互斥：

设置互斥信号量mutex，初值为1
在临界区之前执行P操作
在临界区之后执行V操作

semaphore mutex=1;

P1(){
    ...
    P(mutex);
    临界区代码段...
    V(mutex);
    ...
}

P2(){
    ...
    P(mutex);
    临界区代码段...
    V(mutex);
   	...
}

注意：对不同的临界资源需要设置不同的互斥信号量。PV操作必须成对出现

实现进程同步：

分析发生“同步关系”的位置
设置同步信号量S，初始为0
在前操作之后执行V操作
在后操作之后执行P操作

semaphore S=0;

P1(){
    代码1;
    代码2;
    V(S);
    代码3;
}

P2(){
    P(S);
    代码4;
    代码5;
    代码6;
}

实现前驱关系：

要为每一对前驱关系各设置一个同步变量
在前操作之后对相应的同步变量执行V操作
在后操作之前对相应的同步变量执行P操作

管程机制

高级同步机制：管程（monitor，Java中称为监视器，对应的关键字为synchronized），不用关注复杂的PV操作

管程是一个特殊（软件）模块，包括对描述共享资源的数据结构以及对该结构的操作的一组过程（即函数）

基本特征：

管程中的数据只能被管程中的过程访问；
一个进程仅通过调用管程内的进程才能进入管程访问共享数据；
管程是互斥进入的，每次仅允许一个进程在管程内执行某个内部过程

语法描述：

管程的名字
变量（初始值）
一组过程

功能

设置条件变量（condition），等待（wait）/唤醒（signal）操作来解决同步问题

条件变量：管程内的等待机制
- 进入管程的进/线程因资源被占用而进入等待状态
- 每个条件变量表示一种等待原因，对应一个等待队列
wait()：
- 将自己阻塞在等待队列
- 唤醒一个等待者或释放管程的互斥访问
signal()：
- 将等待队列中的一个进/线程唤醒
- 如果等待队列为空，则等同空操作

经典IPC问题

生产者－消费者问题

问题描述：

一个或多个生产者生成某种类型的数据放置在缓冲区中
有消费者从缓冲区中取数据，每次取一项
只能有一个生产者对缓冲区进行操作

要解决的问题：

当缓冲区已满时，生产者不会继续向其中添加数据
当缓冲区为空时，消费者不会从中移走数据

正确性要求：

在任何一个时间只能有一个线程操作缓冲区（互斥）
当缓冲区为空，消费者必须等待生产者（同步）
当缓冲区满，生产者必须等待消费者（同步）
需要三个信号量（每个要求需要一个单独的信号量）：二进制信号量mutex；一般信号量fullBuffers；一般信号量emptyBuffers

初始化：设开始时buffer为空，生产者可以往buffer添加n个单位

Class BoundedBuffer{
    mutex = new Semaphore(1);
    fullBuffers = new Semaphore(0);
    emptyBuffers = new Semaphore(n);
}

生产者：

BoundedBuffer::Deposit(c){
    emptyBuffers->P(); // 生产
    mutex->P();
    Add c to the buffer;
    mutex->V(); // mutex的PV操作保证互斥
    fullBuffers->V(); // 有货，来取
}

消费者：

BoundedBuffer::Remove(c){
    fullBuffers->P(); // 消费
    mutex->P();
    Remove c from the buffer;
    mutex->V(); // mutex的PV操作保证互斥
    emptyBuffers->V(); // 空仓，生产
}

多生产者－多消费者问题

案例：桌上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子等着吃盘子中的橘子，女儿等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿才可以从盘子中取水果

分析：

互斥关系：盘子是共享资源，访问需要互斥
同步关系：父亲－>女儿；母亲－>儿子。“盘子为空”这个事件可由儿子或女儿触发，事件发生后才允许父亲或母亲放水果。

设计：

互斥关系：对盘子的互斥访问，初值为 mutex=1

同步关系：同步信号量的初始值要看对应资源的初始值是多少（这里apple=0，orange=0）盘子容量的初始值为plate=1

读者－写者问题

多个进程共享一个数据区，这些进程分为两组：

读者进程：只在数据区中读数据，不会清空数据
写者进程：只往数据区中写数据

要求：

允许多个读者同时执行读操作（读进程不排斥其他读进程）
不允许多个写者同时操作
不允许读者、写者同时操作（写进程排斥其他所有进程）

问题分析：

互斥关系：写－写、读－读
同步关系：（即上面的要求）

解法一：读者优先

如果读者执行：

无其他读者、写者，该读者可以读
若已有写者等，但有其他读者正在读，则该读者也可以读
若有写者正在写，该读者必须等

如果写者执行：

无其他读者、写者，该写者可以写
若有读者正在读，该写者等待
若有其他写者正在写，该写者等待

初始化

rw = new Semaphore(1);    // 用于实现对文件的读写互斥访问
int count = 0;    // 记录当前有几个读者在访问文件
mutex = new Semaphore(1);    // 用于保证对count变量的互斥访问

读者：

reader(){
    while(True){
        P(mutex); // 保证各读者互斥
        if(count==0) // 第一个读者读
            P(rw); // 阻止写进程
        count++; // 读者计数器加1
        V(mutex);
        
        读文件
        
        P(mutex); // 保证各读者互斥
        count--; // 读者计数器减1
        if(count==0) //当最后一个读者读完文件
            V(rw); // 允许写进程
        V(mutex);
        }
}

写者：

writer(){
    while(True){
         P(rw); // 互斥访问
         
         写文件
         
         V(rw); // 释放资源
         
         }
}

问题：当不断有读者进来，那么写者就一直被阻塞等待，可能产生“饥饿”

解法二：写者优先

保证一个写进程声明想写时，不允许新的读进程访问该数据区

初始化

rw = new Semaphore(1); // 用于实现对文件的读写互斥访问
int count = 0; // 记录当前有几个读者在访问文件
mutex = new Semaphore(1);// 用于保证对count变量的互斥访问
w = new Semaphore(1); // 用于保证写优先

读者

reader(){
    while(True){
        P(w); // 在无写者请求时进入
        P(mutex); // 保证各读者互斥
        if(count==0) // 第一个读者读
            P(rw); // 阻止写进程
        count++; // 读者计数器加1
        V(mutex);
        V(w); // 恢复对文件的访问
        
        读文件
        
        P(mutex); // 保证各读者互斥
        count--; // 读者计数器减1
        if(count==0) // 当最后一个读者读完文件
            V(rw); // 允许写进程
        V(mutex);
    }
}

写者

writer(){
    while(True){
         P(rw); // 互斥访问
         
         写文件
         
         V(rw); // 释放资源
         
         }
}

并发执行P(w)的情况：

读者1->读者2

写者1->写者2

写者1->读者1

读者1->写者1->读者2

写者1->读者1->写者2

哲学家进餐问题

场景：5个哲学家，5把叉子，5盘意大利面（需要两把叉子才能吃）。哲学家的活动方式为：要么放下左右手叉子进行思考，要么拿起刀叉开始吃饭，且只有者两种交替状态

问题分析：

关系分析：5个哲学家，每个与左右邻居对其中间的叉子的访问是互斥关系
整理思路：每个哲学家需要同时持有两个临界资源才能开始吃饭，如何避免出现死锁现象是关键
信号量：定义5把叉子的信号量数组{1,1,1,1,1}，哲学家（0~4）i左边的叉子编号为i，右边的为(i+1)%5

线程

是一个处理器调度和资源分配的基本单元，也是程序执行流的最小单位，可以理解为“轻量级进程”

每个线程都有一个线程ID、线程控制块（TCB）

引入线程后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务

多线程：指操作系统在单个进程内支持多个并发执行路径的能力

执行路径：即处理器执行指令的执行顺序

与进程的区别

进程中所有线程共享该进程的状态和资源，所有线程都驻留在同一地址空间中，并可访问相同的数据

调度的基本单位：无线程操作系统中，进程作为独立调度和分派的基本单位，在每次被调度时，都需要进行上下文切换，开销大；有线程操作系统中，线程作为调度和分派的基本单位。当线程切换时，仅需保存和设置少量寄存器内容，切换代价远低于进程，且在同一进程中，线程的切换不会引起进程的切换
并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行。不同进程间的线程也能并发执行。从而有效地提高系统资源的利用率和吞吐量
拥有资源：进程可以拥有资源，而线程本身并不拥有资源，而仅有一些必要的、能保证独立运行的资源。多个线程共享进程所拥有的资源
独立性：在同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多
系统开销：线程轻量级，开销小
支持多处理机

功能

类似于进程，线程也具有执行状态，且可彼此同步

线程状态：和进程一样，线程的主要状态有运行态、就绪态和阻塞态

与线程状态改变相关的操作：

派生：在派生一个新进程时，同时也会为该进程派生一个线程。随后，进程中的线程可在同一个进程中派生另一个线程，并为新线程提供指令指针和参数；新线程拥有自己的寄存器上下文和栈空间，并放在就绪队列中
阻塞：线程需要等待一个事件时会被阻塞（保存线程的用户寄存器、程序计数器和栈指针），处理器转而执行另一个就绪线程
解除阻塞
结束：一个线程完成后会释放其寄存器上下文和栈

分类

用户级线程（User-Level Thread, ULT）：由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）

内核级线程（Kernel-Level Thread, KLT）：管理工作由操作系统内核完成，包括线程调度、切换等，因此内核级线程的切换必须在核心态

进程调度

实质上是一种资源分配

三个问题

WHAT：调度算法

WHEN：调度时机

HOW：进程

调度概念

调度时机

典型事件：

创建、唤醒、退出等进程控制操作
进程等待IO、IO中断
时钟中断，如时间片用完，计时器到时
进程执行过程中出现abort异常

当内核对中断/异常/系统调用做出处理时都是调度时机

调度过程（进程切换）

进程切换的代价：开销（cost）

直接开销：内核完成切换所用的CPU时间，包含保存和恢复寄存器、切换地址空间（相关指令比较昂贵）
间接开销：高速缓存（Cache）失效、缓冲区缓存失效和TLB（快表）失效

场景：进程A下CPU，进程B上CPU

保存进程A的上下文环境（程序计数器、程序状态字、其他寄存器等）
用新状态和其他相关信息更新进程A的PCB
把进程A移至合适的队列（就绪、阻塞等）
将进程B的状态设置为运行态
从进程B的PCB中恢复上下文

调度层次

长程调度（作业调度、高级调度）：对象是作业。根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列（外存与内存之间的调度，每个作业只调入一次，调出一次）

注：进程挂起时会被调到外存，但PCB不会被调到外存

中程调度（内存调度、中级调度）：决定将哪个处于挂起状态的进程重新调入内存

短程调度（进程调度、低级调度）：对象是进程（或LWP）。根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程

调度算法

进程优先级：表示进程的重要性和紧迫性

优先数：表示优先级的一个数值

静态优先级：在创建进程时确定的，其在进程的整个运行期间保持不变

动态优先级：在创建进程之初，先赋予进程一个优先级，然后优先级会随进程的推进或等待时间的增加而改变，以便获得更好的调度性能

抢占式：当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用

非抢占式：继续运行

时间片：是一个时间段，分配给调度上CPU的进程，确定了允许该进程运行的时间长度

性能指标

CPU利用率：指cpu的有效工作时间占总时间的比例
系统吞吐量：单位时间内完成作业的数量 = 作业数 / 时间
到达时间（提交时间）：操作系统开始处理进程的时间点，之后进程进入队列等待被处理
开始时间：操作系统真正开始处理进程的时间点
执行时间：操作系统处理完这个程序的时间
周转时间：是指从作业被提交给系统开始，到作业完成为止的这段时间间隔

周转时间 = 作业完成时间（结束时间） - 作业提交时间（到达时间）

平均周转时间 = 各作业周转时间之和 / 作业数

带权周转时间 = 作业周转时间 / 作业实际运行的时间（执行时间）
等待时间（响应时间）：指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低

等待时间 = 开始时间 - 到达时间

多道批处理系统的调度算法

做题时先画个甘特图再画表

先来先服务（FCFS）：先进先出（FIFO），非抢占式算法
最短作业优先（SJF）：在有多个进程在队列中等待处理时，具有最短完成时间的进程优先执行，即要求服务时间最短
最短剩余时间优先（SRTN）：SJF抢占式版本，当一个新就绪的进程比当前运行进程具有更短的完成时间，系统抢占当前进程，选择新就绪的进程执行
最高响应比优先（HRRN）：考虑到各个作业的等待时间，也能兼顾运行时间。计算响应比R，选择R最高的进程执行：

响应比R = 周转时间 / 执行时间 = （执行时间 + 等待时间）/ 执行时间 = 1 + （等待时间 / 执行时间）

满足短作业优先且不会发生饥饿现象

交互式系统的调度算法

轮转调度（RR）：轮流让各个进程执行一个时间片，用完时间片但是未执行完则被中断，重新放到就绪队列队尾排队（就绪状态）

不可能导致饥饿现象
最高优先调度（HPF）：选择优先级最高的进程投入运行。通常系统进程优先级高于用户进程；前台进程优先级高于后台进程；操作系统更偏好IO型进程
多级队列调度（MQ）
多级反馈队列（MFQ）

时间片问题：

如果时间片太长（长于典型的交互时间）：降级为先来先服务算法，延长短进程的相应时间
如果时间片太短（短于典型的交互时间）：进程频繁切换浪费CPU时间

实时系统调度算法

硬实时系统：要求在指定的时间内必须完成任务

软实时系统：要求在指定的时间内尽量完成任务

最早截止时间优先算法（EDF）：根据任务的截止时间确定任务的优先级。任务的截止时间越早，其优先级越高

最低松弛度优先（LLF）：根据任务的紧急或松弛程度来确定优先级。松弛度最低的优先级最高

例如，1个任务要在200ms时必须完成，其本身的执行时间为100ms，则松弛度为100ms；1个任务要在400ms时完成，其本身的执行时间为150ms，则松弛度为250ms

死锁处理

死锁概述

定义：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程

参与死锁的进程是被阻塞的，无法上CPU

活锁：先加锁，再轮询。既无进展也无阻塞。能上CPU，但只能忙等

饥饿：长期得不到想要的资源，而无法上CPU

产生死锁的必要条件：

互斥使用：一个资源每次只能给一个进程使用
占有且等待：进程在申请新的资源的同时保持对原有资源的占有
不可抢占：资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放
循环等待（环路等待）

死锁发生时，以上四个条件一定是同时满足的，如果其中任何一个条件不成立，死锁就不会发生

注：发生死锁时一定有循环等待，但是发生循环等待时未必有死锁

死锁建模

圆形：进程节点
方形：资源节点
从资源节点到进程节点的有向边：该资源已被请求、授权并被进程占用
从进程节点到资源节点的有向边：当前进程正在请求该资源，并且该进程已被阻塞，处于等待状态

处理策略

忽略该问题
避免死锁：仔细分配资源，动态地避免死锁
预防死锁：通过破坏引起死锁的4个必要条件之一，防止死锁的发生
检测死锁并恢复（解除）：让死锁发生，检测它们是否发生，一旦发生，采取行动解决

鸵鸟算法

假装无事发生

死锁避免

在系统运行过程中，对进程请求的资源进行动态检查，并根据检查结果决定是否分配资源，若分配后系统发生死锁或可能发生死锁，则不予分配，否则予以分配

考虑一个系统，它有固定数量的进程和固定数量的资源，任何时刻一个进程可能分配到零个或多个资源

安全序列：如果系统按照这种序列分配资源，则所有进程都能顺利完成。只要能找出一个安全序列，系统就处于安全状态。安全序列可能有多个
不安全状态：如果分配资源后，系统找不出任何一个安全序列，则系统进入不安全状态。当然，如果有进程提前归还了一些资源，则系统有可能重新回到安全状态

系统处于安全状态，就一定不会发生死锁；如果系统进入不安全状态，就有可能发生死锁。处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态

两个状态的区别：从安全状态出发，系统能保证所有进程都能完成；而从不安全状态出发，就无法保证

银行家算法

在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会，就暂时不答应这次请求，让该进程先阻塞等待

检查一个状态是否安全的算法：

查找右边矩阵中是否有一行，其没有被满足的资源数均小于等于A。如果不存在，那么系统将会死锁，因为任何进程都无法运行结束
假如找到这样一行，那么可以假设它获得所需的资源并运行结束，将该进程标记为终止，并将其资源加到向量A上
重复以上两步，或者直到所有的进程都标记为终止，其初始状态是安全的；反之，发生死锁

预防死锁

破坏互斥条件：一般来说无法破坏
破坏占有且等待条件：
破坏不可抢占条件：当一个进程请求当前被另一个进程占有的一个资源时，操作系统可以抢占另一个进程，要求它释放资源
破坏循环等待条件：采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源

死锁检测和死锁恢复

死锁检测

死锁恢复：

利用抢占恢复
利用回滚恢复：设置进程检查点
通过杀死进程恢复

存储器管理

分层存储器系统

内存基础

帕金森定律：不管存储器有多大，程序都可以把它填满

内存是用于存放数据的硬件，程序执行前需要先放到内存中才能被CPU处理

Screenshot_2024-05-29-08-31-43-197_com.orion.notein-edit

寄存器：是CPU内部用来存放数据的一些小型存储区域，用来暂时存放参与运算的数据和运算结果，对寄存器的访问速度最快
高速缓存（Cache）：主要用于备份主存中较常用的数据，以减少处理机对内存的访问次数，提高程序执行速度。为了缓和内存与处理机速度之间的矛盾
主存储器（内存）：用于保存进程运行时的程序和数据
磁盘缓存：暂时存放频繁使用的一部分磁盘数据和信息，减少访问磁盘的次数

寄存器和主存储器被称为可执行存储器

外存：外储存器是指除计算机内存及CPU缓存以外的储存器，此类储存器一般断电后仍然能保存数据。外存需要通过I/O系统与之交换数据，又称为辅助存储器。常见的外储存器有硬盘、软盘、光盘、U盘等

内存保护

方法一：在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。但是需要存储在连续的地址

Screenshot_2024-05-29-08-35-01-609_com.orion.notein-edit

方法二：采用重定位寄存器（基址寄存器）和界址寄存器（限长寄存器）进行越界检查，重定位寄存器中存放的是进程的起始物理地址；界址寄存器中存放的是进程的最大逻辑地址。可用于非连续存储或虚拟内存

Screenshot_2024-05-29-08-36-08-047_com.orion.notein-edit

程序的装入和链接

编译：由编译程序将用户源代码编译成若干目标模块（高级 -> 机器）
链接：由链接程序将编译后的目标模块和所需库函数链接在一起，形成一个完整的装入程序
装入：由装入程序将装入模块装入内存运行

装入

物理地址 / 绝对地址：物理内存中实际地址，内存单元看到的地址（即装入内存地址寄存器的地址）

逻辑地址 / 相对地址：相对于程序开始地址的地址，由CPU生成

地址空间：一个进程可用于寻址内存的一套地址集合，独立于其他进程

绝对装入：直接访问物理内存，导致同时运行两个程序可能导致崩溃，不同时运行也可能崩溃

静态重定位

Screenshot_2024-05-29-08-41-44-410_com.orion.notein-edit

又称为可重定位装入，编译、链接后的装入模块的地址都是从0开始的。指令中使用的地址，数据存放的地址都是相对于起始地址而言的逻辑地址。装入内存后，对地址进行“重定位”

特点：在一个作业装入内存时，必须分配其要求的全部内存空间。作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间

动态重定位

又称为动态运行时装入，编译、链接后的装入模块的地址都是从0开始的，装入内存后，并不会立即进行转换，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存的依然是逻辑地址。需要重定位寄存器支持。允许程序在内存中发生移动

模块在内存中的起始地址 + 目标内存单元相对于起始位置的偏移量

链接

链接程序的功能是将目标模块以及它们所需的库函数装配成一个完整的装入模块

链接后形成的目标程序中的地址就是逻辑地址

静态链接

在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完成的可执行文件，之后不再拆开

Screenshot_2024-05-29-08-45-00-617_com.orion.notein-edit

装入时动态链接

将各目标模块装入内存时，边装入边链接的链接方式。其优点是便于修改和更新，以及实现对目标模块的共享

Screenshot_2024-05-29-08-45-52-878_com.orion.notein-edit

运行时动态链接

在程序执行中需要该目标模块时，才对它进行链接。优点是加快程序的装入过程，且节省内存空间

Screenshot_2024-05-29-08-46-25-544_com.orion.notein-edit

连续分配存储方式

程序装入内存前，必须为它分配一定大小的存储空间

碎片问题

内存分配会导致碎片问题：

内部碎片：分配给某个进程的内存区域中，有空闲

外部碎片：内存中的某些空闲分区由于太小而无法分配。可采用紧凑技术来解决

单一连续分配

Screenshot_2024-05-29-08-50-15-757_com.orion.notein-edit

固定分区分配

将整个用户空间划分为若干固定大小的区域

Screenshot_2024-05-29-08-51-49-510_com.orion.notein-edit

优点：简单，无外部碎片

缺点：内存利用率低。程序太大而分区太小，使用覆盖技术设计程序；程序太小也要占用整个分区，从而导致内部碎片

动态分区分配

对应的数据结构：空闲分区表和空闲分区链

Screenshot_2024-05-29-09-01-26-907_com.orion.notein-edit

Screenshot_2024-05-29-09-02-10-097_com.orion.notein-edit

动态分区分配没有内部碎片，但有外部碎片

分配算法

基于顺序搜索：首次适应、下次适配算法、最佳适配算法、最差适配算法

首次适应算法（FF）：每次都从低地址开始查找，找到第一个能满足大小需求的空闲分区
下次适配算法（NF）：每次找到合适的空闲区时都记录当时的位置，以便在下次寻找空闲区时从上次结束的地方开始搜索
最佳适配算法（BF）：搜索整个链表，找出能够容纳进程的最小空闲区，即试图找出最接近实际需要的空闲区
最差适配算法（WF）：该算法总是分配最大的可用空闲区，使新的空闲区比较大从而可以继续使用

以上四种方法，随着时间的推移，内存中会形成越来越多的外部碎片，内存的利用率随之下降

基于索引搜索：快速适应、伙伴系统、哈希算法

分配回收

上相邻：回收分区的上邻分区是空闲的，需要将两个相邻的空闲区合并成一个更大的空闲区，然后修改空闲区表

下相邻：回收分区的下邻分区是空闲的，需要将两个相邻的空闲区合并成一个更大的空闲区，然后修改空闲区表

上下相邻：回收分区的上、下邻分区都是空闲的（空闲区个数为2），需要将三个空闲区合并成一个更大的空闲区（空闲区个数为1 ），然后修改空闲区表

上下都不相邻：回收分区的上、下邻分区都不是空闲的，则直接将空闲区记录在空闲区表中

非连续分配方式

实际应用中，所有进程所需的内存容量通常要远远超出存储器能够支持的范围，现通用的方法有：交换技术和虚拟内存技术

虚拟存储只能基于非连续分配技术

交换技术

覆盖技术

将程序分为多个段（模块）。常用的段常驻内存，不常用的段在需要时调入内存

Screenshot_2024-05-29-09-17-54-523_com.orion.notein-edit

交换技术

内存空间紧张时，系统将内存中暂时不能运行的或不用打进程（或数据）暂时移到外存（挂起），把外存中已具备运行条件的进程交换进内存

地址空间结构

Screenshot_2024-05-29-09-33-00-233_com.orion.notein-edit

例：

int a = 0;    // 全局初始化区
char *p1;    // 全局未初始化区
main()
{
    int b;    // 栈
    char s[];    // 栈
    char *p2;    // 栈
    char *p3 = "123456";    // 123456\0在常量区，p3在栈上
    static int c = 0;    // 全局（静态）初始化区
    p1 = (char *)malloc(10);
    p2 = (char *)malloc(20);    // 分配得来的区域在堆区
}

分页式存储管理

如果允许将一个进程分散地装入到许多不相邻的分区中，便可更充分地利用内容，从而产生非连续分配方式

基本概念

用户进程的地址空间被划分为大小相等的分区（或块），称为页或页面（page），从0开始编号

内存空间按同样大小划分为大小相等的块，称为页框（frame），或称物理页面、页帧、内存块，物理块等，也从0开始编号

Screenshot_2024-05-29-09-48-50-790_com.orion.notein-edit

地址转换

系统以页框为单位为各个进程分配内存。典型的页面大小：4K或4M（大小必须是2的整数倍）

页面与页框是一一对应关系。逻辑上相邻的页，物理上不一定相邻。划分是系统自动完成的，对用户是透明的

分页技术会产生较少的内部碎片，没有任何外部碎片

Screenshot_2024-05-29-09-58-47-088_com.orion.notein-edit

计算：十进制数表示逻辑地址时，

页表

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表

页表项（PTE）：记录了逻辑页号与页框号的对应关系，存放在内存（或虚存），页表起始地址保存在页表寄存器中，其结构包括：

页框号：物理页面号
有效位（在/不在位）：1表示该页在内存，0表示不在内存
访问位：此页是否被访问过
修改位：此页在内存中是否被修改过
保护位：只读/可读写
用户/内核位，高速缓存禁止位等

快表

为了提高地址变换速度，可在地址变换机构中增设一个具有并行查询能力的高速缓冲寄存器

将逻辑（虚拟）地址直接映射到物理地址，而不必访问页表。这种设备称为地址变换高速缓存（TLB），即快表

此时的地址变换过程：

CPU给出有效地址后，由地址变换机构自动地将页号送入快表
并将此页号与快表中的所有页号进行比较
- 若匹配到（TLB命中），可直接从快表中读出该页所对应的物理块号b，并将其送到物理地址寄存器中
- 若TLB未命中，则还需再访问内存中的页表，直至找到后，把从页表项读出的物理块号送到地址寄存器；同时，再将此页表项存入快表的一个寄存器单元中，即重新修改快表
  - 若快表已满，则OS必须找到一个老的且已被认为是不再需要的页表项，并将它换出

多级页表

让线性页表的一部分消失（释放这些帧用于其他用途），并用页目录来记录页表的哪些页被分配

基址变换机构

负责将页表中的逻辑地址转换为物理地址

通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块PCB中，当进程被调度时，系统内核会把它们放到PTR中

Screenshot_2024-05-30-17-19-27-735_com.orion.notein-edit

地址转换的计算

算出逻辑地址对应的页号 = 逻辑地址 / 页面长度（下取整）
获取该页号对应页面在内存中的起始地址
算出逻辑地址在页面内的逻辑量 = 逻辑地址 % 页面长度
物理地址 = 页面起始地址 + 页内偏移量

分段存储管理

段表

段表记录了段与内存位置的对应关系。

段表保存在内存中

段表的基址及长度由段表寄存器给出

地址映射表：每个进程一张段表，每个段一张页表

虚拟内存管理

局部性原理

程序执行过程中，数据和指令往往倾向于在短时间内多次访问一部分的地址空间，而不是随机地访问整个地址空间

形式：

时间局部性（Temporal Locality）：当程序访问了某个存储单元（如内存中的某个数据）后，很可能在不久的将来再次访问相同的存储单元。这表明程序具有重复访问相同数据的趋势
空间局部性（Spatial Locality）：当程序访问了某个存储单元后，很可能在不久的将来访问其附近的存储单元。这表明程序倾向于顺序地访问内存，使得紧邻的数据也被频繁地访问

局部性原理使得虚拟存储技术的实现成为可能

虚拟内存：是一种计算机操作系统的技术，它允许程序使用比实际物理内存更大的虚拟地址空间

请求分页存储管理

为了解决系统内存容量不足

在请求分页系统中，只要求将当前最需要的一部分页面装入内存，就可以启动作业进行运行

当需要访问的页面不在内存中时，可通过调页功能将其调入内存，通过置换功能将暂时不用的页面调到外存

页表机制

主要的数据结构，将用户地址空间中的逻辑地址映射为内存空间中的物理地址

状态位：用于指示该页是否已调入内存，供程序访问时参考
**访问字段(A)**：记录本页在一段时间内被访问的次数，或者记录本页最近已有多久时间未被访问，供置换算法在选择换出页面时参考
**修改位(M)**：表示该页在调入内存之后有没有被修改。供置换页面时参考。未修改则无需写入外存。
外存地址：用于指出该页在外存上的地址，通常是物理块号地址，供调入该页时参考。

缺页中断

当所要访问的页面不在内存时，便产生一缺页中断，请求 OS 将缺的页调入内存

注：缺页中断属于内中断，一条指令在执行期间，可能会产生多次缺页中断

地址变换

逻辑地址到物理地址的变换

在进行地址变换时，首先检索快表，试图从中找出所要访问的页
1. 若找到，便修改页表项中的访问位，供置换算法选换出页面时参考
2. 对于写指令，还须将修改位改成“1”，表示该页在调入内存后已被修改
3. 然后利用页表项中给出的物理块号和页内地址形成物理地址
如果在快表中未找到该页的页表项，则应到内存中去查找页表，再从找到的页表项中的状态位 P 来了解该页是否已调入内存
1. 若该页已调入内存，这时应将该页的页表项写入快表
2. 当快表已满时，则应先调出按某种算法所确定的页的页表项，然后再写入该页的页表项
3. 若该页尚未调入内存，这时应产生缺页中断，请求 OS 从外存把该页调入内存

虚拟内存管理策略

读取策略

确定一个页何时取入内存，常用的两种方法是请求分页和预先分页

请求分页：只有当访问到某页中的一个单元时才将该页取入内存
预先分页：读取的页并不是缺页中断请求的页

放置策略

决定一个进程块驻留在实存中的什么地方

置换策略

页面置换算法

抖动：一个进程在运行中把大部分时间都花费在了页面置换工作上

先进先出（FIFO）：总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰
最佳页面置换算法（OPT）：将未来最长时间不会被访问的页面淘汰
最近最久未使用页面置换算法（LRU）：将最近最久未使用的页面进行淘汰

做题：参考https://www.bilibili.com/video/BV1kJ411E7AQ

画表格进行判断

页面走向	1	2	…
物理页0
物理页1
物理页2
…
缺页

FIFO

先进先出，谁长换谁

前4个走向都是直接置换进去，所以均存在缺页

第5个开始，因为1存在的时间最久（即连续占的格子最多），于是5和1置换，以此类推

缺页率：缺页数 / 页面走向的总数

OPT

往右看，谁最远首次出现换谁

注：遇到出现两个以上可换的情况时，继续遵循FIFO

LRU

往左看，谁最远首次出现换谁

缺点：可能出现Belady异常现象

Clock

可以认为是一种最近未使用算法，即逐出的页面都是最近没有使用的那个。我们给每一个页面设置一个标记位u，u=1表示最近有使用；u=0则表示该页面最近没有被使用，应该被逐出

按照1-2-3-4的顺序访问页面，则缓冲池会以这样的一种顺序被填满：

注意中间的指针，就像是时钟的指针一样在移动，这样的访问结束后，缓冲池里现在已经被填满了

此时如果要按照1-5的顺序访问，那么在访问1的时候是可以直接命中缓存返回的

但是访问5的时候，因为缓冲池已经满了，所以要进行一次逐出操作，其操作示意图如下：

最初要经过一轮遍历，每次遍历到一个节点发现u=1的，将该标记位置为0，然后遍历下一个页面，一轮遍历完后，发现没有可以被逐出的页面，则进行下一轮遍历，这次遍历之后发现原先1号页面的标记位u=0，则将该页面逐出，置换为页面5，并将指针指向下一个页面

假设我们接下来会访问2号页面，那么可以直接命中指针指向的页面，并将这个页面的标记为u置为1

但是考虑一个问题：数据库里逐出的页面是要写回磁盘的，这是一个很昂贵的操作，因此我们应该优先考虑逐出那些没有被修改的页面，这样可以降低IO

于是对Clock算法做一个改进：增加一个标记为m，修改过标记为1，没有修改过则标记为0

(u=0, m=0) 没有使用也没有修改，被逐出的优先级最高；
(u=1, m=0) 使用过，但是没有修改过，优先级第二；
(u=0, m=1) 没有使用过，但是修改过，优先级第三；
(u=1, m=1) 使用过也修改过，优先级第四。

页缓冲

一种可以提高分页的性能并且允许使用较简单的页面置换策略的方法

工作集

在某段时间间隔里，进程实际访问页面的集合

驻留集管理

概念

是进程当前分配到物理页框中的所有页构成的集合，即给进程分配的物理块的集合，受操作系统分页分配策略和内存可用状态影响

驻留集大小问题：即操作系统决定分配多大的内存空间给进程的问题

分配策略

固定分配策略：为一个进程在内存中分配固定数量的页框，以供执行时使用。一旦发生缺页中断，进程的一页必须被置换
可变分配策略：允许分配给一个进程的页框在该进程的生命周期中不断地发生变化。若该进程的缺页率高，则多分配页框；若特别低，则可适当减少页框

置换范围

局部置换策略：发生缺页时，仅选进程自己的物理块进行置换
全局置换策略：可以将系统保留的空闲物理块分配给缺页进程，也可将别的进程持有的物理块置换到外存，再分配给缺页进程

注：全局意味着一个进程拥有的物理块数量必然会改变，因此不可能是固定分配，即固定分配,全局置换不可能同时存在

清除策略

用于确定何时将已修改的一页写回辅存

请求式：只有当一页被选择用于置换时才被写回
预约式：将这些已修改的多页在需要使用它们所占据的页框之前成批写回

请求分段存储管理

硬件支持

请求段表机制

请求分段的段表项：

| 段名 | 段长 | 段基址 | 存取方式 | 访问字典 A | 修改位 M | 存在位 P | 增补位 | 外存始址 |

存取方式：标识只执行、只读、读写
访问字段 A：记录该段被访问的频繁程度
修改位M：表示该段在进入内存后，是否被修改过
存在位P：表示该段是否在内存中
增补位：用于本段在运行过程中是否做过动态增长

缺段中断机构

地址变换机构

共享与保护

输入输出系统管理

概述

设备无关性

又称设备独立性：操作系统把所有外部设备统一当作成文件来看待，只要安装它们的驱动程序，任何用户都可以象使用文件一样，操纵、使用这些设备，而不必知道它们的具体存在形式

实现：引入逻辑设备和物理设备两个概念，在应用程序中，使用逻辑设备名来请求使用某类设备；而在系统实际执行时，必须将逻辑设备名映射成物理设备名使用

硬件原理

IO控制器

主要任务

接收和识别CPU发出的命令，如CPU发来的 read/write 命令，控制器中控制寄存器用来存放命令和参数
向CPU报告设备的状态，控制器中有状态寄存器，用于记录IO设备的当前状态，如空闲或忙碌
数据交换，控制器有数据寄存器。在输出时，用于暂存CPU发来的数据，之后再由控制器传送给设备；输入时，用于暂存设备发来的数据，之后CPU从中取走数据
地址识别，为了区分控制器中的各个寄存器，也需要给它们设置一个特定的地址。控制器通过该地址来判断CPU要读/写的是哪个寄存器

组成

一个I/O控制器可能会对应多个设备
数据寄存器、控制寄存器、状态寄存器可能有多个（如：每个控制/状态寄存器对应一个具体的设备），且这些寄存器都要有相应的地址，才能方便CPU操作。有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像I/O；另一些计算机则采用I/O专用地址，即寄存器独立编址

IO控制方式

中断驱动方式

CPU发出读写命令，将等待IO进程阻塞。切换其他进程执行。
当IO完成后，控制器向CPU发出一个中断信号，CPU检测到中断信号后，会切换进程，处理中断。
CPU将一个字的数据传送到CPU寄存器，再写入主存。
CPU恢复等待IO的进程（或其他进程）的运行环境，然后继续执行。

例：键盘输入信息

DMA方式

Direct Memeoy Access，直接存储器存取

主要用于块设备的IO控制

数据的传送单位是块，不再是一个字、一个字的传送

数据的流向是设备->内存，或者内存->设备，不再需要CPU作为中间媒介，在IO设备和主存之间建立一条直接数据通路

仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。

IO通道控制方式

通道又称为IO处理机,它主要用于实现内存与外设之间的信息传输

通道控制设备控制器，设备控制器控制设备工作

CPU向通道发出IO指令，指明通道程序在内存中的位置，并指明要操作哪个IO设备，之后CPU就切换到其他进程执行了。
通道执行内存中的通道程序。比如指明要读入、写出多少数据，读写数据应放在内存的什么位置等信息。
通道执行完规定的任务后，向CPU发出中断信号，之后CPU对中断进行处理。

软件原理

层次划分

用户层软件：通过系统调用请求设备独立性软件层的服务
设备独立性软件层（设备无关软件）：根据LUT调用设备对应的驱动程序
驱动程序：向IO控制器发出具体命令
中断处理
等待IO完成的进程应该被阻塞，因此需要进程切换，而进程切换必然需要中断处理

设计关键

设备独立性：程序可以访问任意IO设备而无需事先指定设备，如读取一个文件作为输入的程序应该能够从硬盘、光盘或U盘上读取文件，无需为每一种不同设备修改程序
统一命名：一个文件或一个设备的名字应该是一个简单的字符串或一个整数，不依赖于设备；而所有文件和设备都采用相同的方式进行路径寻址
错误处理：错误应尽可能地在接近硬件的层面得到处理。比如控制器发现一个读错误时，它能够自己处理，如果处理不了才交给设备驱动程序，高层软件可能不知道该错误的存在
同步和异步：大多数物理IO是异步的，cpu启动传输后便转去做其他工作，直到中断发生；如果IO操作是同步的，则比较容易实现，比如用户程序在系统调用read之后，直接挂起，直到缓冲区中的数据准备好
缓冲：数据离开一个设备之后通常并不能直接存放到其最终的目的地，此外，有些设备具有严格的实时约束（如数字音频设备），所以数据必须预先放置到输出缓冲区中
共享和独占：磁盘可以由多个用户同时使用，但磁带机就不行。独占设备的引入也带来许多问题，如死锁。操作系统必须能够处理共享设备和独占设备以避免问题发生

核心子系统

假脱机技术（SPOOLing）

是一种用软件的方式模拟脱机工作方式的技术

脱机（输入/输出）：脱离主机的控制而进行的输入/输出操作的一种方法

批处理系统中引入脱机技术是为了缓解CPU与慢速IO设备的速度矛盾问题，以空间换取时间

组成：

预输入程序、井管理程序和缓输出程序

输入进程：模拟脱机输入时的外围控制机
输出进程：模拟脱机输出时的外围控制机
输入缓冲区：用于暂存从输入设备输入的数据，之后再转存到输入井中
输出缓冲区：用于暂存从输出井送来的数据，之后再传送到输出设备上
输入井：模拟脱机输入时的磁盘，用于收容I/O设备输入的数据
输出井：模拟脱机输出时的磁盘，用于收容用户程序的输出数据

输入/输出井中的数据一般以文件的形式组织管理，我们把这些文件成为井文件。一个文件仅存放某一个进程的输入或者输出数据，所有进程的输入或者输出文件链接成为一个输入（或输出）队列
井管理程序：用于控制作业与磁盘之间信息的交换。当作业执行过程中向某台设备发出启动输入或输出操作请求时，由操作系统调用井管理程序，由其控制从输入井读取信息或将信息输出至输出井

缓冲区管理

缓冲区是一个存储区域，可由专门的硬件寄存器组成，也可用内存作为缓冲区

在系统内存中设置磁盘缓冲区的主要目的：减少磁盘IO次数

双缓冲

为了加快输入和输出速度，提高设备利用率，引入了双缓冲区机制（缓冲区对换）。若采用双缓冲的策略，系统会在主存中为其分配两个缓冲区（一般一个缓冲区大小就是一块）

不存在等待磁盘块从缓冲区读入用户区的问题

采用双缓冲策略，处理一个数据块的平均耗时为Max(T, C+M)

输入输出设备（磁盘）

处理流程：用户程序->系统调用处理程序->设备驱动程序->中断处理程序

设备驱动程序：计算数据所在磁盘的柱面号、磁头号、扇区号

性能参数

寻道时间、旋转延迟、传输时间、时序比较

调度算法

先来先服务FCFS

按请求的接收顺序完成请求

最短寻道优先SSF

下一次总是处理与磁头距离最近的请求以使寻道时间最小

电梯算法SCAN

保持按一个方向移动，直到在那个方向上没有请求为止，后改变方向

循环扫描算法CSCAN

CSCAN把扫描限定在一个方向上，当访问到某个方向的最后一个磁道后，磁头臂返回到相反方向末端的磁道，并再次开始扫描

文件管理

文件和文件系统

概念

文件系统是OS的一部分，提供了一种管理机制，以便OS对自身及所有用户的数据与程序进行在线存储和访问

文件系统由两部分组成：文件集合和目录

文件是指具有文件名的若干相关元素的集合

数据的组成可以分为三级：

数据项：数据名，数据类型
记录：一组相关数据项的集合，用于描述一个对象在某方面的属性
文件：分为有结构文件（由若干相关记录组成）和无结构文件（一个字节流），主要属性有文件类型、文件长度、文件的物理位置、文件的建立时间

文件结构

逻辑结构

按文件是否有结构来分：

有结构文件
无结构文件

按文件的组织方式来分：

顺序文件：由一系列记录按某种顺序排列所形成的文件，其中的记录可以是定长记录或可变长记录
索引文件：为可变长记录文件建立一张索引表，为每个记录设置一个索引表项
索引顺序文件

直接文件：可根据给定关键字直接获取指定记录的物理地址。即关键字决定了记录的物理地址。

哈希文件：哈希文件也称为散列文件，是利用哈希存储方式组织的文件，亦称为直接存取文件。它类似于哈希表，即根据文件中关键字的特点，设计一个哈希函数和处理冲突的方法，将记录哈希到存储设备上。

物理结构

连续组织方式
链接组织方式
索引组织方式

文件类型

目录：是管理文件系统结构的系统文件
普通文件：是包含有用户信息的文件，可分为文本文件和二进制文件。前者是没有经过处理的数据（ASCII）；二进制文件则是经过编码的文件，普通的编辑器打不开
特殊文件：如UNIX中的字符特殊文件和块特殊文件。前者与输入输出有关；后者与磁盘设备有关

文件访问

顺序访问：就是从开头开始访问，按先来后到的顺序读取数据。不能在中间随便跳转，但可以进行快进或快退（早期使用）
随机访问：可按照任意顺序读取数据记录。先seek()，到达指定位置后再开始读写，后又可以再选择新的位置。现代操作系统都提供随机访问

目录系统

文件控制块

文件控制块FCB是实现文件目录的关键数据结构，实现了文件名和文件之间的映射

目录文件中的一条记录就是一个文件控制块（FCB）

最重要的是文件名、文件存放的物理地址。它们能使用户可以实现“按名存取”

FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。为了创建一个新文件，系统将分配一个FCB并存放在文件目录中，成为目录项

在一个文件被用户进程首次打开的过程中,系统需要做的是将文件控制块读到内存中

目录结构

单级目录

早期操作系统并不支持多级目录，整个系统只建立一张目录表，每个文件占一个目录项

单级目录实现了“按名存取” ，但不允许文件重名。在创建一个文件时，需要先检查目录表中有没有重名文件，确定不存在后才允许建立文件，并将新文件对应的目录项插入目录表中

两级目录

将文件目录分成主文件目录（Master FileDirectory, MFD）和用户文件目录（User FileDirectory, UFD）两级

用户要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用 "/" 隔开。可以很方便地对文件进行分类，能有效地进行文件的管理和保护

有向无环图目录

路径

绝对路径

相对路径

链接

链接的建立使用操作系统的link()系统调用，该调用给出一个目录名和一个文件名，在操作后，从该目录到该文件将存在一个直系下属关系，我们从该目录可以直接访问该文件

目录操作

文件系统的实现

文件系统的布局

文件系统存放在磁盘上，多数磁盘被分为一个或多个分区，每个分区中有一个独立的文件系统

磁盘的0号扇区称为主引导记录（MBR），用来引导计算机。在MBR的结尾是分区表，给出每个分区的起始和结束地址。表中的一个分区（不一定是第一个分区）被标记为活动分区

inode区记录文件的元信息

文件的实现

连续空间存放方式

非连续空间存放方式

链表方式

隐式链接：在每个数据块里面留出一个指针的空间，用来存放下一个数据块所在的地址
显式链接（FAT）：Windows在内存中设计一个文件分配表（File Allocation Table，FAT）专门存放文件数据块的指针

文件分配表中的每个记录为下一个数据块所存放的物理磁盘块编号。虽然指针的使用跟链表差不多，但是其存在内存中，所以效率大大提高

索引方式

索引结构inode（linux下）

inode通常包含：文件类型、文件大小（单位字节）、时间戳、链接数、文件权限、用户ID和组ID、数据块位置、其它系统相关属性

共享文件

硬链接

将文件的地址映射直接加到链接目录下

特性：

文件有相同的inode及数据块
只能对已存在的文件进行创建
不能交叉文件系统进行硬链接的创建
不能对目录进行创建，只可对文件创建
删除一个硬链接文件并不影响其他有相同 inode 号的文件（以文件副本的形式存在，但不占用实际空间）

问题：文件的创建者没有权利断开已链接用户的链接

硬链接本质上是同一个文件的多个名字，它们共享相同的inode和数据块，只是文件名不同

建立硬链接时,引用计数值加1

软链接（符号链接）

让系统建立一个类型为LINK的新文件，并把该文件放在其他共享文件使用者的目录下

软链接则是一个特殊的文件，其中包含了指向另一个文件的路径名，可以理解为快捷方式或符号链接

建立软链接时,引用计数值是直接复制的

文件挂载

挂载是一种将一个文件系统并入到另一个文件系统的方法

比如光盘、U盘等都有自己的文件系统，插入到计算机后，将其文件系统并入到计算机的文件系统，从而可以对其进行访问

文件存储空间管理

在给文件分配空间时，是以磁盘的盘块为基本单位分配的，必须记录磁盘可用于分配的盘块(即空闲盘块)，以及提供磁盘分配和回收的手段

实质上是对外存空闲区的组织和管理

位示图法

位示图的位表示的是比特位(bit)，也就是一位二进制，在记录空闲空间的时候，主要需要完成的工作是将空闲的空间列出来，方便去调用，在某一个空闲空间被使用的时候，需要分配出去，如果用完之后，空间还可以被回收，在这里主要区别的就是这个块有没有被用，占用和空闲是两种不同的状态，来那种状态用一位二进制来表示就足够了。

在记录过程当中，可以用一位二进制的当中0表示这个磁盘块是空闲的，1表示磁盘块已经被占用，如果说对一个空闲磁盘块要分配出去，就把它当前位置上的0置为1就可以了，要回收的话就是把1改为0。

例题：某字长位32位的计算机的文件管理系统采用位示图（bitmap）记录磁盘的使用情况。若磁盘的容量为300GB，物理块的大小为1MB，那么位示图的大小为（9600）字。

位示图表示的是磁盘情况，一个磁盘对应一个比特位来记录

磁盘总容量为300GB，也就是磁盘块大小为300GB

每一个物理块大小是1MB，则可以求出磁盘块的数量=300GB/1MB，**1GB和1MB之间转换是2¹⁰**，则磁盘块的数量=300GB/1MB=300×2¹⁰
也就是需要300×2¹⁰个比特位来表示位示图

问一共需要多少个字？

题目中告知字长位32位的计算机，所以需要的字=300×2¹⁰/32=300×2¹⁰/2⁵=300×32=9600

文件系统用位图法表示磁盘空间的分配情况,位图存于磁盘的32~127号块中,每个盘块占1024个字节,盘块和块内字节从0开始编号。假设要释放的盘块号为409612,则位图中要修改的位所在的盘块号和块内字节序号分别是(82 、1 )

盘块号b=409612，字长n=1024
盘块号对应的字号(行)i=b/n(下取整)，位号(列)j=b%n
修改位所在的字号i=409612/(1024*8)=50，由于32块为起始块，所以修改位所在的盘块号=32+50=82，位号=409612%1024=12，则块内字节序号=12%8=1

目录

LOADING

计算机操作系统

前言

引论

操作系统定义

主要功能

提供接口

资源管理

资源抽象

操作系统的发展过程

集成电路和多道批处理

CPU利用率

分时系统

基本特征

并发

共享

虚拟

异步

运行机制与体系结构

状态转换

中断和异常

系统调用

操作系统结构

进程与线程

概述

定义&特征

进程与程序的区别

进程的组成

PCB

程序段

数据段

层次结构

进程状态

基本状态与转换

进程控制

创建

执行

切换

终止

阻塞与唤醒

进程通信（IPC）

概念

直接制约关系——相互合作

间接制约关系——共享资源

临界资源

临界区

进程同步

进程互斥

进程通信方法

共享存储

管道通信

消息传递

客户机－服务器

进程间的关系

术语

原子操作

死锁

饥饿

互斥访问的实现方法

软件解法

Dekker解法——三标志法

Peterson解法

硬件解法

进程同步

信号量机制

应用

管程机制

功能

经典IPC问题

生产者－消费者问题

多生产者－多消费者问题

读者－写者问题

解法一：读者优先

解法二：写者优先

哲学家进餐问题

线程

与进程的区别

功能

分类