第二章操作系统复习要点

第二章操作系统复习要点

本章每次约3题

一、资源互斥（PV）

信号量包含两类，一类是公用信号量，他实现进程间的互斥，初值为1或资源数目；另一类是私用信号量，它实现进程间的同步，初值为0或某个正数。

• PV操作是对信号量的操作

• P是给信号量减1、V是给信号量+1

• P操作的是自己的私有信号量、V是操作别人的私有信号量、公有信号量每个进程的PV都能操作

二、进程管理

三态模型

• 就绪状态：就是“万事俱备只欠东风”的状态，进程已得到运行所需资源，只等待cpu的调度便可运行。

• 运行状态：进程已得到运行所需资源，并且得到了cpu的调度。

• 等待状态：不具备运行条件，等待时机的状态，也叫阻塞状态

引起进程状态转换的具体原因：

（1）运行态->等待态。等待使用资源；如等待外设传输；等待人工干预

（2）等待态->就绪态。资源得到满足；如外设传输结束；人工干预完成。

（3）运行态->就绪态。运行时间片到；出现更高优先权进程。

（4）就绪态->运行态。CPU空闲时选择一个就绪进程。

五态模型

（1）活跃阻塞态->静止阻塞态。如果当前不存在活跃就绪进程，那么至少有一个等待进程将被对换出来成为静止阻塞态；操作系统根据当前资源状况和性能要求，可以决定把活跃阻塞态进程对换出去成为静止阻塞态。

（2）静止阻塞态->静止就绪态。引起进程等待的事件发生之后，相应的静止阻塞态进程将转换为静止就绪态。

（3）静止就绪态->活跃就绪态。如果内存中没有活跃就绪态进程，或者静止就绪态进程具有比活跃就绪态进程更高的优先级，系统将把静止就绪态进程转换成活跃就绪态。

（4）活跃就绪态->静止就绪态。操作系统根据当前资源状况和性能要求也可以决定把活跃就绪态进程对换出去成为静止就绪态。

（5）静止阻塞态->活跃阻塞态。当一个进程等待一个事件时，原则上不需要把它调入内存。但当一个进程退出后，主存已经有了一大块自由空间，而某个静止阻塞态进程具有较高优先级，并且操作系统已经得知导致它阻塞的事件即将结束，此时便发生这一状态变化

三、资源安全

资源数（安全的）= 互斥进程数X（每个进程所需最大资源数-1）+1

如果题目给出的资源数不是安全的，则有产生死锁的可能

四、磁盘读写时间、序列相关

读取磁盘需要3个参数：柱面号、磁头号（盘面号）、扇区号。

读取顺序：先根据柱面号找柱面->选定磁头->找扇区

存取时间=寻道时间+等待时间

处理时间=等待时间+记录处理时间

(记录处理最少等待时间=0，最长等待时间=磁盘旋转周期N ms/周*记录道数)

移动道数(或扇区)=目标磁道(或扇区)-当前磁道(或扇区)

寻道时间=移动道数*每经过一磁道所需时间

等待时间=移动扇区数*每转过一扇区所需时间

读取时间=目标的块数*读一块数据的时间

数据读出时间=等待时间+寻道时间+读取时间

平均等待时间=磁盘旋转一周所用时间的一半

(自由选择顺逆时钟时，最长等待时间为半圈，最短为无须旋转)

平均等待时间=(最长时间+最短时间)/2

平均寻道时间=(最大磁道的平均最长寻道时间+最短时间)/2

最大磁道的平均最长寻道时间=(最长外径+圆心)/2

位示图计算物理块

物理块的编号从0开始，实际物理块=物理块号+1（例4195号物理块其实是第4196块）

字长与物理块的关系：设字长为32位，也就是说每个字可以记录32个物理块的使用情况，4196/32=131.125,也就是说4195号物理块应该是在第131个字中。到第130个字为止，共保存了131*32=4192个物理块(0～4191)，所以，第4195块应该在第131个字的第3位记录(要注意：0是最开始的位)。

五、页式存储管理

基本思路：把物理内存划分为许多固定大小的内存块，称为物理页面；把逻辑地址空间也划分为大小相同的块，称为逻辑页面。当一个用户程序被装入内存时，不是以整个程序为单位，把它存放在一整块连续的区域，而是以页面为单位来进行分配的。对于一个大小为N的页面程序，需要有N个空闲的物理页面来把它装载。这些物理页面不一定是要连续的。

在页式存储管理中需要解决三个问题：数据结构、内存分配与回收、地址映射。

数据结构有两个：页表和物理页面表。

• 页表：给出了任务逻辑页面号和内存中物理页面号之间的对应关系。

• 物理页面表：描述内存空间中，各个物理页面的使用情况。

内存的分配过程：

• 对于一个新来的任务，计算它所需要的页面数N，然后查看位示图，看是否还有N个空闲的物理页面。

• 如果有足够的空闲物理页面，就去申请一个页表，其长度为N，并把页表的起始地址填入到该任务的控制块中。

• 分配N个空闲的物理页面，把他们的变换填到页表中，建立逻辑页面与物理页面直接的对 应关系。

• 修改位示图，对刚刚被占用的那些物理页面进行标记。

地址映射的基本思路：

• 逻辑地址分析：对逻辑地址，找到它所在的逻辑页面，以及它在页面内的偏移地址。

• 页表查找：根据逻辑页面号，从页表中找出它对应的物理页面号。

• 物理地址合成：根据物理页面号和页内偏移地址，最终确定物理地址。

逻辑地址分析：页面的大小都是2的整数次幂。对于给定的一个逻辑地址，可以直接把它的高位部分作为逻辑页面号，把它的低位部分作为页内偏移地址。例如，假设页面的大小是4KB，即2的12次幂，逻辑地址为32为，那么在一个逻辑地址当中，最低12位为页内偏移地址，而剩下的20位就是逻辑页面号。

计算方法：

• 逻辑页面号＝逻辑地址/页面大小

• 页内偏移量＝逻辑地址％页面大小

页表查找：

页表作为操作系统的一个数据结构，通常保存在内核的地址空间中。

页表基地址寄存器用来指向页表的起始地址；页表长度寄存器用来指示页表的大小，即对于当前任务，它总共包含有多少个页面。

物理地址合成：

假设物理页面号为f，页内偏移地址为offset，每个页面大小为2的n次方，那么相应的物理地址为：f×（2的n次方）+offset。