[TOC]

chap2 处理器管理

如何区分内核态和用户态？

P43

处理器状态位（程序状态字PSW中的一个比特位

中断源

硬件故障中断：电源故障，主存故障，线路故障
程序性中断：执行指令异常或出错

除0、溢出、虚拟地址异常等
**自愿性中断：**又称为系统调用
**I/O中断：**比如外围设备输入输出完了，又或者输入输出异常了
**外部中断：**时钟中断，关机重启等

系统调用的处理过程

P46 + P25-26（详细）

陷入指令：操作码（用于标识是陷入指令）+ 功能号

这是非特权指令

中断、异常与系统异常

感觉就是前面5类分成了三类

中断：I/O + 外部
异常：程序性 + 硬件故障
系统异常：自愿性中断（系统调用）

三态模型

PSW vs PCB

进程管理是由许多程序共同实现的

队列管理程序：核心模块

进程控制程序：使用原语

进程切换：必须在内核态完成，所以需要模式切换

进程切换使用的是软中断，反正不是硬件中断，就是软中断了，书上程序性中断里有一条就是“终止进程中断”，应该就是能引起进程切换的一种中断

单线程到多线程

用户栈和内核栈

多线程技术的优点和应用

P67

KLT与ULT

稍微有点理解，因为虽然是用户级多线程，但是OS调度的还是进程去执行，并没有达到并行的效果

混合策略

三级调度

补充：周转时间的概念

进程调度算法汇总

1.优先数调度算法

分为抢占式和非抢占式

优先数可以是

1.1 FCFS先来先服务

一个短进程可能不得不等待很长时间才能获得执行

偏袒计算为主的进程

I/O多的进程不得不等待计算为主的进程做完

1.2 最短进程优先SPF

例子

非抢占式，所以轮到了就能执行完，从没轮到的里挑最短的就行

问题在于长进程可能会饿死

1.3 最短剩余时间优先SRTF

例子

应该每个时间片都会检查下，不然没法抢占

emm也可能是有新进程到达的时刻会进行能否抢占的判断

1.4 最高响应比优先HRRF

非抢占式，一个进程能运行完

作业1有例子：算一下1+ 已等待时间/服务所需时间

2.时间片轮转调度算法

2.1 RR时间片轮转

反正就是有个队列

例子

0-1: A

1-2: A

2-3: B执行（因为2的时候B来了，B开始执行，A进入队列

3-4: A执行（B进入队列，4的时候C进入队列，此时队列是BC

4-5: B执行（队列C，A执行完了

3.分级调度算法feedback

又叫多级反馈队列，抢占式

例子

如何分级？

算法如下：

被抢占才会降级

q=1

q=1表示虽然是多级但其实每个分的时间片都是1，所以后续会有一个跟RR算法的比较（因为看起来似乎一样，都是平等时间片

q=2ⁱ 表示RQ0分到2⁰ = 1个片，RQ1分到2个，RQ2分到4个

对比RR和Feedback(q=1)

上面的比较就是Feedback算法 C会先获得一段运行的时间

Feedback：RQ0->RQ2优先级降低，时间片增长，有种均衡的感觉，优先级高的队列里都没了才轮到优先级低的队列

t=0，A到进入RQ0，A运行

t=1，A虽然没有结束，但是没有别的队列，所以A还是可以运行

t=2，B到B进入RQ0，A被降到RQ1，B运行

t=3，B也没运行完，进入RQ1排在A后面，由于没有RQ0，调度RQ1，A轮到运行，A结束

t=4，C到了，进入RQ0，C运行

t=5，C进入RQ1排在B之后，B运行

t=6，B又没运行完，进入RQ2，C运行

B一直运行到结束

例2

4.彩票调度算法

基本思想：为进程发放针对系统各种资源(如CPU时间)的彩票；当调度程序需要做出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源
功能比保证调度好的多，服务器和客户：客户需要调用服务器服务，则将彩票交给服务器
合作进程之间的彩票交换
一般不会在实时操作系统中使用，但是可以在服务器端进行使用，特别是视频点播服务器

这篇文章写的蛮生动的，但是公式显然是错的

彩票调度算法——让进程们拼手气？ - tobe的呓语 - 博客园 (cnblogs.com)

P应该是1-(99/100)^100 = 0.634概率随n增大而增大

Unix SVR4 调度算法

任务的优先级分成了三种

实时》内核》分时

进程管理的fork调用

注意题干：可再产生，所以是7个

chap3 存储管理

逻辑地址：用户编程用的

物理地址：又叫绝对地址，是实际的地址

四种模式

P83

2*2=4种

大体分为两类

虚拟存储器的基本思想

存储管理把进程全部信息放在辅存中，执行时先将其中一部分装入主存，以后根据执行行为随用随调入（部分装入
如主存中没有足够的空闲空间，存储管理需要根据执行行为把主存中暂时不用的信息调出到辅存上去（空间不足时需要调出一部分信息（部分替换

虚拟存储器的示意图

虚拟地址可以说是将逻辑地址映射到物理地址的一种手段

单用户连续分区存储管理->固定分区存储管理->可变分区存储管理

P90

可变分区主存分配算法

最先适配/最先适应：

最先适应就是从上向下查找，找到第一块区域放进去，将剩下的区域分割后仍作为空闲区。有利于大作业装入，但也使得内存低地址和高地址两端的分区利用不均衡，回收分区麻烦。（都从低开始放，为的是后面能放下大的，但也势必造成不平衡
邻近适应/下次适配：

从上次查找结束的地方开始执行最先适应分配算法

缩短平均查找时间，且存储空间利用率更均衡，不会使得小空闲区集中在内存一侧（算是对最先适应的变种
最优适应

最优就是要找到最适合的，所以未分配分区按小到大排，查找到第一个满足的就用

明显更容易造成很多小的内存内零头

每次都是分配最接近需要使用大小的部分，会生成很多很小的内存内零头，通常会将空闲区按照长度递增顺序排列，等同于最先适应分配算法，查找时间最长

最优适配算法最容易产生外零头
最坏适应

与最优相反，每次都挑最大的进行分配，有利于中小型作业，剩下的空闲区不至于过小

移动技术（内存紧凑/程序浮动技术）

P95

页式存储管理的地址转换思路

逻辑地址到物理地址的转换通过页号到页框号的转换实现（利用页表）

使用位示图记录分配情况

每一位与页框相对应，记录使用情况

利用Cache存放部分页表

只是部分存在cache，主存中依旧有

页表通常被存储在主存中。每个进程都有自己的页表，用于将其虚拟地址空间映射到物理内存中的实际地址。当程序访问虚拟地址时，通过查询页表可以确定对应的物理地址，从而进行实际的内存访问。

由于页表通常比较大，访问页表可能会导致频繁的主存访问。为了提高访问效率，现代计算机系统通常使用缓存（cache）来存储最近访问的页表项。这样，当需要查询页表时，先在缓存中搜索，如果缓存命中则可以快速获取所需的映射关系，减少对主存的访问。

这个缓存通常称为"Translation Lookaside Buffer"（TLB），它是一个快速的硬件缓存，用于存储页表的部分或全部映射信息。TLB位于CPU内部，作为虚拟地址到物理地址转换的一级缓存。当CPU需要进行地址转换时，首先在TLB中查找对应的页表项，如果找到了映射关系，则可以直接进行物理地址访问，而无需访问主存中的页表。如果在TLB中未找到对应的映射关系，就需要访问主存中的页表来获取相应的映射信息，并将其存储到TLB中以供后续使用。

总结起来，页表主要存储在主存中，但部分或全部的页表项可能被缓存到TLB中，以提高地址转换的速度。

抖动或颠簸

缺页中断率：类似于未命中率

1. Belady/最佳置换/OPT

按照不再访问、最长时间后访问到进行替换

2. FIFO/先进先出

存在Belady异常：

一般情况下，增加物理内存的页框数会减少缺页次数，因为更多的页面可以留在内存中，减少了对磁盘的访问。然而，FIFO算法存在Belady异常，即在某些情况下，增加物理内存的页框数反而导致更多的页面置换和更高的缺页次数。

3. 最近最少使用/ LRU

严格实现的代价比较大

前面3个有5，命中

前面3个没2，F，最前的是4，替换4

*4. 最不常使用 LFU

这个似乎不考

5. 时钟CLOCK

一步步移动，2 3 2 1 5

5的时候发生了什么？指针开始寻找插入位置，会把带星号的变成不带星号的（即把访问位为1的置为了0

一遍走下来全是0了，指针回到指向2的位置，发现2的访问位为0了，就进行替换，同时让5带上*，指针指向下一个3

*为什么有了页表还要反置页表?

只记住了减少了空间使用

请求(分)页式存储管理

首次只把进程第一页信息装入主存

页式和段式

书上写的很好的一段话

如果说促使存储管理方式从固定分区到动态分区，从分区方式向分页方式发展的主要原因是要是提高主存空间利用率。
那么，引人段式存储管理的主要目的则是满足用户编程的需求。

页式存储管理是从0开始编址的单一连续逻辑地址空问，虽然可以把程序划分成页面，但页面与源程序之间并不存在逻辑关系，也就难以对源程序以模块为单位进行分配、共享和保护。段式程序设计可以更好地体现模块化程序设计的思想,应用程序由若干程序段(模块）和数据段组成，如主程序段(M)、子程序段(又）、数据段(D)和工作区段(W），每段都从0 开始编址，有各自的名字和长度，且实现不同的功能。

程序的分段结构

数组也可分成一“段”

从段式存储到段式虚拟存储

请求分段管理方式

在请求分段存储管理系统中，作业运行之前，只要求将当前需要的若干个分段装入内存，便可启动作业运行。在作业运行过程中，如果要访问的分段不在内存中，则通过调段功能将其调入，同时还可以通过置换功能将暂时不用的分段换出到外存，以便腾出内存空间。

跟请求分页大致一个意思

关于辅存

段页式存储的地址转换过程

gg补充部分

这一章有好多部分没细看，页的大小设计之类的

伙伴系统

参考1：

(2条消息) 操作系统学习笔记（九）：连续内存分配——伙伴系统_时间很奇妙！的博客-CSDN博客

长得有点丑

参考2：

例题

Slab分配器

Linux 内核 | 内存管理——slab 分配器 - 知乎 (zhihu.com)

其中一个功能就是可以自己分配管理更小的内存，减少与Buddy系统打交道

*6. 局部最佳页面替换算法MIN

可能不考？

看个例子吧

驻留集其实没必要分成已驻留和In，徒增麻烦

好像也有点用，In的次数好像就是缺页的次数

因为是闭区间，所以刚到来的那个肯定是会驻留的（下一时刻能不能留当然还不好说

7. 工作集模型和工作集置换方法

基于程序性原理向后看

补充一道mooc选择题：

简单理解就是分段是按自己需求来的，要多少划分多少，所以不可能有内部碎片（内部就是指放段的地方和段本身是否契合，那显然是正好的，因为是自己划分的），但是会有外部碎片，因为段和段直接肯定没法正好放下相容

分页全都分成一个个固定的页了，自然没有外部碎片，但是自己一个页内不一定能放满，自然就造成了内部碎片

段页式本质还是分页，只是对段进行页的拆解后再塞入，所以还是有内部碎片

固定分区显然还会有内部碎片

chap4 设备管理

*I/O设备分类

设备管理的目标

解决设备和CPU速度的不匹配，使主机和设备充分并行工作，提高设备使用效率

什么是设备控制器？

I/O控制

轮询

中断

**DMA直接存储器访问：**相当于小处理器：模仿处理器来控制主存和设备控制器之间的数据交换

“周期窃取”

完成后依然需要中断，因为要告知CPU处理的情况，只是数据交换/传输/传送不需要CPU的介入了

通道 I/O处理器通道控制器

多级连接

通道可以一次面向多个不同的数据块

*I/O缓冲

解决设备和进程速度不匹配的问题

单缓冲技术

双缓冲技术

以输入为例，从设备读一部分数据到缓冲区1，用户进程从缓冲区1读取数据的同时，缓冲区2可以从设备读取下一部分数据读取，这样就有了一定的并行性，提高了效率

循环缓冲技术

没细看

*设备独立性

用户不指定物理设备，而是逻辑设备

分离用户进程和物理设备，达成设备的独立性

独占型设备需要分配共享设备一般不必分配

磁盘存取时间：三部分

驱动调度：移臂调度 + 旋转调度

**移臂调度：**使移动臂的移动时间最短，从而减少寻道总时间

**旋转调度：**在最少的旋转圈数之内解决该柱面上的全部I/O请求（处理同一个柱面上的请求

移臂调度算法

1. FCFS

移臂距离大，性能不好，移动臂是随机移动，寻道性能较差
按顺序处理请求，对所有进程公平

2. 最短查找时间优先 SSTF

先执行查找时间最短的请求，具有较好的寻道性能
存在“饥饿”现象：距离比较远的很难被满足
总是选择最小寻道时间并不能保证平均寻道时间最小，但是它的性能比 FCFS 更好

3. 扫描算法

SCAN/双向扫描

双向，扫到头回头
分步扫描/N-step-SCAN
LOOK/电梯

双向，扫到某方向最后一个回头
C-SCAN/循环扫描/单向扫描

旋转调度

没看

虚拟设备

虚拟设备技术

虚拟设备是用一类物理设备模拟另一类物理设备的技术，可以让独享型设备变为共享设备

鼠标模拟游戏操纵杆

串行接口设备模拟并行接口设备

SPOOLing系统

SPOOLing = 外围设备联机并行操作 = 假脱机操作

简单理解

一个经典的SPOOLing系统

主要就是预输入，缓输出，加上一个“井”管理程序

简单理解就是先存一点，然后统一抽个去处理，这样就不会某个设备其实实际上使用外围设备的时间就只有一开始一点点，但是占用了外围设备很久，导致其他进程无法使用外围设备

补充内容

磁盘Cache

设备的分配

设备类表和设备表

设备分配算法

出错处理

I/O软件层次

其中设备驱动程序会做一件事情：

这部分最好再看看，每个层次的I/O都做了什么事情

习题

通道技术是一种硬件机制

chap5 文件管理

文件系统的组成

总体结构

存取存储方法

顺序存取

磁带机

光盘设备

直接存取/随机存取

磁盘

机械硬盘 + 固态硬盘

它的每个物理记录有确定的位置和唯一的地址，存取任何一个物理块所需的时间几乎不依赖于此信息的位置

顺序存取和直接存取的理解：

文件的逻辑结构

流式文件

全是连续字节流，可能有特殊字符作为分界线

无结构

记录式文件

若干逻辑记录组成的记录流文件

如每个职工的工资信息是一个逻辑记录

成组与分解

文件的物理结构

顺序文件/连续文件

磁带文件、光盘文件

连接文件/串联文件

每个块会有个连接字，指出文件的下一个物理块位置，为0则表示本文件块结束，第一个块的位置由文件目录给出

直接文件/散列文件

hash

通过计算记录的关键字建立与其物理存储地址之间的对应关系

索引文件

文件目录->索引表地址->查索引表得到键和存储地址

多级索引结构

文件目录

一级文件目录

二级文件目录

树形目录结构

有点像FAT12

内容既可以是文件也可以是目录

应该是目前主流的，树形目录结构

存取控制矩阵

存取控制表

因为矩阵往往比较稀疏

文件的存取方法

顺序存取

读指针，写指针进行推进

直接存取

没啥可说的，找到地方直接就能读写

索引存取

实际的系统中，大都采用多级索引，以加速记录查找过程

再遇位示图

成组连接法

比如这张图上，盘块50里面的内容就是记录了下一组的情况，空闲数100，有哪些空闲块，然后第一个空闲块是150，又被用来记录下一组的情况，依此类推（其实是一个栈的结构，第一个空闲块最先进入，所以最后出去

归还时的算法

如果已经100了怎么办

比如a盘块目前记录了100个空闲块，

又归还来一个c，那么把a盘块的专用快b的信息复制到c，然后把b清空，c放进去（b的空间快置为1）

分配时如果不够了怎么办，其实就是把下一个的数据复制进来

a盘块目前只有一个空闲块b，b是专用块，里面存了信息的，现在要分配，那么复制b的信息到栈中继续分配

看这个例子把，PPT不知道写的什么玩意

(2条消息) 实例讲解成组链接法_成组链接法例题_smartab的博客-CSDN博客

补充部分chap5

最重要的其实就是这一张表

用户打开文件表在pcb里，存放的是指向系统打开文件表项的指针，系统打开文件表就有inode等重要信息

files_struct 用户打开文件表

file_struct 系统打开文件表

简答题汇总

1. 试写出进程映像包括哪些组成部分(不必详述每个组成部分的具体内容)。

进程控制块、进程程序块（进程数据块）和进程核心栈。

第六版的书上P57只分了三个

进程数据块包含了下图的绿色部分

2. I/O 软件的一般分为四层结构，请按照自顶向下的顺序写出四层结构的名称。

3. 请画出三状态、五状态和七状态进程模型（包括挂起）及其状态转换图

4. 进程调度：6种 3抢 3不抢

感觉就是FeedBack只要来了就会给机会运行一段时间

注意RR算法是先来先服务的，所以新来的只要还有在运行，就要排队，而且新来的会比正在运行的那个先排到队尾

5. 银行家算法

6. 页面替换算法

Belady/最佳置换/OPT

FIFO/先进先出

最近最少使用/ LRU

时钟CLOCK

设置访问位和一个循环移动的指针
如果命中，指针是不会动的，只是把访问位变为1（本来是1就还是1

工作集模型和工作集置换方法

7. 操作系统三个最基本的抽象以及为什么要引入

进程抽象–是对已进入主存正在运行的程序在处理器上操作的状态集的抽象
虚存抽象–是对物理主存的抽象,进程可获得-个硕大的连续地址空间来存放可执行程序和数据，可使用虚拟地址来引用物理主存单元。
文件抽象–是对设备(磁盘)的抽象。

防止硬件资源被失控的应用程序滥用

以及屏蔽复杂的硬件资源操作细节，为应用程序提供使用硬件资源的简单且一致的方法。

8. 霍尔管程

读者写者：应该是写者优先，实现的是

ChrisDing's bblog

notes-os