操作系统理论部分笔记

计算机系统概述

操作系统的四个特征

并发和共享是两个最基本的特征，两者互为存在条件
没有并发和共享，就谈不上虚拟和异步。

并发

并发：宏观上同时发生，微观上交替发生
并行：确实在同时发生

共享

共享即资源共享，指系统中的资源可供内存中多个并发执行的进程共同使用。
两种资源共享方式：互斥共享方式（一个时间段内只允许一个进程访问，如qq和微信视频摄像头），同步共享方式（宏观上一个时间段内多个进程“同时”访问）如qq和微信发文件，微观上实际上仍是交替访问硬盘）。

虚拟

把一个物理试题变为若干个用户能感受到的逻辑对应物。分为空分复用技术（如虚拟存储器技术）和时分复用技术（如虚拟处理器）。
eg1. 4GB内存，虚拟化之后远大于4GB
eg2. 虚拟处理器技术，实际上只有一个单核CPU，用户看来似乎有6个CPU同时服务

异步

由于资源有限，进程的执行又不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

操作系统的发展和分类

批处理操作系统

用户提交作业，系统按顺序执行，用户无法干预和交互。

分时操作系统

以时间片为单位，轮流为每个用户进程服务，各个用户通过终端与操作系统交互。

实时操作系统

能够优先响应一些紧急任务，不用等待时间片排队。

操作系统的运行机制

CPU有内核态和用户态，CPU中有一个寄存器存二进制位来区分两种状态。处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令。处于用户态时，说明正在运行的是应用程序，此时只能执行非特权指令。
内核态切换到用户态：执行一条特权指令——修改标志位为用户态，这个动作意味着操作系统将主动让出CPU使用权
用户态切换到内核态：由“中断”引发，硬件自动完成切换过程，触发中断信号意味着操作系统将强行夺回CPU使用权。且中断是唯一能让操作系统内核夺回CPU使用权的途径。

中断和异常

（广义的）中断是让操作系统内核取回CPU使用权的唯一途径。
异常（exception）的类型：

• 同步：与当前执行的指令有关，中断信号来源于CPU内部 e.g. 用户态执行特权指令、执行指令非法、应用程序想请求操作系统内核的服务，则执行“陷入指令”发一个内部中断信号。
  分为

  • 陷阱（trap）：陷入指令（用户态下执行的，非特权指令）引发，是应用程序故意引发的
  • 故障（fault）：错误条件引起，可能被内核程序修复，如缺页故障
  • 终止（abort）：致命错误引起，内核程序无法修复该错误，直接终止该应用程序

• 异步（中断interrupt）：与当前执行的指令无关，中断信号来源于CPU外部 e.g. 时钟部件每隔一个时间片给CPU发送一个时钟中断信号、由IO设备发来的中断信号

可以理解为异步随时可能发生，而同步需要触发。

中断机制的原理：当CPU检测到中断信号后，根据中断信号的类型查表，找到对应程序指针，执行对应的中断处理程序（要在内核态中才能完成）。

系统调用

系统调用是OS给应用程序使用的接口，应用程序可以通过系统调用来请求获得操作系统内核的服务。与共享资源有关的操作（存储分配，IO，文件管理等），都必须通过系统调用的方式向OS内核提供服务请求，由内核代为完成，保证系统的稳定性和安全性。
与库函数的区别：库函数隐藏了系统调用的一些细节，使程序员编程更加方便。
系统调用的过程：传递系统调用参数，执行陷入指令（用户态）引发一个内中断使得CPU进入核心态，执行相应的内请求核程序处理系统调用（核心态），返回应用程序

操作系统的功能

处理机管理

核心任务：如何分配CPU时间

• 进程管理
• 线程管理

主要功能

• 公平分配
• 保证非阻塞
• 按优先级分配

存储器（内存）管理

核心任务：管理缓存、主存、磁盘等所形成的多级存储架构，为多道程序的并发提供良好的环境。
主要功能

• 内存分配和存储无关性：方便用户
• 内存保护：互不干扰
• 内存扩充：虚拟存储器

设备管理

核心任务：管理IO设备，屏蔽差异性，提供并发访问
主要功能

• 设备无关性：逻辑设备->物理设备
• 设备分配：独享、共享和虚拟
• 设备的传输控制：中断、通道

文件系统

核心任务：将磁盘变成一个很容易使用的存储媒介提供给用户使用。
主要功能

• 文件存储空间的管理
• 目录管理
• 文件读、写管理
• 文件保护
• 向用户提供接口

作业控制

作业调度，作业控制（批量性作业、终端型作业）

操作系统的体系结构

大内核

内核中包含了所有的操作系统功能，如进程管理、存储管理、设备管理等。这样的内核称为大内核。大内核的优点是功能模块之间的通信效率高，缺点是内核庞大，不易维护。

微内核

对系统资源管理的功能（进程管理，存储器管理，设备管理等+时钟管理，中断处理，原语）也放在用户态运行。微内核的优点是内核小巧，易于维护。显而易见，需要频繁地切换核心态和用户态，性能较低。

非内核功能

非内核功能（如GUI）：Ubuntu，CentOS的开发团队，主要工作是实现非内核功能，运行在用户态
内核+非内核功能=OS

操作系统的引导（boot）

安装了操作系统的磁盘中，除了CDEF等盘中，还有一个区域，主引导记录（MBR），包含磁盘引导程序和分区表。如果把操作系统安装在C盘上，称C盘为活动分区。C盘中存在一个引导记录PBR，负责找到“启动管理器”。
计算机的组成包含RAM,ROM。RAM断电丢失，ROM断电不丢失，包含ROM引导程序，即自举程序。
操作系统引导过程：

1. 开机通电时，执行ROM中的引导程序。（先硬件自检，再开机）
2. 将磁盘的第一块——主引导记录读入内存，执行磁盘引导程序，扫描分区表。
3. 从活动分区（又称主分区，即安装了操作系统的分区）读取分区引导记录PBR，执行其中的程序。
4. 从根目录下找到完整的操作系统初始化程序（即启动管理器）并执行，完成“开机”的一系列动作。

虚拟机

使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机器，每个虚拟机器都可以独立运行一个操作系统。

进程管理

程序是静态的实体，进程（Process）是执行中的程序，是动态的。同一个程序多次执行会对应多个进程。

进程的组成

分为PCB，程序段（程序代码），数据段。

每一个进程有一个PID（Process ID）。操作系统记录PID，UID，还要记录给进程分配了哪些资源以及运行情况。这些信息都被保存在一个数据结构PCB（Process Control Block）中，即进程控制块，供操作系统使用。

同时挂三个QQ号会对应三个QQ进程，它们的PCB、数据段各不相同，但程序段内容相同。

进程的特征

动态性：最基本的特征。动态地产生、变化、消亡。
并发
独立
异步：各系统按各自独立的、不可预知的速度向前推进，操作系统要提供“进程同步机制”来解决异步问题。

进程的调度：创建、挂起、激活
进程间的通信：同步、互斥、死锁

进程的状态

三种基本状态：就绪、运行、阻塞

就绪态：已经具备运行条件，由于没有空闲CPU暂时不能运行
运行态：上CPU运行
阻塞态：进程运行中，可能会等待某个事件发生（如等待某种系统资源分配，或者等待其他进程相应），此时OS会让这个进程下CPU并进入阻塞态，当CPU空闲时，又会选择另一个就绪态进程上CPU运行。

另外两种状态

创建态：一个进程被创建后，进入创建态，操作系统为其分配资源，初始化PCB等，进程进入就绪态
终止态：一个进程可以执行exit系统调用，请求操作系统终止该进程，进程进入终止态

进程状态的转换

就绪态到运行态：进程被调度
运行态到就绪态：时间片到，或CPU被其他高优先级进程抢占
运行态到阻塞态：等待系统资源分配，或等待某时间发生，为进程运行时自身做出的主动请求，因此必须从运行态开始转换。
阻塞态到就绪态：资源分配到位或等待时间发生，是被动行为
运行态到终止态：进程运行结束，或遇到不可修复错误

注：不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态（因为进入阻塞态是进程主动请求的，需要在运行时才能发出这种请求）

进程的组织方式

链接方式和索引方式

链接方式

分为多个队列
执行指针：指向处于运行态的进程
就绪队列指针：指向当前处于就绪态的进程
阻塞队列指针：可能存在多个阻塞队列，如等待打印机的阻塞队列，等待磁盘的阻塞队列

索引方式

建立索引表，操作系统持有指向各个索引表的指针

进程控制——实现进程状态转换

创建新进程，撤销已有进程，进程状态转换（需要原子性，一气呵成）
可以用“关中断指令”和“开中断指令”这两个特权指令实现原子性，CPU执行了关中断指令后就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查。这样，关中断、开中断之间的指令就是不可被中断的，实现了原子性。

大致过程：更新PCB信息，将PCB插入合适的队列，分配/回收资源。

相关原语：进程创建，终止，阻塞，唤醒，切换（阻塞和唤醒要成对出现）

进程通信

IPC（Inter-Process Communication）进程间通信指的是两个进程间产生数据交互。

共享存储

通过增加页表项/段表项即可将同一片共享内存区映射到各个进程的地址空间中。为避免出错，各个进程对共享空间的访问应该是互斥的，各个进程可使用操作系统内核提供的同步互斥工具（如P、V操作）

基于数据结构的共享：比如共享空间只能放一个长度为10的数组，是一种低级通信方式
基于存储区的共享：数据形式和存放位置都由通信进程控制，而不是OS。速度快，是一种高级通信方式。

消息传递

进程通过操作系统提供的“发送、接受消息”两个原语进行数据交换。
分为直接通信方式（指明ID）、间接通信方式（信箱）。

管道通信

进程P向管道写数据，进程Q从管道读数据，数据流向和水管一样是单向的。管道是一个特殊的共享文件，又名pipe文件，其实就是在内存中开辟一个大小固定的内存缓冲区。数据读写FIFO。
各个进程要互斥地访问管道（由OS实现）
管道写满时，写进程将阻塞，直到读进程取走数据，即可唤醒写进程。

线程

有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此引入线程，实现并发性。
例如：QQ可以视频、文字聊天、发送文件。
进程是资源分配的基本单位，线程是调度的基本单位。同一进程间的线程切换，不需要切换进程环境，系统开销小。这些线程共享进程的资源。

线程的实现方式

用户级线程（较早期）

用户视角能看到的线程，由线程库实现。很多编程语言提供了强大的线程库。
优点：用户空间完成，不需要切换核心态
缺点：一个用户级线程阻塞，整个进程阻塞，并发度不高。且无法利用多核CPU

内核级线程（一对一）

内核级线程管理工作由OS内核完成，在核心态下完成。一个内核级线程才是处理机的调度单位。
优点：一个线程阻塞，不会影响其他线程。可以利用多核CPU
缺点：线程切换由OS完成，需要切换到内核态，开销大

多线程模型

一对一：一个用户级线程映射到一个内核级线程
多对一：多个用户级线程映射到一个内核级线程，且一个进程只被分配一个内核级线程。（退化为用户级线程）
多对多（用户级线程比内核级线程多）

线程的状态与转换

和进程一样，只是PCB变成了TCB（线程控制块）

处理机调度

调度类型	要做什么	调度发生在…	发生频率	对进程状态的影响
高级调度（作业调度）	按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程	外存→内存	最低	无→创建态→就绪态
中级调度（内存调度）	按照某种规则，从挂起队列中选择合适的进程将其数据调回内存	外存→内存	中等	挂起态→就绪态（阻塞挂起→阻塞态）
低级调度（进程调度）	按照某种规则，从就绪队列中选择一个进程为其分配处理机	内存→CPU	最高	就绪态→运行态

注：挂起态为资源不够时被调到外存了。阻塞态的进程映像还在内存中
低级调度（进程调度）为最基本的，最频繁的调度

进程调度（低级调度）的时机

需要进行调度的时机：当前运行的进程主动or被动放弃CPU
不能进行调度的的情况：处理中断的过程中，在原子操作中，进程在操作系统内核程序临界区。
内核程序临界区访问的临界资源

进程调度的方式

非抢占式调度（非抢占方式）：只允许进程主动放弃CPU，适用于批处理系统
抢占式调度（抢占方式）：允许操作系统内核强行夺回CPU使用权，如果有更紧急的进程需要运行，则立刻暂停当前执行的进程，将CPU分配给更紧急的进程。每K个时钟中断会触发调度程序。适合现代的分时操作系统、实时操作系统。

调度算法

调度算法的评价指标

CPU利用率：忙碌时间/总时间
系统吞吐量：总共完成了几道作业/总共花了多少时间
周转时间：从作业被提交给系统开始，到作业完成为止的时间间隔
带权周转时间：作业周转时间/作业实际运行时间 必定大于等于1
以上两个时间都是越小越好
等待时间：进程/作业处于等待处理机的状态的时间
响应时间：从提交请求到首次产生响应所用的时间

批处理系统的调度算法

先来先服务FCFS

按照作业到达的先后顺序服务。
非抢占式
对短作业不友好

短作业优先SJF

最短的进程优先服务
对长作业不友好

最短剩余时间优先

高响应比优先

调度时先计算各个作业的响应比，选最高
响应比=（等待时间+要求服务时间）/要求服务时间 大于等于1

交互式系统的调度算法

时间片轮转

按照各个进程到达就绪队列的顺序，轮流让各个进程跑一个时间片。若进程一个时间片未执行完，则进程重新放到就绪队列队尾重新排队

优先级调度算法

非抢占式：每次调度时选择当前已到达且有限度最高的进程。

多级反馈队列调度算法

再设置多个队列，赋予不同优先级

优先级反转

高优先级进程被低优先级进程延迟或阻塞
解决方法：优先级置顶（低优先级的进程进入临界区后，就不允许别人抢占）、优先级继承（原来低优先级进程直接继承要上的进程的优先级）

实时系统的调度算法（待续）

多处理机调度

进程同步与进程互斥

进程同步：协调工作次序而产生的制约关系。比如读进程和写进程…
进程互斥：我们把一个时间段内只允许一个进程是用的资源称为临界资源，比如内存，打印机，摄像头等。而对临界资源的访问必须互斥地进行。
临界资源的互斥访问：进入区上锁，临界区访问临界资源，退出去解锁，剩余区其余代码部分。
每个进程中访问临界资源的那段代码称为临界区。

do{
  entry section; //进入区
  critical section; //临界区  为访问临界资源的代码
  exit section; //退出区  进入区和退出区是为了保证互斥
  remainder section; //剩余区
}

进程互斥设计上的原则

• 空闲让进：如果临界区空闲，且有进程要访问临界区，则应立即让进程访问
• 忙则等待：如果临界区正被进程访问，则其他进程应等待
• 有限等待：对进程访问临界区的等待时间应有限制
• 让权等待：如果一个进程不能进入临界区，则应立即释放CPU，让其他进程进入

进程互斥的软件实现方法（重点）

单标志法

设一个turn，表示当前允许进入临界区的进程号。进程turn不匹配则无法进入。进入临界区的权限只能被另一个进程赋予。

int turn = 0; //turn 表示当前允许进入临界区的进程号
//P0
while(1){
  while(turn!=0);
  critical section;
  turn=1;
  remainder section;
}
//P1
while(1){
  while(turn!=1);
  critical section;
  turn=0;
  remainder section;
}

由此可见只能P0P1P0..这样轮流访问，如果此时允许进入临界区的是P0，而P0一直不访问临界区，那么虽然此时临界区是空闲的，但P1也无法进入。
因此违背空闲让进原则。

双标志先检查法

思想：布尔数组flag[]，标志各个进程是否想要进入临界区。每个进程都有一个flag，表示自己是否想要进入临界区。进程进入临界区前，先检查其他进程是否想要进入临界区，如果没有，则进入临界区，否则等待。

bool flag[2] = {false,false};
//P0
while(1){
  flag[0]=true;
  while(flag[1]);
  critical section;
  flag[0]=false;
  remainder section;
}
//P1
while(1){
  flag[1]=true;
  while(flag[0]);
  critical section;
  flag[1]=false;
  remainder section;
}

主要问题是喂饭忙则等待原则。原因在于进入区的检查和上锁两个处理不是一气呵成的，检查后上所前可能发生进程切换。

双标志后检查法

先上锁后检查，避免上述问题

bool flag[2] = {false,false};
//P0
while(1){
  flag[0]=true;
  while(flag[1]){
    flag[0]=false;
    while(flag[1]);
    flag[0]=true;
  }
  critical section;
  flag[0]=false;
  remainder section;
}
//P1
while(1){
  flag[1]=true;
  while(flag[0]){
    flag[1]=false;
    while(flag[0]);
    flag[1]=true;
  }
  critical section;
  flag[1]=false;
  remainder section;
}

Peterson算法

表达意愿和谦让
解决了进程互斥问题。遵循了空闲让进、忙则等待、优先等待原则。但未满足让权等待原则。

bool flag[2] = {false,false};
int turn = 0;
//P0
while(1){
  flag[0]=true;
  turn=1;
  while(flag[1]&&turn==1);
  critical section;
  flag[0]=false;
  remainder section;
}
//P1
while(1){
  flag[1]=true;
  turn=0;
  while(flag[0]&&turn==0);
  critical section;
  flag[1]=false;
  remainder section;
}

进程互斥的硬件实现方法

中断屏蔽方法

利用开/关中断指令实现原子操作，即不能发生进程切换。缺点：开关中断指令是特权指令，只能在核心态下执行，只适用于OS内核进程，不适用于用户进程；不适用于多处理机系统。

硬件指令方法TestAndSetLock

XCHG指令

几个算法的共性问题

1. 忙等待：浪费CPU时间
2. 优先级反转：低优先级进程占用了临界资源，导致高优先级进程无法访问临界资源，一直忙等待。

注：需要连续循环忙等的互斥锁，都可称为自旋锁。

基于信号量的同步方法

同步中，进程经常需要等待某个条件的发生，如果使用忙等待的解决方案，势必浪费大量CPU时间。解决方法：将忙等变为阻塞，可使用两条进程间的通
信原语：Sleep和Wakeup。Sleep原语将引起调用进程的阻塞，直到另外一个进程用Wakeup原语将其唤醒。很明显，wakeup原语的调用需要一个参数——被唤醒的进程ID。
信号量：(s,q)
s是一个具有非负初始值的整型变量，q是一个初始状态为空，指向需要该资源的队列。
当发出P操作时：

• s为正，则值等于可立即执行的进程数量；s小于等于0，则发出P操作后的进程被阻塞，s的绝对值为被阻塞的进程数。只能进行初始化、P、V操作！
• 有进程被阻塞时则进入q队列。

可以对其进行P(wait)、V(signal)操作，实现进程间的同步和互斥。
value的初始值表示系统中某种资源的数目。
P意味着进程请求一个该类资源，value–。如果value<0，则进程被阻塞并进入等待队列中。遵循了让权等待原则。
V意味着进程释放一个该类资源，value++。如果+1后仍是value<=0，表示依然有进程在等待该类资源。则调用wakeup原语唤醒一个等待队列中的进程。（被唤醒进程从阻塞态变为就绪态）
总结：P申请一个资源，如果资源不够就阻塞等待。V释放一个资源，如果有进程在等待该资源，就唤醒一个进程。PV操作必须成对出现。

用信号量实现进程同步

1. 分析哪里需要必须保证一前一后的两个操作，找出同步（只有..才能..）关系。再找出互斥关系。
2. 设置同步信号量初始值为0，或者看对应资源初始值为多少。互斥信号量初始值一般为1。
3. 在前一个操作后执行V操作，后一个操作前执行P操作（前V后P）

理解：S代表资源，一开始没有这种资源，P2需要使用这种资源，而只能由P1产生这种资源，这就实现了先后。
类似地可以实现前驱关系：画出图，把每一对关系都看成一个同步问题，各设置一个同步信号量，初始值为0。

经典同步互斥问题

生产者消费者问题

题目：生产者生产产品，消费者消费产品。生产者和消费者之间共享一个有限的缓冲区，生产者不能向满的缓冲区中放入产品，消费者不能从空的缓冲区中取出产品。
分析：

1. 缓冲区是临界资源，各进程必须互斥地访问。
2. 发现隐含的两对同步关系：消费者需要等待生产者生产，生产者需要等待消费者消费。这是两个不同的一前一后问题，因此需要设置两个同步信号量。

注：

1. 在同一个进程内，互斥是进行一对PV操作。而实现两进程的同步关系，是在一个进程中执行P，另一个进程中执行V。
2. 实现互斥的P操作一定要在实现同步的P操作之后，否则会导致死锁。V操作不会导致进程阻塞，因此两个V操作顺序可以交换。

semaphore mutex = 1; //互斥信号量，实现对缓冲区的互斥访问

读者写者问题

题目：

1. 多个读者可以同时读取数据
2. 只允许一个写者写信息。
3. 当有一个写者在写数据时，不允许其他读者或写者访问数据。
4. 写者执行写操作之前，应让已有的读者、写者执行完毕退出。

哲学家就餐问题

管程（Monitor）

信号量变成困难、易出错。管程是一种特殊的软件模块（特征有点像面向对象中的类）。
存在共享数据、操作这些数据的过程（类似于方法），进程只能通过调用管程内的过程才能访问共享数据。（类似gettersetter）每次仅允许一个进程进入管程执行操作。

管程要解决的问题

1. 互斥：管程中的每个过程都是互斥的，即同一时间只能有一个进程在管程中执行。
2. 同步：通过设置条件变量，并实施wait、signal操作，使得一个进程或线程当条件不满足（满足）时在条件变量上等待（唤醒）。
3. 条件变量：不同的条件变量，对应不同原因的进程阻塞等待队列，初始值为空。可以使用wait和signal原语操作。

条件变量与信号量的区别

• 条件变量的值不可增减，PV信号量可以。
  wait一定会阻塞当前进程。如果没有等待的进程，signal将丢失。
• 访问条件变量必须拥有管程的锁。

死锁

死锁产生的必要条件

必须同时满足以下四个条件：

1. 互斥条件：一个资源每次只能被一个进程使用，即互斥资源争抢彩会导致
2. 不剥夺条件：进程所获得的资源在未使用完之前不能被其他进程强行剥夺，只能由进程自己释放
3. 请求和保持条件：一个进程已经保持了至少一个资源，但又因请求资源而阻塞时，对已获得的资源保持不放
4. 循环等待条件：存在一种进程的循环等待链。

注：如果同类资源数大于1，则即使有循环等待也未必发生死锁。但如果系统中只有一个资源，则循环等待就是死锁的充要条件了。

死锁的处理——静态策略：预防死锁

破坏死锁产生的条件。破坏其中一个条件，死锁就不会发生。

死锁的处理——动态策略：避免死锁

银行家问题中，存在安全序列：如果按照这个序列分配资源，则每个进程都能顺利完成。
进入不安全状态，可能会发生死锁。死锁一定处于不安全状态。
银行家算法核心思想：分配资源之前，先判断分配后是否会进入不安全状态，以此决定是否分配。
流程：列表花出各个进程最多还需要的资源。检查手里的剩余资源是否满足，如果满足则可以加入安全序列，并更新剩余可用资源（完成的进程的资源全部归还）

死锁的处理——允许死锁发生，但检测和解除死锁

死锁的检测：资源分配图
两种节点：资源、进程节点
两种边：请求边、分配边
开始查看剩余的（空闲资源，不包括已经用箭头分出去的）可用资源数是否足够满足进程的需求。如果满足就还能归还资源。最后逐步消去边。若必须剩下边则说明发生了死锁。仍然连着边的进程就是死锁进程。

死锁的解除：剥夺资源、撤销进程、进程回退

内存管理

内存的基础知识

从写程序到程序运行：编辑，编译（翻译为机器语言），链接（形成完整的逻辑地址），装入（将装入模块装入内存，之后形成物理地址）
三种链接方式：
三种装入方式：绝对装入（编译时产生绝对地址）、可重定位装入（装入时将逻辑地址转换为物理地址）、动态运行时装入（运行时转换，需设置重定位寄存器）

内存管理的概念

1. 负责内存空间的分配与回收
2. 虚拟技术，内存扩展
3. 实现逻辑地址到物理地址的转换（地址重定位）：三种装入方式
4. 内存保护，保证进程互不干扰：
   • 方法一：CPU设置一对上下限寄存器，CPU检查是否越界
   • 方法二：采用基址寄存器和界地址寄存器进行越界检查。分别存放起始物理地址和最大逻辑地址

内存空间的分配与回收

连续分配管理方式

为用户进程分配的是一个连续的内存空间。
内部碎片：分配给某进程的内存区域中，有些部分没用上
外部碎片：内存中的某些空闲分区由于太小，利用不了

单一连续分配

内存氛围系统区、用户区，内存中只能有一道用户程序，用户程序独占整个用户区空间。
优点：无外碎片
缺点：有内碎片（分配，但没用上），存储器利用率低

固定分区分配

建立一个分区说明表

分区号 |大小| 起始地址 |状态

优点：无外碎片
缺点：有内碎片

动态分区分配

根据进程大小动态建立分区。

1. 用什么结构记录内存使用情况？空闲分区表、空闲分区链
2. 有多个空闲分区能够满足需求，应选择哪个分区进行分配？
   1. 首次适应算法：每次都从低地址开始查找，找到第一个能满足大小的空闲分区
   2. 最佳适应算法：优先使用更小的空闲区
   3. 最坏适应算法：优先使用最大的连续空闲区
   4. 临近适应算法：首次适应算法每次都从链表头开始查找，开销较大。改为每次都从上次查找结束得到位置开始检索。
3. 如何进行分区的分配与回收操作？总之，回收后相邻的空闲分区要合并

无内部碎片，有外部碎片，外部碎片可以用紧凑技术解决

非连续分配管理方式

基本分页存储管理（重难点）

将内存空间分为一个个大小相等的分区，每个分区就是一个页框（内存块/物理页面）
将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个页。
页框号和页号都从0开始。
OS为每一个进程建立一张页表，通常存储在PCB中。
每个页表项由页号（不占字节）和内存块号（占字节）组成，这就完成了进程页面和实际存放的内存块的映射关系。

逻辑地址空间图：

重要考点：计算机中内存块数量->页表项中块号至少占多少字节？
E.g. 物理内存大小4GB，页面大小4KB，则每个页表项至少应该为多少字节？
共2^20个内存块，块号范围0~2^20-1，至少要用20bit表示->至少要用3字节表示块号（3*8=24bit）
注意页表记录的只是内存块号，而不是内存块的起始地址

如何实现地址的转换？如果要访问逻辑地址A，则：

1. 确定逻辑地址A对应的页号P和页内偏移量
2. 检查页号合法性（与页表长度对比）
3. 找到P号页面在内存中的起始地址，根据页号找到页表项（需要访问内存查页表）
4. 根据页表项中记录的内存块号和页内偏移量得到物理地址
5. 访问物理地址对应的内存单元

逻辑地址的结构：
31…12 11…0
页号P 页内偏移量W
页面大小和页内偏移量位数可以互推

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。通常会在系统中设置一个页表寄存器PTR，存放页表在内存中的起始地址F和页表长度M（多少个页表项）

具有快表TLB的地址变换机构：TLB是页表项的缓存，加快地址变换的速度。TLB命中则直接找到了内存块号，，直接获取物理地址。因此若快表命中则仅需一次访存。

两级页表

单级页表存在的问题：

1. 页表需要连续存放，才能使用页号查询的方式找到页表项，因此页表很大时，需要占用很多歌连续的页框。

解决：如何解决进程在内存中必须连续存储？将进程地址空间分页，建立页表，记录页面存放位置。同样的思路，把必须连续存放的页表再分页

31..22 21…12 11…0
一级页号 二级页号 页内偏移量W

先查一级页号对应的内存块号，去对应内存块号取出相应的二级页表（显然，各级页表的大小不能超过一个页面的大小，据此计算一个页面能存放多少个页表项，进而确定总共xx位的页号要分为多少级页表），再根据二级页号查到内存块号

2. 根据局部性原理可知：很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了，因此没必要让整个页表常驻内存。

解决：可以再需要访问页面时才把页面调入内存（虚拟存储技术）。可以在页表项增加一个标志位，用于表示该页面是否已调入内存

基本分段存储管理

与分页最大的区别就是：离散分配时分配地址空间的基本单位不同
分段（类似于分页管理的分页）：按照自身逻辑关系划分为若干个段，每个段都有一个段名，每段从0开始编址。内存分配时以段为单位进行分配，每个段占据连续内存空间，但各段之间可以不相邻。分段系统的逻辑地址，也分为段号和段内偏移量组成

31…16 15…0
段号 段内地址

段表：每个段对应一个段表项，其中记录了该段在内存中的起始位置（基址）和段的长度。而段表寄存器储存着段表始址F和段表长度M，根据这个查询段表，找到对应段表项。

分段分页管理的对比

页是信息的物理单位，对用户不可见。
段是信息的逻辑单位，对用户可见。分段的用户进程地址空间是二维的，既要给出段名，也要给出段内地址。
分段比分页更容易实现信息的共享和保护。不能被修改的代码可以共享，可修改的代码（比如有很多变量，各个进程并发访问可能造成数据不一致）不能共享

分页管理 不会产生外碎片 不方便共享
分段 会产生外碎片

段页式管理方式

31…16 15…12 11…0
段号 页号 页内偏移量

页内偏移量决定了页面大小！

内存空间的扩充

覆盖技术

思想：程序分为多个段，常用的段常驻内存，然后按照自身逻辑结构，让那些不可能同时被访问的程序段共享同一个覆盖区
已退出历史舞台，对用户不透明，增加了用户编程负担。

交换技术

思想：进程在内存与磁盘间动态调度。
暂时换出外存等待的进程状态为挂起状态（suspend）、挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。

1. 把磁盘空间分为文件区和对换区，文件区追求存储空间利用率，对换区空间占得小，提高IO速度。
2. 内存吃紧时换出进程。如果缺页率明显下降，就可以暂停换出。
3. 可优先换出阻塞进程，可换出优先极低的进程…
   （注：PCB会常驻内存，不会换出外存）

覆盖与交换的区别

覆盖是在同一个进程中的，交换是在不同进程之间的

虚拟内存技术

程序不需全部装入即可运行，运行时根据需要动态调入数据，若内存不够还需要换出数据。也需要建立在离散分配的内存管理方式基础上。
区别：访问信息不在内存时，需要请求调页/段，弱内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

请求分页存储管理

请求分页存储管理的页表，比基本页表（页号-内存块号）多了状态位（是否已调入内存）、访问字段（访问过几次/上次访问时间，供换出算法参考）、修改位（调入内存后是否被修改过）、外存地址。
如果访问的页面不在内存，产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，调页完成后再将其唤醒，放回就绪队列。
如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改也表中相应的页表项。
如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，还要写回外存。

缺页中断属于内中断

页面置换算法

缺页中断未必发生页面置换。若还有可用的空闲内存块，就直接分配就好了。当内存空间不够时，由操作系统负责将内存中暂时不用的页换出

最佳置换算法：淘汰在最长时间内不会再被访问的页面
先进先出FIFO：淘汰最早进入内存的页面 Belady异常：分配的物理块数增大，缺页次数反而减少了！
最近最久未使用LRU：淘汰最近最久未使用。实现方法：每个页面对应的页表项中，用访问字段记录自上次被访问以来所经历的时间t。（在时间序列中向左找，最久未使用的块被换出）
OPT：（在时间序列中向右找，最久不会被使用的块被换出）
简单时钟置换算法CLOCK（NRU）：每个页面设置一个访问位：页面通过链接指针链接成一个循环队列，被访问时访问位置置1。当需要淘汰一个页面时，开始扫描，检查页的访问位，如果为1则置0，直到访问到一个访问位为0的页面
改进时钟置换算法：再增加一个修改位，优先淘汰没有被修改过的页面，避免IO操作。第一优先级：最近没访问，且没修改。第二优先级：最近没访问，但修改过的页面。本轮把扫描过的访问位设为0。第三优先级：最近访问过，但没修改的页面。第四优先级：最近访问过，且修改过的页面

页面分配策略

页面分配、置换策略

驻留集：请求分页存储管理中，给进程分配的物理块的集合。采用虚拟存储技术时，大小一般小于进程的总大小。
固定分配+局部置换：分配一定数量物理块，缺页只从进程在内存中的页面换出
可变分配+全局置换：分配动态数量物理块，缺页可以从任意一个未锁定的物理块

何时调入页面？预调入，缺页时才调入
从何处调入页面？外存（磁盘）分为对换区和文件区，对换区采用连续分配方式，读写速度块

抖动（颠簸）现象：刚换出又要换入，刚换入又要换出，原因是分配给进程的物理块不够
工作集：在某段时间间隔里，进程实际访问页面的集合。
驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。

文件管理

文件系统基础概念

操作系统以“块”为单位为文件分配存储空间。和内存一样，外存也被分为这样的一个个存储单元。存取都是以物理块为单位！！！！

文件系统实现方法

文件控制块

目录文件中的一条记录就是一个“文件控制块”FCB。存文件名、类型（目录or文件）

目录结构

无环图目录结构：设置共享计数器。当有多个文件指向同一个目录项时，共享计数器+1。当计数器为0时，删除目录项。

文件的逻辑结构

无结构文件

由一系列字节组成，没有固定的格式，如二进制文件，txt

有结构文件

顺序文件

串结构：记录顺序与关键字无关
顺序结构：记录顺序与关键字有关
可变长记录的顺序文件无法实现随机存取，定长记录可以。

索引文件

建立索引表，每个记录对应一个表项。

索引顺序文件

将记录分组，每组对应一个索引表项。

文件的物理结构

文件数据应该怎样存放在外存中？
很多os中，磁盘块的大小与内存块、页面的大小相同。
在内存管理中，进程的逻辑地址空间被分为页面。在文件管理中，文件的逻辑地址空间被分为文件块。文件的逻辑地址可以表示为（逻辑块号，块内地址）
！注意：主要解决两个问题：

• 假设一个文件被划分成N块，这N块在磁盘上是怎么存放的？
• 其地址（块号或簇号）是怎样记录的？
  单文件的物理结构分为连续结构、链接结构、索引结构

连续结构

每个文件在磁盘上占有一组连续的块。
用户给出要访问的逻辑块号，OS找到该文件的目录项FCB…
物理块号=起始块号+逻辑块号，由于要访问的逻辑块号已经给出，则只需找到起始块号。
一个文件的目录项中已经记录了该文件的第一个磁盘块的物理块号和所占用的块数：
目录结构：文件名、起始块号、长度
（逻辑块号，块内地址）→（物理块号，块内地址）

串联/链接结构

每个物理块的最某/第一个字作为链接字，指向下一个块的物理地址。一块中可包含一个逻辑记录或多个逻辑记录，也可以若干物理块包含一个逻辑记录。
从目录项找到文件的第一个块，读取该块，找到下一个块，直到读取完整个文件。

索引结构

系统为每个文件建立逻辑块号与物理块号的映射表，称为文件的索引表。文件由数据文件和索引表构成。这种文件称为索引文件。它们在存储区中占两个区：索引区和数据区。索引区存放索引表，数据区存放数据文件本身。
索引表的长度可能是不一样的，不能存放在FCB中，FCB中只记录索引表的地址。可存放在文件目录中/文件开头等。
目录项-inode索引表-文件（子目录项）
目录结构为：文件名->inode索引块物理块号（该索引表存放在第几号磁盘块）
inode索引表结构：逻辑块号->物理块号

访问索引文件需要两步操作：

• 读取文件索引区，由逻辑块号查得物理块号
• 访问物理块号而获得所需信息

举例：读取Linux下/tmp/hello的过程（假定根目录inode已在内存中）

• 读取根目录内容，获得tmp目录的inode所在的物理块号
• 读取tmp的inode信息，获得tmp目录项所在的物理块号
• 读取tmp目录内容，获得hello的inode所在的物理块号
• 读取hello的inode信息，获得hello的物理块号。
• 读取hello的数据

OS对非空闲磁盘块的管理

连续分配

每个文件在磁盘上占有一组连续的块。（逻辑块号，块内地址）→（物理块号，块内地址）。
连续分配支持顺序访问和随机访问。顺序读写时速度最快。
缺点：不方便拓展、容易产生碎片。

链接分配

分为隐式链接和显式链接。两种链接方式都不会产生外碎片。

隐式链接

隐式链接：每个文件块中都有指向下一个文件块的指针。
不支持随机访问。

显式链接

显式链接：把用于链接文件各物理块的指针存放在一张表中。专门存放指向下一个文件块的指针。
支持随机访问。

索引分配

系统为每个文件建立一个索引表，记录文件的逻辑块到物理块的映射关系。（类似内存管理中的页表，建立逻辑页面到物理页面的映射关系）注意，每个文件的索引表长度是不一样的，不能存放在FCB中，FCB中只记录索引表的地址。

问题：如果一个索引块装不下表了呢？

1. 将多个索引块链接起来存放
2. 多级索引
3. 混合索引

考点：根据多层索引、混合索引的结构计算出文件的最大长度。分析访问某个数据块所需要的读磁盘次数。

OS对空闲磁盘块的管理

设备管理