操作系统作业

发表于 更新于 分类于 ， 阅读次数：

作业一

1

题目：

在某个计算机系统中有一台输入机和一台打印机，现有两道程序投入运行，且程序A先运行，程序B后开始运行。

  • 程序A的运行轨迹为：
    计算50ms，打印100ms，再计算50ms，打印100ms。

  • 程序B的运行轨迹为：
    计算50ms，输入80ms，再计算100ms，结束。

问题：

  1. 两道程序运行时，CPU是否空闲等待？____（有空闲等待 / 无空闲等待）
    若有，在哪段时间内等待？_ms - _ms（两个空，第一个填起始时间，第二个填结束时间，仅数字）

  2. 程序A，B是否有等待CPU的情况？
    A：（有等待 / 无等待）
    B：    （有等待 / 无等待）
    若有，指出发生等待的时刻（若无等待，空格填0）
    （若有两段以上等待时间，用“/”标表示不同等待时间，如0/30和20/40表示0ms-20ms是第一段空闲；30ms-40ms是第二段空闲）
    A：_ms - _ms
    B：___ms - ___ms

IMG_20250917_090110

2

题目：

在单CPU和两台I/O设备（I1和I2）的多道程序设计环境下，同时投入三个作业运行，其执行轨迹如下：

  • Job1：I2（30ms），CPU（10ms），I1（30ms），CPU（10ms）
  • Job2：I1（20ms），CPU（20ms），I2（40ms）
  • Job3：CPU（30ms），I1（20ms）

已知条件：

  • CPU、I1、I2可以并行工作；
  • 优先级从高到低依次为：Job1、Job2、Job3；
  • 优先级高的作业可以抢占优先级低的作业（抢占式调度）；
  • 所有作业同时投入运行。

问题：

  1. 每个作业从投入到完成分别所需的时间。
    • Job1：____ ms
    • Job2：____ ms
    • Job3：____ ms
  2. 从作业投入到完成，CPU的利用率是：
    • ____ / ____ = ____%（保留小数点后两位）
  3. I/O设备利用率：
    • I1 利用率：____ / ____ = ____%（保留小数点后两位）
    • I2 利用率：____ / ____ = ____%（保留小数点后两位）
IMG_20250917_090158

3

题目：

在单机系统中，有同时到达的两个程序A、B，若每个程序单独运行，则使用CPU，DEV1（设备1）、DEV2（设备2）的顺序和时间如下表所示。

运行情况 程序A 程序B
CPU 25 20
DEV1 39 50
CPU 20 20
DEV2 20 20
CPU 20 10
DEV1 30 20
CPU 20 45

给定条件：

  1. DEV1和DEV2是不同的I/O设备，它们能够同时工作。
  2. 程序B优先级高于程序A，非抢占式。当程序A占用CPU时，即使程序B需要使用CPU，也不能打断程序A的执行，而应等待。
  3. 当使用CPU之后控制转向I/O设备，或者使用I/O设备之后控制转向CPU，由控制程序执行中断处理，但这段处理时间可以忽略不计。

问题：

  1. 哪个程序先结束？（A / B）
  2. 程序全部执行结束需要多少时间？（____ ms）
  3. 程序全部执行完毕时，CPU利用率是多少？（____%）
  4. A程序等待CPU的累积时间是多少？（____ ms）
  5. B程序等待CPU的累积时间是多少？（____ ms）
IMG_20250917_090145

作业二

1

image-20251010094314155
IMG_20251010_101637
IMG_20251010_101643

2

image-202510101021044143.

IMG_20251010_103349

3

image-20251010110615738
IMG_20251010_110541

作业三

1

有一个盒子里混装了数量相等的黑白围棋子，现在利用自动分拣系统把黑子、白子分开，设分拣系统有两个进程P1和P2，其中进程P1拣白子，进程P2拣黑子。规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试写出进程P1和P2能够正确并发执行的程序。

image-20251111211928061

2

请用信号量和PV操作解决以下问题：桌上有一只盘子，最多可以容纳两个水果，每次仅能放入或取出一个水果。爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放橘子(orange)，两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子里的苹果。写出爸爸（father）、妈妈（mother）、儿子（son）和女儿（daughter）进程及所需定义的变量和信号量。用PV操作实现爸爸、妈妈、儿子、女儿间的同步与互斥关系。

image-20251111211937533

3

设当前的系统状态如下，此时Available=(1,1,2)

进程 Claim (R1, R2, R3) Allocation (R1, R2, R3) Available (R1, R2, R3)
P1 3, 2, 2 1, 0, 0 1, 1, 2
P2 6, 1, 3 5, 1, 1
P3 3, 1, 4 2, 1, 1
P4 4, 2, 2 0, 0, 2
image-20251111211949933

作业四

1

数组int A[100][100]；元素按行存储，在虚拟系统中，采用LRU淘汰算法，一个进程有3页内存空间，每页可以存放200个整数，其中第1页存放程序，假定程序已在内容中，问：

A程序缺页次数为：____次；

B程序缺页次数为：____次。

程序A：

for(int i=0; i<100; i++)
   for(int j=0; j<100; j++)
        A[i,j]=0;

程序B：

for(int j=0;j<100;j++)
   for(int i=0;i<100;i++)   
        A[i,j]=0;

程序 A 分析

代码逻辑：

1
2
3
for(int i=0; i<100; i++)    // 外层循环：行
   for(int j=0; j<100; j++) // 内层循环：列
      A[i][j]=0;

访问顺序：A[0][0], A0, …, A[0][99], A[1][0], …

这是按行访问，与数组的按行存储顺序一致。

缺页计算过程：

  1. 访问第0、1行：都在虚拟页0中。
    • 第一次访问 A[0][0] 时，内存为空，发生 1次缺页，调入页0。
    • 后续访问第0行和第1行的剩余199个元素时，都在页0中，直接命中（不缺页）。
  2. 访问第2、3行：都在虚拟页1中。
    • 访问 A[2][0] 时，页1不在内存，发生 1次缺页，调入页1。
    • 后续元素全部命中。
  3. 以此类推：
    • 程序按照顺序访问：页0 → 页1 → 页2 … → 页49。
    • 由于我们有2个物理块，LRU算法会淘汰最久未使用的旧页面，但因为访问是单向顺序向前的，每一页只需要调入一次。

结果：共有50个页面，每页调入一次。

Total = 50 次缺页。

程序 B 分析

代码逻辑：

1
2
3
for(int j=0; j<100; j++)    // 外层循环：列
   for(int i=0; i<100; i++) // 内层循环：行
      A[i][j]=0;

访问顺序：A[0][0], A[1][0], A[2][0], …

这是按列访问，即“跳跃式”访问。

缺页计算过程：

  1. 分析内层循环（i 从 0 到 99，处理第 j 列）：
    • i=0, 1: 访问第0、1行 → 需要 虚拟页0。
    • i=2, 3: 访问第2、3行 → 需要 虚拟页1。
    • …
    • i=98, 99: 访问第98、99行 → 需要 虚拟页49。
    • 一轮内循环（i=0~99）会依次访问：页0, 页1, 页2, …, 页49。
  2. 内存状态与置换：
    • 我们只有 2个 物理块用于数据。
    • 当访问页0、页1时，填满内存。
    • 当需要页2时，根据LRU，淘汰页0。
    • 当需要页3时，根据LRU，淘汰页1。
    • …
    • 因为循环访问的页面数量（50页）远大于物理内存（2页），导致内存中的页面不断被替换（颠簸/Thrashing现象）。
    • 结论：在处理每一列（内层循环）时，需要访问所有50个页面。因为内存存不下，这 50个页面每一次都需要重新从磁盘调入。
    • 单列（一次外层循环）产生的缺页次数 = 50次。
  3. 结合外层循环：
    • 外层循环 j 从 0 到 99，共执行 100次。
    • 每次外层循环都要重新把这50个页面遍历一遍。由于上一轮留下的页面（最后访问的页48、49）对下一轮开头需要的页（页0）没有帮助。
    • 总缺页次数 = 每列缺页数 × 列数
    • Total = 50 × 100 = 5000。

结果：5000 次缺页。

2

在一个请求分页虚存管理系统中，一个程序运行的页面走向是：1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6

分别用FIFO、OPT、和LRU算法，对于分配给程序3个页框的情况，求出缺页异常次数和缺页中断率：

（1）FIFO：缺页异常次数：_____次, 缺页中断率：______%.

（2）OPT：缺页异常次数：_____次, 缺页中断率：______%.

（3）LRU：缺页异常次数：_____次, 缺页中断率：______%.

image-20251205102751318

3

一个页式虚拟存储管理系统中的用户空间为1024KB，页面大小为4KB，内存空间为512KB。已知用户的10、11、12、13号虚页分得的内存页框号为62、78、25、36，试将逻辑地址0BEBCH转换为对应的物理地址: _______H。

名词 英文 所在空间 本质 通俗解释（类比）
页面 (Page) Page 逻辑/虚拟空间 (程序里) 程序被切分成的“块” 客人 (要住店的人)
页号 (Page No.) VPN 逻辑/虚拟空间 页面的编号/索引 客人的身份证号
页框 (Page Frame) Page Frame 物理内存 (硬件里) 内存条被切分成的“格” 酒店的房间 (物理存在的空间)
页块 (Block) Physical Block 物理内存 完全等同于“页框” (别名) 完全等同于“房间”
页框号 (PFN) PFN 物理内存 页框的物理编号 房间号码 (如 302 号房)
页表 (Page Table) Page Table 内存中 (系统管理) 映射表 (记录对应关系) 前台登记簿 (记录谁住哪个房间)
image-20251205104211485