1.用户接口和作业管理

1.1作业

在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所作的有关该次业务处理的全部工作称为一个作业。

作业构成：

程序：
数据（作业体）：
作业说明书（作业控制语言）：体现用户的控制意图，包括作业基本情况、作业控制、作业资源要求的描述。

1.2用户接口

程序级接口——系统为用户在程序一级提供有关服务而设置，由一组系统调用命令组成
操作级接口——为用户提供各种命令

2.进程管理

2.1进程Pc和Pp合作完成计算打印任务

信号量

semaphore bufempty = 1 // 表示buf 空
semaphore buffull =0   //  表示buf满,

Pc {
  while(1)
  {
    P(bufempty)
    // 计算
    // buf -> 计算结果
    V(buffull)
  }  
}

Pp {
  while(1)
  {
    P(buffull)
    //  取出buf中的数据
    //  置空标记，打印
    V(bufempty)
  }  
}

2.2银行家算法

设系统在T0时刻系统状态为：剩余资源向量为：A=（2, 3, 3）

（1）T0时刻是否为安全状态？若是，请给出安全序列。

（2）在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？

（3）在②的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？

分析：

（1）安全，P5-> P4->P3->P2->P1

（2）若P2请求（0,3,4）大于剩余向量（2, 3, 3）,不能分配。

（3）可以，安全，安全序列为P4->P5->P1->p2->P3

3.处理机调度

3.1 单道系统

假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间：

应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间。

（1）FCFS：J1->J2->J3->J4

（2）短作业优先：J1->J3->J4->J2

（3）最高响应比优先：J1->J3->J2->J4

响应比：(等待时间 + 要求服务时间) / 要求服务时间

3.2 两道系统

在两道环境下有四个作业，已知它们进入系统的时间、估计运行时间，作业调度采用短作业优先算法，作业被调度运行后不再退出，进程调度采用剩余时间最短的抢先调度算法（假设一个作业创建一个进程）

请给出这四个作业的执行时间序列，并计算出平均周转时间及带权平均周转时间。

4.存储管理

4.1简单页式管理取

一次数据至少要访问内存两次：页表和指令

4.2 逻辑地址 → 物理地址

在一个段式存储管理系统中，其段表为:

求下述逻辑地址对应的物理地址是什么?

   （段号，段内位移）
1：（0，430）: 210+430 = 640
2：（1，10）：2350+10 = 2360
3：（2，500）：越界
4：（3，400）：1350+590=1750
5：（4，112）： 越界

4.3 访问时间计算

请求分页管理系统中，假设某进程的页表内容如下表所示：

页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为10^8ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设，①TLB初始为空；②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；③有效位为0表示页表不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：

(1)依次访问上述三个虚地址，各需要多少时间，给出计算过程；

(2)基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。

解析：

页面大小为4K， 12位，占用3个字节，所以地址2362H、1565H、25A5H所对应的页号为2、1、2，根据页表，2362H、25A5H在内存中，1565H不在内存中。

初始快表为空，故2362H需转入快表，25A5H直接访问快表，1565H需装入内存，再装入快表

（1）时间计算

2363H：10(访问快表)+100(访问页表)+100(访问主存单元)=210ns
1565H：10(访问快表)+100(访问页表)+10^8(调页)+10(访问快表)+100(访问主存)=100000220ns
25A5H：10(访问快表)+100(访问主存单元)=110ns

（2）根据页表，第0、2页中，由于第二页刚刚被访问过(2362H)，根据LRU算法，将第0页换出，因此对应页框号为101H，故1565H的物理地址为101565H。

4.4置换算法

在一采取局部置换策略的请求分页系统中，分配给某个作业的内存块数为4，其中存放的4个页面的情况如表所示：

上面所有时间均是从进程开始运行时从0开始计时的时钟数，如果系统采用：(1)FIFO算法；(2) LRU算法；(3) 改进的Clock算法，将选择哪一页换出？

（1）：物理3、虚拟3

（2）：物理0，虚拟2

（3）：物理2，虚拟0

4.5 置换算法

设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若进程最多需要6页存储空间，页的大小为1KB，操作系统若采用固定分配局部置换策略为此进程分配4个页面。在时刻260前的该进程访问情况如表所示（访问位即使用位）

当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据，请回答：（1）逻辑地址对应的页号是多少（2）若采用先进先出置换算法，该逻辑地址对应的物理地址是多少？给出计算过程。（3）若采用时钟置换算法，该逻辑地址对应的物理地址是多少？给出计算过程。设顺时针搜索下一页，且当前指向2号页面，示意图如下。

分析：

（1）页面大小为1KB，则页内偏移量为 2^10位，物理地址空间大小为64KB，需要2^5位存储页号和页框号。

17CAH: 0001 0111 1100 1010

所以页号为前6位：00101，页号为5。

（2）页号为5对应的页框号需要重新调入，由于页号为0的页面最先调入，替换该页，此时对应的页框号为7，即0111，所以物理地址为：0001 1111 1100 1010 ，1FCAH.

（3）换出2号页面，所以页框号为2，所以物理地址为：0000 1011 1100 1010，即0BCAH.

时钟置换算法规则：

为每一个页面设置一个访问位，再将内存中的页面都通过连接指针链接成一个循环队列。
当某个页面被访问时，其访问位置为1。
当需要淘汰一个页面时，只需检查页的访问位。如果是0就选择该页换出；如果是1，则将它置为0，暂不换出。
继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面依次置为0，在进行第二轮扫描（第二轮扫描一定会有访问位为0的页面）。

4.6请求分页

某请求分页系统的局部页面值环策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。

假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的<虚拟页号，访问时刻>是：<1,1>、<3,2>、<0,4> 、<0,6> 、<1,11> 、<0,13> 、<2,14>。请回答下列问题。

（1）访问<0,4>时，对应的页框号是多少？

（2）访问<1,11>时，对应的页框号是多少？说明理由。

（3）访问<2,14>时，对应的页框号是多少？说明理由。

（4）该策略是否适合于时间局部性能好的程序？说明理由。

分析：

（1）<0，4>对应的页框号为21.

（2）<1,11>对应的页框号为32；理由：因11>10故发生第三轮扫描，页号为1的页框在第二轮已处于空闲链表中，此刻该页又被重新访问，因此应被重新放回驻留集中，其页框号为32。

（3）<2,14>对应的页框号为41；理由：因第2页从来没被访问过，它不再驻留集中，因此从空闲页框链表中取出链表头的页框41，页框号为41。

（4）适合；理由：如果程序的时间局部性能越好，从空闲页框表中重新取回的机会越大，该策略的优势越明显。

4.7段页式管理

某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下所示：

请回答如下问题

（1）页和页框的大小各为多少字节？进程的虚拟地址空间大小为多少页？

（2）假定页目录项和页表均占4个字节，则进程的页目录和页表共占多少页？要求写出计算过程

（3）某指令周期内访问的虚地址为01000000H和01112048H，则进行地址转换时共访问多少个二级页表？要求说明理由。

分析：

（1）页大小 = 页框大小 = 2^12 = 4KB

进程的虚拟地址空间为：2^32 / 2^12 = 2^20页

（2）页目录所占页数：(2^10 * 4)/ 2^12 = 1页

页表所占页数：(2^10 * 2^10 *4) / 2^12 = 1024页（一个目录页装有2^10个页面）

共占 1+1024 = 1025 页

（3）访问一个二级页表

5.文件系统

5.1链接分配

设磁盘块大小为1KB，硬盘大小为500MB，采用显式连接分配方式时，其FAT需占多少存储空间？如果文件A占用硬盘的第11、12、16、14四个盘块，试画出文件A中各盘块间的链接情况及FAT的情况。

500MB/1KB = 500K(块)
250K < 500K < 512K
 字节存储 ：所以需要19位表示，19位需占用4个字节，即每个块占用4个字节的空间。500K * 4B = 2000KB
 位存储 ：500K * 19b = 9500Kb = 1187.5KB

5.2成组链接法

某个文件系统采用成组链接法管理磁盘空闲空间，目前磁盘的状态如图所示：

(1) 该磁盘中目前还有多少空闲盘块？301个，最后一个算标记，不存储数据。

(2)在为某个文件分配3个盘块后，系统要删除另一文件，并回收它所占的5个盘块，它们的盘块号依次为700、711、703、788、701，请画出回收后的盘块链接情况

分配三块，299,、300、301

回收700、711、703、788、701