软考流水线的一个典型题：

某指令流水线由5段组成，各段所需要的时间如下图所示。

--> t --> 3t --> t --> 2t --> t -->

连续输入10条指令时的吞吐率为（ ）。

A.10/70t B.10/49t C.10/35t D.10/30t

解答：

第一条指令　－（ －－－）－（－－）－

第二条指令　　　　　 －（－－－）－（－－）－

第三条指令                      　　　　－（－－－）－（－－）－

因为　是流水线，所以时间为3t的指令不能重叠（小马认为可以理解为就一个3t的执行单元），所以每隔3t时间开始一条指令，当第一条指令花费8t时间后，每隔3t完成一条指令，第10条指令完成的时间是：8+3*9=35t.

吞吐率为:10条指令/花费时间35t＝10/35

弄懂两个概念就好做了：流水线时间和吞吐率

流水线时间计算有个公式：一条指令所需时间+（指令条数-1）*时间最长的指令的一段 // 8t+9*3t=35t

吞吐率也有个公式：指令条数除以流水线时间 // 10/35t

原文

PV和前趋图

概念：

信号量 ： 信号量(Semaphore)，以下简写为S，有时被称为信号灯，是在多线程环境下使用的一种设施，是可以用来保证两个或多个关键代码段不被并发调用。

当S>0时，表示当前可用资源的数量。

当S<0时，其绝对值表示等待使用该资源的进程个数。

注意，信号量的值仅能由PV操作来改变。

PV操作： PV操作与信号量的处理相关，P表示通过的意思，V表示释放的意思。PV原语中P是荷兰语的Passeren，相当于英文的pass， V是荷兰语的Verhoog，相当于英文中的increment。

  P操作可以看作是获得或者请求、消耗一个信号量。

将信号量S的值减1，即S=S-1；

如果S>=0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。

  V操作可以看作是释放或者发送一个信号量。

将信号量S的值加1，即S=S+1；

如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。

下面来看几道例题：

1.（2016年下半年例题）假设系统中有n个进程共享3台扫描仪，并采用PV操作实现进程同步与互斥。若系统信号量S的当前值为-1，进程P1、P2又分别执行了一次P(S)操作，那么信号量S的值应为___。

解答：

根据PV操作概念中P操作公式，S=S-1，这里发生两次P操作，那么当前S的值应该为-1减2次操作后等于-3。

【小马认为，这个根据公式，是属于比较简单的一个送命题，啊不是，送分题】

2.（2016年上半年例题) 进程P1、P2、P3、P4和P5的前趋图如下图所示：

若用PV操作控制进程P1、P2、P3、P4和P5的并发执行过程，则需要设置5个信号量S1、S2、S3、S4和S5，且信号量S1～S5的初值都等于零。下图中a和b处应分别填入___;c和d处应分别填入___;e和f处应分别填入___。

解答：

根据前趋图，P1进程执行完需要通知P2和P3进程，所以需要利用V(S1)和V(S2)操作通知P2和P3进程，所以空a应该填V(S1)和V(S2)，P2进程执行完要通知P4进程，所以空b应该填V(S3)。P3进程运行前需要等待P1进程的结果，所以执行程序前要先利用1个P操作，所以空c应该填P(S2)，而P3进程运行结束需要利用一个V操作通知P5进程，所以空d应该填V(S4)。P4进程执行结束需要利用一个V操作通知P5进程，所以空e处应该填V(S5)，P5进程执行前需要等待P3和P4进程的结果，所以空f处需要两个P操作，那应该填P(S4)和P(S5)。

【小马认为，这种解题技巧可以这样理解：既然是参考前趋图那就充分利用前趋图，在前趋图上的每一个箭头画上信号灯，如下图，问题便可迎刃而解。】

3.(2015年下半年例题) 某企业的生产流水线上有2名工人P1和P2，1名质检员P3。P1将初步加工的半成品放入半成品箱B1；P2从半成品箱B1取出继续加工，加工好的产品放入成品箱B2；P3从成品箱P2取出产品检验。假设B1可存放n件半成品，B2可存放m件产品，并设置6个信号量S1、S2、S3、S4、S5和S6，且S3和S6的初值都为0。采用PV操作实现P1、P2和P3的同步模型如下图所示，则信号量S1和S5初始值分别为___，S2、S4的初始值分别为___。

解答：

根据题意可以看出这是一道很典型的生产者消费者问题，P1为生产者，P2即是消费者又是生产者，P3为消费者，B1和B2为缓存区。

因为信号量S1是一个互斥信号量，表示半成品箱B1当前有无生产者使用，所以初值为1。信号量S5也是一个互斥信号量，表示成品箱B2当前有无生产者使用，所以初始值为1。

信号量S2表示半成品箱B1的容量，所以S2的初值为n。当生产者P1不断将半成品放入B1时，应该先测试B1是否有空位，所以生产者P1使用P(S2)，当消费者P2从B1取出一件半成品时，B1就空出一个空位，所以消费者P2使用V(S2)释放空间。

同理，信号量S4表示半成品箱B2当容量，所以S4的初值为m。当生产者P2完成一件产品放入B2时，应先测试B2是否有空位，所以生产者P2使用P(S4)，当消费者P3从B2取出一件产品时，B2就空出一个空位，所以消费者P3使用V(S4)释放空间。

程序执行图如下所示：

经典问题，如：生产者与消费者，哲学家进餐，读者与作家等等。

操作系统相关知识-死锁-银行家算法

死锁：

两个以上的进程互相都要求对方已经占有的资源，导致无法继续继续执行下去的现象。

死锁产生的条件：

环路等待，互斥，保持和等待，不剥夺。

打破死锁的的条件：

死锁预防，死锁避免，死锁检测，死锁解除。

考点为死锁避免的银行家算法：

银行家算法：像借贷一样，安全才审批额度。

对于进程发出的每一个系统可以满足的资源请求命令加以检测，如果发现分配资源后系统进入不安全状态，则不予分配。

若分配资源后系统仍处于安全状态，则实施分配。

与死锁预防相比，提高了资源利用率，但检测分配后系统是否安全增加了系统开销。

此题的结题思路为：

先找到各资源未被分配的数量，看看哪个进程的需求量满足就可以执行该进程，进程执行完会将该进程的已分配资源数释放，累加到之前未分配的数量上，继续看哪个进程满足，依次执行。

【比如根据已分配资源得到，R1-R3未分配的资源是2,1,0；根据最大需求量，给P1资源也不够执行，给P2的话是可以执行的，则P2执行后将占有的资源释放到未分配的资源中，继续类推。小马认为该算法理解后不难】

存储管理（内存）之页式存储（虚拟存储）

存储管理

       操作系统中的存储有很多种，分别是页式存储，段式存储，段页式存数，磁盘存储等。分这么多种存储方式，无非是让我们在操作计算机的时候，计算机内存和用户操作之间的作业变的更加清楚和简单，并且能够保证数据不会丢失。接下来具体看下什么是页式存储。

基本原理：

       把用户数据加载到内存中进行处理，这个时候就会出现两种数据，一种是加载到内存中的数据，另一种是用户作业数据，为了合理利用内存的空间，并且使作业能够连续，这个时候将内存划分为大小相同的块，同样的，将用户作业空间划分为大小相同的页。

        所以： 页=块（大小相同）

说明：

注意理解一个概念，编程空间和页+页内偏移地址  是逻辑地址，块号和偏移地址是 物理地址。

p先计算每个数字（地址访问）大小用几位01可表示。   B KB MB.....1024=进制，          1字节=8bit

为什么每次要用2的几次方来运算，因为2B代表的是两位，组合起来为01,10，或者11，所以当每次计算的时候，用的就是2的幂次方来计算页内地址。

本题内存16KB数字是没用的吗？

【虚拟地址=页号+页内偏移；物理地址=块号+偏移，根据逻辑地址和位数 定位页号和偏移，根据页表查块号，拼接偏移得物理地址。小马觉得教材书上的那个图比这个图好理解】

虚设备与SPOOLing技术

为缓和CPU和高速性与I/O设备低速性的矛盾而引入了脱机输入、脱机输出技术。该技术是利用专门的外围控制机，将低速设备上的数据传送到高速磁盘上；或者相反。

这样就可以在主机的直接控制下实现脱机输入输出。此时外围操作与CPU对数据的处理同时进行，我们把这种来联机情况下实现的同时外围操作称为SPOOLing,或称为假脱机操作。

SPOOLing系统的有三大部分组成：

输入井和输出井。是磁盘上开辟的两大存储空间。

输入缓冲区和输出缓冲区。在内存中开辟两个缓冲区，输入缓冲区暂存由输入设备送来的数据，后送输入井来输出缓冲区暂存从输出井送来的数据，后送输出设备。

输入进程和输出进程。利用两个进程模拟脱机I/O时的外围处理机。

SPOOLing系统的特点：

提高了I/O的速度。利用输入输出井模拟成脱机输入输出，缓和了CPU和I/O设备速度不匹配的矛盾。

将独占设备改造成共享设备。

实现了虚拟设备功能。多个进程同时使用一台独占设备，虚拟成了多台设备。

【用一个类似队列排队的过程，就可以所有进程同时处理了】