操作系统笔记

JJuprising2023-09-142024-01-04

错题

进程虚存文件

内存管理

第二章进程

进程的“同步”和“互斥”反映了进程间直接制约和间接制约的关系。

信号量

例5程序描述前驱关系

semaphore a-b-c=d-e-f-g-h-0;
S1(){...;signal(a);signal(b);} //…表示原来S1内的语句序列
S2(){wait(a);...;signal(c);signal(d);}//…表示原来S2内的语句序列
S3(){wait(b);.;signal(e);}//…表示原来S3内的语句序列
S4(){wait(c);…;signal(f);}//…表示原来S4内的语句序列
S5(){wait(d);..;signal(g);}//…表示原来S5内的语句序列
S6()wait(e);;signal(h);}//…表示原来S6内的语句序列
S7(){wait(f);wait(g);wait(h);...;)//…表示原来S7内的语句序列
main(){
	cobegin //注意这个开头表示并发执行
		S1();S2(),S3():S4();S5();S6();S7();	
	coend //注意这个结尾
}

进程同步

生产者消费者：

//最原型代码
Producer(item){
	wait(empty);
	Wait(mutex);
	Enqueue(item);
	signal(mutex)
	signal(full);
}
Consumer(){
	wait(full);
	wait(mutex);
	item=Dequeue();
	signal(mutex);
	signal(empty);
}
//这个版本交换了wait会造成死锁，当生产者过了mutex，此时如果是满的状态，无法向下执行，而此时消费者无法进入mutex就不能执行signal(mutex)来唤醒生产者，发生死锁
Producer(item){
	Wait(mutex);
	wait(empty);
	Enqueue(item);
	signal(mutex)
	signal(full);
}
Consumer(){
	wait(mutex);
	wait(full);
	item=Dequeue();
	signal(mutex);
	signal(empty);
}
//此版本交换signal不会造成死锁，只会改变临界资源的释放次序
Producer(item){
	wait(empty);
	Wait(mutex);
	Enqueue(item);
	signal(full);
	signal(mutex)
}
Consumer(){
	wait(full);
	wait(mutex);
	item=Dequeue();
	signal(empty);
	signal(mutex);
}

生产消费变体例15 有三个进程PA、PB和PC协作解决文件打印问题。PA将文件记录从磁盘读入内存的缓冲区1，每执行一次读一个记录：PB将缓冲区1的内容复制到缓冲区2中，每执行一次复制一个记录，PC将缓冲区2的内容打印出来，每执行一次打印一个记录缓冲区的大小与记录大小一样。请用信号量来保证文件的正确打印。

  graph LR
磁盘--PA-->缓冲区1--PB-->缓冲区2--PC-->打印

这里会发生冲突的只有缓冲区1和缓冲区2这两个临界资源。都只能存放一个记录——无需in,out指针，原来的生产消费者中的mutex信号量在这里可以省去

注意初始化empty=1，full=0
主函数cobegin,coend

semaphore empty1=1,full1=0,empty0=1,full2=0;
PA(){
	while(1){
		从磁盘读入一个记录;
		wait(empty1);//缓冲区1没记录
		将记录放入缓冲区1;
		signal(full1);//缓冲区1有记录
	}
}

PB(){
	while(1){
		wait(full1);//缓冲区1有记录
		从缓冲区1取出一个记录;
		signale(empty1);
		wait(empty2);//等缓冲区2空
		将记录复制到缓冲区2
		signal(full2);
	}
}
PC(){
	while(1){
		wait(full2);//缓冲区2有记录
		从缓冲区2取出一个记录;
		signal(empty2);
		将取出的记录打印出来
	}
}
main(){
	conbegin
	PA();PB();PC();
	coend
}

生产消费变体桌上有个能盛得下五个水果的空盘子。爸爸不停地向盘中放苹果或桔子，儿子不停地从盘中取出桔子享用，女儿不停地从盘中取出苹果享用。规定三人不能同时从盘子中取放水果。试用信号量实现爸爸、儿子和女儿这三个循环进程之间的同步。

关键点：信号量的设置

判空盘子empty，而且还有初始值为5
保护碗 mutex，初始为1，这样爸爸才能取到碗
区分苹果还是桔子 orange apple，儿子女儿其他都是一样

semaphore empty=5,orange=0,apple=0,mutex=1;
Dad(){
	while(1){
		wait(empty);//能放东西
		wait(mutex);//保护碗
		将水果放入碗;
		signal(mutex);//释放碗
		if(放入的是桔子);signal(orange);
		else signal(apple);
	}
}
Son(){
	while(1){
		wait(orange);//有桔子
		wait(mutex);//保护碗
		取出桔子;
		signal(mutex);//释放碗
		signal(empty);//减少水果
		享用桔子；
	}
}
Daughter(){
	while(1){
		wait(apple);
		wait(mutex);
		从盘中取一个苹果;
		signal(mutex);
		signal(empty);
		享用苹果;
	}
}

生产消费变体例18

关键点：

A-B≤m，B-A≤n，各自设一个信号量，SAB表示当前允许A生产的产品数量，初始值为m；SBA表示允许B生产的产品数量，初始值为n；
千万理解搭配wait(SAB)–signal(SBA)，wait(SBA)–signal(SAB)
还需要设置一个初值为0的资源信号量S，对应于仓库中的产品量
看懂生产者有两个步骤1是生产、2是放入仓库，一个用SAB/SBA维护，一个用mutex(初值为1)维护
生产后要增加S,signal(S)，消费要先判断S,wait(S)

semaphore SAB=m,SBA=n,S=0,mutex=1;
PA(){
	while(1){
		wait(SAB);//满足条件
        生产一个产品A;
        signal(SBA);//意味着B允许生产的数量要同步增加
        wait(mutex);//保护仓库
        将产品A放入仓库;
        signal(mutex);
        siganl(S);//增加仓库产品量
	}
	
}
PB(){
	while(1){
		wait(SBA);
		生产一个产品B;
		signal(SAB);//A允许数量增加
        wait(mutex);
        将产品B放入仓库
        signal(mutex);
        signal(S);
	}
	
}
PC(){
	while(1){
		wait(S);//有S
		wait(mutex);//记得保护仓库
		取出一个产品
		signale(mutex);
		售卖;
	}
}
main(){
	conbegin
		PA();PB();PC();
	coend
}

⭐读者写者问题过独木桥

关键点：

保护过桥人数
保护桥

int countA=0,countB=0;//分别表示A、B两个方向过桥的行人数量
semaphore bridge=1;//实现不同方向行人对桥的互斥共享
semaphore mutexA=mutexB=1;//分别实现对countA、countB的互斥共享
PA(){
	//进入桥
	wait(mutexA)
		if(countA==0)wait(bridge);//等桥，此时过桥的A初始状态为0，保护桥，其他人别来
		countA++;//人数增加
	signal(mutexA);//人数定了，不用保护
	过桥;
	//离开桥
	wait(mutexA);
		countA--;
		if(countA==0)signal(bridge);
	signal(mutexA);
}
PB(){
	//进入桥
	wait(mutexB)
		if(countB==0)wait(bridge);//等桥，此时过桥的A初始状态为0，保护桥，其他人别来
		countB++;//人数增加
	signal(mutexB);//人数定了，不用保护
	过桥;
	//离开桥
	wait(mutexB);
		countA--;
		if(countA==0)signal(bridge);
	signal(mutexA);
}

第四章存储管理

3.设有16页的逻辑空间，每页有1024字节，它们被映射32块的物理存储区中，那么，逻辑地址的有效位是14位，物理地址至少是15位。

页大小就是块大小，块大小1024字节，一共32块，那就是1024*32=2^15

二级页表

某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟__牛客网 (nowcoder.com)

第六章 I/O

9.I/0软件的分层结构中，I/0中断处理程序负责将把用户提交的逻辑I/0请求
转化为物理I/0操作的启动和执行。X 是设备驱动程序

10.为了使多个进程能有效地同时处理输入和输出，最好使用循环缓冲结构的缓冲技术 × 应该是缓冲池

第七章文件管理

文件系统的主要目的是实现对文件的按名存取。

第八章磁盘管理

一次磁盘读写操作需要的时间：寻道时间、旋转延迟时间、传输时间

寻道时间：把磁臂（磁头）移动到指定磁道上所经历的时间。
旋转延迟时间：把指定扇区移动到磁头下所经历的时间。
传输时间：把数据从磁盘读出或向磁盘写入数据所经历的时间

第一章操作系统引论

操作系统的概念、功能

操作系统

是指控制和管理整个计算机系统的硬件和软件资源——操作系统是系统资源的管理者
- ⭐提供的功能：处理机管理、存储器管理、文件管理、设备管理
- 目标：安全高效
以提供给用户和其他软件方便的接口环境——向上层提供方便易用的服务
- 硬件只接受二进制指令，在硬件之上安装操作系统，友好交互接口
- 把复杂的硬件功能封装成简单易用的服务
是计算机系统中最基本的系统软件——是最接近硬件的一层软件
- 直接给用户使用：GUI 图形化用户接口、命令接口（联机命令接口、脱机命令接口，前者说一句计算机做一句，后者说一堆做一堆如txt配置文件)
- 给软件/程序员使用：程序接口

没有任何软件支持的计算机称为裸机，操作系统实现了对硬件机器的拓展。

通常把覆盖了软件的机器称为扩充机器，又称之为虚拟机

用户
——
应用程序
——
操作系统
——
裸机(纯硬件)

进程-虚存-文件

操作系统的特征

并发

并发：指两个或多个时间在统一时间间隔发送，宏观上是同时发生，微观上是交替的。

注意区分，并行指两个或多个同时发生，宏观微观都是同时

操纵系统并发性：同时运行多个程序，微观上交替运行

操作系统伴随着“多道程序技术”出现，操作系统和程序并发是一起诞生的

考点：

单核CPU同一时刻执行一个程序，各个程序并发执行
多核执行多个，并行执行

计算机系统中同时存在多个运行的程序，需要OS管理和调度

共享

资源共享，系统的资源可供内存中多个并发执行的程序共同使用

两种方式

互斥共享方式，一个时间段只允许一个进程访问该资源
同时共享方式，一个时间段允许多个进程“同时”对它们进行访问
- 读取文件，微观上其实也是交替访问硬盘的；扬声器确实可以微观上同时使用

并发与共享的关系

并发性指计算机系统中同时存在着多个运行着的程序。
共享性是指系统中的资源可供内存中多个并发执行的进程共同使用。

互为存在条件，失去并发性，系统只有一个程序，共享性没意义；失去共享性，无法实现同时访问资源，无法并发。

虚拟

指把物理上的实体变为逻辑上的对应物，物理实体存在，而逻辑上对应物是用户感受的。

虚拟存储器，好像运行内存大于实际的内存

虚拟技术：

空分复用技术，如虚拟存储技术
时分复用技术，如虚拟处理器

失去了并发性，一个时间段只运行一道程序，失去了实现虚拟性的意义。因此没有并发现就失去了虚拟性

异步

允许多个程序并发执行，但进程的执行不是一贯到底，而是走走停停

并发的程序会争用资源

由于并发运行的程序会争抢着使用系统资源，而系统中的资源有限，因此进程的执行不是一贯到底的，而是走走停停的，以不可预知的速度向前推进
如果失去了并发性，即系统只能串行地运行各个程序，那么每个程序的执行会一贯到底。只有系统拥有并发性，才有可能导致异步性。

操作系统的发展

手工操作阶段

批处理阶段

单道批处理系统(引入脱机输入输出技术)

优：缓解人机速度矛盾

缺：资源利用率依然很低

多道批处理系统(操作系统开始出现)

优：多道程序并发执行，资源利用率高

缺：不提供人机交互功能

分时操作系统

以时间片轮流为各个用户服务，用户请求可以被即时响应，解决了人机交互问题

缺点：不能有限解决紧急任务

实时操作系统

优点：能优先响应一些紧急任务

要在严格时限内处理完事件，及时性和可靠性

硬实时系统：必须在绝对严格的规定时间内完成处理
软实时系统：能接受偶尔违反时间规定

操作系统的运行机制

两种程序

内核程序：负责实现操作系统，由很多内核程序组成操作系统内核，内核(Kernel)是操作系统最核心的部分，也是最接近硬件的部分
应用程序，跑在操作系统之上

两种指令

指令：是指处理器(cpu)能识别、执行的最基本命令，二进制机器指令

两种处理器状态

cpu判断指令类型，如何区分此时正在运行的是内核程序还是应用程序？

内核态(目态)，此时正在运行内核程序，可以执行特权指令
用户态(管态)，运行应用程序，只能执行非特权指令

CPU有一个寄存器叫程序状态字寄存器(PSW)，其中有个二进制位，1表示内核态，0表示用户态。

⭐状态切换

内核态->用户态：执行一条特权指令–修改PSW的标志位为”用户态”，操作系统主动让出CPU使用权

用户态->内核态：由中断(非法使用特权指令等)引发，硬件自动完成变态过程，触发中断信号意味着操作系统强行夺回CPU使用权

中断和异常

中断的作用

CPU运行两种程序，内核程序和应用程序，内核程序是系统管理者

一个应用程序上cpu运行后就会一直运行下去

“中断”是让操作系统内核夺回CPU使用权的唯一途径，用户态->内核态

中断的类型

内中断(也称异常)

与当前执行的指令有关，中断信号来源于CPU内部

例子：

试图在用户态执行特权指令，终止
执行除法指令发现除数为0，终止

若当前执行的指令是非法的，则会引发一个中断信号

应用程序请求内核服务，执行一条特殊的指令——陷入指令，会引发内部中断信号，陷阱、陷入(trap)

陷入指令主动将控制权还给操作系统内核，“系统调用”就是通过陷入指令完成。陷入指令不是特权指令！

外中断(也称中断，狭义的中断)

与当前执行的指令无关，中断信号来源于CPU外部

例子：

时钟中断——由时钟部件发来的中断信号
- 如时钟部件每隔一个时间片发送时钟中断信号，用户态->内核态
- 执行内核程序，操作系统内核决定接下来让另一个程序上CPU运行，内核态->用户态
I/O中断——由输入/输出设备发来的中断信号
- 当输入输出任务完成后，向CPU发送中断信号

每一条指令执行结束后，CPU都会例行检查是否有外中断信号

中断机制的基本原理

不同的中断信号，需要不同的中断处理程序来处理

CPU检测到中断信号后，根据中断信号的类型去查询”中断向量表“，找到相应的中断处理程序在内存中的存放位置

系统调用

系统调用是操作系统提供给应用程序(程序员/编程人员)使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以通过系统调用来请求获取操作系统内核的服务

操作系统向上的的接口

给用户用的
- GUI
- 命令接口
  - 联机命令接口
  - 脱机命令接口
给应用程序用的
- 程序接口(系统调用)

计算机本质四个字寻址执行

系统调用和库函数的区别

为什么系统调用是必须的

生活场景：去学校打印店打印论文，你按下了WPS的“打印”选项，打印机开
始工作。
你的论文打印到一半时，另一位同学按下了Wod的“打印”按钮，开始打印他
自己的论文。
思考：如果两个进程可以随意地、并发地共享打印机资源，会发生什么情况？
两个进程并发运行，打印机设备交替地收到WPS和Word两个进程发来的打印请求，结果两篇论文的内容混杂在一起了…
解决方法：由操作系统内核对共享资源进行统一的管理，并向上提供“系统调用”，用户进程想要使用打印机这种共享资源，只能通过系统调用向操作系统内核发出请求。内核会对各个请求进行协调处理。

系统调用按功能分类

设备管理，完成设备的请求/释放/启动等功能
文件管理，完成文件的读/写/创建/删除等功能
进程控制，完成进程的创建/撤销/阻塞/唤醒等功能
进程通信，完成进程之间的消息传递/信息传递等功能
内存管理，完成内存的分配/回收等功能

由于

①应用程序通过系统调用请求操作系统服务

②而系统中的各种共享资源由操作系统内核统一掌管

因此，凡是与共享资源有关的操作(如存储分配、I/O操作、文件管理等)，都必须通过系统调用的方式向操作系统内核作出服务请求，由操作系统内核代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作。

系统调用的过程

用户态应用程序要执行一列执行然后加一条陷入指令，引发一个内中断，使得能够转变为内核态运行系统调用入口程序，检查寄存器中的应用程序设置好的参数，判断是那种服务，调用处理程序上CPU运行，然后转回用户态

操作系统的体系结构

本节简要了解

内核是操作系统最基本、最核心的部分

实现操作系统内核功能的那些程序都是内核程序

大内核和微内核√

大内核√又名宏内核/单内核和微内核√

分层结构

模块化

外核

操作系统引导

BIOS：Basic Input/Output System

虚拟机

传统计算机，一台物理机器只能运行一个操作系统，容易造成性能浪费

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

第一类VMM，直接运行在硬件上

此种上层操作系统运行在虚拟内核空间不是真实的，因此一些特权指令需要通过虚拟机管理程序进行转化并反馈

第二类VMM，运行在宿主操作系统上

常用的虚拟机软件，VirtualBox、Vmware。

虚拟机管理程序请求宿主操作系统再进行资源分配

两类虚拟机管理程序(VMM)的对比

	第一类VMM	第二类VMM
对物理资源的控制权	直接运行在硬件之上，能直接控制和分配物理资源	运行在Host OS之上，依赖于Host OS为其分配物理资源
资源分配方式	在安装Guest OS时，VMM要在原本的硬盘上自行分配存储空间，类似于“外核“的分配方式，分配未经抽象的物理硬件	GuestOS拥有自己的虚拟磁盘，该盘实际上是Host OS文件系统中的一个大文件。GuestOS分配到的内存是虚拟内存
性能	性能更好	性能更差，需要HostOS作为”中介”
可支持的虚拟机数量	更多，不需要和Host OS竞争资源，相同的硬件资源可以支持更多的虚拟机	更少，Host OS本身需要使用物理资源，HostOS上运行的其他进程也需要物理资源
虚拟机的可迁移性	更差	更好，只需导出虚拟机镜像文件即可迁移到另一台Ho5tO5上，商业化应用更广泛
运行模式	第一类VMM运行在最高特权级(Ring 0),可以执行最高特权的指令。	第二类VMM****。GuestOS发出的系统调用会被VMM截获，并转化为VMM对Ho5tOS的系统调用

进程和线程

进程的概念、组成和特征

进程的概念

程序：是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。

进程：是动态的，是程序的一次执行过程。(同一个程序多次执行会对应多个进程)

进程的组成——PCB

操作系统给每一个进程分配一个PID，相当于进程的身份证号

还记录进程所属用户ID(UID)
还记录进程的运行情况(CPU使用时间，磁盘使用情况..)

这些信息都保存到PCB(Process Control Block)这个数据结构中，即进程控制块

操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息都被放在PCB中。

PCB
- 进程描述信息
- 进程控制和管理信息
- 资源分配清单
- 处理机相关信息
程序段
- 程序的代码(指令序列
数据段
- 运行过程中产生的各种数据(程序中定义的变量)

进程的特征

程序是静态的，进程是动态的，相比于程序，进程有以下特征

动态性，是进程最基本的特征
- 进程是程序的一次执行过程，是动态地产生、变化和消亡
并发性
- 内存中有多个进程实体，各进程可并发执行
独立性
- 进程是独立运行、独立获得资源、独立接受调度的基本单位
异步性，异步性会导致并发程序执行结果的不确定性。
- 各进程按各自独立的、不可预知的速度向前推进，操作系统要提供“进程同步机制”来解决异步问题
结构性
- 每个进程都会配置PCB，结构上看，进程是由程序段、数据段、PCB组成

进程的状态与转换

进程的状态

运行态

一个进程此时在CPU上运行，处于运行态。

就绪态

阻塞态

等待态。在进程运行的过程中，可能会请求等待某个时间的发生(如等待某种系统资源的分配，或者等待其他进程的响应)

创建态

正在被创建，尚未转到就绪态

结束态

进程正在从系统中消失，正常结束或其他原因退出运行。进程需要结束则先置为结束态——>再进一步处理资源释放和回收等工作

进程的控制

进程的创建

1)为新进程分配一个唯一的进程标识号，并申请一个空白PCB(PCB是有限的)。若PCB申请失败，则创建失败。

2)为进程分配其运行所需的资源，如内存、文件、I/O设备和CPU时间等（在PCB中体现)。这些资源或从操作系统获得，或仅从其父进程获得。如果资源不足（如内存），则并不是创建失败，而是处于创建态，等待内存资源。

3)初始化PCB,主要包括初始化标志信息、初始化处理机状态信息和初始化处理机控制信息，以及设置进程的优先级等。

4)若进程就绪队列能够接纳新进程，则将新进程插入就绪队列，等待被调度运行。

进程的终止

操作系统终止进程的过程如下（终止原语）：

1)根据被终止进程的标识符，检索出该进程的PCB,从中读出该进程的状态。

2)若被终止进程处于执行状态，立即终止该进程的执行，将处理机资源分配给其他进程。

3)若该进程还有子孙进程，则应将其所有子孙进程终止。

4)将该进程所拥有的全部资源，或归还给其父进程，或归还给操作系统。

5)将该PCB从所在队列（链表）中删除。

进程的阻塞和唤醒

阻塞：

1)找到将要被阻塞进程的标识号对应的PCB。

2)若该进程为运行态，则保护其现场，将其状态转为阻塞态，停止运行。

3)把该PCB插入相应事件的等待队列，将处理机资源调度给其他就绪进程。

唤醒：

1)在该事件的等待队列中找到相应进程的PCB。

2)将其从等待队列中移出，并置其状态为就绪态。

3)把该PCB插入就绪队列，等待调度程序调度。

进程的通信

共享存储

对共享空间进行读/写操作时，需要使用同步互斥工具(如P操作、V操作)，对共享空间的写/读进行控制。

共享存储分两种：

低级方式的共享是基于数据结构的共享
高级方式则是基于存储区的共享

消息传递

若通信进程之间不存在可直接访问的共享空间，则必须利用操作系统提供的消息传递方式实现进程通信。

直接通信方式，发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息，如图23所示。
间接通信方式。发送进程把消息发送到某个中间实体，接收进程从中间实体取得消息。这种中间实体一般称为信箱。该通信方式广泛应用于计算机网络中。

graph LR
共享存储:
进程1-->共享空间
共享空间-->进程1
共享空间-->进程2
进程2-->共享空间

graph LR
消息传递:
进程3-->进程4
进程4-->进程3

管道通信

向管道（共享文件）提供输入的发送进程（即写进程），以字符流形式将大量的数据送入（写）管道：而接收管道输出的接收进程（即读进程）则从管道中接收（读）数据。

graph LR
进程1--字符流-->缓冲区
缓冲区--读取-->进程2
进程2-->- 
- -->进程1

为了协调双方的通信，管道机制必须提供以下三方面的协调能力：互斥、同步和
确定对方的存在。

管道可以理解为共享存储的优化和发展

如果共享有进程在操作，会阻塞

儿存储空间变回缓冲区，不用担心阻塞，可以一边写入一边读出

线程和多线程

引入进程——多道程序能并发执行——提高资源利用率和系统吞吐量

引入进程——减小程序在并发执行时所付出的时空开销——提高操作系统的并发性能

线程-轻量级进程

一个进程内部有多个线程，线程切换发生在一个进程内部

引入线程机制后带来的变化

资源分配、调度
- 传统进程机制中，进程是资源分配和调度的基本单位
- 引入后，进程是资源分配的基本单位，线程是调度的基本单位
并发性
- 传统进程机制，只能进程间并发
- 引入后，可各线程也能并发，提升了并发度
系统开销
- 传统进程间开发，需要切换进程的运行环境，系统开销很大
- 线程间并发，如果是同一进程内的线程切换，不需要切换进程环境，系统开销小
- 引入线程后，并发所带来的系统开销很小

线程的属性

线程是处理机调度的单位
多CPU计算机中，各个线程可占用不同的CPU
每个线程都有一个线程ID、线程控制块 (TCB)
线程也有就绪、阻塞、运行三种基本状态
线程几乎不拥有系统资源
同一进程的不同线程间共享进程的资源
由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
同一进程中的线程切换，不会引起进程切换
不同进程中的线程切换，会引起进程切换
切换同进程内的线程，系统开销很小
切换进程，系统开销较大

线程的实现方式

用户级线程

三段代码逻辑，可以看作三个“线程”

int main(){
	int i=0;
	while (true){
		if(i==0)(处理视频聊天的代码：}
		if（i==1){处理文字聊天的代码：}
		if(i==2){处理文件传输的代码：)}
		i=（i+1)%3：//i的值为0,1,2,0,1,2...
}

用户级线程的管理由应用程序完成，而不是操作系统

在用户态下就能换成切换

操作系统不能意识到用户级线程的存在，因为是在用户态进行的，不涉及内核态

优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

内核级线程

有操作系统支持的线程

线程管理工作由操作系统完成

需要CPU变态切换为内核态

通过TCP(线程控制块进行管理)

优点：分配到不同核心，可以并发执行，当一个线程被阻塞后，别的线程可以继续执行，并发能力强，多线程在多核处理机上并发执行

缺点：一个用户进程会占多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大

多线程模型

一对一模型：一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。左图
多对一模型：多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。右图
- 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
- 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行
- 重点重点重点：操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。

多对多模型，n用户级线程映射到m个内核级线程(n>=m)。每个用户进程对应m个内核级线程。
- 克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞)，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。
- 只有所有内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会阻塞

线程的状态与转换

graph LR
就绪--3被调度程序选中-->运行
运行--2时间用完-->就绪
运行--1等待某事件-->阻塞
阻塞--4等待的事件发生-->就绪

线程的组织和管理

按照需要把TCB分门别类组织起来

处理调度

资源有限，事情没法同时处理——需要确定某种规则决定处理任务的顺序

调度的三个层次

作业：一个具体的任务

高级调度（作业调度）。按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。

简化理解：好几个程序需要启动，到底先启动哪个

低级调度（进程调度/处理机调度）一一按照某种策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。

中级调度（内存调度）一一按照某种策略决定将哪个处于挂起状态的进程重新调入内存。

当内存不足的时候，有些进程需要先挂起。组织成挂起队列。中级调度决定下一步的策略

七状态模型

graph LR
创建态-->就绪态
创建态-->就绪挂起
就绪态-->运行态
就绪态--挂起-->就绪挂起
就绪挂起--激活-->就绪态
运行态-->就绪态
运行态-->阻塞态
运行态-->终止态
阻塞态-->就绪态
阻塞态--挂起-->阻塞挂起
阻塞挂起--激活-->阻塞态
阻塞挂起--事件出现-->就绪挂起

三级调度的联系

作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程，这些进程被送入就绪队列，

进程调度从就绪队列中选出一个进程，并把其状态改为运行态，把CPU分配给它。

中级调度是为了提高内存的利用率，系统将那些暂时不能运行的进程挂起来。

特点：

作业调度为进程活动做准备，进程调度使进程正常活动起来。
中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间
作业调度次数少，中级调度次数略多，进程调度频率最高。
进程调度是最基本的，不可或缺。

调度的目标

调度算法性能评价指标：

CPU利用率
$$
\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}
$$
系统吞吐量，表示单位时间CPU完成作业的数量

$$
\frac{总共完成作业数}{总共花了多少时间}
$$

周转时间，周转时间=作业完成时间-作业提交时间

平均周转时间=(作业1的周转时间+…+作业n的周转时间)/n

带权周转时间=作业周转时间/作业实际运行时间=(作业完成时间-作业提交时间)/作业实际运行时间越小用户满意度越高
等待时间，进程处于等处理机的时间之和
响应时间，指从用户提交请求到系统首次产生响应所用的时间

调度的实现

调度程序：用于调度和分派CPU的组件，由三部分组成

排队器，故名思意，将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便于调度程序选择。每当有一个进程转变为就绪态时，排队器便将它插入到相应的就绪队列中。
分派器。依据调度程序所选的进程，将其从就绪队列中取出，将CPU分配给新进程。
上下文切换器。在对处理机进行切换时，会发生两对上下文的切换操作：
- 第一对，将当前进程的上下文保存到其P℃B中，再装入分派程序的上下文，以便分派程序运行；
- 第二对，移出分派程序的上下文，将新选进程的CPU现场信息装入处理机的各个相应寄存器。

调度的时机、切换与过程

调度程序是操作系统内核程序

不能进行进程的调度与切换的情况
- 在处理中断的过程中
- 进程在操作系统内核临界区中
- 其他需要完全屏蔽中断的原子操作过程中。如加锁，中断现场保护
应该进行进程调度与切换的情况
- 发生引起调度条件且当前进程无法继续运行下去时，可以马上进行调度与切换。若操作系统只在这种情况下进行进程调度，则是非剥夺调度。
- 中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换。若操作系统支持这种情况下的运行调度程序，则实现了剥夺方式的调度。

进程调度方式

非抢占调度方式，又称非剥夺方式。不打断
- A进程在处理机上执行，此时有进程B进入就绪队列，虽然B可能会比A更紧要，但是还是让A继续，直至运行完成或发生某种事件而进入阻塞态，才把处理机分配给其他进程。
- 优点：实现简单、系统开销小，适合大多数批处理系统
- 缺点：不能用于分时系统和大多数的实时系统
抢占调度方式，又称剥夺方式。可以打断
- 与上述相同情况，当B进入就绪队列，则允许调度程序根据某种原则去暂停正在执行的进程A，将处理机分配给更为重要或紧迫的进程。
- 优点：对提高系统吞吐率和响应效率都有明显好处
- 注意：但“抢占”不是一种任意性行为，必须遵循一定的原则，主要有优先权、短进程优先和时间片原则等

闲逛进程

在进程切换时，如果系统没有就绪进程，就会调度闲逛进程(idle)运行。优先级最低。

两种线程的调度

1)用户级线程调度。由于内核并不知道线程的存在，所以内核还是和以前一样，选择一个进程，并给予时间控制。由进程中的调度程序决定哪个线程运行。
2)内核级线程调度。内核选择一个特定线程运行，通常不用考虑该线程属于哪个进程。对被选择的线程赋予一个时间片，如果超过了时间片，就会强制挂起该线程。
用户级线程的线程切换在同一进程中进行，仅需少量的机器指令；

内核级线程的线程切换需要完整的上下文切换、修改内存映像、使高速缓存失效，这就导致了若干数量级的延迟。

典型的调度算法

FCFS

先来先服务(first-come first-served，FCFS)调度算法。

系统将按照作业到达的先后次序来进行调度，非抢占调度方式

可以分别用于作业调度和进程调度。

先到先得：简单、直观

问题：平均周转、响应时间过长

SJF

短作业优先(short job first，SJF)调度算法

SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。

可以分别用于作业调度和进程调度。

短任务优先：平均周转时间短
问题：1）不公平，任务饿死 2）平均响应时间过长

PR

优先级调度算法PR

每个进程都有一个优先数，优先数为整数。
默认：小的优先数具有高优先级。
目前主流的操作系统调度算法。

RR

轮转调度算法（时间片轮转(RR，Round-Robin)调度算法）

分时操作系统的诞生而诞生

在轮转(RR)法中，系统将所有的就绪进程按FCFS策略排成一个就绪队列。系统可设置每隔一定时间(如30 ms)便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。这样，就可以保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间。

优点：公平；响应快，适用于分时操作系统

缺点：由于高频率进程切换有开销，不区分进程紧急程度

如果时间片太大就变成了FCFS了
如果时间片太小，进程切换过于频繁，大量时间都用在处理进程切换了

注意实际做题遇到一种情况：

当A执行完一个时间片下处理机时，B正好到达，此时默认新进程B先进入队列，下处理机的A后进入队列

时间片没用完就执行完了，那么也会发生调度，

优先级调度算法

优先级一样的先到的先运行

多级反馈队列调度算法

是对上面方法的折衷

两个关键

新进程FCFS先进入第一级
执行完放到下一级队列队尾
只有当k级队列为空，才会为k+1级队头的进程分配时间片
((默认是抢占式的)被抢占处理机的进程重新放回原队列队尾
在最后一级用完时间片回到原队列队尾(即采用时间片轮转调度)

优点

对各类型进程相对公平(FCFS的优点)
每个新到达的进程都可以很快就得到响应(RR的优点)
短进程只用较少的时间就可完成(SPF的优点)；
不必实现估计进程的运行时间（避免用户作假）
可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程（拓展：可以将因/O而阻塞的进程重新放回原队列，这样
/O型进程就可以保持较高优先级)

总结

进程同步

忙等待：指在单CPU情况下，一个进程进入临界区之后，其他进程因无法满足竞争条件而循环探测竞争条件。其缺点是，在单CPU情况下，等待进程循环探测竞争条件，浪费了时间片。

概念定义

并发相互合作

两种形式的制约关系

间接相互制约关系(互斥关系)

对资源互斥访问，提出申请
直接相互制约关系(同步关系)

多个进程完成同一个任务

进程同步机制

软件同步机制
硬件同步机制
信号量机制：一种有效的进程同步机制，已被广泛应用
管程机制

软件同步机制

面包店算法

Peterson方案，主动谦让

do {
	flag[i] = true; //表示希望占用
	turn = j; //如果另一进程希望进入，当前进程忙等
	while (flag[j] && turn == j); //flag[j]表示另一进程在用，turn==j表示我进行谦让
	临界区;
	flag[i] = false;
	剩余区;
} while (1);

turn=j保证了当我是最后一个被谦让的就能得到资源了

硬件同步机制

关中断

最简单的实现互斥的方法。
进入锁测试前，关掉中断机制，完成锁测试且上锁后，开启中断测试。则执行临界区期间，不响应中断，所以保证了原子性。
缺点：①滥用关中断权限可能导致严重后果。②关中断太长影响系统效率，限制CPU交叉执行程序能力；③不适用于多CPU系统，一个CPU关中断不防其他CPU执行相同临界区代码

test-and-set

bool ts(bool& lock) { //原语(原子性)
	bool old = lock;
	lock = true;//上锁
	return old;
}

do {
	//...
	while (ts(lock));
	//临界区
	lock=false;//解锁
	//剩余区;
} while(true);

如果测试返回结果为 true，证明被上锁了，则需要等待(再赋值一次lock为真也没用)。否则，证明还没被上锁，赋值一次代表进行上锁。

swap

然而以上都不适合由普通用户实现

因此出现信号量机制

信号量机制

找到哪些地方要停，什么时候再走

信号量为正表示多多少个资源可以被使用

为负表示有多少个进程等待使用

信号量-软件解决方案：

保证两个或多个代码段不被并发调用
在进入关键代码段前，进程必须获取一个信号量，否则不能运行
执行完该关键代码段，必须释放信号量
信号量有值，为正说明它空闲，为负说明其忙碌

类型：

整型信号量->记录型信号量->AND型信号量->信号量集

信号量vs锁

信号量是一个一般的锁
- 锁{0,1}，信号量：{-∞,…,-2,-1,0,1,2,…∞}
- 信号量即信号的数量，唤醒的就是发一个信号
- 开锁也是一个信号
信号量作用
- 实现互斥
- 记录睡眠操作的次数
- 记录资源个数
- 记录等待进程个数
- 实现复杂的进程间同步关系

基本知识

用户进程->使用操作系统提供的一对原语->对信号量进行操作，从而很方便的实现了进程互斥、进程同步
信号量其实就是一个变量，表示系统中某种资源的数量
原语，其执行只能一气呵成，不可被中断
一对原语：wait(S) 原语和 signal(S) 原语
wait、signal 原语常简称为 P、V操作，把wait(S)，signal(S) 两个操作分别写为 P(S)、V(S)

wait,signal操作定义

wait(semaphores *S) {   	//请求一个单位的资源
  S->value --; 			//资源减少一个
  if (S->value<0) {
     block(S->list) ；}	//进程自我阻塞，并将其挂到信号S的等待队列（阻塞队列）中
}

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

信号量的应用

1. 利用信号量实现进程互斥

为使多个进程能互斥地访问某临界资源，只需为该资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。

semaphore mutex; 
mutex=1; // 初始化为 1
while(1)
{	wait(mutex);
	临界区；
	signal(mutex);
	剩余区；}

2. 利用信号量实现同步（前趋后继关系）　　还可利用信号量来描述程序或语句之间的前趋关系。设有两个并发执行的进程P1和P2。P1中有语句S1；P2中有语句S2。我们希望在S1执行后再执行S2。为实现这种前趋关系，只需使进程P1和P2共享一个公用信号量S，并赋予其初值为0，将signal(S)操作放在语句S1后面，而在S2语句前面插入wait(S)操作，保证了S2 一定是在S1之后执行。技巧口诀：前V后P。

P1(){
  S1;
  signal(S);
  ...
}

P2(){
  wait(S);
  S2;
  ...
}

利用前趋图

解法分析——出现死锁

管程机制

Hansan为管程所辖的定义：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。

数据结构：信号量操作：pv原语

生产者消费者

哲学家进食

读者写者

3.5死锁上课插入的

原因：

1. 竞争不可抢占性资源引起死锁

2. 竞争可消耗资源引起死锁

3. 进程推进顺序不当引起死锁

目前处理死锁的方法可归结为四种：
　(1) 预防死锁。
　(2) 避免死锁。
　(3) 检测死锁。
　(4) 解除死锁。

预防死锁

满足两种协议

第一种协议：该协议规定，所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。缺点：资源利用率低，可能出现饥饿。特别是需要申请很多资源的时候更容易出问题。
第二种协议：该协议是对第一种协议的改进，它允许一个进程只获得运行初期所需的资源后，便开始运行。其后在运行过程中逐步释放已经分配的且用毕的全部资源，然后再请求新资源。缺点：对进程运行过程中的资源需求要有清晰的认识，实现难度很大。

避免死锁

银行家算法

本题的安全序列为P2，P1，P3，可以先满足P2，P2释放后足够给P1，P1释放后足够给P3

存储管理

引入

程序需要先放到内存中才能被CPU处理——用来缓和CPU与硬盘之间的速度矛盾

内存地址从0开始，每个地址对应一个存储单元。

每个小房间就是一个存储单元

两种说法：

如果计算机”按字节编址“则每个存储单元大小为1字节，即1B，即8个二进制位
如果字长为16位的计算机“按字编址”，则每个存储单元大小为1个字；每个字的大小为16个二进制位。

内存使用：将程序放到内存中，PC指向开始地址

程序的执行

1编译–从C到汇编

2链接–从汇编到可执行程序
3然而还是程序，不是进程，要由装载器进行内存装入…
同时，由于内存地址从0开始，为了防止内存中从0开始的一段内存有专门的用途怎么办? 要有：

重定位: 为执行程序而对其中出现的地址（相对地址）所做的修改

重定位两个时机：

1在编译链接时，绝对代码: 这样的代码只能放在事先确定的位置上。即编译时重定位的程序只能放在内存固定位置
2载入时，一旦载入内存中就不能移动

因此，移动也是必要的

交换

能让更多的进程并发

存储器管理

目标：容量大，速度快，成本低

多层结构的存储器系统

三级：

最高层：CPU寄存器
中间为主存（高速缓存、主存储器、磁盘缓存）
最底层是辅存（固定磁盘，可移动介质）

特点：

＊层次越高－访问速度越快－价格越高－存储容量也最小

＊寄存器和主存掉电后存储的信息不再存在

＊辅存的信息长期保存

程序的装入和链接

用户的程序要在系统中运行，要先装入内存再转变为可执行的程序，步骤：

(1) 编译，由编译程序(Compiler)对用户源程序进行编译，形成若干个目标模块(Object Module)；
(2) 链接，由链接程序(Linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module)；
(3) 装入，由装入程序(Loader)将装入模块装入内存。

物理地址和逻辑地址

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

程序的装入

三种装入方式：

绝对装入方式-编译连接时。编译时产生的地址使用绝对地址
可重定位装入方式-载入时。编译后的目标模块使用相对地址，装入后的地址是绝对地址(物理地址)

在装入时，完成重定位（静态重定位）重定位，通常来说把在装入时对目标程序中指令和数据地址修改的过程称为重定位

重定位：逻辑地址转换为物理地址的过程，称为重定位，也成为地址变换。
动态运行时的装入方式。编译后的目标模块使用相对地址。在运行后完成重定位(动态重定位)-地址翻译

两种重定位方式比较

静态重定位，地址变换是在进程装入时一次完成的以后不再改变

优点：是无需增加硬件地址转换机构，便于实现程序的静态连接。在早期计算机中大多采用这种方案

缺点：内存空间不能移动；各个用户进程很难共享同一程序的副本。
动态重定位，并不立即把装入模块的逻辑地址进行转换，推迟到程序执行是才进行。需要寄存器的支持

优点：内存空间可以移动；各个用户进程可以共享内存中同一程序的副本。

缺点：增加了机器成本，而且实现存储管理的软件算法比较复杂。

程序的连接

三种

静态链接方式
装入时动态链接
运行时动态链接

对换和覆盖

引入：某些进程由于某些事件未发生导致阻塞运行，有很多作业又因为内存不足一直驻留在外存，不能进入内存运行。

严重浪费系统资源，吞吐量下降

对换：不能运行/暂时不用的进程调出到外存，已具备条件的调入到内存

多道程序环境下的对换技术

对换的类型：

整体对换
页面对换

对换空间的管理

对换与覆盖

分页存储管理方式

单一连续分配

存储器把内存分配系统区和用户区

系统区给os用
用户区内存仅装有且一道用户程序

固定分区分配

动态分区分配

动态可重定位分区分配

内存紧缩: 将空闲分区合并在一起，需要移动进程3(复制内容)

分页存储管理方式

把物理内存分成大小固定的块，称为物理块(frame，也称为页框)（大小为2的幂，通常为1KB~8KB）

把逻辑内存也分成固定大小的块，称为页(page)

分页存储管理的基本方法

⭐页表要考几题的

地址结构：

以32位地址举例，

页号P：

12-32位：20位
地址空间最多允许有1M(2²⁰)页

位移量W(页内地址)

0-11：12位
每页大小为4KB(2¹²)

在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程仍然能够正确地运行，即能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面映像表，简称页表

页表的作用：实现从页号到块号的地址映射。（类比路由表）

页表的实现

地址变换机构

基本地址变换机构-地址翻译

即将用户地址空间中的逻辑地址变换为内存空间中的物理地址

页表功能是由一组专门的寄存器来实现的。一个页表项用一个寄存器(PTR)。
具有快表的地址变换机构(类别缓存)

起因：

由于页表是存放在内存中的，这使CPU在每存取一个数据时，都要两次访问内存。

第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W拼接，以形成物理地址。

第二次访问内存时，才是从第一次所得地址中获得所需数据(或向此地址中写入数据)。

因此，采用这种方式将使计算机的处理速度降低近1/2

通过快表查询，可以直接得到逻辑页所对应的物理块号，由此拼接形成实际物理地址，减少了一次内存访问，缩短了进程访问内存的有效时间

由于快表的容量限制，不可能将一个进程的整个页表全部装入快表，存在着命中率的问题

页表结构的缺点

逻辑地址空间很大，页表变得非常大，要占相当大的内存空间
解决办法
- 对页表所需的内存空间采用离散方式
- 部分页表调入内存
页表结构
- 两级页表
- 多级页表
- 反置页表

TLB(Translation Look-aside Buffer)

是一组相联快速内存

反置(反向)页表

目的：为减少页表占用的内存空间，引入反置页表，一个系统一张页表

可使用哈希表来将查找限制在一个或少数几个页表条目。

分页技术总结

实现机理
- 地址空间和内存都分开大小相等的片(页和页框)
- 每个进程用页表(多级、反向等)建立页和页框的映射
- 进程创建时申请页，可用表、位图等结构管理空闲页
- 逻辑地址通过页表算出物理地址，到达内存
- 进程切换时，页表跟着切换

优点：靠近硬件，结构严格，高效使用内存，分页更适合于自动化(硬件实现)

缺点：不符合程序员思考习惯——引出分段技术

虚拟存储器

用户眼里的内存：

用户可随意使用该地址空间，就象单独拥有4G内存，这个地址空间怎么映射到物理内存，用户全然不知——虚拟内存

优点：

地址空间>物理内存
- 编写比内存大的程序
- 空间使用简化编程
部分程序放入物理内存
- 可以放更多进程
- 需要的才放进去，用不到的不放，内存利用率高
- 程序执行响应效率更高

虚拟存储器概述

常规存储管理方式特征
1. 一次性：作业被一次性全部装入内存
2. 驻留性：作业一直驻留在内存
局部性原理
1. 程序执行仅局限于某个部分，它访问的存储空间也局限于某个区域

局限性：

时间局限性：一条指令被执行了，则在不久的将来它可能再被执行
空间局限性：若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用。

工作原理：

基于局部性原理可知，应用程序在运行之前没有必要将之全部装入内存，而仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。

虚拟存储器：具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而成本接近于外存

特征：

多次性。作业中的程序和数据允许被分成多次调入内存允许
对换性。作业运行时无须常驻内存
虚拟性。从逻辑上扩充了内存容量，使用户看到的内存容量远大于实际内存容量

实现方法

分页请求系统
　1) 硬件支持
　主要的硬件支持有：
　　　　　　　 (1) 请求分页的页表机制。
　　　　　　　 (2) 缺页中断机构。
　　　　　　　 (3) 地址变换机构。
　2) 实现请求分页的软件
请求调页软件、页面置换软件。

请求分段系统
　1) 硬件支持
　主要的硬件支持有：
　　　　　　　 (1) 请求分段的段表机制。
　　　　　　　 (2) 缺页中断机构。
　　　　　　　 (3) 地址变换机构。
　2) 软件支持
请求调段软件、段置换软件。

请求分页中的硬件支持

请求页表机制

缺页中断机构

(1) 在指令执行期间产生和处理中断信号。

(2) 一条指令在执行期间可能产生多次缺页中断

地址变换机构

在分页系统地址变换机构的基础上，为实现虚拟存储器，再增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。

缺页率：

访问页面成功(即所访问页面在内存中)的次数为S，访问页面失败(即所访问页面不在内存中，需要从外存调入)的次数为F，则该进程总的页面访问次数为A = S + F 缺页率：f=F/A

影响因素：页面大小、分配内存块的数目、页面置换算法、程序固有属性

缺页中断处理时间：

假设被置换的页面被修改的概率是β，其缺页中断处理时间为ta，被置换页面没有被修改的缺页中断时间为tb，那么，缺页中断处理时间的计算公式为 t=βxta+(1-β)xtb

⭐页面置换算法

最佳置换算法（OPT）
先进先出置换算法（FIFO）
最近最久未使用置换算法（LRU）
最少使用算法（LFU）
Clock置换算法
页面缓冲算法

目标：需要一个最小的缺页率

FIFO

OPT

未来最远(或不访问的)替换掉

LRU

换谁？当前离进入的页最远的，比如D进来，应该把A换掉

需要的条件：

每页维护一个时间戳(time stamp)
栈

LFU

在采用LFU算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。（代价大，少用）

LRU近似算法

简单的Clock置换算法

当利用简单Clock算法时，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。

Ø每个页都与一个访问位相关联，初始值位0

Ø当页被访问时置访问位为1

Ø置换时选择访问位为0的页；若为1，重新置为0

指针指向上一个缺页的，最近最少

相比于栈，指针效率更高

改进型Clock置换算法

在改进型Clock算法中，除须考虑页面的使用情况外，还须再增加一个因素—置换代价（页表项里的修改位）。

“抖动”与工作集

人们希望在系统中能运行更多的进程，即增加多道程序度，以提高处理机的利用率

如果没有足够的页框——缺页率将很高，导致

CPU利用率低下
操作系统认为需要增加多道程序设计的道数
系统中将加入一个新的进程

抖动：一个进程的页面经常换入换出

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

抖动的发生与系统为进程分配物理块（页框）的多少有关

工作集

所谓工作集，是指在某段时间间隔Δ里，进程实际所要访问页面的集合。Denning指出，虽然程序只需要少量的几页在内存便可运行，但为了较少地产生缺页，应将程序的全部工作集装入内存中。然而我们无法事先预知程序在不同时刻将访问哪些页面，故仍只有像置换算法那样，用程序的过去某段时间内的行为作为程序在将来某段时间内行为的近似。

请求分段存储管理方式

文件

⭐文件的物理结构(分配方式)

连续分配

连接分配：显式隐式

类似于内存分页，磁盘中的存储单元被分为一个个“块/磁盘块/物理块”

一般，磁盘块大小=内存块大小=页面大小，方便数据交换

在内存管理中，进程的逻辑地址空间被分为一个一个页面
同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。
物理块号不可知

操作系统仍然需要一个逻辑快号到物理块号的映射

连续分配

逻辑上连续，则在物理上位置也要连续

如何实现？

查目录项实现

物理块号=起始块号+逻辑块号

优点

连续分配的文件在顺序读/写时速度最快(磁头移动距离短

缺点

不方便拓展(如果要拓展但是没有相邻的空闲块了，需要整体迁移，拓展不方便)
存储空间利用率低，会产生难以利用的磁盘碎片(可能没有连续的足够长的块大小，那都分配不了了)
- 利用紧凑来处理，但是消耗很大资源

链接分配

采用离散的方式为文件分配磁盘块

隐式链接

每个磁盘块都会保存指向下一个盘块的指针

取出来一个逻辑块，才知道下一个块存放的物理块号

因此读入i号逻辑块欧总共需i+1次磁盘I/O

结论：

优点

采用隐式链接的链接分配方式，很方便文件拓展。
另外，所有的空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高。

缺点

采用链式分配（隐式链接）方式的文件，**只支持顺序访问(看作是链表)**，不支持随机访问，查找效率低。
另外，指向下一个盘块的指针也需要耗费少量的存储空间。

显示链接

把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配(FAT,File Allocation Table)

一个磁盘有多少块，在FAT就有多少个表项。就是把隐式的指针信息都汇总到一个表方便找

用户给出要访问的逻辑块号，操作系统找到文件对应的目录项(FCB)

找到起始块，查询FAT，然后找到i号逻辑块对应的物理块号

对比隐式链接：逻辑块号转换为物理块号的过程不需要读磁盘操作

优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
缺点：文件分配表的需要占用一定的存储空间。

一个磁盘只会建立一张文件分配表
开机FAT放入内存，并常驻内存

单说链接分配默认是隐式链接

索引分配

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表一一建立逻辑页面到物理页之间的映射关系)。

索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

在FCB目录项记录索引块

注：区分显式链接和索引分配

在显式链接的链式分配方式中，文件分配表FAT是一个磁盘对应一张。
而索引分配方式中，索引表是一个文件对应一张。

文件存储空间的管理

存储空间的划分与初始化

存储空间的划分：将物理磁盘划分为一个文件卷(逻辑卷、逻辑盘)

文件卷划分为目录区和文件区

目录区主要存放文件目录信息(FCB)、用于磁盘存储空间管理的信息

文件区用于存放文件数据

存储空间管理

空闲表法

空闲盘块表，适用于”连续分配方式“，表头第一个空闲盘块号–空闲盘块号

类比内存管理中的动态分区分配，可以用首次适应、最佳适应和最坏适应等来决定分配。

如何回收磁盘块：与内存管理中的动态分区分配很类似，当回收某个
存储区时需要有四种情况一一

①回收区的前后都没有相邻空闲区：

②回收区的前后都是空闲区：

③回收区前面是空闲区：

④回收区后面是空闲区。

总之，回收时需要注意表项的合并问题。

空闲链表法

空闲盘块链，空闲盘区链

操作系统保存着链头、链尾指针。
如何分配：若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法

从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区分配给文件。
若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据

如何回收：

若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中.
若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。

离散分配、连续分配都适用，为一个文件分配多个盘块时效率更高

⭐位示图法

每一个二进制对应一个盘块，0表示空闲，1表示非空闲

字号、位号二元组来定位盘块号

注意盘块号、字号、位号是从0开始还是从1开始

0和1哪个代表空闲哪个代表不空闲

从0开始，(字号、位号)=(i,j)的二进制位对应的

盘块号 b=ni+j
由盘块号推字号位号：字号 i=b/n，位号 j=b%n

盘块从1开始，正推盘块加，逆推字位号减

盘块号 b=ni+j+1
字号 i=(b-1)/n，位号 j=(b-1)%n

如何分配：若文件需要K个块，

①顺序扫描位示图，找到K个相邻或不相邻的“0”;
②根据字号、位号算出对应的盘块号，将相应盘块分配给文件;
③将相应位设置为“1”。

如何回收：

①根据回收的盘块号计算出对应的字号、位号
②将相应二进制位设为“0”

成组链接法

UNIX采用的策略

空闲表和空闲链表法不适用于大型文件系统

超级块：空闲盘块数+空闲盘块号

第一个盘块也是一个类似超级块，记录下一个分组的空闲盘块数+空闲盘块号

注：一个分组中的块号不需要连续

最后一个分组少一个盘块，原因是他不需要一个超级块指示下一个分组了

如何分配：

当占满一个分组时，需要把这个分组指向下一个分组的信息赋值到超级块，超级块充当链头的作用，否则会丢失后面的链接

如何回收：

第一种：分组未满，插入到空闲块号，并增加空闲盘块数

第二种，若分组已满，回收的时候新建一个分组，并将超级块的信息复制到新的分组，作为一个新的分组，指向下一个分组，超级块指向新分组

输入输出系统

外设如何工作：

I/O系统的功能、模型和接口

什么是I/O设备？

“I/O” 就是 “输入/输出”（Input/Output）。I/O 设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件。

UNIX系统将外部设备抽象为一种特殊的文件，用户可以使用与文件操作相同的方式对外部设备进行操作。

I/O系统管理的主要对象是I/O设备（Terminal）和相应的设备控制器。

最主要的任务

完成用户提出的I/O请求，提高I/O速率
提高设备的利用率
能为更高层的进程方便地使用这些设备提供手段

设备的分类

块设备
字符设备
低速设备
中速设备
高速设备

基本功能

隐藏物理设备的细节
能够保证OS与设备的无关性
提高处理机和I/O设备的利用率
对I/O设备进行控制

既要与CPU通信，又要与设备通信，还要具有按CPU发来的命令去控制设备工作的功能

I/O接口由三部分组成

设备控制器与CPU的接口
设备控制器与设备的接口
I/逻辑

I/O端口，有三类寄存器

数据寄存器
状态寄存器
控制寄存器

CPU与I/O端口进行通信两种方法

独立编址
统一编制

I/O控制方式

程序直接控制

计算机从外部设备读取每个字
CPU需要对外设状态进行循环检查
直到确定改字已经在I/O控制器的数据寄存器种

然而CPU和高速性和I/O设备的低速性，使得CPU都处于等待I/O设备完成循环测试，造成浪费

-》需要不断测试的原因：没有采用中断-I/O无法报告已经完成一个字符操作-CPU要不断测试设备状态

程序直接控制方式

优点：简单且易于实现，

缺点：由于CPU和I/O设备只能串行工作，导致CPU的利用率相当低。

中断驱动方式

DMA方式

特点：

1)基本单位是数据块。

2)所传送的数据，是从设备直接送入内存的，或者相反。

3)仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在DMA控制器的控制下完成的。

要在主机与控制器之间实现成块数据的直接交换，须在DMA控制器中设置如下4类寄存器：

1)命令状态寄存器(CR)。接收从CPU发来的I/O命令、有关控制信息，或设备的状态。

2)内存地址寄存器(MAR)。在输入时，它存放把数据从设备传送到内存的起始目标地址：在输出时，它存放由内存到设备的内存源地址。

3)数据寄存器(DR)。暂存从设备到内存或从内存到设备的数据。

4)数据计数器(DC)。存放本次要传送的字（节）数。

	中断时机	控制
中断方式	中断方式在每个数据需要传输时中断CPU	数据传送中断处理时由CPU控制完成的
DMA方式	DMA方式则是在所要求传送的一批数据全部传送结束时才中断CPU	DMA方式则是在DMA控制器的控制下完成的

通道控制方式

I/O软件层次结构

用户层I/O软件
设备独立性软件
设备驱动程序
中断处理程序
硬件

应用程序I/O接口

(1)字符设备接口

(2)块设备接口

(3)网络设备接口

(4)阻塞/非阻塞/O

文件系统：文件+目录

缓冲区管理

缓冲池

一般将缓冲池中具有相同类型的缓冲区链接成一个队列，于是可形成以下三个队列：

(1) 空白缓冲队列emq。空缓冲区所链成的队列

(2) 输入队列inq。装满输入数据的缓冲区所链成的队列

(3) 输出队列outq。装满输入数据的缓冲区所链成的队列

缓存

缓存是保存数据副本的高速内存区域：
- CPU缓存、磁盘缓存、光驱缓存等
CPU缓存（高速缓存）：
- 为了缓和CPU运行速率与内存读/写速率不匹配的矛盾；
- 当CPU要读取一个数据时，首先从CPU缓存中查找，找到就立即读取并送给CPU处理；若没有找到，则从速率相对较慢的内存中读取并送给CPU处理，同时把这个数据所在的数据库调入缓存中。
缓存和缓冲
- 缓冲可以保存数据项的唯一的现有版本。
- 缓存只是提供一个位于其他地方的数据项的更快存储副本。
- 有时，同一个内存区，既可以是缓冲，也可以是缓存

磁盘存储器的性能和调度

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

c h s

40GB硬盘
- cylinder:19710、head:16、sector:255
- 计算：19710×255×16×512B=41173401600B=40GB
1.44MB软盘
- Sides:2、Tracks:80、Sectors:18
- 计算：2×80×18×512B=1.44MB

磁盘的类型*考试几率不大

磁盘-块-块集-文件

一次磁盘读写操作需要的时间：寻道时间、旋转延迟时间、传输时间

寻道时间：把磁臂（磁头）移动到指定磁道上所经历的时间。
旋转延迟时间：把指定扇区移动到磁头下所经历的时间。
传输时间：把数据从磁盘读出或向磁盘写入数据所经历的时间

文件目录

查找的时候只关心文件名，因此把除了文件名的描述信息全部放到索引结点

文件名+指向索引结点的指针

FCB一个代表一个目录项

错题

内存管理

第二章进程

信号量

进程同步

第四章 存储管理

二级页表

第六章 I/O

第七章 文件管理

第八章 磁盘管理

第一章 操作系统引论

操作系统的概念、功能

操作系统的特征

并发

共享

并发与共享的关系

虚拟

异步

操作系统的发展

手工操作阶段

批处理阶段

单道批处理系统(引入脱机输入输出技术)

多道批处理系统(操作系统开始出现)

分时操作系统

实时操作系统

操作系统的运行机制

两种程序

两种指令

两种处理器状态

⭐状态切换

中断和异常

中断的作用

中断的类型

内中断(也称异常)

外中断(也称中断，狭义的中断)

中断机制的基本原理

系统调用

系统调用和库函数的区别

为什么系统调用是必须的

系统调用按功能分类

系统调用的过程

操作系统的体系结构

大内核和微内核√

操作系统引导

虚拟机

进程和线程

进程的概念、组成和特征

进程的概念

进程的组成——PCB

进程的特征

进程的状态与转换

进程的状态

运行态

就绪态

阻塞态

创建态

结束态

进程的控制

进程的创建

进程的终止

进程的阻塞和唤醒

进程的通信

共享存储

消息传递

管道通信

线程和多线程

引入线程机制后带来的变化

线程的属性

线程的实现方式

用户级线程

内核级线程

多线程模型

线程的状态与转换

线程的组织和管理

处理调度

调度的三个层次

七状态模型

三级调度的联系

调度的目标

调度的实现

第四章存储管理

第七章文件管理

第八章磁盘管理

第一章操作系统引论

3.5死锁上课插入的

⭐页表要考几题的