操作系统
2021-08-31 10:00:08 47 举报AI智能生成
考研408操作系统笔记
作者其他创作
大纲/内容
第四章 文件管理
文件系统以及实现
文件管理的基础知识
文件的定义：一组有意义的信息的集合
文件的属性：文件名、标识符、类型、位置、大小、保护信息..
文件内部应该如何被起来(逻辑结构)
无结构文件
一系列二进制或字符流组成，也叫流式文件
有结构文件
记录（包含数据项）
文件之间又该如何被组织起来(目录结构)
操作系统应该向上提供那些功能
创建文件(create系统调用)
删除文件(delete系统调用)
读文件(read系统调用)
写文件(write系统调用)
打开文件(open系统调用)
关闭文件(close系统调用)
文件应该如何放在外存中(文件的物理结构)
子主题
操作系统如何管理外存中的空闲块（存储空间的管理）
操作系统需要提供其他文件管理功能
文件共享
文件保护
文件的基本功能
创建文件(create系统调用)
分配外存文件，创建目录项
删除文件(delete系统调用)
回收外存空间，删除目录项
打开文件(open系统调用)
将目录项中的信息赋值到内存中的打开文件表中，并将打开文件表的索引号(也被称作文件描述符)返回给用户
两个打开文件表
打开文件之后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作
每个进程都有自己的打开文件表，系统中也有一个张总的打开文件表
进程打开文件表中特有的属性：读写指针、访问权限(只读？读写？)
系统打开文件表特有的属性：打开计数器(有多少个进程打开了该文件)
关闭文件(close系统调用)
将进程打开文件表对应表象删除
系统打开文件表的打开计数器减1，若打开计数器为0，则删除系统表的表项
读文件(read系统调用)
根据读指针、读入数据量、内存位置将文件数据从外村读入内存
写文件(write系统调用)
根据写指针、写出数据量、内存位置将文件数据从内存写出外存
文件的逻辑结构
无结构文件
有二进制或字符流组成，无明显的逻辑结构
有结构文件
由记录组成，分为定长记录、可变长记录
逻辑结构
顺序文件
补充
顺序结构
记录之间的顺序按关键字顺序排列
串结构
记录之间的顺序与关键字无关
链式存储
无论定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始一次往后查找
顺序存储
可变长记录
无法实现随机存取。每次只能从第一个记录开始一次往后查找
定长记录
可实现随机存取。记录长度为L，则第i个记录存放的相对位置是I*L
若采用串结构，无法快速找到某关键字对应的记录，因为关键字和记录的顺序无关
若采用顺序结构，可以快速找到某关键字对应的记录
索引文件
索引顺序文件
多级索引顺序文件(其实就是多次分组)
文件目录
文件控制块
一个文件对应一个FCB，一个FCB就是一个目录项，多个FCB组成文件目录
对目录的操作：搜索、创建文件、删除文件、显示文件、修改文件
目录结构
单级目录结构
一个系统只能有一张目录表，不允许对文件重名，所以也不支持多用户系统
两级目录结构
不同用户可以重名，但不能对文件进行分类(因为只有两张表，第一张用户表，第二张目录表)
多级目录结构(树形目录结构)
不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享
系统根据“文件路径”找到目标文件
从根目录出发的路径是“绝对路径”
从“当前目录”出发的路径是相对路径
但是不方便文件共享
无环图目录结构
在树形目录结构的基础上。增加一些指向同一节点的有向边，使整个目录称为一个有向无环图
在共享节点设置一个共享计数器，计时器为0时才真正删除该节点
索引结点(对文件控制块的优化)
除了文件名之外的所有信息都放在索引节点汇总，每个文件对应一个索引节点
目录项中只包括文件名、索引节点指针，因此每个目录项长度大幅减小
由于目录项长度减小，因此每个磁盘块可以存放更多目录项，因此检查文件时I/O的次数就变小了
当找到文件名对应的目录项时，才需要将索引节点调入内存，索引节点中记录了文件的各种信息，包括在外存中的存放位置，根据“存放位置”即可找到文件
补充：存放在外存的索引节点称为“磁盘索引节点”，当索引节点放入内存后称为“内存索引节点”,相比内存索引节点中需要增加一些信息，比如：文件是否被修改，此时有几个进程正在访问改文件等。
文件的物理结构(文件分配方式)：文件是怎么样存放在外存的？
文件块、磁盘块
磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”。磁盘块的大小与内存快、大小相同。方便IO操作，文件的地址可以表示为(逻辑块号，块内地址)
连续分配
优点
支顺序访问和直接访问(随机访问)；连续分配的文件在顺序访问时速度最快
缺点
不方便文件扩展；存储空间利用率低，会产生磁盘碎片
链接分配
隐式链接
优点
很方便文件扩展，不会有碎片问题，外存利用率高
缺点
只支持顺序访问，不支持随机访问，查找效率低，指向下一个指针也需要耗费内存空间
显式链接
优点
很方便文件扩展，不会有碎片问题，外存利用率高，并且支持随机访问。相比隐式连接来说，地址装换不需要访问磁盘，因此文件的访问效率跟高
索引分配
解决索引表过大的方法
链接方案
多层索引
混合索引
总结
文件的逻辑结构VS物理结构
逻辑结构
用户(文件创建者)的视角看到的样子
在用户看来整个文件占用了连续的逻辑地址空间
文件内部的信息组织完全由用户自己觉得，操作系统并不关心
物理结构
由操作系统决定文件采用什么物理结构存储
操作系统负责讲逻辑地址转变为(逻辑块号，块内偏移量)的形式，并负责实现逻辑块号到物理块号的映射
总结：文件的逻辑结构有用户决定，链式 还是索引还是顺序，表示的是你这个文件数据的逻辑关系，而物理结构表示你这个文件被操作系统分为一个个的(根据磁盘块大小为参照物)文件块，然后，根据分配方式，比如索引分配、链接分配等，为其分配到外存
文件存储空间的管理
存储空间的划分与初始化
文件卷(逻辑卷)的概念
文件卷(逻辑卷)，目录区，文件区的概念
目录区与文件区
目录区包含文件目录、空闲表、位示图、超级快等用于文件管理的数据
管理方法
空闲表法
空闲表中记录每个连续空闲区的起始盘块号、盘块数
分配时可采用首次适应、最佳适应等策略；回收时注意合并问题
空闲链表法
空闲盘块链
以盘块为单位组成一条空闲链
分配时从链头依次取出空闲块，回收时将空闲块查到链尾
空闲盘区链
以盘区为单位组成一条空闲链
分配时可采用首次适应、最佳适应等策略；回收时注意相邻空闲盘区的合并问题
位示图法
一个二进制为对应一个盘块的空闲状态。（字号，位号）或（行号，列号）与盘块号一一对应
重要考点
（字号，位号）→盘块号
盘块号=字号*n+位号（n表示字长）
盘块号→（字号，位号）
字号=盘块号/n，位号=盘块号%n
（字号，位号）
需要注意题目条件
二进制0/1到底那个代表空闲，那个代表不空闲
字号、位号、盘块号到底从0开始还是从1开始
成组链接法
文件共享
硬链接
每个用户的目录项指向同一个索引节点
索引节点中需要有连接计数count
某用户想删除文件时，只是删除该用户的目录项，且count--
只有count==0时才能真正删除文件数据和索引节点，否则会导致指针悬空
软链接(符号链接，类似于快捷方式)
在一个Link型的文件中记录共享文件的存放路径(Winows快捷方式)
操作系统根据路径一层层查找目录，最终找到共享文件
即使软链接指向的共享文件已被删除，Link型文件依然UC你在，只是通过Link型文件中的路径去查找共享文件会失败(找不到对应目录项)
由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O，因此用软链接访问更慢
文件保护
口令保护
为文件设置一个“口令”，用户想要访问文件时需要提供口令，有系统验证口令是否正确
实现开销小，单“口令”一般存放在FB或索引结点中(也就是存放在系统中)因此不太安全
加密保护
用一个“密码”对文件加密，用户想要访问文件时，需要提供相同的“密码”才能解密，而且这个密码不用存放在操作系统且只有当前用户知道
安全性高，但加密/解密需要耗费一定的时间
范文控制
用一个访问控制表(ACL)记录各个用户(或各组用户)对文件的访问权限
对文件的访问类型可以分为：读/写/执行/删除等
实现灵活，可以实现复杂的文件保护功能
文件索引的层次结构
总结实例
子主题
最好看看王道视频
补充：
当你访问一个文件，你的进程首先是查询自己的进程文件打开表，这个表的内容来自文件打开表，文件打开表的内容又是通过open()来查询文件目录的，操作系统将你的物理磁盘划分为卷也就是磁盘区 c...，磁盘去分为目录区和文件区 目录存放文件目录 文件打开表
然后你的文件区分为空闲区和非空闲区，这里时文件系统的物理结构，也就是操作系统怎么分配他们，而文件的逻辑结构是用户怎么来看待他们
文件打开表操作系统只有一个，用户文件打开表每个进程有一个；FAT每个磁盘只有一个，但是会常驻内存
索引节点(inode)指的是文件目录中的文件数量，而索引节点里面的才是文件的分配，
磁盘组织与管理
磁盘的结构
磁盘、磁道、扇区的概念
磁盘由表面涂有磁性物质的圆形盘片组成
每个盘片被划分为一个个磁道，每个磁道又划分为一个个扇区
如何在磁盘中读\写数据
磁头移动到目标位置，盘片旋转，对应扇区划过磁道才能完成读\写
盘面、柱面的概念
磁盘有多个盘片“摞起来”，每个盘片有两个盘面
所有盘面中相对位置相同的磁道组成柱面
磁盘的物理地址
（柱面号、盘面号、扇区号）
磁盘的分裂
磁盘是否可以移动
固定头磁盘（每个磁道有一个磁头）
移动头磁盘（每个磁盘只有一个磁头）
根据盘片是否可更换
固定盘磁盘
可换盘磁盘
磁盘调度算法
一次磁盘读写操作需要的实际时间
寻找时间(寻道时间)：启动磁臂、移动磁头所花的时间
延迟时间：将目标扇区转到磁头下面所花的时间
传输时间：读写 数据所花费的时间
补充：延迟时间和传输时间都是和转速有关的，所以我们无法从操作系统上对其操作，我们下面的算法时面向寻找时间的
例图
磁盘调度算法
先来先服务算法（FCFS）
按照访问请求到达的先后顺序进行处理
最短寻找时间优先算法(SSTF)
每次都优先响应距离磁头最近的磁道访问请求
贪心算法的思想，能保证眼前最优，但无法保证总的寻道时间最短
缺点：可能导致饥饿
扫描算法 （电梯算法、SCAN）
只有磁盘移动到最边缘时才可以改变磁盘移动方向
缺点：对每个位置的磁道的响应频率不平均
循环扫描算法（C-SCAN）
只有磁头朝某个方向移动时才会响应请求，移动到最边缘后，立刻让磁头返回起点，返回途中不会响应任何请求
低频考点
LOOK算法
SCAN算法的改进，只有在磁头移动方向上不在有请求，就立即改变磁头方向，返回的过程会处理请求
C-LOOK算法
C-SCAN的改进，只有在磁头移动方向上不在有请求，就立即改变磁头方向，移动到有请求的位置，返回的过程不会处理请求，会和C-SCAN类似，返回到了最前面有请求的磁道开始向后扫描
TIPS:
减少延迟时间的方法
交替编号
具体做法：让编号相邻的扇区在物理上不相邻
原理：读取玩一个扇区后需要一段时间处理才可以继续读入下一个扇区
错位命名
具体做法：让相邻盘面的扇区编号“错位”
原理：要访问同一扇区，与“交替编号”的原理相同有处理时间，物理位置相邻会因为处理时间而导致读不上。所以错位来让“空缺”那段时间来处理数据，“错位命名法”可降低延迟时间
磁盘的管理
理解为什么要用(柱面号，盘面号。扇区号)的结构
理解为什么不用(盘面号。柱面号，扇区号)的结构
原因：在读取地址连续的磁盘块时，前者更不需要移动磁头
补充
磁盘的管理
磁盘初始化
①低级格式化/物理格式化：划分扇区
②磁盘分区(C盘、D盘、E盘...)
③逻辑格式化：建立文件系统(建立根目录文件，建立用于存储空间管理的数据结构)
引导块(初始块/启动分区)
计算机启动时需要运行初始化程序(自举程序)来完成初始化
ROM中存放很小的自举装入程序
完整的自举程序存放在初始快(引导块/启动分区）中，位于磁盘的固定位置
拥有启动分区的磁盘叫做启动/系统 磁盘
坏块的管理
简单的磁盘：逻辑格式化时将坏块标记出来
复杂的磁盘：磁盘控制块维护一个坏块链，并管理备用扇区
第五章 I/O管理
I/O设备的基本概念与分类
什么是IO设备
将数据Input/Output计算机的外部设备
UNIX系统将所有的外设抽象为一种特殊的文件，用户可以对其使用对文件一样的方式（Write/Read）来使用设备
按使用特性分类
人机交互类外部设备
存储设备
网络通信设备
按传输速率分类
低速设备
中速设备
高速设备
按信息交换的单位分类
块设备(以磁盘块为单位，传输快、可寻址)
字符设备（以字符为单位、不可寻址、采用中断驱动方式）
I/O控制器
主要功能
接受和识别CPU发出的指令(要有控制寄存器)
向CPU报告设备的状态(要有状态存器)
数据交换(要有数据寄存器，暂存输入/输出的数据)
地址识别(由I/O逻辑实现)
例图
组成
CPU与控制器之间的接口(实现控制器与CPU之间的通信)
I/O逻辑(负责识别发出的命令，并向设备发出指令)
控制器与设备一直的接口(实现控制器与设备之间的通信）
补充
两种不同的寄存器编址方式
内存映射I/O
控制器中的寄存器与内存统一编址
可以采用堆内存进行操作的指令来对控制器进行操作
寄存器独立编址
控制器中的寄存器独立编址
需要设置专门的指令来操作控制器
例图
I/O的控制方式
程序直接控制方式
完成IO的过程：CPU发出IO指令需要不断的轮询
CPU干预频率：极高
每次IO数据传输单位：字
数据流向：设备→CPU→内存，内存→CPU→设备
优点
实现简单
缺点
CPU必须和IO设备串行工作，CPU需要一直轮询检查，长期“忙等”状态，CPU利用率低
图例
中断驱动方式
CPU发出IO命令后，将当前进程阻塞，可以去做其他工作，本次IO完成后设备控制器发出中断信号
CPU干预频率：高
每次IO数据传输单位：字
数据流向：设备→CPU→内存，内存→CPU→设备
优点
与“程序直接控制方式”相比，CPU不用去一直轮询，CPU和IO设备并行的工作，CPU利用率提高
缺点
每个字在IO设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间
中断的补充
CPU会在每个指令周期末尾检查中断
中弹的处理是需要保存和回复当前进程的运行环境，所以这个过程是由时间开销的
图例
DMA方式
CPU发出IO命令后，将当前进程阻塞，可以去做其他工作，本次IO完成后DMA控制器发出中断信号
CPU干预频率：中
每次IO数据传输单位：一个块或顺序相连的块
数据流向：设备→内存，内存→设备
优点
数据传输以“块”为单位，CPU介入频率进一步降低。数据的传输不在需要先经过CPU在写入内存，数据传输效率进一步增加，CPU和IO设备并行性进一步提升
缺点
CPU每发出一个IO指令，只能读/写一个或多个连续的数据块
图例
通道控制方式
CPU发出IO命令后，将当前进程阻塞，可以去做其他工作，通道会执行通道程序完成IO，完成后通道向CPU发出中断信号
CPU干预频率：低
每次IO数据传输单位：一组块
数据流向：设备→内存，内存→设备
优点
CPU、IO、通道设备可并行工作，资源利用率高
缺点
实现复杂，需要有专门的设备支持
图例
IO软件层次结构
用户层软件
用户层软件实现了与用户交互的接口，用户可直接使用该层提供、与I/O操作相关的库函数对设备进行操作
设备独立性软件（设备无关性软件）
与设备的硬件特性无关的功能都是在这一层实现
实现的功能
向上一层提供统一的系统调用（例如：write/read调用）
设备保护
差错处理
设备的分配与回收
数据缓冲区管理
建立设备名到物理设备名的映射关系；根据设备类型选择相应的驱动程序
逻辑设备表
TIPS:设备独立性需要通过“逻辑设备表（LUT，Logical Unit Tavle）”来确定逻辑设备对应的物理设备，并找到该设备对应的设备驱动程序
设备驱动程序
主要负责对硬件的具体控制，将上层一系列命令，通过设备提供的驱动程序“翻译”成设备看的懂的语言
中断处理程序
IO设备
例图
补充
直接涉及到硬件的具体细节、且与中断无关的操作肯定实在设备驱动程序层完成的；没有涉及到硬件的、对各种设备都需要进行的管理工作实在设备独立性软件完成的
只有设备驱动程序和中断处理程序可以与IO设备打交道
I/O核心子系统
假脱机技术（SPOOLing）
脱机技术
外围控制机+更高速的设备————磁带
作用：缓解设备与CPU的速度矛盾，实现预输入，缓输出
假脱机技术
又叫SPOOLing技术，用软件的方式模拟输入/输出时的磁带
输入井和输出井——模拟脱机输入\输出时的磁带
输入进程和输出进程-模拟脱机输入\输出时的外围控制机
输入缓冲区和输出缓冲区-内存中的缓冲区，输入、输出时的“中转站”
图例
共享打印机
用SPOOLing技术将独占式的打印机“虚拟”成共享打印机
设备的分配与回收
应该考虑的因素
固有属性
独占设备、共享设备、虚拟设别（SPOOLing）
分配算法
先来先服务、优先级、短任务优先算法等
安全性
安全分配、不安全分配
静态分配与动态分配
静态分配：进程运行前为其分配全部所需资源，运动结束后归还资源
动态分配：进程运行过程中动态申请设备资源
设备分配管理中的数据结构
系统设备表（SDT）
记录整个系统管中所有设备的情况，每个设 备对应一个表目，关键字段：设备类型/标识符/DCT/驱动程序入口
设备控制表（DCT）
每个设备对一个一张DCT，关键字段：类型/标识符/状态/指向COCT的指针/等待队列指针
控制器控制表（COCT）
每个设备对一个一张COCT，关键字段：状态/指向CHCT的指针/等待队列指针
通道控制表（CHCT）
每个设备对一个一张CHCT，关键字段：状态/等待队列指针
TIPS：一个通道控制器控制多个设备控制器，一个设备控制器控制多个设备，而一个操作系统有多个通道
设备分配的步骤
①根据进程请求的物理设备查找SDT②根据SDT找到DCT并分配设备；③根据DCT找到COCT并分配控制器；④根据COCT找到CHCT并分配通道
注意：只有设备、控制器、通道三者都分配成功后，这次设备分配才算成功，之后便可启动IO设备进行数据传输
缺点：用户编程时必须使用“物理设备名”，如换了一个物理设备，程序无法运行，若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待
设备分配步骤的改进
用户编程时使用逻辑设备名申请设备，操作系统负责实现从逻辑设备名到物理设备名的映射(通过LUT)
例图
缓冲区管理
缓冲区概念
一般利用内存作为缓冲区
缓解CPU与设备的速度矛盾、减少CPU的中断频率、解决数据力度不匹配的问题、提高CPU与IO之间的并行性
单缓冲
处理一块数据平均消耗Max（C,T）+M
分析初始状态：工作区满，缓冲区空
双缓冲
处理一块数据平均耗时MAX（T,C+M）
分析问题的初始状态：工作区空，一个缓冲区设备满，另一个缓冲区空
循环缓冲
多个缓冲区连接成循环队列，in指针指向第一个空缓冲区，out指针指向第一个满缓冲区
缓冲池
三个队列：空缓冲队列、输入队列、输出队列
四种缓冲区
用于收容输入数据的工作缓冲区、用于提取输入数据的工作缓冲区
用于收容输出数据的工作缓冲区、用于提取输出数据的工作缓冲区
补充
第一章 操作系统的概述
操作系统的概念和功能
概念
负责管理协调硬件、软件等计算机资源的工作
为上层用户、用用程序提供简单易用的服务
是一种软件
功能和目标
资源的管理者
处理机管理
管理器管理
文件管理
设备管理
向上层提供服务
给普通用户
GUI用户界面（程序接口实现的）
命令接口
联机命令接口
脱机命令接口
区别: 联机(交互)命令：用户输入一个命令，操作系统执行一个. ----- 联机(批处理)命令：批量执行多个命令
给程序员
程序接口
即系统调用（部分教材说广义指令）：通过陷入指令(非特权指令，它是一种特殊的指令)让处理器进入内核态，让系统执行对应的指令，再变为用户态，这也是应用程序请求操作系统的唯一办法
对硬件机器的扩展
扩充机器（虚拟机）就是机组里面是3、4、5层 说白了就是为了扩展裸机层次
操作系统的发展与分类
OS的发展与分类
手工操作阶段
缺点：程序员独占主机，导致计算机资源利用率极低
批处理阶段
单道批处理系统
引入脱机输入/输出技术，并由监督程序负责控制输入输出
优点：相较于之前、一定程度缓解了人机速度矛盾、提高了资源利用率
缺点：内存中仅有一个通道、只能在当前程序运行结束、才会执行下一个程序、CPU大部分事件都是在等待I/O完成、资源利用率依然很低
多道批处理系统（操作系统正式诞生）
优点：多道程序并发执行、资源共享、 资源利用率大幅提升
缺点：用户响应时间过长、没有人机交互、用户无法调试程序/在运行过的程序中输入参数
分时操作系统
优点：提供人机交互功能
缺点：不能优先处理紧急任务
实时操作系统
硬实时操作系统
必须在严格的规定时间内完成处理
例如导弹系统
软实时操作系统
能接受偶尔违反时间规定
例如12306
网络操作系统
将网络的计算机结合起来，实现计算机间的通讯和各种资源的共享
分布式操作系统
主要特点：并发性和并行性，任何工作分配在这个系统上、都是由他们协同完成任务
个人操作系统：windows xp macOs
操作系统的特征
并发
并发与并行区别：并发是多个事件同一时间段内发生，并行则是多个事件同时发生
共享
互斥共享技术(如对摄像头的调用)
同时共享方式（如对硬盘资源的共享使用，其实微观上可能是交替访也就是“分时访问”）
虚拟
空分复用技术(如虚拟存储技术)
时分复用技术(如虚拟处理器技术)
异步
关系：并发和共享互相依靠、并发是异步和虚拟的前提、并发和共享是两个最基本的状态
操作系统的运行环境
程序的运行原理
编译
解释
将高级语言转换为机器指令，cpu执行指令的过程就是程序运行的过程
两类程序
内核程序(Kernel)
应用程序
两种指令
特权指令
非特权指令
两种处理器状态
内核态/核心态/管态
用户态
内核
内核(Kernel)是操作系统中最重要的部分
由很多内核程序组成的操作系统内核
如何变态
内核态->用户态
一条修改PSW寄存器状态（1为内核态、0为用户态）的特权指令
用户态→内核态
由中断引起，硬件自动完成，操作系统强制多会处理器控制权（唯一方式）
中断和异常
中断的作用
让操作系统强行夺回处理器控制权
实现并发
让处理器从用户态转变为内核态
中断的类型
内中断（也称异常）：内部引起的
陷阱、陷入（trap）：由陷入指令造成
故障（fault），由错误条件引起
终止（abort），出现致命错误，直接杀死出现错误的程序的进程，例如程序中出现：/0、应用程序直接使用特权指令
外中断：外部引起的
时钟中断
I/O中断
中断机制的基本原理
中断机制的基本实现原理
检查中断信号
内中断：cpu执行指令时会检查是否有异常
外中断：Cpu每执行完指令周期末尾，都会检查是否有中断指令需要处理
找到相应的中断程序
通过‘’中断向量表“实现
只能在核心态下运行的功能：清理内存、置时钟、分配系统资源、修改虚存的段表或页表、系统调用的执行（进程通信、设备、文件、内存管理、进程控制）、I/O指令、存取用于内存保护的寄存器、切换PSW状态.......
系统调用
什么是系统调用
操作系统对应用程序或程序员提供的接口
系统调用与库函数的区别
有的库函数会对系统调用进行封装
有的库函数不会对系统调用进行封装
系统调用是必须的
例如：Wps和Word同时打印
为什么要实现系统调用(凡是涉及到资源共享一定要系统调用)，防止混乱
设备管理
进程管理
进程通信
文件管理
内存管理
系统调用的过程
传参→陷入/访管/Trap指令→由操作系统进入系统态进行系统调用→返回到应用层序
例图
操作系统体系结构
操作系统内核
时钟管理
实行计时功能
中断处理
负责中断机制
源语
是一种特殊程序
处于处于操作系统的最底层，最接近硬件部分
运行时间较短，调用频繁
对系统资源进行管理功能
进程管理
储存器管理
设备管理
大/单/宏内核
将操作系统的主要功能模块作为内核，运行在内核态
优点：高性能
缺点：内核代码庞大且混乱
微内核
只把基本功能作为系统内核，运行在内核态
有点：内核功能模块少而清晰，方便维护
缺点：必然导致多次处理器状态切换，导致性能低
两者实际运行过程实例：
子主题
第二章 进程管理
进程与线程
进程的概念、组成、特征
概念
进程是动态的，是一个程序(程序是静态的，一个文件，这个文件包含很多指令)执行的过程。同一个程序，多次执行，可以有多次进程
进程(实体)的组成
PCB(进程管理块：进程存在的唯一标志)
概念：PCB是进程存在的唯一标志，当进程被创建时，操作系统为其创建PCB，当进程结束后，回收其PCB
进程的描述
进程标识符PID
用户标识符UID
进程控制和管理信息
CPU、磁盘、网络流量使用情况统计.....
进程当前状态：就绪态/阻塞态/运行态.....
资源分配清单
正在使用那些文件
正在使用那些内存区域
正在使用那些I/O设备
处理机相关信息
如PSW、PC等等寄存器的值（用于实现进程的切换）
程序段
程序的代码，特指序列
数据段
运行过程中产生的数据，如：程序中定义的变量
一个进程实体（映像）由PCB、程序段、数据段组成，进程是动态的，进程实体是静态的
程序运行的过程
子主题
TIPS：①进程实体是进程某个状态的一个快照.②进程是进程实体的运行过程，是操作系统进行资源分配和调度的独立单位③PCB是进程存在的唯一标志
进程的特征
动态性
进程是程序的运行过程，动态的产生、变化、消亡
并发性
内存中有多个进程实体，各个进程可并发执行
异步性
进程各自以不可预知的速度进行着，操作系统会提供进程同步机制，来解决异步问题
独立性
进程是能独立运行，独立获得资源，供操作系统调用的基本单位
结构性
每个进程都会分配一个PCB，从结构上看是PCB、程序、数据段
进程的状态、状态转换、组织
三种主要状态
运行态：占据CPU，并在上面运行
就绪态：已经具有运行的所有条件，但是CPU没有空闲，所以需要等待
阻塞态（等待态）：因为等待某一事件而无法运行，自己主动从运行态转换为阻塞态，这个状态前提条件也不再具备
另外两种状态
创建态：进程正在被创建。操作系统正在给他分配资源，创建PCB
结束态：进程从内存中撤下，操作系统回收其资源，消除其PCB
TIP：进程PCB中有一个变量State ，它的值表示的就是 五个状态
状态转换图
子主题
进程的组织
链接方式
子主题
索引方式
子主题
进程控制
什么是线程控制
对进程进行管理，实现线程转换
如何实现进程控制
用"原语"实现
思考：为什么线程转换操作要一气呵成（原语的原子性）
可能导致操作系统的某些关键数据结构信息不统一的情况，这会影响系统进行别的管理工作
如何实现原语的"原子性"
关中断:导致CPU在执行指令周期末期不在检查中断指令，直到执行开中断指令之后才会回复
开中断
例图
思考：如果允许用户程序使用 开、关 中断指令的话会怎么样？
会导致用户程序一直运行在CPU上
进程控制相关的原语
进程创建
创建的原语
申请空白PCB
为新进程分配所需资源
初始化PCB
将PCB插入到就绪序列（创建态→就绪态）
引进进程创建的事件
用户登录
分时系统中，用户登录成功，系统会创立一个新的进程
作业调度（作业：外存的程序 作业调度：将作业放入内存）
多道批处理系统中，有新的作业放入内存，会为其建立一个新的进程
提供服务
用户向操作系统提出某些请求，会创建一个进程，处理该请求
应用请求
用户进程主动请求创建一个子进程
进程终止
撤消原语(就绪态/阻塞态/运行态→终止态→无)
从PCB集合中找到目的进程的PCB
若进程正在运行，立即剥夺CPU，将CPU分配给其他进程
终止其所有子进程
将该进程拥有的所有资源归还给父进程或操作系统
删除PCB
引进进程终止的事件
正常结束:进程自己请求终止（exit指令）
异常结束：整数除以0，非法使用特权指令，最后被操作系统杀死
外界干预:用户自己主动杀死进程
进程的阻塞和唤醒(阻塞和唤醒成对出现)
进程的阻塞
阻塞原语(运行态→阻塞态)
找到进程阻塞的PCB
保护进程的运行现场，将PCB状态信息设置为"阻塞态"，暂时停止进程运行
将PCB插入相应事件的等待队列
引起进程阻塞的事件
需要等待系统分配某种资源
需要等待相互合作的其他进程完成工作
进程的唤醒
唤醒原语(阻塞态→就绪态)
在事件等待队列找到PCB
将PCB从等待序列移除，设置进程为就绪态
将PCB插入就绪队列，等待被调用
引起进程唤醒的事件
等待的事件发生（因何事件阻塞，就会因何事件唤醒，进入到就绪态）
进程的切换
切换原语
将运行环境（PSW、PC、通用寄存器等）信息存入PCB
PCB移入相应队列（老：运行态→就绪态。新：就绪态→运行态）
选择另一个进程执行，更新其PCB
根据PCB恢复进程所需运行环境
引起进程切换的事件
当前进程时间片到了
有优先级更高的进程到了
当前进程主动阻塞
当前进程终止
进程的通信
什么是进程的通信
进程之间的信息交换
通信方式
共享存储（共享区域是互斥的）
基于数据结构的共享：例如：数组 。这种方式限制多，速度慢是一种低级存储方式
基于存储区的共享：在内存中画一个存储区。由进程控制，与上面相比，这个方式更快，是一种更高级的存储费那事
消息传递：进程间的信息交换以格式化的信息为单位，进程通过操作系统提供的“提供信息/回复信息”两个原语进行数据交换
直接通信方式
消息会直接放入消息缓冲队列
子主题
间接通信方式
消息放入到消息信箱中，在通过发送/接受 原语获取
子主题
管道通信：其实就是一个连接读写进程的文件，它是一种在内存中的开辟了大小固定的缓冲区
特点
管道只能是半双工的，也就是单一时间内只能单方向传送数据
管道是互斥的
数据以字符流的形式进入管道，到管道满了，写进程的Write()系统调用被阻塞，等待管道内的数据变空，当管道空了，读进程的Read()会阻塞
如果没空 不允许写，若不满，不允许读
数据一旦被读出，就从管道被抛弃，为了防止数据被读错，所以读进程必须只有一个
线程、多线程模型
线程概念、属性、带来的变化
概念
可以理解为轻量级进程，
是一个基本的CPU处理单位，也是程序流的最小单位
引入线程后，进程只作为除CPU之外的系统资源的分配单元，如：打印机...
带来的变化
资源分配、调度
传统进程机制中、进程是资源分配、调度的基本单位
引入线程后，进程是资源分配(CPU外部)的基本单位，线程是调度的基本单位
并发性
传统进程机制中，只能进程间并发
引入线程后，各个线程间也能并发，提升了并发度
系统开销
传统的进程间并发，需要切换进程的运行环境，系统开销很大
线程间并发，若果是同一进程内的线程切换，则不需要切换进程环境，系统开销小
引入线程后，并发所带来的的系统开销减小
线程的属性
线程是处理机调度的单位
多CPU计算机中。各个线程可占用不同的CPU
每个线程都有一个线程ID、线程控制块（TCB）
线程也有就绪、阻塞、运行三种基本状态
线程几乎不占有系统资源
同一进程的不同线程间共享进程的资源
由于共享内存地址空间，同一个进程中的线程通信无需操作系统插手
同一进程的线程切换不会引起进程切换
不同进程中的线程切换，会引起进程切换
切换同进程内的线程，系统开销小
切换进程，开销大
线程的实现方式
用户级线程
用户级线程由线程库实现，管理
线程切换在用户态下即可完成
例图
操作系统看不见线程，只看得见进程，用户级线程只能被用户看见
优点
用户级线程的切换在用户空间即可完成，不用切换到核心态，线程管理开销小，效率高
缺点
当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高，多个线程不可以在多个处理机上并行运行
内核级线程
内核级管理工作有操作系统管理
线程调度和切换都有内核负责，都必须进入到内核态下完成
例图
操作系统为每一个线程创建一个线程控制块TCB，此线程只可以被操作系统看到
优点
当一个线程被阻塞的时候，别的线程可以继续运行，他们相互独立，可在多核处理器并行
缺点
一个用户进程会占用多个内核级线程，线程切换有操作系统进入到内核态完成，管理成本高，开销大
多线程模型
一对一模型
优点
当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机并发执行
缺点
一个用户进程会占用多个内核级线程，线程切换有操作系统进入到内核态完成，管理成本高，开销大
例图
子主题
多对一模型
优点
用户级线程的切换在用户空间即可完成，不用切换到核心态，管理开销小，效率高
缺点
当一个用户线程被阻塞后，整个进程都会被阻断，并发度不高，多个线程不可在多核处理机并行运行
例图
子主题
多对多模型
例图
子主题
补充：线程才是处理器分配到最小单位，一个核跑一个线程，如上图
重点：能被分配的只有内核级线程，它才是处理机分配，调配的单位，也就是说，在进程里面的内核级线程可以并发的跑起来，而多对一这样的，用户级线程只是一种用户看到简单的“线程”，并不是处理机分配，调配的单位
子主题
处理机调度
处理机调度概念，层次
调度的概念
按照某种算法从就绪队列中选择一个进程为其分配处理机
调度的层次
高级调度(作业调度)
按一定原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB
中级调度(内存调度)
当内存不够时，操作系统会将进程调出到外存。等内存空闲或者进程需要进行时，在重新调入到内存。暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列，中级调度(内存调度)就是按照某种策略决定将那个处于挂起状态的进程重新调入内存，注意：一个进程可能会被多次调出。调入内存，因此中级调度发生的频率比高级调度要高
低级调度(进程调度/处理机调度)
按照某种策略从就绪队列中选取一个进程，将处理机分配给它，进程调度时操作系统最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次
补充：进程挂机态和七状态模型
挂起状态分类
就绪挂起
阻塞挂起
七状态模型，就绪状态和就绪挂起的区别
三种状态的联系和对比
进程调用的时机切换与过程调度方式
什么是进程调度
低级调度
按照某种算法从就绪队列中选择一个进程为其分配处理机
进程调度的时机
什么时候需要进程调度
当前运行进程主动放弃处理机
进程正常终止
运行过程中发生异常而终止
进程主动请求阻塞（如：等待I/O完成）
当前运行进程被动放弃处理机
分给进程的时间片用完
有更紧急的事情要处理 (I/O中断)
有更高优先级的进程进入就绪队列
什么时候不能进行进程调度
处理中断的过程中，这个过程复杂且与硬件密切相关，就很难做到一边处理中断，一边进行进程切换
进程在操作系统内核程序临界区
在原语操作过程中，原子操作不可中断，要一气呵成（如：上一小节讲述的PCB的状态切换）
临界
临界资源
一个时间段只允许一个进程使用的资源。各进程互斥地访问临界资源
临界区
临时访问临界区资源的那些代码
进程在操作系统内核程序临界区中不能进行进程调度和切换
例如：进程进入到内核程序临界区中访问就绪队列的时候，操作系统会给就绪队列资源上锁（保证互斥性，只有当前的交互进程可以访问） ，这个时候是不可以进行进程调度，因为你的进程还内核程序临界区内，就绪队列还在上锁，所以这个访问内核程序临界区的过程很快完成否则极有可能影响到操作雄的其他管理工作，也因此表明了，访问内核程序临界区期间不可以进行调度和切换
进程在操作系统非内核程序临界区中能进行进程调度和切换
例如：进程访问打印机的时候，打印机会被上锁，由于打印机对于CPU来说是慢速设备，此时如果一直保持，则会让CCPU一直保持空闲状态，而且PCB状态序列也没有被锁住，所以我们可以进行进程调度和切换，当前进程进入阻塞状态，让其他进程和我们并发运行。所以这表明 访问不同临界区时，不会直接影响到系统内核的管理工作，因此可以进行进程的调度和切换
进程调度的方式
非剥夺式调度方式(非抢占式)
只允许进程主动放弃处理机，当运行过程中有更紧急的任务到来时，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态
实现简单，系统开销小但是无法即使的处理紧急任务，适用于早期的批处理系统
剥夺式调度方式(抢占式)
当一个进程正在处理机上运行，如果有个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要的那个进程
可以优先处理更紧急的进程，也可以实现各进程哪找时间片轮流执行功能（通过时间中断）。适合分时操作系统，实时操作系统
进程调度的切换过程
"狭义的调度"与"切换"的区别
狭义的调度：指定是从就绪队列选中一个要运行的进程(这个进程可以是刚刚被暂停执行的进程,也可能是另一个进程，后一种就需要进程切换）
进程切换：指定一个进程让出处理机，让另一个进程占用处理机的过程
广义的进程调度：调度包含了狭义的调度和进程切换的过程
进程切换的过程需要做什么
对原来的进程的各种数据保存→对新的进程各种数据的回复(如：程序计数器，程序状态字，各种数据寄存器等处理机现场信息，这一信息一般保存在进程控制块)
注意：进程切换是有代价的，因此如果过于频繁的进行现场调度、切换，必然会让整个系统效率低下
调度算法的评价指标
CPU利用率:CPU忙碌时间站总时间的比例
系统吞吐量：单位时间完成作业数量
周转时间：从作业被提交给系统开始，到作业完成为止的这段间隔时间
等待时间：指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低
响应时间：指从用户提交请求到首次产生响应所用的时间
具体事例
调度算法
先来先服务(FCFS)
算法思想
主要从"公平"的角度考虑
算法规则
按照作业/进程到达的先后顺序进行服务
用于作业/进程调度
用于作业调度时，考虑的是哪个作业先到达后备(外存)队列；用于进程调度时，考虑的是哪个进程先到达就绪队列
是否可抢占
非抢占式算法
优缺点
优点
公平，算法实现简单
缺点
排在长作业(进程)后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即FCFS算法对长作业有利，对短作业不利
是否导致饥饿（某进程/作业长期得不到服务）
不会
实例
最短作业优先（SJF）
算法思想
追求最少的平均等待时间，最少的平均周转时间，最少的平局周转、平均带权周转时间
算法规则
最短的作业/进程优先得到服务(所谓"最短",是指要求服务时间最短)
用于作业/进程调度
即可用于作业调度，也可用于进程调用。用于进程调度时称为“短进程优先算法(SPF)”
是否可抢占
SJF和SPF是非抢占式的算法。但是也有抢占式的版本--最短剩余优先算法SRTN
优缺点
优点
公平，算法实现简单
缺点
排在长作业(进程)后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即FCFS算法对长作业有利，对短作业不利
是否导致饥饿（某进程/作业长期得不到服务）
会，一直输送短作业进程，导致长进程一直访问不到，导致饥饿
小细节
若题目未说明。那么所提到的"短作业/进程优先算法"默认是非抢占的
实例
非抢占式SJF
子主题
抢占式最短作业优先（SRTN）
子主题
实例
很多书上会说：SJF调度算法的平均等待时间,平均周转时间最短，严格意义来说这不严谨，上面两个例子已经证明了，应该这样说：①在所有进程同时可运行时，采用SJF调度算法的平均扥大概时间，平均周转时间最短。②在所有进程几乎同时到达时，采用SJF调度算法的平均扥大概时间，平均周转时间最短。③抢占式的短作业/进程优先算法(最短剩余时间优先，SRNT算法)的平均等待时间，平均周转时间最少
虽然SJF最短优先算法不一定是最短的，但相比于FJFS先来先服务算法，HRRN最高响应比优先算法，依然可以获得较少的平均等待时间、平均周转时间
最高响应比优先（HRRN）
算法思想
综合考虑作业/进程的等待和要求被服务时间
算法规则
每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。响应比=(等待时间+要求服务时间)/要求服务时间
用于作业/进程调度
即可用于作业调度，也可用于进程调用。
是否可抢占
非抢占式的算法。因此只有当前运行作业/进程主动放弃处理机时，才需要调度，才需要计算响应比
优缺点
优缺点
综合考虑了等待时间和运时间(要求服务时间)，等待时间一样时，要求服务时间最短的优点(SLF的优点)，要求服务的时间一样时，等待时间长的优先(FCFS的优点)
实例
FCFS、SJF、HRRH总结
时间片轮转调度算法(RR)
算法思想
公平的、轮流的为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则
按照个进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，若进程未在一个时间片内执行完成，则剥夺处理机，将记录运行环境，重新放到就绪队列对位重新排队
用于作业/进程调度
用于进程调度，因为只有作业进入到内存，建立对应的进程后，才能被分配处理机时间片
是否可抢占
若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转算法属于抢占式算法。由时钟装置发出时钟中断来通知CPU时间片已到
优缺点
优点
公平，响应快，适用于分时操作系统
缺点
由于高频的进程切换，因此一定开销：不区分任务的紧急程度
是否导致饥饿
不会
补充
若时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法会退化为先来先服务算法(例如：当前有是个进程在并发执行，若时间片为1秒，这一个进程被响应可能就会要9秒，也就是说，用户在这个进程交互时，需要等9秒)，并且会增加进程响应时间()，因此时间片不能太大
若时间太小，会导致进程切换和调度(进程的调度与切换也是需要时间开销的)过于频发，导致实际处理机处理时间占比变小
实例
优先级调度算法
算法思想
随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
算法规则
每个作业/进程有各自的优先级，调度室选择优先级高的作业/进程
用于作业/进程调度
即可用于作业调度，也可用于进程调度。甚至，还会用于I/O调度
是否可抢占
抢占式、非抢占式都有。做题的区别在于：非抢占式秩序在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占
优缺点
优点
用优先级区分紧急程度、重要程度，使用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度
缺点
若源源不断的有高优先级的进程到来，则可能导致饥饿
是否导致饥饿
会
补充
就绪队列未必只有一个，可以按照不同优先级组织。另外，也可以把优先级高的进程排在更靠近对头的位置，方便调度
优先级类型
静态优先级
创建进程后，无法改变
动态优先级
创建进程时有一个初始值，之后可以根据情况动态的调整优先级
如何合理的设置各类进程的优先级
系统进程优先级高于进程用户
前台进程优先级高于后台进程
操作系统更偏好I/O型进程（I/O繁忙型进程，与其相对的是计算型进程（CPU繁忙型进程））,原因是I/O设备和CPU可以并行工作。如果优先让I/O繁忙类型进程优先运行的话，就越可能让I/O设备尽早的投入工作，则资源利用率，系统吞吐量都会得到提升
如果采用动态调整的优先级，应该在什么时候调整
考虑整体平衡性，追求公平，合理利用资源考虑。如果在就绪队列中等待了时间很长时，则考虑适当提升其优先级。如果某进程占用处理机运行很长时间，则可适当降低其优先级(类似HRRH高性价比算法)
实例
抢占式
非抢占式
多级反馈队列调度算法
算法思想
对上述其他调度算法的折中权衡
算法规则
1.设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。2.新进程到达时先进入第1级队列，按FCFS原则排队对等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。若此时已经是最下级队列，则重新放回该队列队尾。3.只有第K级队列为空时，才会为K+1级队头分配时间片
用于作业/进程调度
用于进程调度
是否可抢占
可抢占式，在K级队列的进程运行过程中，若更上级队列(1~k-1级)中进入一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回K级队列队尾
优缺点
优缺点
对各类型进程都相对公平点(FSFC)；对每个新到达的进程都可以很快的得到响应(RR的优点)；短进程只用较少的事件就可完成(SPF的优点)；不必实现估计进程的运行时间(避免用户作假)；可灵活的调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程(拓展：可以将因I/O阻塞的进程重新放原队列，这样I/O型进程就可以保持较高优先级了)
是否导致饥饿
会，因为当你一直不断输入短进程任务，低级的队列将会一直饥饿
实例
子主题
时间片轮转(RR)、优先级、多级反馈队列调度算法总结
进程同步
进程同步、互斥问题
什么是进程同步
进程具有异步性(进程各自独立、按照自己的速度执行)，但是很多情况需要进程同步，例如：进程通信-管道通信：输入、输出进程一定是并发的且要按照"输入→输出"的进程顺序执行，如何来解决这个问题？通过进程的同步：进程的同步就是为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置协调他们的工作次序而产生的的制约关系。进程间的直接制约关系就是源于他们之间的相互合作
什么是进程互斥
对于临界资源的访问，需要互斥的进行。进程互斥：互斥也称间接制约关系，它是指同一时间内只允许一个进程访问该资源，必须等待当前正在访问进程结束后，才可以访问
临界资源的四个区
进入区(entry section)
检查是否可进入临界区。若可进入，则应设置正在访问临界资源标志(可理解为“上锁”)，以阻止其他进程同时进入临界区
临界区(critical section)
访问临界资源的那段代码
退出区(exit section)
负责解除正在访问临界资源的标志(可理解为“解锁”)
剩余区(remainder section)
作其他处理
注意：①临界区是进程中访问临界资源的代码段。②进入区和退出区是负责实现互斥的代码段。③临界区也可称为临界区
进程互斥原则
空闲让进
临界区空闲时，应允许一个进程访问
忙则等待
临界区正在被访问时，其他试图访问的进程需要等待
有限等待
要在有限的时间内进入临界区，保证不会饥饿
让权等待
进不了临界区的进程，要释放处理机，防止忙等，一直让处理机等待着
进程互斥的软件实现方法
单标志法
算法思想
两个进程在访问完临界区后会把临界区的权限转交给另一个进程。也即是 每个进程进入临界区的权限只能被另一个进程赋予
具体事例
主要缺陷
只能按p0→p1→p0......这样轮流访问访问，如果此时允许进入临界区的进程是p0，而p0一直不去访问临界区(不回去谦让)，那么虽然此时临界区空闲，但是并不允许p1访问，违反了空闲让进
双标志先检查法
算法思想
设一个布尔型数组flag[]，数组中各个元素用来标记个进程想进入临界区的意愿，比如“flag[0]=true”意味着0号进程p0现在想进入到临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，这把自身对应的标志flag[i]设为true，之后在访问临界区
实例
主要缺陷
若按照1,5,2,6,3,7的顺序执行，p1和p0同时访问临界区，因此，双标志先检查法的主要问题是违反了“忙则等待”原则 ，原因在于，进入区的检查和上锁 两个操作不是一气呵成的。检查后上锁钱可能发送进程切换
双标志后检查法
算法思想
双标志先检查的缺点在于无法将上锁和检查的操作一气呵成，因此导致了两个进程同时访问临界区的问题，因此我们引申出了向先上锁，再检查(保证赋完值在来检查)，避免上述问题
实例
主要缺陷
若按照1,5,2,6的顺序执行，p0和p1都无法访问临界区，因此双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各个进程都长期无法访问临界资源而产生饥饿现象
Peterson算法
算法思想
结合双标志法，单标志法的思想。如果双方都争着进入临界区，那就可以让进程尝试“孔融让梨”
实例
Tips：可以理解为每个进程都在主动争取→主动谦让→检查对方是否想进入、己方是否谦让，若两个进程都在互相谦让，那么谁最后说了谦让的话，谁就后执行
主要缺陷
遵循了空闲让进、忙则等待、有限等待(双方谦让，谁最后一个谦让，谁做倒霉蛋)三个原则，但是依然未遵循让权等待原则
进程硬件的互斥方法
中断屏蔽指令
使用“开/关中断”（使用开中断后不允许中断，也就不会发生进程切换，也就不可能发生两个进程同时访问一个临界区）指令实现
优点：简单、高校
缺点：不适用于多处理机，只适用于操作系统内核，不适用于用户进程(因为开关中断指令只可以在内核态进行)
TestAndSet(TSL/TS)指令
old记录是否已经被上锁；再检查lock设为true；检查临界区是否已经被上锁(若已上锁，则循环重复前几步)
优点：相较软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成一气呵成的原子操作，实现简单，适用于多处理机环境
缺点：不满足让权等待，会一直停留在“检查”代码
实例
Swap指令(XCHG/exchange指令)
逻辑上与TSL一样
优点：相较软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成一气呵成的原子操作，实现简单，适用于多处理机环境
缺点：不满足让权等待，会一直停留在“检查”代码
实例
信号量机制(解决“检查”“上锁”操作无法一气呵成和无法实现“让权等待”的机制)
概念
①信号量就是一个变量(可以是整数，也可以是复杂的记录型变量)，可以用一个信号量来表示系统某种资源的数量，例如：系统只有一个打印机，就可以设置一个初值为1的信号量。
②原语是一个特殊的程序段，他通过开关中断实现（不可打断），如果把进入区、退出区都用原语实现，这样就解决了“一气呵成”的问题
③使用wait(s)和signal(s)原语，也称为P,V原语，一般做题写作P(S）、V(S),相当于函数，其中的S就是信号量
整形信号量
用一个整数型变量作为信号量，数值表示资源数
整形信号量和普通的信号量的区别是：对信号量的操作只能是 初始化，P，V操作
实例
存在的问题
由于只要等不到资源（s>0）的时候，他就会一直在处理机上运行，导致出现“让全等待”的问题
记录型信号量
为了解决整形信号量的问题（忙等），人们提出了记录型信号量
实例
总结
考题一般没有特别声称，wait(s)、signal(s)也可称为P(S)，V(s)，他们就是记录型信号量，可以用来“申请”和“释放”
S.value表示当前资源数量（<=0表示当前还有其他进程在阻塞队列中等待资源）
P操作中，一定是先S.value--，之后再去检查，是否去做block原语（当前资源不够，将进程从运行态进入到阻塞态，直到被唤醒）
V操作中，一定是先S.value++，之后可能需要执行wakeup原语（当前判断表示还有进程等待资源，则使用wakeup原语，将其从阻塞态变为就绪态）
记录型信号量可以实现系统资源的“申请”和释放
记录型信号量可以实现进程互斥、同步
等待队列：可以让阻塞的进程排队
用信号量机制实现进程互斥、同步、前驱关系
实现进程互斥
分析问题,确定临界区
设置为互斥信号量(mutex)，初值为1
临界区之前对信号执行P操作
临界区之前对信号执行V操作
图例
实现进程同步
分析问题，找出那里需要实现“一前一后”的同步关系
设置同步信号量，初始值为资源数
在“前操作”之后执行V操作
在“后操作”之后执行P操作
图例
实现进程的前驱关系
分析问题，画出前驱图，把每一个关系都看成一个同步问题
为每对前驱关系设置同步信号量，初值为0
前V后P
在每个“前操作”之后执行V操作
在每个“后操作”之后执P操作
具体事例
PV操作题目解题思路
1.关系分析。找出题目中描述是各个进程，分析他们之间的同步、互斥关系
2.整理思路。根据各个进程的操作流程确定P、V操作的大致顺序
3.设置信号量。设置需要的信号量，并根据题目条件确定信号初值。(互斥信号初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)
生产者、消费者问题
子主题
思考：能否改变PV操作的顺序
补充：①其中增加一个产品，使用产品都可以加入到临界区，但是这样会增加访问临界区的访问时间，会导致整体效率降低②实现互斥和实现同步的两个P操作的先后顺序（互斥的P操作必须在同步的P操作后，否则会导致死锁问题，上面的实例有）
多生产者、多消费者问题
可不可以不使用互斥信号量
当缓存区为2时
会出现互斥资源被共享的问题
子主题
当缓存区为1时
子主题
总结
在生产者-消费者问题在，若果缓存区大小为1，那么优肯不需要设置互斥信号量就可以实现互斥访问缓存区的功能，但是这不绝对，所以我们自己写题，需要时就用上互斥信号量
不要去思考单个进程行为，要去思考进程抽象出来的时间，例如上述，儿子 女儿进程都会导致盘子（缓存区）变空，让父母，从而导致父母去放水果，这样就会出现四个一前一后关系了，我们应该去思考“事件的前后关系”儿子，女儿进程都会做的一个是事情就是让盘子变空：也就是盘子变空事件；而父母都会去放入水果：也就是放入水果时间。说白了就是 进程都要做到是行为，抽象出来就是事件
吸烟者问题
总结
吸烟者问题为我们解决“可以生成多个产品的单生产者问题”
轮流提供服务，使用一个整形变量I实现“轮流”这个过程
读者-写者问题
但是这样出现一个问题，那就是读进程优先(因为只要有读进程count一直在增加，那么就不会出现count=0时，执行V（解锁资源操作）)
解决办法
总结
核心思想
设计了一个count计数器用来记录当前正在访问共喜爱那个文件的读进程数。我们可以用count的值来判断当前进入进程是否是第一个/最后一个进入进程的。从而做出不同的处理
对count变量的检查和赋值不能一气呵成
使用互斥信号量
写进程饥饿问题（读进程优先）
使用了P(w)操作
哲学家进餐问题
问题描述和解析
子主题
引起的问题“死锁问题”
解决办法
③当且仅当一个哲学家两边筷子都可以用是才允许他抓取筷子（更准确的说法在后面）
总结
每当之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程需要同时持有两个临界资源，因此就会有“死锁”的问题的隐患
如果在考试遇到一个进程同时持有多个临界资源的情况，应该参考哲学家问题，分析是否会有循环等待，死锁问题
管程
为什么要引入管程
解决信号量机制编程麻烦，易出错问题
管程的定义和基本特征
组成
共享数据结构
对数据结构初始化的语句
一组用来访问数据结构的过程（函数）
基本特征
各个线程/进程只能通过管程提供的特定“入口”才能访问共享数据
每次仅允许一个进程在管程内执行某个过程
补充
各个进程必须互斥访问到的特性有编译器实现
可在管程中设置条件变量及等待唤醒操作来解决同步问题
拓展1：用管程解决生产者消费者问题
拓展2：JAVA中类似管程的机制
死锁
死锁的概念
什么是死锁
各进程互相等待对方手里的资源，导致各进程无法向前推进
死锁、饥饿、死循环的共同点和区别
共同点
都是无法顺利向前推进的现象(故意设计的死循环除外)
区别
死锁一定是“循环等待对方手里资源”导致的，因为如果有死锁现象，那至少有两个或两个以上的进程同时发生死锁。此外发生死锁的进程一定处于阻塞态，这里等待的是临界资源例如IO，打印机而不是cpu，所以不会是就绪态
长期得不到想要的资源(IO,打印机，处理器等)。可能只有一个进程发生饥饿。发生饥饿的进程姐可能是阻塞态(如长期等待IO设备)，也可能是就绪态(长期得不到处理机)
可能只有一个进程发生死循环。死循环可以在处理机上运行(可以是运行态)，只不过不一定可以顺利运行，死锁和饥饿问题是由操作系统的分配资源的不合理导致的，死循环则是代码逻辑有问题
死锁和解是操作系统要解决的问题，死循环是应用程序员解决的问题
死锁产生的必要条件
互斥条件
只对互斥资源的争抢才会出现死锁
不剥夺条件
进程所获得的资源未使用完成时，不可以由其他进程抢夺资源
请求和保持条件
进程已经获得了至少一个资源，但又提出新的资源请求，而该资源又被其他进程占有，此时进程被堵塞，但是对自己所占有的资源保持不放
循环等待条件
存在一种进程资源的循环等待链，链中每一个进程已获得资源且被下一个进程请求
注意：发生死锁时，一定有循环等待；但发生循环等待时未必发生死锁
图例
总结：如果同类资源树大于1，则即使有循环等待，也未必会发生死锁。但如果系统中每类资源都只有一个，那循环的古代就是死锁的充分必要条件
什么时候会发生死锁
对不可剥夺资源的不合理分配，可能导致死锁
对系统资源的竞争，各进程对不可剥夺的资源（如打印机）会产生死锁，但可资剥夺源（cpu）的进程不会引起死锁
进程推进非法.请求和释放资源顺序不当
信号量使用不当也会造成死锁，例如：消费者的互斥和同步P操作先后顺序
死锁的处理策略
预防死锁
破坏死锁的四个必要条件
避免死锁
避免系统进入不安全状态(银行家算法)
死锁的检测和解除
允许死锁发生，系统负责检测出死锁并解除
死锁的处理
不允许死锁发生
静态策略：预防死锁
破坏互斥条件
将互斥资源变成不互斥资源
缺点：可行性不高，很多时候操作系统为了保证安全，很多资源不允许这样
破坏不剥夺条件
方案一：申请的资源得不到满足时，立即释放拥有的所有资源
方案二：申请的资源被其他进程占用时，由操作系统协助剥夺(根据优先级)
缺点：①实现复杂；②如方案二剥夺了资源可能导致部分工作失效；反复申请和释放导致系统开销大②如方案一，得不到就一直放弃，可能会导致饥饿
破坏请求和保持条件
运行前分配好所有需要的资源，之后一直保持
缺点：资源利用率低；可能导致饥饿，例如：一个进程用的资源1只用2秒，而这个进程却运行50秒，造成长时间的空闲，还会让其他需要资源1的进程饥饿
破坏循环等待条件
给资源编号，必须按编号从小到大的顺序申请资源
缺点：增加新设备不方便；会导致资源浪费(要先用大进程，就必须把无关的小进程申请/访问)；用户编程麻烦(不同的机子，编号不同，就要对待更改操作)
动态策略：避免死锁
什么是安全序列
如果系统按照一种序列分配资源，则每个进程都会顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个
什么是系统的不安全状态，与死锁有何练习
若系统找不到一个安全序列，系统就进入不安全状态。当然，若有进程现在归还了资源，系统有可能重回安全状态
若系统处于安全状态，那么一定不会发生死锁（当前已经分配完资源）。如果系统进入不安全状态(当前并没有分配资源)，就可能发生死锁（处于不安全状态可能发生死锁，发生了死锁一定处于不安全状态）
在系统资源分配之前先判断这次是否会导致系统进入不安全状态，这也是银行家算法的核心
如何避免系统进入不安全状态-银行家算法
核心思想
在系统资源分配之前先判断这次是否会导致系统进入不安全状态，若会进入不安全状态，就暂时不打印这次请求，让进程阻塞等待
手算步骤
PPT
算法步骤
数据结构
检查此次申请是否超过了之前声明的最大需求数
检查此时系统剩余的可用资源是否还能满足这次请求
试探分配(逻辑分配)，更改数据结构
用安全性算法检查此次分配是否会导致系统进入不安全状态，若安全则分配，不安全数据回溯，当前进程阻塞等待
安全性算法
检查当前可用剩余资源是否满足某个进程的最大需求，若果可以，把它加入安全序列，并把该进程持有的资源全部回收
不断银行家→安全性算法的过程，看最终是否将所有进程都加入到安全序列
允许死锁发生
死锁的检测和解除
死锁的检测
数据结构：资源分配图
两种节点
进程节点
资源节点
两种边
进程节点→资源节点(请求边)
资源节点→进程节点(分配边),表示当前资源已经被分配
死锁检测算法(有可能和数据结构一起考察)
依次消除与不阻塞进程相连的边，直到无边可消除(可完全简化图)
注：所谓不阻塞进程是指其申请的资源数还足够的进程
死锁定理：若资源分配图是不可完全简化的，说明发生了死锁
例子
死锁的解除
资源剥夺法
挂起（到外存）进程，抢占其资源，将其资源分配给其他死锁进程，但是也要防止这个被挂起进程长期得不到资源导致饥饿
撤销进程法(终止进程法)
强制撤销部分、设置全部死锁进程，剥夺其资源，这种方式实现简单，但所付出的代价可能很大，因为有些进程可能运行了好久，接近结束了，一旦强制撤销，又得重新再来
进程回退法
让一个或多个死锁进程回退到足以避免的地步，这要求操作系统记录进程的历史信息，设置还原点
如何决定对谁动手
进程优先级
已执行时间、
还要多久完成
进程使用多少资源
进程是交互还是批处理式的
第三章 内存管理
内存的基础知识
什么是内存，有何作用
存储单元，内存地址 的概念和联系
按字节编制vs按字编址
图例
进程运行的基本原理
指令工作原理
操作码+若干参数（可能包含地址参数）
逻辑地址VS物理地址
逻辑地址(相对地址)vs物理地址（绝对地址）
从写程序到程序运行的过程
编辑源代码文件
编译
由源代码文件生成目标模块（将高级语言翻译成机械语言）
链接
将目标模块生装入模块，链接后生成完整的逻辑地址
装入
将装入模块装入内存，装入后(根据不同的装入方式)形成物理地址
图例
三种链接方式
静态链接
装入前链接成一个完整的装入模块
装入时动态链接
运行前边装入边链接
运行态动态链接
运行时需要目标模才装入并连接
三种装入方式
绝对装入（单道装入阶段，这个阶段还没有操作系统，所以这个过程是由编译器完成）
编译时产生绝对地址
静态重定位/可重定位装入（用于早期的多道批处理系统）
装入时将逻辑地址转换为物理地址
动态重定位/动态运行时装入(现代操作系统)
运行时讲逻辑地址转换为物理地址，需设定重定位寄存器
内存管理的概念
内存的分配和回收
内存空间的扩充
地址转换
操作系统负责实现逻辑地址到物理地址的转换
三种方式
绝对装入：编译器负责地址装换（单道程序阶段，无操作系统）
可重定位装入：装入程序负责地址装换（早期多道批处理系统）
动态运行装入:运行时才进行地址转换（现代操作系统）
存储保护
保证各个进程在自己的内存空间内运行，不会越界访问
两种方式
设置上下限寄存器
利用重定位寄存器、接地址寄存器进行判断
内存管理
内存的扩充
覆盖技术
一个固定区
存放最活跃的程序段
固定区中的程序在运行时不会调入调出
若干个覆盖区
不可能同时被访问程序段可共享一个覆盖区
覆盖区中的程序段在运行过程中会根据需要调入调出
必须由程序员声明覆盖结构，操作系统完成自动覆盖
缺点：对用户不透明，增加了用户负担
图例
交换技术
内存紧张时换出某些进程以腾出内存空间，再换如某些进程
磁盘分为文件区和对换区，换出的进程放在对换区
引申问题：调出的外存放在那里；什么时候进行交换；应该换那些进程
TIPS:PCB会常驻内存，不会被换出外存，因为需要作为调回凭证放入挂起序列
虚拟存储技术
本章节省略，下个章节详述
覆盖和交换点区别
覆盖是在同一个程序或者进程中的
交换实在不同进程（作业）之间的
内存的分配和回收
连续分配管理内存
单一连续分配
概念
支持多道程序；在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统给的相关数据；用户区用于存放用户进程的相关数据，内存中只能有一道用户程序，用户程序独占整个用户区空间
例图
优缺点
优点
实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护(例如早期的操作系统MS-DOS)
缺点
只能用于单用户、单任务的操作系统；有内部碎片(分配给进程但是进程未完全利用空闲的内存空间)；存储器利用率极低
固定分区分配
概念
将整个用户区划分为若干个固定大小的分区，在每个分区中只装入一道作业
分区方式
分区大小相等
图例
优缺点
缺乏灵活性，但是很适合用于一台计算机控制多个相同对象的场合
分区大小不等
图例
优缺点
增加了灵活性，可以满足不同大小的进程需求。根据常在系统运行的作业大小进行划分
分区说明表
来实现各个分区的分配和回收。每个表对应着一个分区，通常安分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否以及分配）
图例
子主题
优缺点
优点
实现简单，无外部碎片
缺点
当前用户程序太大时候，可能所有的分区都不能满足，此时不得不才去覆盖技术来解决，但这又会降低性能；会产生内部碎片，内存利用率低
动态分区分配
概念
也称为可变分区分配，这个分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态的建立分区，并使分区大小正好适合进程的需要。因此系统分区的大小和数目是可变的
引申问题
系统采用什么样的数据结构记录内存使用情况
两种常用的数据结构
空闲分区表
空闲分区链
图例
子主题
系统如何进行内存的分配和回收
分配
在已空闲的内存，分配比当前更小的进程
分配一个与进程所需内存大小相同的内存
回收
回收后面有相邻的空闲分区
回收区前面有相邻的空闲分区
回收区前后都有相邻的空闲分区
回收区前后都没有相邻的空闲分区
TIPS：各个表的顺序不一定按照地址递增顺序排列，具体怎么排列按照动态分区分配算法来确定
内部和外部碎片
内部碎片
分配给某个进程的内存区域，有些部分没有用上
外部碎片
内存中某些空闲分区由于太小难一利用
当我们的内存外部碎片大小之和可以运行一个进程，我们可以通过紧凑的方法来解决
子主题
TIPS:连续分配是指为用户分配一个连续的存储空间
无内部碎片，有外部碎片
动态分区分配算法
首次适应算法
算法思想
从头到尾找适合的分区
分区排列顺序
空闲分区以地址递增次序排列
优点
综合看性能是最好的。算法开销小，回收分区后一般不要对空闲分区重新排列
最佳适应算法
算法思想
优先使用更小的分区，以保留更多大分区
分区排列顺序
空间分区以容量递增次序排列
优点
会有更多的大分区被保留下来，更能满足大进程需求
缺点
会产生很多太小的，难以利用的碎片；算法开销大（因为会需要分配玩调转分区顺序）回收分区后可能对空闲分区队列重新分配
最坏适应算法
算法思想
优先使用更大的分区，以防产生太小不可用的碎片
分区排列顺序
空闲分区以容量递减次序排列
优点
可以减少难以利用的小碎片
缺点
大分区容易被用完。不利于大进程；算法开销大（原因和最佳适应算法一样）
邻近适应
算法思想
由首次适应演变而来，每次从上次查找到位置继续查询
分区排列顺序
空间分区按照地址递增次序排列（可排列成循环队列）
优点
不用每次都从用不到的低地址小分区开始检索，算法开销小(原因和首次适应算法的原因类似)
缺点
会使高地址的大分区也被用完（原因和最坏适应算法一样）
图例
见官方ptt
非连续分配管理方式
TIPS：为用户分配的可以是一些分散内存空间
基本分页存储管理
分页存储的概念
页框和页框号
将内存分为一个个大小相等的分区,每个分区就是一个“页框”(页框=页帧=内存块=物理块=物理页面）。每个页框都有一个编号，即“页框号”（页框号=页帧号=内存块号=物理块号=物理页号），页框号从0开始
页面和页号
将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个“页”或“页面”。每个页面都有一个编号，即为“页号”，页号也是从0开始
关系
操作系统以页框的为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框。也就是说，进程的页面与内存大页框一一对应。且各个页面不必连续存放，可以放入不相邻的各个页框
图例
操作系统如何记录这种关系？
页表
为了知道进程每个页面在内存存放的位置，操作系统要为每个进程建立一张页表。注：页表一般存放在PCB
一个进程对应一张页表
进程每个页面对应一个页表项
每个页表项由“页号”和“块号”组成
页表记录进程页面和实际存放的内存快之间的映射关系
图例
每个页表项多大？占多少字节
注意：页表记录的只是内存块号，而不是内存的其实地址！！！，J号内存块的起始地址=J（内存块号）*内存快大小
如何通过页表实现逻辑地址到物理地址的转换
确定逻辑地址A的对应的“页号”P
找到P号页面在内存中的其实地址（需要查找页表）
确定逻辑地址A的“页内偏移量”W
逻辑地址A对应的物理地址=P号页面在内存中的起始地址+页内偏移量W
引申问题
如何确定一个逻辑地址对应的页号、页内偏移量？
基本地址变换机构
页表寄存器的作用
存放页表起始地址
存放页表长度
地址变换过程
根据逻辑地址算出页号，页内偏移量
页号的合法性检查（与页表长度对比）
若页号合法，再根据页表起始地址、页号找到对应表项
根据页表项中记录的内存块号、页内偏移量 得到最这种的物理地址
访问物理内存对应的内存单元
图例
例题
补充细节
页内偏移量位数与页面大小之间的关系(要能用其中一个条件推出另一个条件)
页式管理中地址一维的，给出一个逻辑地址就可以推出页号 页内偏移量这两个部分
实际应用中，通常是一个页框恰好能放入整数个页表项
为了方便找到页表项，页表一般是放在连续的内存块中
地址变换过程一共访问两次内存 第一次是查页表，第二个是实际访问物理内存对应的内存单元
图例
x
具有快表的地址变换机构
什么是快表
快表，又称联想寄存器(TLB),是一种访问速度比内存快很多的高速缓存(TLB不是内存！)，用来存放最近访问的页表项的副本，可以加速地址变换的速度，相对的内存大页表常称为慢表
引入快表后的地址变换过程
图例
补充：部分操作系统支持慢表块表同时查找
局部性原理
时间局部性
如果执行了程序中的某个指令，那么不久后这条指令很可能再次执行；如果某个数据北方问过，不久之后很可能再次被访问(因为程序中存在大量的循环)
空间局部性
一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也被访问(因为很多数据在内存中都是连续存放的)
例
如基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很多次查到的都是同一个页表
具有块表和不具有块表的地址变换机构的区别与联系
两级页表
单级页表存在什么问题？如何解决？
问题1：页表必须连续存放，因此当页表很大时，需要占用很多歌连续页框
解决办法：多级页表
问题2：由于局部性原理可知，没必要让整个页表常住内存，因为进程在一段时间内可能只需要访问某几个特定页面
解决办法：虚拟存储技术，只在需要访问某个页面的时候，此页面不在内存中，则产生缺页中断(内中断)，然后将目标页面从外存调入内存
两集页表的原理、逻辑地址结构
将一个比较长的页表再分页
逻辑地址结构：(一级页号,二级页号，页内偏移量)
注意几个术语：页目录表/外层页表/顶级页表
图例
如何实现地址变换
按照地址结构将逻辑地址拆分成三部分
从PCB中读出页目录表初始地址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置
根据二级页号查表，找到最终想要访问的内存块号
结合页内偏移量得到物理地址
图例
两级页表问题需要注意的几个细节
多级页表中，各级页表的大小不能超过一个页面。若两级页表不够，可以分更多级
多级页表的访问内存的次数(假如没有快表机构)——N级页表访问一个逻辑地址需要N+1次访问内存
基本分段存储管理
分段
将地址空间按照程序自身的逻辑关系划分若干个段，每段从0开始编址
每个段在内存中在内存中占据连续空间，但各段之间可以不相邻
逻辑地址结构：(段号，段内地址)
图例
段表
记录逻辑段到实际存储地址的映射关系
每个段对应一个段表项。各段表项长度相同，由段号(隐含)、段长、基址组成
图例
地址变换
由逻辑地址得到段号、段内地址
段号与段表寄存器中的段长度比较，检查是否越界
由段表始址、段号找到对应段表项
根据段表中记录的段长，检查段内地址是否越界
由段表中“基址+段内地址”得到的最终物理地址
访问目标单元
图例
分段VS分段
分页对用户不可见，分段对用户可见
分页的地址空间是一维法，分段的地址空间是二维的
分段更容易实现信息共享和保护(纯代码/可重入代码可以共享)
分页(单级页表)、分段访问一个逻辑地址都需要两次访存，分段存储中也可以引入快表机构
段页式存储管理
分段+分页的结合——段页式管理方式
将地址空间按照程序自身的逻辑关系划分若干段，在将各段分为大小相等的页面
将内存空间分为与页面大小相等的一个个内存块(就是页框)，系统以块为单位为进程分配内存
逻辑地址结构：(段号，页号，页内偏移量)
图
段表、页表
每个段对应一个页表项。各段页表项长度相同，有段号(隐含)、页表长度、页表存放地址组成
每个页对应一个页表项。各页表项长度相同，由页号(隐含)、存放的内存块号 组成
分页、分段管理方式的最大的优缺点
地址转换
由逻辑地址得到段号、页号、页内偏移量
段号与段表寄存器中的段长度比较，检查是否越界
由段表始址、段号找到对应端表项，检查页号是否越界
根据段表中记录的页表长度，检查页号是否越界
由段表中的页表地址、页号得到查询页表，找到相应页表项
由页面存放的内存块号、页内偏移量得到最终的物理地址
访问目标单元
访问一个逻辑地址所需访存次数
第一次--查段表、第二次--查页表、第三次--访问目标单元
可引入快表机构、以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存
虚拟内存管理（扩充内存技术）
基本概念
传统存储管理方式的特征、缺点
一次性：作业必须一次性全部调入内存
当作业过大时，系统无法执行
驻留性：作业数据整个运行期间都会常驻内存
作业量太大时，而运行一个过程仅仅需要几个作业，造成内存空间的浪费
局部性原理
时间局部性
空间局部性
高速缓存技术
使用频繁的数据放到更高速的存储器中
虚拟内存的定义和特征
程序不需要全部装入即可，运行时动态调入。如果内存不够，需要操作系统换出一些数据
特征
多次性：无需再作业运行时一次性全部装入内存，而是运行被分成多次调入内存
对换性：无需作业在作业运行时一直常驻内存，而是允许在作业运行过程中，讲作业换入，换出
虚拟性 ：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量
如何实现虚拟内存技术
虚拟内存和传统的存储方式的区别
访问的信息不在内存。有操作系统负责将所需信息从外存调入内存(请求调页功能)
内存不够时，将内存中暂时用不到的信息换到外存(页面置换功能）
虚拟内存的实现
请求分页存储管理
请求分段存储管理
请求段页式存储管理
请求分页管理方式
页表机制
在基本的分页基础上增加了几个表项
状态位：表示页面是否已在内存中
访问字段：记录最近被访问过几次，或者记录上次被访问时间，工置换泛选择换出页面时参考
修改位：表示页面调入内存后是否被修改过，只有修改过的页面才需要在置换时（先复制到外存，在进行对换）写回外存
外存地址：页面在外存中存放的位置
图例
缺页中断机构
找到页表项后检查页面是否已在内存，若没在内存，产生缺页中断
缺页中断处理中，需要将目标页面调入内存，有必要时还要换出页面
补充
缺页中断
因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断
一条指令在执行期间，可能产生多次缺页中断。例如：copy a to b 即将逻辑地址的A复制到B，而AB属于两个不同的进程且都不在内存，则可能产生两次中断
地址变换机构（侧重点在于与基本分页不同的地方）
找页表项时需要检查页面是否在内存中
若页面不存在内存中，则需要请求调页
若内存不够，则需要换出调页
页面调入内存后，需要修改相应页表项
图例
页面置换算法
最佳置换算法(OPT)
先进先出置换算法(FIFO)
先进先出置换算法(FIFO)
最近最久未使用置换算法(LRU)
时钟置换算法(CLOCK)
改进型的时钟置换算法
这四种算法的优缺点
页面分配策略
驻留级
指请求分页存储管理中给进程分配的内存快的集合
引申问题
若驻留级太小，会导致缺页频繁，系统需要花费大量的时间处理缺页，实际用于进程推进的时间很少
若驻留级太大，会导致多道程序并发度下降，资源利用率降低
页面分配、置换策略
基本概念
分配方式
固定分配:操作系统为每个进程分配一组固定数目的物理块。在进程运行期间不再改变。即，驻留级大小不变
可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少，即，驻留级大小可变
置换方式
局部置换：发生缺页时只能选进程自己的物理块进行置换
全局置换：可以将操作系统保留的空闲物理块分给却也经常，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程
固定分配局部置换
进程运行前就分配一定数量的物理块，缺页时只能换出进程自己的某一页
缺点：很难在刚开始就确定应该为每个进程分配几个物理块才算合理
可变分配全局置换
只要缺页就分配新物理块，可能来自空闲物理块，也肯需要换出别的进程的页面，注意：必须是未锁定的页面，有时候操作系统的数据是被锁定的不可以被换出
缺点：会导致别的进程物理块减少，缺页率增加
可变分配局部置换
开始分配好一定数量的物理块，当某进程发生缺页时，只允许从该进程自己的物理块中进行对换。频繁的缺页的进程多分配给一些物理块；缺页很低的进程，回收一些物理块，知道缺页率合适
没有固定全局置换，因为全局变化一定会导致不固定的进程驻留级
调入页面时机
预调页策略
一般用于进程运行前，根据局部性原理，一次调入若干个相邻页面可能是高校的，但是成功率不高，这种一般用于进程的是首次调入
请求调页策略
进程在运行的期间发现缺页时才将所缺页面调入内存。有这种策略调入的页面一定会被访问，但是每次只能调入一页，而每次调页都要磁盘I/O操作，因此I/O开销较大
从何处调页
对换区--采用连续存储方式，速度更快；文件区一般采用离散存储的方式，速度更慢
对换区足够大；运行将数据从文件去复制到对换区，之后所有的页面调入、调出都是在内存和对换区之间进行
对换区不够大；不会修改的数据每次都从文件区调入；修改的数据都写回对换区，再次使用时从对换区调入
UNIX方式：第一次使用的页面从文件区调入；调出的页面都写回对换区，再次使用时从对换区调入
抖动(颠簸)现象
页面频繁换入换出的现象，主要原因是分配给进程的物理块不够
工作集
在某段时间间隔内，进程实际访问页面的集合。驻留级大小一般不能小于工作集大小
个人理解：工作集就是测试进程能在窗口尺寸下进行的最大内存快的个数为多少，在通过工作集决定实际分配给进程的驻留级是多少(总结：工作集通过窗口来决定驻留级)
0 条评论
下一页
