关于内存地址如何转化成存储空间大小

0x0000-0x1000，为 $16^{3}=2^{12}=4k$ ，如果按字节寻址就是4KB，按字寻址就是4k字。

0d 十进制，0b 二进制，0o 八进制

透明==不可见

1s=1000ms

小端：数据的低位放在低地址空间，数据的高位放在高地址空间

大端：数据的高位放在低地址空间，数据的低位放在高地址空间

引入

冯若依曼体系结构：将程序指令存储器和数据存储器合并在一起的存储器结构

特权指令：只能在核心态执行

操作系统：管理计算机资源

处理机管理（进程，线程控制&同步&通信&调度）
存储器管理（执行一个程序前需要将该程序放到内存中）
文件管理。
设备管理。（I/O摄像头的分配等等）

用户接口：

程序接口：通过系统调用请求OS为其提供服务。GUI——调用程序接口实现。系统调用是提供给应用程序的接口，只能通过用户程序间接使用
命令接口：
- 联机命令接口：命令行一条命令，系统就响应一条。
- 脱机命令接口：*.bat文件集合多条命令。

api和abi

abi：应用程序二进制接口，应用程序和操作系统之间。保证编译好的（二进制）代码，可以在 ABI 兼容的系统上都能运行

api：programing应用程序编程接口，应用程序与开发人员之间，库函数。

区别：

描述的内容不同。ABI 规定了二进制文件的格式、内容、装载/卸载程序的要求、函数调用时的参数传递规则、寄存器、堆栈的使用；API 规定操作系统、硬件平台、服务组件、语言函数库等需要提供的功能函数接口。

作用的层面不同。ABI描述二进制层面的接口，API描述代码级层面的接口。

兼容的难度不同。ABI的兼容程度比API更为严格，即ABI实现兼容更加困难。

操作系统发展

手工操作阶段

用户独占全机，资源利用率低。

批处理系统

CPU和I/O设备之间速度不匹配。

解决：将用户提交的作业成批送入计算机，作业调度程序自动选择作业运行。

联机&脱机[你航]

联机批处理：作业的输入输出由CPU处理，缩短了建立作业和人工操作时间。（输入输出时CPU仍处于空闲状态）
脱机批处理：克服高速主机与慢速外设的矛盾，增加专门用于输入输出的卫星机，利用其完成输入输出，主机与卫星机并行工作。使主机摆脱I/O操作。
- 优：主机不直接与慢速的输入&输出打交道
- 缺：内存仅存放一道作业，CPU等待低速的I/O作业

单道&多道

单道批处理系统：监督程序控制作业的输入/输出，但串行。内存中只有一道程序。
多道批处理系统：类似于流水线，多道程序并发执行，用户无法调试。允许多个程序同时进入内存并允许他们在CPU中交替运行（遇到I/O切换程序）
- 优：吞吐量大，资源利用率高，系统开销小
- 缺：平均周转时间长，交互能力差

分时系统

多个用户分享使用同一台计算机，但每个人都认为独占一个计算机。多个程序分时共享硬件和软件资源。把CPU处理时间分成时间片，按时间片轮流把处理器分配给不同程序，可人机交互。交互性作业

缺点：不能优先处理紧急任务

实时系统

优先紧急任务

网络操作系统和分布式计算机系统

网络操作系统：在传统单机OS上加单独软件层，主要提供联网功能和资源的远程访问，实现多机互联，通信。集中控制

分布式计算机系统：系统中任意两台计算机通过通信方式交换信息，不同：分布式操作系统中的若干计算机相互协同完成同一任务

特征

并发

两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观是交替发生。【并发性通过分时实现，进程——并发执行】

&并行：两个或多个事件同一时刻同时发生。

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

eg：显示屏与打印机，设备与设备

共享

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

互斥共享：一个时间段只允许一个进程访问该资源。
同时共享：多个“同时”。

虚拟

指把一个物理上的实体变为若干个逻辑上的对应物。

程序同时运行的内存远大于实际。空分复用技术（虚拟存储器技术），时分复用技术（虚拟处理器）。

异步

多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行走走停停，以不可预知的速度向前推进（被阻塞）。

运行机制

程序状态字寄存器：1“内核态”，0“用户态”。

内核态：运行内核程序，执行特权指令。连接硬件与应用程序
- 与硬件关联紧密：时钟管理，中断处理（保护和恢复中断现场），设备驱动。
- 运行频率高：进程管理，存储器管理，设备管理。
用户态：运行应用程序，执行非特权指令。

刚开机，启动内核程序；之后主动将CPU让给应用程序，进入用户态。

系统调用

库函数封装调用系统调用。陷阱，运行在核心态。

凡是与共享资源有关的操作，都必须通过统一系统调用的发生向内核提出服务请求。

是用户进程进入内核的接口层，本身不是内核函数，由内核函数实现。“类似于封装”

体系结构

大内核：也包含进程管理、存储器管理、设备管理等（Linux，Windows）。

微内核：只包含时钟管理，中断处理。（上述只能运行在用户态，对性能造成影响）

优点：内核容易实现，可移植性好，配置灵活。
缺点：速度慢。用户态和内核态相互切换频率高。

中断和异常

陷阱和中断。

同步&异步[你航]

同步异常：它是某一特定指令执行的结果。在相同条件下，异常可以重现。例如内存访问错误、调试指令以及被零除。
异步异常：不可预知。

中断是异步异常，可能随时发生，与处理器正在执行的内容无关。中断主要由I/O设备、处理器时钟或定时器产生，可以被启用或禁用。

系统调用=陷阱trap。

软件和硬件都可以产生中断（异常？），软件中断常称为陷阱trap

陷阱(trap)帧：完整的线程描述表的子集，用于现场保护。
陷阱处理程序处理少量事件，多数转交给其他的内核或执行体模块处理。

基本原理

不同的中断信号，使用不同的中断程序处理。查询中断向量表，找到中断处理程序在内存中存放的位置。

当产生中断信号时，操作系统会抢夺CPU重回内核态，执行中断的内核程序。

没有中断就没有多道程序并发

链接与装载

编译：由编译程序将用户源代码编译成若干目标模块
链接：由链接程序将编译后的一组目标模块，以及它们所需的库函数链接在一起，形成一个完整的装入模块
装载/装入：由装入程序将装入模块装入内存运行
- 绝对装入：编译时产生绝对地址。（单道程序阶段：整个内存只有两个程序：用户程序和os）
- 可重定位装入：装入时将逻辑地址转换为物理地址（多道）
- 动态重定位：运行时将逻辑地址转换为物理地址，需要设置重定位寄存器（现代）

链接

链接：将各种代码和数据片段收集并组合成为一个单一文件的过程，这个文件可被加载到内存并执行。

作用：分离编译，多人协作。

编译->汇编->链接

可执行文件格式（ELF）

结构

ELF头

描述生成该文件的系统和字的大小和字节顺序（大小端存储模式）

帮助链接器语法分析和解释目标文件的信息。
节
- .text：已编译程序的机器代码。
- .rodata：只读数据。const常量。
- .data：已初始化的静态变量（当前模块内所有函数可见，模块外不可见）和已初始化的全局变量
- .bss
  - 未初始化和初始化为0的全局变量（所有模块可见）和未初始化的静态变量
  - 局部 C 变量在运行时被保存在栈中
  - malloc出的区域在堆中
- .symtab：符号表。定义和引用的函数和全局变量的信息。每一个可重定位目标文件都有一张符号表。
- .rel.text: .text 节的重定位信息
  
  在合并生成可执行文件时需要修改的指令的指针
  如：任何调用外部函数或者引用全局变量的指令
- .rel.data（.rel.data.rel）: .data节的重定位信息
  在合并生成可执行文件时需要修改的数据的指针
  任何已初始化的全局变量，如果它的初始值是一个全局变量地址或者外部定义函数的地址，都需要被修改
- .debug、.line：调试符号表
- .strtab: 字符串表
节头部表

描述各节的位置和大小，其中目标文件中每个节都有一个固定大小的条目 (项，entry)

装载和运行

装载前的工作：shell调用fork()系统调用，创建一个子进程。

装载：可执行文件按照文件中的段映射（加载）到虚拟地址空间。（子进程调用execve()加载program）

加载：加载器在加载程序的时候看ELF文件和segment相关的信息。

Type为Load的segment需要被加载到内存中的部分

不一定全部加载到内存，如果文件中的大小小于在内存中的大小，补零。

程序在装入时是否分配物理内存？不一定立即分配物理内存。

ELF的program header和section header分别起到什么作用？section header用来描述每个section的特性，如大小、类型、名称等等。program header用于描述segment的特性。

内存管理

程序执行前需要先放到内存中才能被CPU处理。

字word：看计算机有可能是32/16.
字节Byte：1Byte=8bit。
位bit：二进制位。

地址独立：无需知道物理内存的地址。

存储保护：保证各进程在自己的内存空间内运行，不会越界访问。

设置上下限寄存器：只有在两者之间才能访问。
重定位寄存器：存放进程的起始物理地址。界地址寄存器：最大逻辑地址。

功能：

存储分配和回收。
地址变换。
存储共享和保护。
存储器扩充。

SRAM:读写速度快，成本高，Cache。

DRAM:读写速度慢，急程度高，容量大，主存。

存储层次结构：寄存器-Cache-主存-外存。

内存空间的分配与回收

内碎片：已经被分配出去（明确说出哪个进程）但不能被利用。单道连续分配）
外碎片：还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存。

连续分配

装入连续物理地址空间

单一连续分配

内存只有两个程序：系统区，用户区。内存中一道用户程序，独占整个用户区空间。运行前计算所有物理地址。

静态地址翻译：即在程序运行之前就计算出所有物理地址。
静态翻译工作可以由加载器实现。

优点：实现简单，没有外部碎片。

缺点：只能用于单用户、单任务，有内部碎片。

固定分区分配

分区：把内存分为一些大小相等或不等的分区，每个应用程序占用一个或几个分区。操作系统占用其中一个分区**。**

固定式分区：程序适应分区。

分区大小相等：多个相同程序的并发执行。（控制多个相同对象）
分区大小不等：小中大，根据程序大小分配不同分区。（内碎片浪费）

优点：没有外部碎片。

缺点：程序太大，不得不采用覆盖，降低性能；有内碎片。

加载程序

单一队列分配方式：选择一个当前闲置且容量足够大的分区进行加载**，可采用共享队列的固定分区（**多个用户程序排在一个共同的队列里面等待分区）分配。
多队列：每个大小不同的分区都有一个队列，根据程序所需内存大小排在相应的队列。

可变式分区

分区大小可变。（有外碎片，无内碎片）

跟踪内存使用

位图表示法（空闲分区表）

给每个分配单元赋予一个二进制数位，用来记录该分配单元是否闲置。（空间开销固定，时间开销低，没有容错能力）

链表表示法（空闲分区链）

将分配单元按照是否闲置链接起来。（空间开销取决于程序数量，时间开销大，有一定容错能力链表有被占空间和闲置空间相互验证）

可变分区管理

已分配分区表，未分配分区表。

分配内存：<=size不再进一步分割。m.size（空闲分区）-u.size（请求分区）<=size，将该分区从分区表/链中移除，否则画出u.size分区。

回收内存

相邻分区合并。

分配算法

分配算法（基于顺序搜索）

首次适应：按地址递增顺序排序，选择第一个满足要求的。空闲分区以地址递增的次序排列，按顺序查找空闲分区链&表。
- 低地址不断划分，出现小碎片。
- 每次从低地址开始，增加查找可用分区的开销。
下次适应：循环列表，从上次查找结束的地方开始。以地址递增的循环列表。
- 空间利用更加均衡，不会非小的集中在一端。缺乏大的空闲分区。
最佳适应：选择大小最接近的。按容量递增次序排列。
- 小碎片。
最坏适应：寻找最大的空闲区。按容量递减次序排列。
- 大作业申请得不到满足。

分配算法（基于索引）

适合小系统，否则空闲分区表/链很大，检索速度慢。

快速适应：按容量大小分类，常用大小的空闲区设立单独的空闲区链表。系统为多个空闲链表设立一张管理索引表。
- 效率高，仅需要根据程序长度，找到能容纳最小空闲区链表，取下第一块。
- 不会分割分区，不产生内存碎片。取下某链表第一个即可。
- 回收算法复杂。
伙伴系统：（linux）： $2^{n-1}<x<2^{n}$ $2^{n - 1} < x < 2^{n}$ ，如果找不到 $2^n$ $2^{n}$ 就找 $2^{n+1}$ $2^{n + 1}$ 再切割成两个相等的（伙伴）。
- 两个块合并成一个更大的块，首地址必须是块大小的整数倍
- 伙伴地址：两个大小相同的相邻块合并成一个更大的块时，首地址必须是块（合成后的块2倍）大小的整数倍。
- 并不是任意两个相同大小的内存区块都是伙伴

消除外部碎片：紧凑技术。

消除外部碎片，使本来分散的多个小空闲分区连成一个大的空闲区。挪位。

紧凑时机：找不到足够大的空闲分区且总空闲分区容量可以满足作业要求。

实现支撑——动态重定位：挪位。进程起始地址，重定位寄存器中修改。

多重分区分配

将一道作业分成若干片段，增加程序短表，涉及到存储保护。

界限寄存器方法：上下界寄存器，基址、限长寄存器。
存储保护键：每个存储块保护键，每个进入系统的作业保护键，两者不匹配则停止运行。

覆盖与交换

解决大作业在小内存中的运行问题

覆盖

将程序划分为若干个功能上相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区的内存扩充技术。

对用户不透明，增加了用户负担

交换

将系统暂时不用的程序或数据部分或全部从主存中调出，以腾出空间将系统要求使用的程序和数据调入主存，实际上是主存与外存之间不断的交换程序和数据，以实现用户在较小的存储空间中完成较多作业的执行。

优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构
缺点：对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性

换出等待I/O的进程

何时交换：不用&内存空间不够

交换时工作：保存前一个进程的运行现场——寄存器，堆栈；创建新进程的运行现场

换回：恢复

区别

一、结构不同

1、覆盖：要求程序员给出程序段之间的覆盖结构。

2、交换：不要求程序员给出程序段之间的交换结构。

二、进行不同

1、覆盖：主要在同一个作业或同一个进程内进行。

2、交换：主要是在进程或作业之间进行。

三、减少不同

1、覆盖：减少一个程序运行所需的空间。

2、交换：可让整个程序暂存于外村中，让出内存空间。

非连续分配

充分利用空间，减少移动带来的开销

页式内存管理

对用户透明

纯分页：不支持换页，不支持虚拟存储器功能，必须一次全装入主存，否则不能运行
- 没有外碎片，有内碎片
- 一个程序不必连续存放
请求分页：不一次性装入

一级页表

把一个逻辑地址连续的程序分散存放到若干不连续的内存区域。

页&页面（虚拟）：把每个作业&进程的地址空间分成一些大小相等的片。从0开始编号。
页框（物理）：把内存分成与页面大小相同的片。

进程的页面与内存的页框一一对应

页表：每个进程配置一张页表。页表的基址及长度由页表寄存器给出。页号-块号：实际只需存储块号，页号用数组下标表示。只是存放块号而不是地址。需要块号*内存块大小！存放在内存中，访问数据需要访存2次，页表1次，内存1次。

是否在内存中的标识位。
算法换出的标识位。
页面是否改动的脏位。

页表项个数=页面数

*逻辑地址到物理地址的转换

页表项位置=页表基地址+页号*页表项长度
根据页表项位的信息获得页框号。
物理地址：页框号*页大小+页内偏移（按字寻址&按字节寻址）1字节=8位 1字=2字节（16位） 1字=4字节（32位）1字=8字节（64位） 1字节=16进制两位（一定注意前面为0的别漏数！！！）

问题：逻辑地址空间很大，页表更大？实现困难。解决：多级页表。

多级页表

把外部页表（页表的页表：页表号-内存块号）调用到内存，动态调入内部页表。

将一级页表拆分，每个小分组刚好可以装入一个内存块。

由一级页号获得二级页表存放的位置，通过二级页号获得内存中存放的位置。

一级页号/页表项大小=一级页号

二级页表大小与页面大小相同，即页表项大小*个数

问题：内存访问效率降低，由原先的1次增加为3次！（二级页表）解决：快表。

快表TLB

CPU产生逻辑地址的页号，首先在TLB中寻找，命中直接找出；未命中从页表中找出，再将相应页表项复制到快表。

有效内存访问时间：a为TLB命中率

$EAT=a(单次内存访问时间+TLB查询时间)+\\ (1-a)(单次内存访问时间\times2+TLB查询时间)\\ =2*单次内存访问时间+TLB查询-单次内存访问*a\\ =(2-a)*单次内存访问时间+TLB查询$

访问TLB=访问TLB+查询
访问内存中页表+访问内存

哈希页表

通过虚拟页号的哈希值访问页表，每个页表项是一个链表，如果虚拟地址与两表中元素的第一个域相同，则匹配，第二个域形成物理地址。

反置页表

index——物理块号，每个页表项存放使用进程的pid和逻辑页号

如果检索整个页表都没有找到——缺页

不根据进程的逻辑页号组织，只与物理内存大小有关

页共享与保护

共享：需共享的数据&代码的相应页面指向相同页框

问题：共享数据域不共享数据划在同一页框中，不易保密——分段存储管理页式管理缺点：共享数据不方便！！！

保护：

地址越界保护
在页表中设置保护位：W，R，W/R

段式内存管理

对用户可见，可以在用户编程时确定

页式问题：难以满足程序运行时对内存的动态需求。不便于数据共享与保护。

段式（可变的页）：按照程序自身的逻辑关系分成若干个段。编程时需要显式给出段号、段内地址

段表：保存在内存，基址及长度由段表寄存器给出。

段表寄存器：
逻辑地址：

31 …16 15 … 0

段号（位数决定的每个进程最多分几段段内地址（位数决定了每个段最大长度）
段表（每个段表项长度相同，段号隐含）：

31 …16	15 … 0
段号（位数决定的每个进程最多分几段	段内地址（位数决定了每个段最大长度）

地址转换

段表项地址=段号*段表项长度+段表始址。从而获得段长和基址。
判断逻辑地址中的段号S和段长TL，如果S>TL，访问越界，产生越界中断。
基址与段内地址相加获得要访问的物理地址。

信息共享

不同进程可以共享可重入代码（纯代码，多次并发调用安全运行，不能使用全局&静态变量，不能修改代码本身）

优点：易于共享与保护，支持动态的内存需要

缺点：地址变换浪费时间，产生外部碎片（可通过紧凑解决，但时间代价大），辅存中管理不定长度的分段困难。

页式善于管理物理地址，段式善于管理逻辑地址。

为什么页式是一维，段式是二维？

页式虚拟地址从0一直到最大gb，是连续的；段式是好多个从0-特定的地址。分成好多段，数据段、代码段等等，段与段之间不是连续的地址。

页式给一个虚拟地址，可以自动划分页号和页内偏移，系统自动生成；段式程序员自己设定段号。

省流：需要段长和段基址两个值才能确定某段

段页式存储管理

将进程先分段（编程实现）再分页（对用户不可见），再存放在内存中

逻辑地址：

段号：每个进程最多分几段。
页号：位数每个段最大有几页。
页内偏移量：决定页面大小，内存块大小。

地址转换

每个进程一张段表，每个段一张页表。段表中存放页表存放块号和页表长度

三次访存：1.根据段号查取页表长度和页表存放块号。2.根据页表存放块号访问页表获得内存块号。3.访存。

X86

段映射机制：逻辑地址——线性地址

页映射机制：线性地址——物理地址

全局描述符表GDT：段描述符

局部描述符表LDT：专属于某个任务的段描述符

内存空间的扩充

虚拟内存管理

局部性问题

空间局部性：刚访问过的存储单元的临近单位访问的可能性很高。

时间局部性：刚访问过的不能不久后会被再次访问。

虚拟存储提供3种能力：

给所有进程提供一致的地址空间。
保护每个进程的地址空间不被其他进程破坏。
把主存作为磁盘的高速缓存。

原理

程序装入时，不需要将全部读入内存（与覆盖不同，os自动完成，对程序员透明），程序执行时可以换入换出（比交换更小颗粒度）。

虚拟存储技术特征：

离散型。物理内存分配不连续。
多次性。作业被多次调入内存。
对换性。允许作业换入换出。
虚拟性：允许程序从逻辑的角度访存存储器，而不考虑物理内存上可用的空间容量。

与Cache主存的异同

相同点：

出发点相同：提高存储系统的性能。
原理相同：利用程序运行时的局部性原理把最近的常用信息快调入相对高速而小容量的存储器。

不同点：

侧重点不同：cache解决主存与CPU的速度差异。虚存解决存储容量问题。
数据通路不同：CPU与cache和主存之间有直接访问通路，而虚存如果主存不命中只能通过调页解决。
透明性不同：cache管理由硬件完成，对系统程序员和应用程序员完全透明；虚存由os和硬件共同完成，对系统程序员不透明，对应用程序员透明。
未命中的损失不同：主存未命中的性能损失远大于cache未命中。

请求分页管理方式

程序执行过程中，所访问的信息不在内存中，由os负责将所需信息从外存调入内存。若内存空间不够，os将内存中暂时用不到的信息换出到外存。

硬件支持：请求分页的页表机制，缺页中断机构和地址变换机构。
软件支持：请求调页功能和页置换功能的软件。

要解决的问题：

地址映射问题：进程空间到虚拟存储的映射
调入问题：哪些程序和数据应被调入，调入机制
替换问题：哪些程序和数据被调出主存
更新问题：主存和赋存的一致性
其他：存储保护和程序重定位

（进程的）虚拟地址空间=虚拟存储空间，都从0开始编址。

交换分区：连续的磁盘空间（按页划分），对用户不可见。物理内存不够时，os把内存中暂时不用的数据放在这里。

地址映射问题

程序装入时，由装载器Loader完成。

驻留位：1表示在内存中，0表示在外存中。
保护位：只读，可写，可执行。
修改位：此页在内存中是否被修改过。
访问位：页面置换算法。

调入问题

预调页：事先调入页面的策略。
按需调页：仅当需要时才调入页面的策略。

缺页异常&中断处理机制。（懒惰交换）

为每个进程维护一个当前工作集合，如果进程在暂停之后需要重启时，根据这个列表使用预调页将所有工作集合中的页一次性调入内存。

页面置换

最优置换：选择最长时间不需要访问的页面。（用于比较性研究）
先进先出：选择在主存驻留时间最长的一页淘汰。
- 性能较差，Belady异常（分配的页框增多，缺页率反而提高）
second chance（改进FIFO）：如果被淘汰的数据之前被访问过，则给第二次机会，同时清除标志位，否则直接淘汰。
clock（改进FIFO）：环形循环指针。
- 无缺页错误：将访问页置1，指针不动
- 产生：
  - 当前为1：置0，向前移，直至找到0，到当前为0的情况
  - 当前为0：替换，将其置1，向前移一位
最近最少使用LRU：选择在最近一段时间内最久不用的页面。
- 命中时：所有块的计数值与命中块的计数值比较，
  - 如果某块计数值小于命中块的计数值，则该块的计数值加 1
  - 如果该块的计数值大于命中块的计数值，则数值不变。
  - 最后将命中块的计数器清为0。
- 访问未命中：计数值最大的块被替换。被替换的清0，其余加1.
工作集算法：工作集指进程运行正在使用的页面集合。给定一个进程，记录其工作集。当需要进行页面替换时，选择不在工作集中的页面进行替换。

更新问题

file backed&未被修改：直接丢弃，磁盘有相同副本
file backed&修改：写回原有文职
anonymous&（第一次换出|已被修改）：写入swap
anonymous&非（第一次换出&已被修改）：丢弃

工作集与驻留集管理

工作集：当前进程正在使用的页面集合。

驻留集：每个进程驻留在内存的页面集合。（应该给每个进程分配多少页框，分配过多并发运行进程数降低；分配过少，产生抖动问题）

抖动问题

解决办法：

局部置换策略
引入工作集算法
预留部分界面
挂起若干进程
- 可挂起的进程：优先级最低、缺页进程、最后一个被激活的进程、驻留集最小的进程、最大的进程

页面分配策略

固定分配策略：每个活动进程的驻留集大小在运行期间固定不变。
可变分配策略：页框数在其生命周期可变。（要求统计缺页率）

页面置换策略

局部置换策略：系统在进程自身的驻留集中判断当前是否存在空闲页框。
全局替换策略：整个进程空间判断是否存在空闲页框，允许从其他进程的驻留集中选择一个页面换出内存。

可变+局部

页面清除策略

修改过的页面，如果在换出时要等待一个页面的写出和另一个页面的读入，降低处理机使用效率。

页缓冲

发生缺页中断时，不必首先写出置换页，而是将被选中的置换页面暂时保留在内存的缓冲区，批量写出到外存。减少IO次数。（页面缓冲算法）

写时复制技术

多个进程共享物理内存，如果想要写，就会在内存中复制一个页框写，新页框对写进程私有，其余不可见

页目录自映射

[什么是“页表自映射”？ - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/452598045#:~:text=什么是"页表自映射"？学完ICS的我们已经知道，在内存中每个普通的页都有"物理地址"和"虚拟地址"两个地址。用户程序拿到虚拟地址后，可以把虚拟地址交给MMU，MMU先根据寄存器cr3中的物理地址找到一级页表，再根据虚拟地址的第一部分查询一级页表（也有人称为"页目录%2FPage,Directory" ）得到对应的二级页表（也有人称为"页表%2FPage Table" ）的物理地址，再根据虚拟地址的第二部分查询二级页表得到所需的页的物理地址。)

前文中一级页表和二级页表是物理页，没有规定虚拟地址。但想要通过程序（只能通过虚拟地址）查询页表。

1k*1k=1M

页表没有单独的地址空间（在物理内存中），一个页表项指向自己（首地址是页大小的整数倍）。

Q：指向页表的页表项在哪里？

A：虚拟地址右移12位，得到页号，由于一个页表项4个字节，再左移两位。（不等于右移10位，除非那两位为0！）

高10位：一级页目录自映射还是指向自己本身。

再10位：因为指向自己，二级页表项还是那一位。

低12位：页内偏移，因为一个页表项4个字节，左移两位。

存储页表的4MB地址空间中是整个4GB虚拟地址空间的一部分，即这4MB在4GB中
记录这4MB连续地址空间到物理地址空间的映射关系的是一个4KB的页目录
记录这4MB连续地址空间到物理地址空间的映射关系的是一个4KB的页表页(4MB页表中的一员)

所以，页目录和页表页内容相同，页目录无需额外分配单独的存储空间，即有一个4KB的空间可以同时作为页目录和一个页表项，这个4KB的空间表示了整个页表的4MB地址空间与物理地址空间的映射关系。这就是自映射

第两点的理解：页目录记录着1024个页表页的对应物理页号，而这1024个页表页逻辑连续，就相当于页目录记录了着1024*4KB = 4MB的连续地址空间到物理空间的映射关系；

自映射：页目录中有一条PDE指向自身物理地址，这个地址就是页目录基址。

PT_base：页表基址，也就是虚拟内存中第一个页表项的地址，应与4M对齐。PT_base=((PT_base)>>22)<<22。

PD_base：页目录基址，PD_base = PT_base + PT_base >> 10

解释：页目录第一个页目录项一定也是记录着第一个页表页的页表项。 $PT_{base}>>12$ 表示第一个页表页的物理页号，一个页表项占4B空间，所以记录第一个页表页的页表项相对页表的偏移为 $(PT_{base}>>12)<<2 = (PT_{base}>>10)$ ，可得记录第一个页表页的页表项的地址为 $PT_{base} + PT_{base}>>10$ ，这就是页目录第一个页目录项的地址，即页目录基址。

PDE_self_mapping：自映射目录表项， PDE_self_mapping =(PD_base>>12)<<2+PT_base= PT_base + PT_base >> 10 + PT_base >> 20

进程管理

程序：静态永久的，存放在磁盘中的可执行文件。

进程：动态暂时的，程序的一次执行过程。（同步一个程序多次执行会对应多个进程。如何区分？每个进程独立的PID;一个进程也可包括多个程序）

PCB：进程描述信息（PID，UID），进程控制和管理信息（CPU等使用情况，进程状态），资源分配清单，处理机相关信息记录在进程控制块PCB中。给os使用
程序段：程序代码（指令序列）。给进程自身使用
数据段：运行过程中产生的各种数据。给进程自身使用

进程是程序的运行过程，是系统进行资源分配和调度的一个独立单位

进程产生过程：

进程与线程

进程

进程特征

动态性：进程是程序的一次执行过程。因创建而产生，因撤销而消亡。程序是静态实体。
并发性：多个进程实体同时存在于内存中，能在一段时间内同时运行。
独立性：进程是独立运行的基本单位。
异步性：进程之间相互制约，进程以各自独立的不可预知的速度向前推进。

进程执行

顺序执行

顺序性：程序结构所指定的次序。
封闭性：独占全部资源。执行结果只取决于进程本身，不受外界影响
可再现性：初始条件相同则结果相同。

并发

宏观同时发生，微观交替。

间断性：执行-暂停-执行（资源共享，可能被其他程序使用）

非封闭性：多个程序共享系统中资源。与执行速度有关

不可再现性：结果依赖于执行次序。

竞争：多个进程读写一个共享数据。
竞争条件：多个进程并发访问和操作统一数据且执行结果与访问的特定顺序有关。

Beernstein条件：

判断程序并发结果是否可再现的充分条件

R(Si）：Si的读子集，其值在Si被引用的变量集合。

W(Si)：Si的写子集, 其值在Si中被改变的变量的集合。

两个进程S1和S2可并发：当且仅当下列条件同时成立：

$R(S1)\cap W(S2)=\emptyset$
$W(S1)\cap R(S2)=\emptyset$
$W(S1)\cap W(S2)=\empty$

并行

微观同时发生。

前趋图：表示执行次序。

进程状态与控制

进程控制的主要任务是创建和撤销进程，以及实现进程的状态转换。（内核）

创建进程：为进程分配资源，初始化PCB
进程撤销：中止服务，销毁PCB

进程的状态：

就绪状态：只要分配CPU就可执行。
执行状态：处于此状态的进程数目小于CPU的数目。
阻塞状态：由于某种时间而暂时无法执行，请求等待某个事件发生（发生后，由阻塞态转换为就绪态）。

运行态到阻塞态是主动行为，阻塞态到就绪态是被动的，需要相关进程协助

只要就绪队列不空，CPU就总是可以调度进程运行保持繁忙，这和数目无关。除非就绪队列为空，效率降低。

进程控制块PCB

全局变量只与用户代码有关

正文段：二进制代码，常量，全局变量

堆段：动态分配存储区（malloc）

栈段：局部变量，函数调用实参传递值

原语

内核中特殊程序，运行不能中断，必须一气呵成（信息不统一，状态标志与所在队列不统一）。

开中断指令和关中断指令配合完成（只能由内核调用）

每个进程都有一个PCB。作用：创建、撤销进程，实现进程状态转换。

创建原语fork

分配进程标识号，申请PCB
分配运行所需的资源（内存，文件…)
初始化PCB
插入到就绪队列中

父子进程共享代码段，各自拥有数据段

创建新进程成功，产生两个进程，被调用一次，返回两次。

<0：err。
=0：在子进程中。
else：在父进程中，返回子进程pid。

撤销原语kill

释放资源，撤销子进程，重新调度。

检索出PCB
终止进程执行，如正在运行将处理机资源分配给其他进程
如果还有子孙进程一并终止
将拥有的资源归还给父进程or操作系统
PCB从链表中删除

内容

进程标识符：唯一标识，PID。
程序和数据地址：把PCB与其程序和数据联系起来。
当前状态：相同状态组成队列。
现场保护区：陷入阻塞态时，保存CPU各种状态信息。
同步与互斥机制：实现进程间互斥、同步和通信所需的信号量。
优先级：进程的紧迫程度。
资源清单：处CPU外的资源记录，I/O设备，打开的文件列表。
链接字：队列中下一个进程PCB的首地址。

组织方式

线性表：不论状态将所有PCB放在内存的系统区。（适用进程数目不多）
链接：按照进程状态组成多个队列，就绪队列、阻塞队列…
索引：线性表的改进，按照状态建立就绪索引表，阻塞索引表…

进程上下文切换 vs 陷入内核

进程上下文切换：

调度器执行
保存进程执行断点
切换内存映射
只能发生在内核态

陷入/退出内核：

CPU状态改变
由中断、一行、trap指令（系统调用）引起
保存执行现场（寄存器，堆栈）
寄存器上下文的切换，开销远小于进程上下文切换

线程

进程的不足：同一时间只能处理一个任务。

引入线程，将资源与计算费力，提高并发效率。线程是基本的CPU执行单元，程序执行流的最小单位，调度的基本单位。进程是除CPU之外的资源分配的基本单位。

资源拥有者称为进程，可执行单元称为线程。

调度的基本单位。
多进程：多个程序并发执行。多线程：并发粒度更细（任务机并行）。
线程间共享系统资源。
系统开销：进程间切换进程的运行环境，开销大；线程切换开销小。
有独立的栈区，函数临时变量等。

线程实现方式

用户级线程

内核中仍然只有进程的概念，线程在用户空间，通过library线程库（实现线程创建、销毁、调度等功能）模拟thread。

通过线程库管理线程。
线程切换：线程库应用程序完成，不需要转换到内核态。
os不能意识到用户级线程的存在。

优点：用户空间即可完成线程切换，系统开销小。

缺点：其中一个线程被阻塞，整个进程都会被阻塞。并发度并不高。不能发挥多处理机的优势，内核每次分配给进程仅有一个CPU，仅有一个线程执行

内核级线程

内核级线程os内核可感知，用户级线程os内核不可感知。
内核级线程创建、撤销、调度线程均需要内核支持，而用户级依靠线程库。
内核级线程执行系统调用指令，只有该线程中断；用户级所属进程都被中断。

混合的线程实现方式

many-to-one Model:多个用户级线程映射到一个内核级线程。
- 优点：线程管理是在用户空间进行的，因而效率比较高。
- 缺点：当一个线程在使用内核服务时被阻塞，那么整个进程都会被阻塞；多个线程不能并行地运行在多处理机上。
one-to-one Model:一个用户级线程映射到一个内核级线程。
- 优点：一个线程被阻塞，别的线程还可以继续执行，并发能力强。
- 缺点：每创建一个用户级线程都需要创建一个内核级线程与其对应，这样创建线程的开销比较大。
many-to-many Model:n个用户级线程映射到m个内核级线程（n>=m）。只有所有内核级线程都被阻塞才认为进入到了阻塞状态）
- 优点：克服了多对一模型并发度不高的缺点，克服了一对一模型中一个用户进程占用多个内核级进程开销太大的缺点。

POSIX Pthreads

用于线程创建和同步的标准（不只Unix）

可在用户级和内核级实现
API规定了线程库的行为，但不限定实现方法

同步与互斥

临界资源：一次仅允许一个进程访问的资源。互斥共享资源

临界区：每个进程中访问临界资源的那段代码。

进程互斥：>=2的进程不能同时进入关于同一组共享资源的临界区。
进程同步（直接制约关系）：各进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。（各并发进程有序运行）

区别与联系：

互斥无法限制访问者对资源的访问顺序，无序访问。同步：对资源的有序访问。

临界区管理条件：

空闲让进：临界区没有进程时，可进入。
忙则等待：任何两个进程不能同时进入。
有限等待：任何一个进程进入临界区应该在有限时间内得到满足。
让权等待：长时间不能进入临界区，应立即释放处理机，避免忙等。

基于忙等待的互斥方法

软件方法

p执行完while语句后，时间片用完转换到进程q，执行到occupied=true进入临界区，但转到进程p后又临界区的访问，造成空挡，不能实现互斥

单标志法

可以实现互斥：

互相谦让，严格两进程交替轮流使用。如果某一个进程一直不使用临界资源，另一个进程也不能使用，违反空闲让进。

双标志检查法

先上锁，再检查对方是否想要临界区。（检查和上锁不能同步执行）

竞争时pturn和qturn都为true，都无法进入临界区。

并发运行时，就会同时访问临界区。

Dekker算法

解决必须严格轮换的问题，通过让权。

Peterson算法

/*Pi进程：*/                                       flag[i] = True;
while(flag[j]);
critical section;
flag[i] = False;
remainder section; 

/*Pj进程： */                                         flag[j] = True;
while(flag[i]);
critical section;
flag[j] = False;
remainder section;

如果并发执行，flag[i]和flag[j]都为true，互相谦让饥饿，谁也没进去临界区。

/*Pi进程：*/
flag[i] = True;
turn = j;
while(flag[j] && turn == j);
critical section;
flag[i] = False;
remainder section;

/*Pj进程：*/
flag[j] = True;
turn = i;
while(flag[i] && turn == i);
critical section;
flag[j] = False;
remainder section;

turn：理解为轮到谁进临界区了（按到达临界区前的先后顺序），解决饥饿问题

flag：解决临界资源的互斥访问

硬件方法

中断屏蔽方法

使用开/关中断指令。进入临界区之前执行关中断，退出临界区之前执行开中断。

优点：简单高效。

缺点：不适用多CPU系统。带来性能损失。只适用于内核进程，否则用户随意使用开/关中断指令很危险。

Test and Set指令

用硬件实现的，执行过程不允许被中断（原语）。把“1”写到某个内存位置并传回其旧值。

缺点：不满足让权等待。

Spinlocks自旋锁

利用test_and_set硬件原语提供互斥支持。

acquire(lock){
	while(test_and_set(lock)==1);
}
release(lock){
	lock=0;
}

算法共性

检查和上锁不能一气呵成。

不满足让权等待。

忙等待：浪费CPU时间

优先级反转：低优先级进程先进入临界区，高优先级一直忙等。

即先启动低优先级进程，加锁后调度高优先级，但判断锁已经为true，导致一直忙等。是高优先级进程于需要等待低优先级进程所占用的共享资源而被阻塞

解决方案：

设置优先级上限：任何进入临界区的进程都获得最高优先级。
优先级集成：当高优先级等待一个低优先级进程持有的资源时，低优先级进程将暂时获得高优先级进程的优先级别。

基于信号量的同步方法

同步中，进程经常需要等待某个条件的实现，如果使用忙等待，会浪费大量CPU时间。

解决方案：让忙等变为阻塞，原语Sleep和Wakeup。

信号量

semaphore（带队列的，不会忙等）

表示某种资源的数量，一个确定的二元组(s, q)，其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列. 当发出P操作时：

s为正，则该值等于可立即执行的进程的数量；s <= 0，那么发出P操作后的进程被阻塞，│s │是被阻塞的进程数。
q是一个初始状态为空的队列，当有进程被阻塞时就会进入此队列。

只能被初始化、P(S)、V(S)操作

作用

PV操作优点：简单，表达能力强（可解决任何同步互斥问题）

缺点：不够安全，使用不当会出现死锁，遇到复杂同步互斥问题时实现复杂

实现进程同步

P1必须要在P2后执行，可以先初始化信号量为0（前操作之后执行V，后操作之前执行P）

实现前驱关系

eg：后驱有两个，设置不同的锁！！！（一次V只能释放一个）

实现进程互斥

semaphore S=1;
P1(){
    P(S);
    P1临界区;
    V(S);
}
P2(){
    P(S);
    P2临界区;
    V(S);
}

信号量集

控制同时需要多个资源的互斥访问。 $SP(S_1,t_1,d_1,...,)$ 。 $S_i\geq t_i$ ，否则资源量低，不予分配；占用值为 $d_i$ 。信号量增减 $d_i$ 。

对于信号量集错误的是：（多选）
A. SP(S, d, e)表示每次申请d个资源，当资源数少于e个时，便不予分配

B. SP(S, 0, 1)表示互斥信号量

C. SP(S, 1, 0)当S=0时禁止任何进程进入临界区

答：A、B

SP(S, d, e)应当表示每次申请e个资源，但当资源数少于d个时便不予分配，A错误。表示互斥信号量的方法是SP(S, 1, 1)，每次申请1个资源，当资源数少于1个时阻塞，B错误。

基于管程的同步与互斥

管程：名称，局部与管程内存的共享数据结构的说明，对该数据结构进程操作的一组互斥执行的过程，对局部与管程内部的共享数据设置初始值的语句。

依赖于编译器，适用于单机环境

monitor demo{
	共享数据结构 S;
    init(){//初始化
        S=5;
    }
    take_away(){//申请一个资源
        if(s<=0)x.wait();
        S--;
    }
    give_back(){//归还一个资源
        S++;
        if(有进程在等待)x.signal();
    }
}

解决的问题：

1.互斥：只有一个进程能进入。

2.同步：wait和signal，使一个进程&线程当条件满足/不满足的时候在条件变量上唤醒/等待。

3.条件变量：区分等待的不同原因，每个条件变量保存一个等待队列。

x.wait：当x对应的条件不满足时，调用使该进程进入x条件的等待队列，并释放管程。

x.signal：x对应的条件发生变化，调用它唤醒一个因x条件而阻塞的进程。

与信号量的区别：

条件变量的值不可增减（管程中用共享数据结构记录剩余资源数），信号量有值。
wait一定会阻塞当前进程，P操作只有当信号量<0才会阻塞。
如果没有等待的进程，signal将丢失；而V操作增加了信号量的值，不会丢失。
访问条件变量必须拥有管程的锁。

Hoare管程

入口等待队列：管程互斥进入。

紧急等待队列：被其他进程唤醒但由于互斥无法进入管程，优先级高于入口等待队列。

条件变量：每个表示一种等待原因，每个原因对应一个队列。

同步原语wait和signal：针对条件变量x，wait将自己阻塞在x队列中；signal将队列中的一个进程唤醒。

信号量定义

mutex=1：互斥进入管程。进入管程执行P(mutex)，退出管程执行V(mutex)。执行wait由于一定会阻塞该进程，也要V(mutex)。
next=0：发出signal的进程用P挂起自己。进程退出管程前，检查是否有别的进程在next等待，如有用V唤醒。next-count是等待进程数。
x-sem=0：申请资源得不到满足执行P挂起。用x-count记录等待资源的进程数。执行signal时，V。

进程通信的主要方法

低级通信：只能传递状态和整数值，包括信号量和管程机制。（传送信息量小，编程复杂）

高级通信：适用于分布式系统。包括管道、共享内存、消息系统。

管道

（相当于缓冲区，用于连接一个读进程和一个写进程读写可同时进行，写满阻塞写，缓冲区为空阻塞读）

管道是半双工的，数据只能向一个方向流动。双方通信需要建立两个管道。

无名管道：只能用于父子进程或者兄弟进程之间（亲缘关系）；单独构成一种独立的文件系统，只存在于内存；一个进程向管道中写的内容（添加在缓冲区末尾）被管道另一端的进程读出。
有名管道FIFO：不再限制一定有亲缘关系；FIFO不同于无名管道之处在于它提供一个路径名与之关联，以FIFO的文件形式存在于文件系统中。

消息传递

管程：过度依赖编译器；适用于单机环境

原语：send(destination,&message)和receive(source,&message)。

对用户透明，广泛使用

共享内存

最有用，最快的IPC形式（避免开销巨大的缓冲复制）

同一块物理内存被映射到进程A、B各自的进程地址空间。当多个进程共享同一块内存区域，由于共享内存可以同时读但不能同时写，则需要同步机制约束（互斥锁和信号量都可以）。
共享内存可以同时读，不能同时写，需要同步机制约束
通信效率高，进程可以直接读写内存

经典进程同步与互斥问题

解题：

分析同步互斥关系。

同步即先V后P，互斥全部加上PV。

互斥信号量初始值为1，同步要看资源的多少。

生产者-消费者问题

生产者，消费者，固定大小的缓冲区。

同步关系：缓冲区没满->生产者生产，缓冲区不空->消费者取数据
互斥关系：各进程互斥访问缓冲区。

semaphore mutex=1;//互斥进入缓冲区
semaphore empty=n;//缓冲区空块数
semaphore full=0;//缓冲区满块数
producer:{
    while(1){
        P(empty);
        P(mutex);
        put;
        V(mutex);
        V(full);
    }
}
consumer:{
    while(1){
        P(full);
        P(mutex);
        get;
        V(mutex);
        V(empty);
    }
}

如果mutex与empty互换，会被阻塞。互斥锁尽可能紧靠临界区

例题：

桌子有一个盘子，只能放一个水果，爸爸只放apple，妈妈只放orange，儿子只吃orange，女儿只吃apple。

互斥：爸爸妈妈放水果
同步：爸爸放-女儿拿，妈妈放-儿子拿

semaphore plate=1;
semaphore apple=0,orange=0;
dad(){
	while(1){
		P(plate);
        放苹果;
        V(apple);
	}
}
mom(){
    while(1){
        P(plate);
        放橘子;
        V(orange);
    }
}
son(){
    while(1){
        P(orange);
        拿橘子;
        V(plate);
    }
}
daughter(){
    while(1){
        P(apple);
        拿苹果;
        V(plate);
    }
}

读者-写者问题

对共享资源的读写操作，任一时刻“写者”只允许一个，“读者”允许多个。读-写互斥，写-写互斥，读-读允许。

同步关系：
互斥关系：写与写，写与读

读优先

semaphore rw=1;//互斥访问
int count=0;//几个读进程
semaphore mutex=1;//对count互斥访问
main(){
    cobegin{
       write:{
           while(1){
               P(rw);
               write;
               V(rw);
           }
       } 
       read:{
           while(1){
               P(mutex);
               if(count==0)
                   P(rw);
               count++;
               V(mutex);
               read;
               P(mutex);
               count--;
               if(count==0)
                   V(rw);
               V(mutex);
           }
       }
    }coend
}

写与读互斥，两个都加上rw的PV操作。

读与读不互斥：增加count值记录当前有几个读，只有第一次进入读的时候才上锁，最后一个解锁。

读与读同时访问count：给count上锁

读写公平

❓如果读进程一直读，写进程可能会被饿死？

semaphore rw=1;//互斥访问
semaphore r=1;//读写公平
int count=0;//几个读进程
semaphore mutex=1;//对count互斥访问
main(){
    cobegin{
       write:{
           while(1){
               P(r);
               P(rw);
               write;
               V(rw);
               V(r);
           }
       } 
       read:{
           while(1){
               P(r);
               P(mutex);
               if(count==0)
                   P(rw);
               count++;
               V(mutex);
               V(r);
               read;
               P(mutex);
               count--;
               if(count==0)
                   V(rw);
               V(mutex);
           }
       }
    }coend
}

增加w用于实现读写公平。

读者1->写者1->读者2，就会读者2不会继续进入，会被阻塞。

写优先

要想实现写优先，那么比写先来的读者不能在r上排队。

int readcount=0;//记录当前有多少个读进程在访问文件
int writecount=0;//当writecount=0,唤醒读者
semaphore mutex1=1;//用于保证对readcount变量的互斥访问
semaphore mutex2=1;//用于保证对writecount变量的互斥访问

semaphore mutex=1;//用于保证写者之间的互斥访问，其他读者要进入rmutex之前需要在mutex上排队
semaphore rmutex=1;//当有新写者来时，停止所有的读进程。
semaphore wmutex=1;//实现对写操作地互斥访问

reader(){
	while(1){
		P(mutex);//实现写者优先访问，禁止读者在rmutex排队,保证一次只有一个读者进程访问rmutex
			P(rmutex);//读者进程加锁
				P(mutex1);//互斥修改readcount变量
					readcount++;
					if(readcount==1)
						P(wmutex);//当有读者进程执行读操作时，对写者进程加锁
				V(mutex1);
			V(rmutex);//读者进程解锁
		V(mutex);
			读文件...
		P(mutex1);//互斥修改readcount变量
			readcount--;
			if(readcount==0)
				V(wmutex);//当读者数量为0,解锁写者进程，允许写者进程执行写操作
		V(mutex1);
		}
	
writer(){
	while(1){
		P(mutex2);//各写者进程互斥访问writecount
			writecount++;//写进程数量+1
			if(writecount==1)
				P(rmutex);//有写进程时，对读进程加锁
		V(mutex2);
		P(wmutex);//写之前加锁，保证每次只有一个写者可以进行写操作
			写文件...
		V(wmutex);
		P(mutex2);
			writecount--;//每当有一个写进程完成写操作，写者数量-1
			if(writecount==0)
				V(rmutex);//若没有写进程正在执行，解锁读者进程
		V(mutex2);
		}
	}

哲学家进餐问题

哲学家思考or进餐，如果进餐，每个哲学家的左边和右边各有一只筷子。需要持有两个临界资源，如果避免造成死锁。

最多只能四个人拿筷子or奇数号拿左边，偶数拿右边or只有两边都可以使用时再抓起筷子。

互斥关系：哲学家与左右邻居对其中间筷子的访问。

注意死锁现象

定义信号量设置。chopsticks[5]={1,1,1,1,1}。左边筷子为i，右边的(i+1)%5.

最多只允许四个哲学家同时（尝试）进餐——破除资源互斥

semaphore chopsticks[5]={1,1,1,1,1};
semaphore count=4;//最多允许4个人
Pi(){
    P(count);
    P(chopsticks[i]);
    P(chopsticks[(i+1)%5]);
    吃饭;
    V(chopsticks[i]);
    V[chopsticks[(i+1)%5]];
    V(count);
}

同时拿起两根筷子，否则不拿起——破除保持等待

semaphore chopsticks[5]={1,1,1,1,1};
semaphore mutex=1;//互斥的取筷子
Pi(){
    P(mutex);
    P(chopsticks[i]);
    P(chopsticks[(i+1)%5]);
    V(mutex);
    吃饭;
    V(chopsticks[i]);
    V[chopsticks[(i+1)%5]];
}

奇数号拿左边，偶数拿右边

semaphore chopsticks[5]={1,1,1,1,1};
philosopher(int i){
    while(1){
        if(i%2!=0){
            P(chopsticks[i]);
            P(chopsticks[(i+1)%5]);
        }else{
            P(chopsticks[(i+1)%5]);
            P(chopsticks[i]);
        }
        吃饭;
        V(chopsticks[i]);
    	V[chopsticks[(i+1)%5]];
    }
}

睡觉的理发师

有一位理发师，一把理发椅，n把等候用的椅子。

与生产者类似，但生产者可以生产无数个，但顾客没有空座就走了

互斥：排队的顾客数
同步：顾客唤醒理发师，理发师唤醒下一位等待顾客

int waiting=0;//等待的顾客数（不包括正在理发）
int chairs=n;
semaphore customers=0;//顾客数
semaphore barber=0;//空闲的理发师数
semaphore mutex=1;//互斥访问waiting
barber:{
    while(1){
        P(customers);
    	P(mutex);
    	waiting--;
    	V(mutex);
    	V(barber);
   	 	cut_hair();
    }
}
customer:{
    P(mutex);
    if(waiting<chairs){
        waiting++;
        V(mutex);
    	V(customers);
    	P(barbers);//理发师忙，顾客坐下等待
    	get_haircut();
    }else{
        V(mutex);
    }
}

调度

CPU调度：控制、协调多个进程对CPU的竞争。

进程调度算法

进程调度的时机

CPU切换过程（进程的上下文切换）

CPU三级调度

高级调度（作业）：（用户角度）一次提交若干作业，对每个作业进行调度。从外存后备队列挑选一个使其获得竞争CPU的权利
中级调度（内外存交换）：指令和数据必须在内存里才能被CPU直接访问。（存储器资源管理角度）进程的部分或全部换出到外存，当前所需部分换入到内存。将内存中暂时不能运行的调出到外存等待（挂起态），具备条件后再调入内存（就绪态）
低级调度（进程&线程调度）：（CPU资源管理角度）执行单位ms。高效率

调度频率：低级>中级>高级

调度准则

不同角度判断处理机调度算法的性能

周转时间：作业从提交到完成经理时间=收容队列等待+CPU执行+就绪、阻塞等待+结果输出等待（批处理系统）
带权平均周转时间：周转时间/实际服务时间
响应时间：用户输入请求到系统给出首次响应（分时系统）
截止时间：开始截止时间和完成截止时间（实时系统，与周转时间类似）
优先级：使关键任务达到更好的指标
公平性：不因作业或进程本身的特性使上述指标过分恶化（eg：长作业等待时间极长）
吞吐量：单位时间内完成作业数

平均周转时间不一定是吞吐量的倒数。并发执行作业时间可重叠⚠️
处理机利用率
各种资源的均衡利用：CPU繁忙的和作业和I/O繁忙（次数多，时间短）的作业搭配

易于实现，执行/开销比小

设计调度算法考虑问题

进程优先级（数）

优先级：进程重要性和紧迫性。优先数：数值反应优先级

静态优先级&动态

进程就绪队列组织

按优先级：优先级较高先执行

所有进程创建都进入第一级就绪队列，随着进程运行，降低某些进程的优先级，进入之后级的队列。（比如时间片用完）

占用CPU方式

不可抢占式：一旦分配进程一直占用处理机，除非进入阻塞&时间片用完
抢占式：一旦有优先级高于当前进程优先级，立即进程调度

进程分类

I/O密集型&CPU密集型
批处理进程（无需用户交互，无需马上响应）&交互式进程（交互平凡，响应时间快）&实时进程（实时要求，不能被低优先级阻塞，响应时间短）

时间片

分配给占用CPU的长度，确定允许该进程运行的时间长度

批处理系统的调度算法

先来先服务FCFS

按照作业提交或进程变为就绪状态的先后次序，非抢占式，I/O完成并不立即恢复执行。

利于长作业，利于CPU繁忙的作业

Q：有利于CPU繁忙的作业，不利于I/O繁忙的作业。why？

A：FCFS在CPU繁忙的作业到达时，可以立即执行，一直占用CPU资源直到完成。当I/O繁忙的作业，每运行一点点就因为I/O而被阻塞，返回就绪状态后又返回到了队列的队尾，I/O繁忙型作业响应时间长。

延伸：I/O型进程比计算型优先级高，I/O设备可以和CPU并行工作，优先的话可以使其今早投入工作，以提升吞吐量。

短作业优先SJF

对FCFS改进，减少平均周转时间，非抢占

优：缩短作业等待时间，提升吞吐量

缺：不利于长作业，不划分优先级，难以估计作业的执行时间

最短剩余时间优先SRTN

SJF改进为抢占式

缺：长作业饥饿

最高响应时间比优先HRRN

FCFS和SJF折中，非抢占，调度时先计算每个作业响应比RP，选择值最大的。

$RP=(作业已等待时间+作业服务时间)/作业服务时间=1+作业等待时间/作业服务时间$

优：短作业容易获得较高响应比，长作业等待时间长后也可以得到高响应比。

缺：计算RP时间开销。

交互式系统的调度算法

时间片轮转RR

一定是可抢占

提高进程并发性和响应时间特性，从而提高资源利用率。

按FCFS排成队列，执行一个时间片后暂停，送到就绪队列末尾，通过上下文切换到队首进程。

时间片过长：退化为FCFS，进程在一个时间片内部即可执行完，响应时间长。
过短：上下文切换次数增加，响应时间长。

$T(响应时间)=N(进程数目)*q(时间片)$

就绪进程数目越多，时间片越小。通常用户输入在一个时间片内处理完。

优先级算法PS

平衡各进程对响应时间的要求。

抢占&非抢占：

抢占：出现更高优先级的进程进入就绪队列，立即调度
非抢占：继续执行

静态&动态：

静态：依据进程类型，对资源需求，用户要求
动态：等待时间长调高优先级，每执行一个时间片降低优先级。

多级队列MQ

引入多个就绪队列，区别对待各列（进程兴致或类型不同），每个作业固定归入一个队列。

多级反馈队列MFQ

时间片轮转&优先级算法

线程调度：一个时间片内的调度

优先级倒置

低优先级的进程占用临界资源且被阻塞，且低优先级的很长时间得不到CPU进而间接导致同样需要使用临界资源的高优先级进程被阻塞。

解决方法：优先级置顶。

进入临界区，当前执行进程具有最高优先级

解决方法：优先级进程。

高优先级进入临界区，发现已经有低优先级进程，则其继承高优先级。

实时系统的调度算法

时间起主导作用，硬实时（对时间必须响应）&软实时（偶尔可不满足）。进程行为可预测

静态表调度

对所有周期性任务分析预测，确定固定的调度方案。

优：无计算，开销小。

缺：无灵活性，适用固定场景。

单调速率调度RMS

周期越小，优先级越高。

任务集可调度：

$\sum^{n}_{i=1}\frac{C_i}{T_i}\leq n(\sqrt[n]{2}-1)\approx0.69$

最早时间优先算法EDF

绝对截止日期时间最早，优先级越高

任务集可调度：

$\sum^n_{i=1}\frac{C_i}{T_i}\leq1$

最低松弛度优先算法LLF

根据任务紧急程度确定优先级。

调度时机（抢占）：有进程执行完&进程laxity=0（抢占）

松弛度=任务截止时间-本身剩余运行时间-当前时间

任务集可调度：

$\sum^n_{i=1}\frac{C_i}{T_i}\leq1$

多处理机调度

注重整体效率，多样调度算法，调度范围线程

非对称式AMP

各个处理器的地位不同，有固定分工。

对称式SMP

地位相同。

静态控制

每个CPU设立一个就绪队列，进程从执行到完成，都在同一个CPU上。

优：调度算法开销小
缺：容易出现忙闲不均

动态控制

各个CPU采用公共就绪队列，选择队首分配给空闲CPU

自调度：各个CPU采用公共就绪队列，每个处理机都可以从队列中选择适当进程来执行。
- 优：不需要专门处理机任务分派
- 缺：处理机个数多，对就绪队列的访问有问题
成组调度：将一个进程中的一组线程，每次同时分派到一组处理机上执行，在剥夺处理机时也同时对这一组线程进行。
专用处理机调度：每个线程分配一个CPU

死锁

每个进程无限等待组内其他进程所占有的资源。

原因：资源竞争，并发执行的顺序不当。

可剥夺资源：获得后还可被其他进程或系统剥夺（CPU，内存）
非可剥夺资源：分配后不能强行收回，只能自行释放（打印机）
临时性资源：一个进程产生，被另一个进程使用，短时间后便无用（消息）

必要条件

互斥：进程对分配到的资源进行排他性使用。

请求和保持：进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程阻塞，但仍占有已获得的资源。

不可剥夺：已获得的资源未使用前不能被剥夺，只能使用完自己释放。

环路等待：必然存在一个进程—资源的环形链，循环等待。

活锁和饥饿

活锁：任务没有被阻塞，由于某些条件没有满足导致重复尝试。

与死锁区别：处于活锁的实体是在不断地改变状态，而处于死锁的实体表现为等待。活锁可能自行打开。避免：先来先服务
饥饿：资源分配策略的不公平导致长时间等待。

允许死锁发生：鸵鸟算法

死锁预防（静态）

打破互斥条件：允许进程同时访问某些资源。
打破请求且保持条件：实行资源预先分配策略。只有满足当前进程全部资源才能够一次性分配所申请的资源。

缺点：有些进程动态不可预测；资源利用率低；降低并发性
打破不可剥夺条件：允许进程强行从占有者那里夺取某些资源

缺点：降低系统性能
打破循环等待条件：实行资源有序分配策略，将资源事先分类标号，按号分配。将资源实现编号，只有占有了小号资源才能申请大号

缺点：限制进程对资源的请求，对系统中所有资源合理编号也复杂，增加系统开销；暂不使用的资源也要提前申请，增加进程对资源的占用时间。

死锁避免（动态）

安全序列：对于每一个进程 $P_i$ ，他需要的资源可以被系统中当前可用资源加上所有进程 $P_j(j<i)$ 当前占有资源之和满足。

银行家算法

如果work大于等于需要，就可以finish。

资源分配图

RAG算法

封锁进程：某个进程由于请求了超过系统中现有的未分配资源数目资源，而被系统封锁的进程。

未封锁进程：没有被进程封锁的进程。

化简：未封锁进程，将请求边变成分配边，一段时间后资源全部释放。直到所有进程变成孤立点。

操作系统------资源分配图化简-CSDN博客

计算出所有资源的空闲量：总数-出度
看每个进程：如果请求边<=资源空闲量，删去所有边

死锁解除

剥夺资源：使用挂起/激活挂起一些进程，剥夺他们的资源以解除死锁，条件满足后再激活进程。
撤销进程：使全部死锁的进程夭折；按照某种顺序逐个撤销（回退）进程，直至有足够的资源可用，死锁状态消除。

I/O管理

目的：提高I/O访问效率，方便用户使用，方便对设备的控制。

功能：提供用户接口（命令&编程）；设备分配和释放；设备的访问和控制；I/O缓冲和调度。

总线：数据线，地址线，控制线（接入I/O设备主要方式）

I/O管理概述

软件角度

I/O设备管理可直接从应用程序或文件系统得到请求并负责完成这个请求。包括：

逻辑I/O：完成设备无关的操作，设备分配、回收，数据准备
设备驱动程序：负责对设备控制器进行控制（读写寄存器）
中断服务程序：设备工作结束后负责向CPU发中断信号

特点：速度差异大，接口复杂，传输单位不同，错误多样，与文件系统及其他功能联系紧密

分类

按数据组织

块设备：以数据块为单位存储，传输信息。传输效率高，可寻址（随机读写）

字符设备：以字符为单位存储。传输效率低，不可寻址。

按用途分类

存储设备：磁盘，磁带。

传输设备：网卡，Modem。

人机交互设备：显示器，键盘，鼠标。

资源分配角度

独占设备：只能由一个进程使用的设备（打印机）

共享设备：允许多个进程共同使用（硬盘）

虚设备：在一类设备上模拟另一类设备，用共享设备模拟独占设备，用高速设备模拟低速设备。

I/O管理目标和任务

1.按照用户请求，控制设备操作，完成I/O设备与内存间的数据交换，最终完成用户的I/O请求。

设备的分配与回收：记录设备状态；根据用户的请求和设备的类型，采用一定的分配算法，选择一条数据通路。
执行设备驱动程序，实现真正的I/O操作。
设备中断处理：处理外部设备的中断。
缓冲区管理：管理不同的I/O缓冲区。

2.建立方便、统一的独立于设备的接口。

方便性：向用户提供易于使用的外部设备接口。
统一性：对不同的设备采用统一的操作方式，即在用户程序中使用逻辑设备（对物理设别的抽象，屏蔽物理硬件的细节）

3.充分利用各种技术提高CPU与设备、设备与设备之间的并行工作能力，充分利用资源。由于CPU与I/O间的速度差异很大，应尽可能减少速度差异造成的整体性能开销，尽可能使CPU与设备都处于充分忙碌状态。

4.保护：设备传送或管理的数据应该是安全的、不被破坏的、保密的。

I/O硬件组成

I/O设备由机械部件和电子部件（设备控制器：是硬件）组成

设备控制器

CPU与I/O设备的中介，实现CPU对I/O设备的控制

功能

接收和识别CPU命令（控制寄存器：存放命令和参数read&write）
数据交换：CPU与控制器
设备状态的了解和报告（状态寄存器）
数据交换（数据寄存器）
设备地址识别（判断读写哪个寄存器）
缓冲区
对设备传来的数据进行差错检测

组成

控制器与CPU接口：数据寄存器、控制寄存器、状态寄存器
控制器与设备接口：数据信号、控制信号、状态信号
I/O逻辑：用于实现CPU对I/O设备的控制

可能对应多个设备，寄存器可能对应也有多个。如何编址？

内存映射I/O（MIPS）：

寄存器与内存地址统一编址
- 优点：不需要特殊的保护机制来阻止用户进程进行相应的 I/O 操作
- 缺点：不能对控制寄存器的内容进行高速缓存
I/O独立编址：

控制器中的寄存器使用单独的地址
- 优点：外设不占用内存的地址空间，以区分对内存操作还是I/O操作
- 缺点：操作指令类型少，操作不灵活

I/O控制技术

程序控制I/O

由CPU代表进程向I/O模块发出指令，然后进入忙等状态，直到操作完成之后进程才能够继续执行。

CPU:开始发送指令，不断轮询检查状态，完成后传入内存

数据传送单位：字

优点：实现简单

缺点：CPU与I/O只能串行工作，I/O工作时，CPU忙等轮询检查，CPU效率低

应用程序提出读数据请求
设备驱动程序检查设备的状态
如果状态正常，给设备发出响应的控制命令
不断轮询检查是否完成执行过程
设备控制器完成操作，把数据送给应用程序
应用程序继续进行相应的处理

中断驱动方式

当I/O操作结束后设备控制器主动的来通知设备驱动程序，而不是依靠设备驱动程序不断轮询查看设备的状态

CPU：开始时发出I/O指令，然后阻塞该进程，继续运行进程，直至接受中断指令，完成后处理中断。

数据传送单位：字（一次中断传送一字）

优点：实现CPU与I/O并行工作

缺点：每次传送一个字，频繁中断处理消耗CPU很多时间

用户程序提出I/O请求
设备驱动程序检查设备的状态
如果设备准备好，就向设备发出控制命令
将状态记录在设备状态表中，CPU继续其他工作
设备完成工作后向CPU发中断信号，转入中断处理程序
中断处理程序发现这是一个正常的完成了控制命令的信号后，把结果转发给设备管理程序
设别管理程序从设备状态表里查询是哪个请求的完成
把相应数据送到应用程序
通知应用程序可以继续执行

DMA

直接存储器访问方式，由一个专门的控制器来完成数据从内存到设备或者是从设备到内存的传输工作.

由程序设置DMA控制器中的若干寄存器值（如内存始址、传送字节数），然后发起I/O操作
DMA控制器完成内存与外设的成批数据交换
在操作完成时由DMA控制器向CPU发出中断

寄存器

命令/状态寄存器CR：接收CPU发送来的I/O命令
内存地址寄存器MAR：输入——把数据从设备传送到内存的起始目标地址，输出——存放由内存到设备的内存源地址
数据寄存器DR：暂存从设备到内存，或从内存到设备
数据计数器DC：存放本次CPU要读或写的字节数

优点：CPU只需干预I/O操作的开始和结束，而后续成批的数据读写无需CPU控制，使用高速设备

缺点：数据传送方向，存放数据的内存及传送数据的长度由CPU控制

与中断方式的区别：

中断每个单位数据传送完成中断CPU，DMA传送一批数据完成后中断CPU

中断数据传送由CPU完成，DMA由DMA控制器完成，只有开始和结束需要CPU干预

中断具有对异常事件的处理能力，DMA控制方式适用于数据块的传输

数据传送单位：块（读入内存也要连续！）

数据流向：可以直接从设备放入内存&内存到设备

只需要在传送开始和结束才需要CPU干预

I/O通道

进一步减少CPU的干预

CPU：向通道发出I/O指令，指明通道程序的内存位置，要操作的I/O设备，然后就切换进程

与DMA原理几乎一样。I/O通道专门负责数据输入输出的传输控制。CPU将“传输控制”的功能下放给通道后只负责“数据处理”功能。这样，通道与CPU分时使用内存，实现了CPU内部运算与I/O设备的并行工作。

优点：执行一个通道程序可以完成几组I/O操作，与DMA相比，减少了CPU干预

缺点：费用高

字节多路通道：以字节为单位交叉工作，中低速I/O设备
数组选择通道：以“组方式”工作，每次传输一批数据，速率高，但一段时间只能为一台设备服务。连接磁盘、磁带等高速设备
数组多路通道：洁亮两者特点。对通道程序采用多道程序设计技术，使得与通道连接的设备可以并行工作

与DMA区别：

DMA方式下数据传送方向，存放数据的内存及传送数据的长度由CPU控制；而通道通过执行通道程序实现对数据传输的控制，更强的独立处理I/O功能

DMA只能控制一台&少数同类设备；通道同时控制多种设备

I/O软件组成

分层设计思想

软件组织成多个层次，每层实现一部分功能，依赖更低一层的原始功能，从而隐藏功能细节；给高一层提供服务。

低层考虑硬件特性，向高层软件提供接口；高层不依赖于硬件，向用户提供友好接口。

用户性软件通过“系统调用”请求操作系统内核的服务。
设备独立性软件：处理系统调用（向上处理接口），对设备的保护，差错处理，设备的分配与回收，映射关系逻辑设备表（逻辑设备——物理设备），缓冲区管理
设备驱动程序：自动配置和初始化子程序，I/O操作子程序，中断服务子程序

设备独立性

逻辑设备——物理设备

使用逻辑设备名称来请求使用某类设备，而系统在实际执行时，还必须使用物理设备名称。（所以系统需具有逻辑设备名称转换为物理设备名称的功能）

设备分配的灵活性：直接使用物理名称容易阻塞；逻辑名称可分配给同类设备
易于实现I/O重定向：设备更换不必改变应用程序

逻辑设备名到物理设备名的映射

逻辑设备表LUT

整个系统设置一张LUT（不能使用相同逻辑设备名，多用户难实现）
每个用户设置一张LUT

设备驱动程序

每个设备驱动程序处理一种设备类型。

任务：接收来自于设备无关的上层软件的抽象请求，并执行这个请求

自动配置和初始化子程序
I/O操作子程序：调用该子程序是系统调用的结果。执行该部分程序时，系统仍认为是和调用进程属同一个进程，只是由用户态变成核心态
中断服务子程序

I/O缓冲管理

利用内存

提高外设利用率

匹配CPU与外设的不同处理速度

减少对CPU的中断次数

提高CPU和I/O设备之间的并行性

单缓冲

平均处理一个块所需的时间：从一个状态到下一次回到这个状态

总结： $Max(C,T)+M$

双缓冲

平均处理一个块所需的时间：从工作区空，其中一个缓冲区满，另一个缓冲区空到回到这个状态

$Max(T,C+M)$

环形缓冲

多个指针区分空缓冲区，已装满数据的缓冲区，正在使用的缓冲区

缓冲池

上面消耗大量内存空间，利用率不高。而缓冲池设置了多个可供若干进程共享的缓冲区

相同类型的缓冲区链成队列：空缓冲队列，输入队列，输出队列

收容输入：调用Getbuf(emq)从空缓冲队列取出队首，数据输入其中，装满后调用Putbuf(inq,hin)，将其挂在输入队列上。
提取输入：调用Getbuf(inq)从输入队列队首取出，提取数据后，调用Putbuf(emq,sin)，将其挂到空缓冲队列emq上。
收容输出：调用Getbuf(emq)从空缓冲队列取出队首，装满输出数据后，调用Putbuf(outq,hout)将缓冲区挂在outq末尾。
提取输出：调用Getbuf(outq)从输出缓冲队列取出队首，提取数据后，调用Putbuf(emq,sout)将缓冲区挂在空缓冲队列末尾。

取队头，挂队尾

I/O设备管理

解决外设共享问题，以提高外设资源的利用率

进程间交替使用外设（键盘&鼠标）
通过一个虚拟设备把设备与应用进程隔开，只由虚拟设备使用设备

数据结构

设备控制表DCT：每个设备一张，描述设备特性和状态
- 设备队列队首指针：请求为得到满足的进程（PCB）
- 设备状态：忙/闲
- 控制器表指针
- 重复执行次数：发生错误重传
控制器控制表
通道控制表
系统设备表

SPOOLing技术

假脱机技术：软件方式模拟实现脱离主机的控制进行I/O操作

应用程序进行I/O操作时，实际是和SPOOLing程序交换数据，从SPOOLing程序的缓冲池读出数据或把数据读入缓冲池，而不是跟实际的外设进行I/O操作

输入井和输出井：磁盘上开辟的存储空间。模拟脱机输入输出
输入缓冲区和输出缓冲区：缓和CPU与磁盘之间的速度不匹配，在内存开辟的缓冲区。暂存输入设备送来的数据和将要传送给输出设备的数据
输入进程和输出进程

特点

高速模拟I/O操作
实现对独享设备的共享：由spooling程序提供虚拟设备，对独享设备依次共享使用（独占设备——>共享设备）

I/O性能问题

使CPU利用率尽可能不被I/O降低
使CPU尽可能摆脱I/O

磁盘管理

结构

磁盘
磁道：盘偏上以盘片中心为圆心，不同半径的同心圆
扇区：磁盘划分圆心角度相同的扇区，存储固定大小（盘块）
柱面：不同盘片相同半径的磁道组成，离轴心最远的编号为0

读一个扇区：柱面&磁头&扇区三个参数

磁盘的组织和调度

组织模式

CHS模式

磁头数NH，柱面数NC，扇区数NS

$磁盘容量=磁头数×柱面数×扇区数×512字节$

LBA模式

将磁盘驱动器看做一个一维的逻辑块的数组，逻辑块是最小的传输单位。

1	#lba =（＃c * H +＃h）* S +＃s-1

#c、#h、#s分别是磁柱、磁头、扇区的编号
#lba是逻辑区块编号
H=heads per cylinder，每个磁柱的磁头数
S=sectors per track，每磁道的扇区数

空间管理

位图：每一个物理块对应一位，分配出去为0，否则为1.

空闲表：记录起始块号，块数

成组链接法：把空白物理块分成组，再通过指针把组与组之间链接起来

磁盘访问时间

寻道时间：把磁头从当前位置移动到指定刺刀上的时间。s（启动磁盘），n（移动磁道数）

$T_s=m\times n+s$

旋转延迟时间：r（旋转速度RPM：一分钟转几圈）

$T_r=\frac{1}{2\times r}=\frac{1}{2\times RPM \times 60}$

传输时间：把数据从磁盘读出&向磁盘写入数据。b（读写的字节数），r（旋转速度），N（磁道上的字节数）

$T_t=\frac{b}{r\times N}$

总访问时间：寻道时间+旋转延迟时间+传输时间

$T_a=T_s+\frac{1}{2r}+\frac{b}{rN}$

磁盘调度算法

先来先服务FCFS

按访问请求到达的先后顺序。

优：简单公平

缺：相邻请求可能反复移动，效率低

最短寻道时间优先SSTF：解决效率低

优先选择据当前磁头最近的访问请求

优：改善磁盘平均服务时间

缺：饥饿现象，某些访问长期等待

扫描算法SCAN电梯调度：解决饥饿

磁头按一个方向移动，移动过程中对遇到的访问请求进行服务，知道磁头步进到==最内（最外）==调转扫描方向。

优：克服SSTF缺点，考虑了距离&方向

缺：摆动式，两侧访问频率低于中间

循环扫描算法C-SCAN：解决两端不公平

按照要访问的柱面位置的次序选择访问者。到达最后一个柱面后，带动磁头快速返回到0号柱面，返回时不服务任何。

优：增加两侧访问频率

提高磁盘I/O性能

选择性能好的磁盘
并行化
采用适当的调度算法
设置磁盘高速缓冲区在内存中

形式：独立缓存，以虚拟内存为缓存

数据交付：直接交付（copy开销），指针交付（内存管理复杂）

置换算法LRU

周期性写回：将disk cache中被修改过的内容写回磁盘
优化数据布局：1.连续摆放，磁头移动距离最小 2.优化索引节点的分布
提交读：顺序访问，提前读入下一块到缓冲区
延迟写
虚拟盘

廉价冗余磁盘阵列—RAID

把多个相对便宜的硬盘组合成硬盘组，提供比单个硬盘更高的存储性能和提供数据冗余（用户数据损坏，利用冗余信息可以使损失数据得以恢复）的技术

价格低，功效小，传输速率高（并行传输）
可提供容错功能

RAID0

条带化存储：有N个磁盘组成的是单个磁盘读写速度的N倍

数据传输率高，没有数据冗余。但是没有冗余校验功能

RAID1

镜像存储：通过磁盘数据镜像实现数据冗余，在成对的独立磁盘上产生互为备份的数据。原始数据繁忙，直接从镜像拷贝读取数据。

读性能好，写性能由最差的磁盘决定，可靠性好，代价较高

RAID2

海明码校验+条带存储，码距为3

需要多个磁盘来存放海明校验码信息，冗余磁盘数量与数据磁盘数量的对数成正比

易出错，没有商业化

RAID3

奇偶校验+条带存储，读写要访问组中所有盘，每组一个校验盘

缺：恢复时间长，奇偶校验盘成为瓶颈

文件系统

文件系统基本概念

文件：数据存储和访问的单位，对用户数据的逻辑抽象。连续逻辑地址空间，对磁盘的抽象

用户：屏蔽访问外村上的数据的复杂性
磁盘等资源：提高资源的利用率，优化性能

管理需求：

用户（使用逻辑文件）：使用的用户接口。

操作系统（组织和管理物理文件）：实现功能（管理存储空间，布局，存储位置）

三个层次

1.文件系统的接口：命令行接口，程序接口

2.对象操作管理的软件集合

3.对象及属性：文件，目录，磁盘存储空间

目录

文件说明索引组成的用于文件检索的特殊文件。

内容：文件访问和控制的信息（文件名，文件类型，地址信息，访问控制信息，使用信息）

多级目录：通过绝对路径&相对路径&当前目录（.）&上一级目录（…）

层次清楚，解决文件重名问题，查找速度快，目录级别太多

文件系统实现方法

文件控制块

基本信息：文件名，物理位置，文件逻辑结构，文件物理结构

访问控制信息：文件所有者，访问权限

使用信息：创建时间，上一次修改时间

文件控制块vs文件描述符

文件控制块：描述文件基本信息
文件描述符：唯一标识一个打开的文件，非负整数

文件逻辑结构和物理结构

文件逻辑结构

以字节为单位的流式结构、记录式文件结构（存取文件信息的最小单位是：记录）、树形结构

用户层面看：文件如何组织

提高紧缩效率
便于修改
降低文件存储代价

文件物理结构

操作系统角度：在存储介质上的存放方式

连续（顺序）结构

优：结构简单，效率高

缺：文件长度一经固定不易改变，不利于动态增加和修改

适合变化不大的文件

串联/链接文件

每个物理块的最后一个字为链接字，链首指针放在文件目录。

优：空间利用率高，便于动态扩充修改，顺序存取效率高（类似页式）

缺：随机存取效率太低，如果访问最后内容，实际访问整个文件；指针出错，可靠性低；链接指针占用空间。

索引结构

将每个物理块号存放在索引中，FCB只记录索引表的地址。

索引文件：数据文件+索引表

先通过文件名读出索引块的内容，再通过索引块中的索引表找出文件的各个物理块号。

优（保持链接结构优点又避免缺点）：能顺序&随机存取，满足文件动态增长，充分利用外存。

缺：索引表本身开销（内外存空间，存取时间）

索引表的组织

链接模式：一个盘块一个索引表，多个索引表链接起来
多级索引：将一个大文件的所有索引表的地址存在放另一个索引表中

直接索引——从索引表中直接读出磁盘块号
综合：两者结合

Final

客观题

课上小测

分时系统与批处理系统的主要开销是系统切换
计算机系统中网络带宽增长速度最快
DOS系统增加了网络功能，属于网络操作系统
（x）内存紧缩中用的重定位技术与程序链接过程中的重定位是一样的：前者动态重定位，后者编译链接过程中的重定位，主要原因是编译时程序地址在内存中的地址不确定，当多个程序编译链接后计算出程序地址的操作。
页式管理缺点：共享数据不方便。共享数据和非共享数据在同一页中，解决：分段管理
关于多级页表，下列说法不正确的是：（单选）
A. 能够减少页表占用内存的大小

B. 级数越多，平均访问内存的时间越长

C. 有效的页表项中都会存储页框号

D. 使用二级页表的平均访存性能优于一级页表

答：D

多级页表会采用动态调入机制，有一些页表在不需要的时候不调入内存，解决了页表占用大量内存的问题（A正确）。页表级数越多，就需要越多次访问这些不同级的页表，也就是多次访问内存，平均访存时间会增加（B正确，D错误）。有效的页表项中必然会存储页框号，MMU正是凭借页表项中的页框号才找到物理地址（C正确）。
在Intel x86下从段式地址到线性地址的转换中需要查找的对象可能是：（多选）
A. 全局描述符表GDT

B. 局部描述符表LDT

C. 页目录

D. 页表

答：A、B

逻辑地址的高位取出Segment Selector（相当于段号），然后通过查描述符表来找到对应段的页目录起始地址（x86采用二级页表）。这里的描述符可能查全局描述符表GDT，整个系统独一个；也有可能查局部描述符表LDT，每个进程拥有一个。
关于段式管理描述不正确的有：（多选）
A. 两个段的长度可以不同

B. 每个段内地址都从0开始

C. 段页式管理实质上等价于采用两级页表的页式管理

D. 段内地址是二维的、不连续的

答：C、D

每个段内地址都从0开始是正确的，而再加上段长不一致，这也是段式地址是二维地址的原因，B正确。段页式管理相当于在页式管理之上再查一次段表，段式+一级页式相当于二级页表，但段式之下也可以嵌套多级页表，例如x86的段式+二级页表模式，相当于三级页表，一方面我们不能说段页式就一定相当于二级页表，另一方面我们也不能说段页式就和多级页表“等价”，二者还是有本质上的区别的，C错误。段式地址整体是二维的不连续的，但段内地址是从0开始的连续地址，D错误。
Intel X86下的CR3寄存器中保存的是页目录基地址。
以下哪个地址不可能是自映射页目录的地址？
A. 0x8020 0000
B. 0x0000 0000
C. 0xC040 0000
D. 0x7fdf f000

通过给出的 $PD_{base}$ ，计算 $PD_{base}=PT_{base}+PT_{base}>>10$ ,如果不与4MB对齐则错误
采用页目录自映射方式，有助于实现用户进程的统一内存布局
引入线程的优势包括：（多选）
A. 有利于提高运行实体的创建和撤销效率

B. 有利于提高CPU利用率

C. 有利于提高多个共享数据的计算和IO任务的切换速度

D. 有利于提高多个并发任务间的通信效率

答：A、B、C、D

免去进程切换的开销，切换上下文，提升了运行实体创建和撤销的效率，A正确。提升了进程内部的并发程度，进一步提高了CPU利用率，B正确。线程之间直接共享变量，一个线程进行IO，其他线程还可计算，C正确。线程共享变量，提高多个并发任务间的通信效率，D正确。
以下说法正确的是：
A. PThreads API 是一个 Unix 下的线程实现
B. PThread_yield 的作用是中止当前线程执行并退出
C. PThreads API 可为编程人员提供多线程编程的可移植性
D. PThreads API 仅支持创建用户级线程

答案：成为了IEEE标准不只Unix，A错误。释放CPU给其他线程，B错误。PThread API提供了多线程良好的可移植性，只需要操作系统支持其库函数即可，C正确。支持创建用户级线程和内核级线程，D错误。
以下说法正确的是：（单选）
A. 引用全局变量的函数一定不是线程安全的

B. 引用static变量的函数可以是线程安全的

C. 线程安全的函数一定是可重入的

D. 可重入的函数一定是线程安全的

答：B

线程安全！=可重入
（x）在进程处于临界资源时不能进行处理机调度——当然可以，别与死锁弄混
只要涉及时间片都是抢占！！！！多级反馈，时间片轮转
以下关于单调速率调度算法说法正确的是：（单选）
A. 当进程数较多的时候，会导致CPU利用率下降到70%左右

B. 当所有进程请求的CPU利用率之和大于70%时，不存在满足所有进程实时性约束的调度方案

C. 当所有进程请求的CPU利用率之和小于69%时，一定存在满足所有进程实时性约束的调度方案

D. CPU利用率越高的进程越被优先调度

答：C
信号量可解决任何同步互斥问题
假设磁盘平均损坏时间是100000小时，采用2块这样磁盘组成RAID 0阵列，其平均损坏时间是：（单选）
A. 200000小时

B. 100000小时

C. 50000小时

D. 25000小时

答：C

RAID是一种把多块独立的硬盘（物理硬盘）按照不同方式组合起来形成一个硬盘组（逻辑硬盘），从而提供比单个硬盘更高的存储性能和提供数据冗余的技术。RAID 0是最低级别的RAID，该级别该级仅提供了并行交叉存取，它虽然有效提高了磁盘IO速度，但并无冗余校验功能。其2块磁盘的平均损坏时间将是单个磁盘的一半。
SPOOLing程序和外设进行数据交换使用的是实际I/O。
（x）文件控制块中包含了文件描述符
（x）文件系统中的源程序文件是有结构的记录式文件——没有结构要求
用户态下不能直接进行系统调用。
用户进程通过____系统调用___请求操作系统执行需要更高权限的操作（先中断，进入用户态后进行系统调用）
下列关于可重入代码说法正确的有：
A. 即使只有一个用户进程，使用不可重入代码也可能是不安全的还有内核进程呢！
B. 可重入代码中一般不能使用全局变量
C. 在多道程序下，共享可重入代码可以减少程序对内存的占用
D. 可重入代码中一般不能使用静态变量
【答案】A、B、C、D

若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是 A 。

Ⅰ、若该文件的数据不在内存，则该进程进入阻塞状态

Ⅱ、请求read系统调用会使CPU从用户态切换到核心态

Ⅲ、 read系统调用的参数应包含文件的名称

A. 仅Ⅰ、Ⅱ B. 仅Ⅰ、Ⅲ C. 仅Ⅱ、Ⅲ D. Ⅰ、Ⅱ和Ⅲ

首先要用open系统调用打开该文件。open中的参数包括文件的路径名和文件名，而read只需使用open返回的文件描述符，并不使用文件名作为参数。

read要求用户提供三个输入参数：

文件描述符fd
buf缓冲区首址
传送的字节数n

read的功能是试图从fd所指示的文件中读入n个字节的数据，并将它们送至由指针buf所指示的缓冲区中

算法相关

寻找空闲分区

分配算法（基于顺序搜索）

首次适应：按地址递增顺序排序，选择第一个满足要求的。空闲分区以地址递增的次序排列，按顺序查找空闲分区链&表。
- 低地址不断划分，出现小碎片。
- 每次从低地址开始，增加查找可用分区的开销。
下次适应：循环列表，从上次查找结束的地方开始。以地址递增的循环列表。
- 空间利用更加均衡，不会非小的集中在一端。缺乏大的空闲分区。
最佳适应：选择大小最接近的。按容量递增次序排列。
- 小碎片。
最坏适应：寻找最大的空闲区。按容量递减次序排列。
- 大作业申请得不到满足。

分配算法（基于索引）

适合小系统，否则空闲分区表/链很大，检索速度慢。

快速适应：按容量大小分类，常用大小的空闲区设立单独的空闲区链表。系统为多个空闲链表设立一张管理索引表。
- 效率高，仅需要根据程序长度，找到能容纳最小空闲区链表，取下第一块。
- 不会分割分区，不产生内存碎片。取下某链表第一个即可。
- 回收算法复杂。
伙伴系统：（linux）： $2^{n-1}<x<2^{n}$ $2^{n - 1} < x < 2^{n}$ ，如果找不到 $2^n$ $2^{n}$ 就找 $2^{n+1}$ $2^{n + 1}$ 再切割成两个相等的（伙伴）。
- 两个块合并成一个更大的块，首地址必须是块大小的整数倍
- 伙伴地址：两个大小相同的相邻块合并成一个更大的块时，首地址必须是块（合成后的块2倍）大小的整数倍。

页面置换

最优置换：选择最长时间不需要访问的页面。（用于比较性研究）
先进先出：选择在主存驻留时间最长的一页淘汰（queue）。
- 性能较差，Belady异常（分配的页框增多，缺页率反而提高）
改进的FIFO算法（second chance）：如果被淘汰的数据之前被访问过，则给第二次机会，同时清除标志位，否则直接淘汰。
改进的FIFO算法（clock）：环形循环指针。
- 无缺页错误：将访问页置1，指针不动
- 产生：
  - 当前为1：置0，向前移，直至找到0
  - 当前为0：替换，将其置1，向前移一位
最近最少使用LRU：选择在最近一段时间内最久不用的页面。
- 命中时：所有块的计数值与命中块的计数值比较，
  - 如果某块计数值小于命中块的计数值，则该块的计数值加 1
  - 如果该块的计数值大于命中块的计数值，则数值不变。
  - 最后将命中块的计数器清为0。
- 访问未命中：计数值最大的块被替换。被替换的清0，其余加1.
工作集算法：工作集指进程运行正在使用的页面集合。给定一个进程，记录其工作集。当需要进行页面替换时，选择不在工作集中的页面进行替换。

混淆区分

交换分区：磁盘。将OS暂时不用的数据放在这里。
块高速缓存：内存。相当于虚拟存储的cache。
页缓冲：内存。发生缺页中断时，不必首先写出置换页，而是将被选中的置换页面暂时保留在内存的缓冲区，批量写出到外存。减少IO次数。
输入井和输出井：磁盘。模拟脱机输入输出

计算题

内存管理

注意是大尾端还是小尾端，多少位！！！

同步与互斥

大题：

初始化信号量semaphore，其他变量（注意可不可以定义其他变量）

分析同步互斥关系。
同步即先V后P，互斥全部加上PV。
互斥信号量初始值为1，同步要看资源的多少。
遇到数量，优先考虑初值为N 的信号量
读/写者优先中，“优先”也可以看作资源

main(){
	cobegin{//并发执行
		P1:{
            while（true）{}
        }
		P2:{}
	}coend
}

习题

读者写者问题（写者优先）: 1）共享读; 2）互斥写、读写互斥; 3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）。

semaphore rw=1;//读写互斥
int count=0;//记录进入读的进程数
semaphore mutex=1;//互斥访问count变量
semaphore r=1;//当有写进程时，禁止所有读进程
int writecount=1;//记录进入的写进程数
semaphore mutex1=1;//互斥访问writecount变量
semaphore mutex3=1;//用于只要有写进程读进程一直阻塞，但如果都在一个队列写进程不能跳过，所以读进程被阻塞在mutex3中
main(){
    cobegin{
        Read:{
            while(true){
                P(mutex3);
                P(r);
                P(mutex);
                if(count==0){
                    P(rw);
                }
                count++;
                V(mutex);
                V(r);
                V(mutex3);
                read;
                P(mutex);
                count--;
                if(count==0){
                    V(rw);
                }
                V(mutex);
            }
        }
        Write:{
            while(true){
                P(mutex1);
                if(writecount==0){
                    P(r);
                }
                writecount++;
                V(mutex1);
                P(rw);
                write;
                V(rw);
            	P(mutex1);
                writecount--;
                if(writecount==0){
                    P(r);
                }
                V(mutex1);
            }
        }
    }
}

作业调度

评价指标

响应比=1+S/T （S：等待时间；T：运行时间）

T(响应时间)=N(进程数目)*q(时间片) 数目越多，时间片越小

算法内容

先来先服务FCFS（非抢占）
短作业优先SJF（非抢占）
最短剩余时间优先SRTN（抢占）
最高响应比优先HRRN（非抢占）： $RP=1+作业已等待时间/作业的服务时间$
时间片轮转RR：所有就绪队列按照FCFS，刚用完时间片的排在队尾，刚出现的进程排在队首立即参与第一次调度
优先级算法（抢占&非抢占）
多级队列算法MQ：多个就绪队列，可有不同优先级，时间片长度
多级反馈队列MFQ：多个就绪队列，队列1优先级最高，优先级越低时间片越长，进程先到队列1，然后进入队列2，队列中FCFS。只有队列1为空才会调度队列2.
静态表调度：事先固定调度方案
单调速率调度RMS（静态，抢占）：任务周期越小优先级越高先被调度，优先级一样随机选择。判断任务集可调度（C为运行时间，T为周期）：注意周期，周期内运行完的不用再考虑了！

$\sum^n_{i=1}\frac{C_i}{T_i}\leq n(\sqrt[n]{2}-1)\approx0.69$
最早截止期优先EDF（抢占）：绝对截止时间越早优先。任务集可调度：计算出最小公倍数的周期情况

$\sum^n_{i=1}\frac{C_i}{T_i}\leq1$