OS_homework01

鉴于某OS老师只允许使用word提交作业且不允许手写拍照上传这种难以理解的方式，所以在博客中记载一下自己的答案，如有错误欢迎留言 🥳

最后更新于2023-04-19

• 试述系统调用的实现原理，陷阱机制和绘制系统调用的处理过程，并阐述系统调用的处理逻辑。（满分10分）

操作系统实现系统调用功能的机制称为系统陷阱或系统异常处理机制，由于系统调用而引起处理器中断的机器指令称为陷入指令 (trap)，它是非特权指令，在用户态下执行时会产生 CPU 模式切换，即由用户态转换到内核态。每个系统调用都事先规定编号，称为功能号，执行陷入指令时，必须通过某种方式指明对应系统调用的功能号，大多数情况，还应附带有传递给相应服务例程的参数.

系统调用的实现要点包括：

(1) 编写系统调用服务例程；

(2) 设计系统调用入口地址表，每个入口地址都指向一个系统调用的服务例程，有些还包含系统调用自带参数的个数；(3) 陷阱处理机制，需要开辟现场保护区，以保存发生系统调用时应用程序的处理器现场。

\系统调用的处理过程**：应用程序执行系统调用，产生中断转向内核态，进入陷阱处理程序,它将按功能号来查询入口地址表，并转至对应服务例程执行，完成后退出中断，返回应用程序断点继续运行。

\参数传递**是系统调用中需要处理的问题，不同的系统调用要向相应的内核服务例程传递不同参数，反之，执行系统调用的结果也要以参数形式返回给应用程序。

\实现应用程序和系统调用之间传递参数所采用的方法**有：

(1) 陷入指令自带参数，可以规定陷入指令之后的若干单元存放参数，叫做直接参数；或者在指令之后紧临的单元中存放参数的地址，叫做间接参数，即由间接地址指出参数的存放区；

(2) 通过 CPU的通用寄存器传递参数，该方法不适用于传递大量参数，改进方法是在主存的某个区或表中存放参数，将其首地址送入寄存器，实现参数传递；

(3) 在主存中开辟专用堆栈区传递参数。

• 若内存中有3道程序A、B、C，按照A、B、C的优先次序运行。各程序的计算轨为：

A：计算（20ms），I/O（30ms），计算（10ms）

B：计算（40ms），I/O（20ms），计算（10ms）

C：计算（10ms），I/O（30ms），计算（20ms）

如果3道程序都使用相同的设备进行I/O操作（即程序以串行方式使用设备，调度开销忽略不计），试分别画出①单道和②多道运行的时间关系图。在两种情况下，CPU的平均利用率各是多少？（满分6分）

1.单道运行的时间关系图如下，CPU 平均利用率为 (20 + 10 + 40 + 10 + 10 + 20) / 190 = 57.89%。

2.多道运行的时间关系图如下，CPU 平均利用率为 ( 20 + 30 + 10 + 10 + 10 + 10 + 20 ) / 140 = 78.57%

• 在一个只支持四道程序同时运行的多道程序系统中，若在一段时间内先后到达6个作业，其提交时刻和估计运行时间由下表给出。

  | 作业 | 提交时刻 | 估计运行时间/min |
  | —— | ———— | ———————— |
  | 1 | 8:00 | 60 |
  | 2 | 8:20 | 35 |
  | 3 | 8:25 | 20 |
  | 4 | 8:30 | 25 |
  | 5 | 8:35 | 5 |
  | 6 | 8:40 | 10 |

  系统采用SRTF调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被剩余时间更短的作业所抢占。

  ①分别给出6个作业的开始执行时间、作业完成时间、作业周转时间。

  ②计算平均作业周转时间。（满分8分）

平均作业周转时间为 (155 + 95 + 20 + 55 + 15 + 20) / 6 = 60min

• 设有4个进程P1、P2、P3、P4，它们到达就绪队列的时刻、运行时间及优先级（优先数越大优先级越高）如下表：

  | 进程 | 到达就绪队列时刻 | 运行时间 | 优先级 |
  | —— | ———————— | ———— | ——— |
  | P1 | 0 | 9 | 1 |
  | P2 | 1 | 4 | 3 |
  | P3 | 2.5 | 8 | 2 |
  | P4 | 3.5 | 10 | 4 |

  ①若采用抢占式优先数调度算法（抢占的时间点为高优先级进程达到就绪队列的时刻），试给出各个进程的调度次序以及进程的平均周转时间和平均等待时间。

  ②若采用时间片轮换调度算法，且时间片长度取2ms，试给出各个进程的调度次序以及进程的平均周转时间和平均等待时间。（满分10分）

①平均周转时间：(31 + 14 + 20.5 + 8) / 4 = 18.875 ms

平均等待时间：（ 22 + 10 + 12.5 + 0 ）/ 4 = 11.125 ms

②进程调度次序为 P1、P2、P1、P3、P4、P2、P1、P3、P4、P1、P3、P4、P1、P3、P4

平均周转时间为：(25 + 11 + 24.5 + 27.5)ms ÷ 4 = 22ms

平均等待时间为：(16 + 7 + 16.5 + 17.5)ms ÷ 4 = 14.25ms

• 在UNIX系统中运行以下程序，请画出可能产生的进程的家族树（建议使用字母标识各进程），并计算最多可再产生出多少个进程？（6分）

  main( ){
     fork( ); /*←PC(程序计数器)，进程A
     fork( );
     fork( );
  }

最多可产生8个进程

• 有一多道程序设计系统，1）进程调度采用时间片调度算法（本题中的时间片调度算法理解处于就绪态的若干进程在某个时间段内平分CPU时间），不考虑进程的输入输出和操作系统的调度开销；2）存储管理采用可变分区方式，用户空间为100K，采用最先适应算法分配主存且不允许移动；3）系统配有4台磁带机，对磁带机采用静态分配策略。今有如下作业序列：

  | 作业名 | 进输入井时间 | 需执行时间 | 主存量要求 | 申请磁带机数 |
  | ——— | —————— | ————— | ————— | —————— |
  | J1 | 10:00 | 25分钟 | 15K | 2 |
  | J2 | 10:20 | 30分钟 | 60K | 1 |
  | J3 | 10:30 | 10分钟 | 50K | 3 |
  | J4 | 10:35 | 20分钟 | 10K | 2 |
  | J5 | 10:40 | 15分钟 | 30K | 2 |

  假定操作系统从11:00开始调度，请填空以下时间，并给出详细的解题步骤

  1. 当作业调度采用“先来先服务算法”时
  2. 当作业调度采用“响应比最高优先算法”时

1. 当作业调度采用“先来先服务算法”时：（满分10分)

   J1装入主存时间： 11:00 ；

   J2装入主存时间： 11:00 ； J3装入主存时间： 12:30 ；

   J4装入主存时间： 11:50 ； J5装入主存时间： 12:00 ；

   

2. 当作业调度采用“响应比最高优先算法”时：（满分10分）

   J1装入主存时间： 11:10 ；

   J2装入主存时间： 12:00 ； J3装入主存时间： 11:00 ；

   J4装入主存时间： 11:40 ； J5装入主存时间： 11:10 ；

   

   • 11:00

     J1响应比= 1+60/25 = 3.4

     J2响应比= 1+40/30 = 1+ 4/3

     J3响应比= 1+30/10 = 4

     J4响应比= 1+25/20 = 2.25

     J5响应比= 1+20/15 = 1+ 4/3

   • 11:10

     J1响应比= 1+70/25 = 3.8

     J2响应比= 1+50/30 = 1+ 5/3

     J4响应比= 1+35/20 = 2.75

     J5响应比= 1+30/15 = 3

   • 11:40

     J2响应比= 1+80/30 = 1+ 8/3

     J4响应比= 1+65/20 = 4.25

   • 12:00

     只有J2

• 某一页式存储管理系统，假设其页表全部存放在内存中。

​ ①若访问内存的时间为120ns，那么访问一个数据的时间是多少？
​ ②若增加一个快表，无论命中与否均需20ns的开销，假设快表的命中率为80％，此时访问一个数据的时间是多少？（满分8分）

1. 120 ns * 2 = 240 ns
2. 80% (120+20) + 20% (120+120+20) = 164 ns

• 在一页式存储管理系统中，逻辑地址长度为16位，页面大小为4096B，已知第0、1、2页依次存放在第10、12、14号物理块中，现有逻辑地址2F6AH，请问其相应的物理地址是多少？（地址以十六进制表示）（满分8分)

由于逻辑地址长度为 16 位，页面大小为 4096B，所以后 12 位表示页内偏移量，前 4 位表示逻辑页号，对于逻辑地址 2F6AH，其逻辑页号为 2，对应物理页号为 14，所以该逻辑地址的物理地址是 EF6AH。

• 假设一个物理存储器有4个页框，一个程序运行的页面走向是：1-2-3-1-4-5-1-2-1-4-5-3-4-5。假定所有页框最初都是空的，分别使用OPT、FIFO、LRU、CLOCK、MIN(滑动窗口τ＝3)、WS(工作集窗口尺寸△＝2)。算法，计算访问过程中所发生的缺页中断次数和缺页中断率。（满分24分）

• 最优置换算法OPT

  缺页6次。中断率为42.86%

  | 页面序列 | 1 | 2 | 3 | 1 | 4 | 5 | 1 | 2 | 1 | 4 | 5 | 3 | 4 | 5 |
  | ———— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— |
  | 页框1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 |
  | 页框2 | | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
  | 页框3 | | | 3 | 3 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
  | 页框4 | | | | | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
  | 缺页标记 | F | F | F | | F | F | | | | | | F | | |

• 先进先出算法FIFO

  缺页10次。中断率为71.43%

  | 页面序列 | 1 | 2 | 3 | 1 | 4 | 5 | 1 | 2 | 1 | 4 | 5 | 3 | 4 | 5 |
  | ———— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— |
  | 页框1 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 4 | 4 |
  | 页框2 | | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 5 |
  | 页框3 | | | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
  | 页框4 | | | | | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 3 | 3 | 3 |
  | 缺页标记 | F | F | F | | F | F | F | F | | | | F | F | F |

• 最近最少使用算法（LRU）

  缺页7次。中断率50%

  | 页面序列 | 1 | 2 | 3 | 1 | 4 | 5 | 1 | 2 | 1 | 4 | 5 | 3 | 4 | 5 |
  | ———— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— |
  | 页框1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
  | 页框2 | | 2 | 2 | 2 | 2 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
  | 页框3 | | | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 3 | 3 | 3 | 3 |
  | 页框4 | | | | | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
  | 缺页标记 | F | F | F | | F | F | | F | | | | F | | |

• Clock调度算法

  缺页10次,中断率71.43%

  | 页面序列 | 1 | 2 | 3 | 1 | 4 | 5 | 1 | 2 | 1 | 4 | 5 | 3 | 4 | 5 |
  | ———— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— |
  | 页框1 | 1 | 1 | 1 | 1 | →1 | 5 | 5 | 5 | 5 | 5 | 5 | →5 | 4 | 4 |
  | 页框2 | → | 2 | 2 | 2 | 2 | →2 | 1 | 1 | 1 | 1 | 1 | 1 | →1 | 5 |
  | 页框3 | | → | 3 | 3 | 3 | 3 | →3 | 2 | 2 | 2 | 2 | 2 | 2 | →2 |
  | 页框4 | | | → | → | 4 | 4 | 4 | →4 | →4 | →4 | →4 | 3* | 3 | 3 |
  | 缺页标记 | F | F | F | | F | F | F | F | | | | F | F | F |

• MIN(滑动窗口τ＝3)

  缺页 9 次,中断率64.29%

  | 时刻t | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
  | ———— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— |
  | 引用串 | | 1 | 2 | 3 | 1 | 4 | 5 | 1 | 2 | 1 | 4 | 5 | 3 | 4 | 5 |
  | P1 | | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | | | | | |
  | P2 | | | ✓ | | | | | | ✓ | | | | | | |
  | P3 | | | | ✓ | | | | | | | | | ✓ | | |
  | P4 | | | | | | ✓ | | | | | ✓ | ✓ | ✓ | ✓ | |
  | P5 | | | | | | | ✓ | | | | | ✓ | ✓ | ✓ | ✓ |
  | IN | | P1 | P2 | P3 | | P4 | P5 | | P2 | | P4 | P5 | P3 | | |
  | OUT | | | | P2 | P3 | | P4 | P5 | | P2 | P1 | | | P3 | P4 |
  | 缺页标记 | | F | F | F | | F | F | | F | | F | F | F | | |

• 工作集算法 WS(∆ = 2)

  缺页9次,中断率64.29%

  | 时刻t | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
  | ———— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— |
  | 引用串 | | 1 | 2 | 3 | 1 | 4 | 5 | 1 | 2 | 1 | 4 | 5 | 3 | 4 | 5 |
  | P1 | | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | | | |
  | P2 | | | ✓ | ✓ | ✓ | | | | ✓ | ✓ | ✓ | | | | |
  | P3 | | | | ✓ | ✓ | ✓ | | | | | | | ✓ | ✓ | ✓ |
  | P4 | | | | | | ✓ | ✓ | ✓ | | | ✓ | ✓ | ✓ | ✓ | ✓ |
  | P5 | | | | | | | ✓ | ✓ | ✓ | | | ✓ | ✓ | ✓ | ✓ |
  | IN | | P1 | P2 | P3 | | P4 | P5 | | P2 | | P4 | P5 | P3 | | |
  | OUT | | | | | | P2 | P3 | | P4 | P5 | | P2 | P1 | | |
  | 缺页标记 | | F | F | F | | F | F | | F | | F | F | F | | |