概要

  • 进程管理
  • 进程的状态 ⭐⭐
  • 前驱图 ⭐ ⭐ ⭐
  • 信号量与PV操作 ⭐ ⭐ ⭐ ⭐
  • 死锁及银行家算法 ⭐ ⭐ ⭐ ⭐
  • 存储管理
  • 段页式存储 ⭐ ⭐ ⭐ ⭐
  • 页面置换算法⭐
  • 文件管理
  • 绝对路径与相对路径⭐⭐⭐
  • 索引文件⭐⭐
  • 位示图⭐⭐
  • 作业管理
  • 设备管理
  • 虚设备与SPOOLING技术⭐


    一、进程管理

    1、进程

    1 ）定义

    进程是程序在一个数据集合上运行的过程，他是系统进行资源分配和调度的一个独立单位

    2）组成

    程序块、进程控制块（PCB）、数据块

    2、进程与程序的区别

    1）进程是程序的一次执行过程，没有程序就没有进程
    2）程序是静态的，进程是动态的
    3）进程由创建而产生，完成任务后因撤销而消亡
    4）进程是系统进行资源分配和调度的独立单位，而程序不是

    二、进程的状态

    image.png

    三、进程的同步与互斥

同步 —- 直接制约关系

image.png
步行与自行车一起到终点B，
步行速度慢
自行车速度快，
若要同时到达，自行车需要等待一下步行，两者相互制约
步行与自行车类比的 进程

互斥 —- 间接制约关系，为了争夺临界资源

四、PV操作

1、临界资源

进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等

2、临界区

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

3、信号量

一种特殊的变量

4、P是荷兰语的Passeren，V是荷兰语的Verhoog

P操作—-申请资源的操作
V操作—-释放资源的操作
S —- 信号量

1）P操作，申请资源，信号量（资源）减一，判断资源是否还有，
如果有（F）继续下面的操作
如果没有（T）进入阻塞进程队列，等待资源
2）V操作，释放资源，信号量（资源）加一，判断资源是否还有，
如果有（F）继续下面的操作，
如果没有（T）进入阻塞进程队列
image.png

5、互斥

多个进程共享一台打印机问题（互斥模型）

P(S)
使用打印机；
V(S)
后续代码

例子：
理发店有一个剪头师傅S，师傅就是一个临界资源，
当前S = 1
来了第一个客人，就申请剪头，P1(S)操作
P1(S) —— S = 1-1 = 0
让师傅箭头
V1(S)
当来了第二个客人，申请剪头，P2(S)
此时S = 0 ，s= s-1 = -1<0
师傅在忙，所以第二个客人进入阻塞等待状态
等第一个客人剪完头，V1(S)释放师傅，第二个客人才能剪

6、同步

单缓存区生产者、消费者问题（同步模型）

S1 为市场空位容量，S2 位市场货物容量
S1 初始值为1，S2 初始值为0
S1=0 表示不能生产，S2 = 0 表示不能消费

生产者 —- > 市场 —->消费者

生产者：
生产一个产品；
P(s1) —— 申请一个市场空位的资源，生产完产品后可以放到市场
送产品到缓存区（市场）
V(s2) —— 放一个市场货物资源，由消费者可以申请
此时：S1 = 0 ,S2 = 1

消费者：
P(S2) —— 申请一个市场货物资源，可以取产品
到缓冲区取产品；
V(s1) —- 取完产品后，释放市场空位的资源，生产者就可以继续生产了
此时 ：s1=1 ,s2 = 0

五、前驱图

image.png

sa = 0 , sb = 0, sc = 0 , sd =0 ,se = 0

进程A ：
xxx操作；
V(sa)

进程B：
xxxx操作；
V(sb)

进程C：
xxx操作；
V(sc)

进程D：
P(sa)
P(sb)
P(sc)
xxx操作；
V(sd)

进程E:
P(sd)
xxx操作；

例题
image.png
技巧：
1）每条线上标注 信号量，标注顺序从上到下，从左到右
2）线的起始头是V操作，到达头是P操作

六、死锁

1、例题
假设有5个进程，这5个进程都需要4个系统资源，系统至少有多少个资源，则不可能发送死锁
答：（4-1）x5+1 = 16
每个进程至少要必须的系统资源 减1 +一个系统资源
2、形成死锁的4个必要条件
环路等待 — 》 互斥 — 》保持和等待 —》不剥夺
死锁的预防：打破四大条件
死锁的避免：有序资源分配法、银行家算法
3、银行家算法
1）当一个进程对资源的最大需求量 不超过系统中的资源数时
2）进程可以分期请求资源，但请求的总数不能超过最大需求量
3）当系统现有资源不能满足进程尚需资源时，对进程的请求可以推迟分配，
但总能使进程在有限的时间里得到资源
例题
image.png
解法：
1）最大需求量：R1 = 9 , R2 = 8 ，R3 = 5
2）系统中剩余量：
R1 = 9 - (1+2+2+1+1) = 2
R2 = 8 - (2+1+1+2+1) = 1
R3 = 5 - (1+1+3) = 0
3）各进程剩余所需要的资源数


 R1 R2 R3
P1 5 3 1
P2 0 1 0
P3 6 0 1
P4 0 0 1
P5 2 3 1

4）根据系统资源剩余量 2 1 0 和3）中所需要的资源数做比较，
可以看出，先给P2 分配资源
0 1 0 < 2 10
P2进程完成后，释放P2所需要的资源 21 1 ，故当前剩余资源数为 4 2 1
然后给P4 分配资源，P4完成后，剩余 5 4 1
然后可以给 P5 或者P1 分配资源…

七、存储管理-页式存储

1、页式存储组织

1）定义：将程序与内存均划分成同样大小的块，以页为单位将程序调入内存
2）逻辑地址 = 页号+页内地址
3）物理地址 = 页帧号+页内地址
4）物理块号= 页帧号
5）优点：利用率高、碎片小、分配及管理简单
6）缺点：增加了系统的开销、可能产生抖动现象、

例题：
页式存储系统中，每个页的大小为4kb，
页表：

页号 块号
0 2
1 3
2 6
… …

逻辑地址为 ：
10 1100 1101 1110
那么对应的物理地址是？

答：4kb = 2^12
所以逻辑地址= 页号+页内地址
10 1100 1101 1110
(10)= 2
页号2 对应的块号是 6
6 = (110)
所以对应的物理地址是 110 1100 1101 1110

2、页表补充

高级语言中 内存中 1：在内存中 1：最近被访问过 1：内容被修改过
使用 使用 0：不在 0：未被 0：未被

页号（逻辑） 页帧号（物理） 状态位 访问位 修改位
0 2 1 1 0
1 3 1 0 1
2 6 1 1 0
3 —— 0 0 0


八、存储管理-段氏存储

1、段氏存储

1）定义：按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样
2）优点：多道程序共享内存，各程序段修改互不影响
3）缺点：内存利用率低，内存碎片浪费大
4）合法段地址：（0，25k）
5）非法段地址：（0，35k）
image.png

九、存储管理-段页式存储组织

1）定义：段氏和页式的综合体，先分段、再分页。每个段中可以有若干页，每个页的大小相同，但每个段的大小不同
2）优点：空间浪费小，存储共享容易、存储保护容易、能动态连接
3）缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件及占用的内容也有所增加，使得执行速度下降

快表

是一块小容量的相连存储器，由高速缓存器祖册，速度快，一般用来存放当前访问最频繁的少数活动页面的页号
快表放在cache，慢表放在内存里

页面置换算 法

1、最优算法 OPT
2、随机算法 RAND

3、先进先出FIFO ，有可能产生抖动（考）

4、最近最少使用算法 LRU ,不会 抖动，LRU的理论依据是 局部性原理（考）

时间局部性：刚被访问的内容，立即又被访问
空间局部性：刚被访问的内容，临近的空间很快被访问

十、存储管理-磁盘管理

磁道、扇区、0磁道 柱面
image.png
1）存取时间=寻道时间+等待时间
2）寻道时间：磁头移动到磁道所需的时间
3）等待时间：等待读写的扇区转到磁头下方所用的时间

十一、存储管理-磁盘调度算法

1）先来先服务（FCFS）
2）最短寻道时间优先 （SSTF）
3）扫描算法 （SCAN）-电梯算法
4）循环扫描（CSCAN）算法

读取磁盘数据时间计算

1）找磁道的时间
2）找块（扇区）的时间，级旋转延迟时间
3）传输时间
例题
1）某磁盘磁头从一个磁道移动到另一个磁道需要10ms
2）文件在磁盘上非连续存储，逻辑上相邻的数据块的平均移动距离是 10个磁道
3）每块旋转延迟时间是100ms
4）传输时间是 2ms
问 ：读取一个100块的文件需要多少时间
答：(10x10 + 100+ 2) x100 =20200

十二、作业管理

十三、作业调度算法

1）先来先服务
2）时间片轮转法
3）短作业优先法
4）最高优先权优先法
5）高响应比优先法
响应比= 作业等待时间/执行时间

十四、文件管理-索引文件结构

索引节点 0- 12 号，13个结点
假设每个块是 4K大小，所以为 4kx13 = 52 k
1）直接索引（0-9），容量 4kx10 = 40k
2）一级间接索引，10号节点存的是物理盘块的地址，每个地址假设占4个字节，那么 4k/4 = 1k = 1024个地址
所以容量是 4Kx 1024
3）二级间接索引，11号，4kx 1024 x 1024
3）三级间接索引，12号，4k x1024 x 1024x1024

十五、文件管理-树形目录结构

1、根目录

/

2、相对目录

/D1/W2/F2

3、绝对目录

W2/F2

十六、文件管理-空闲存储空间的管理

位示图法

用于飞机座位订票之类，可能考察容量计算题
例题：
磁盘的物理块依次为 ：0、1、2…
系统中字长为 32 位，每一位对应文件存储器上的一个物理块，
取值0和1 分别代表 空间和占用
问：
1）假设将 4195号物理块分配给某文件
那么该物理块号使用情况为 在位视图中是用第几个字表示
（4195+1）/32 = 131.xxx
故为 132字
2）131 x 32 = 4192 —- 0 - 4191
0 位置 4192
1 4193
2 4194
3 4195

十七、设备管理-数据传输控制方式

程序控制方式（CPU介入）
程序中断方式
DMA方式，无关CPU，硬件完成
通道方式
IO处理机（IOP）

从上到下，效率越来越高

十八、设备管理-虚设·备与SPOOLING技术

假脱机技术

十九、微内核操作系统
微内核、单体内核的对比