操作系统经典习题解析合集

操作系统经典习题解析合集这里需要特别注意`P(mutex)`和`P(empty)/P(full)`的顺序。如果将`P(mutex)`放在`P(empty)`或`P(full)`之前，可能会导致死锁。例如，生产者先获取了`mutex`，然后执行`P(empty)`时发现缓冲区满而阻塞，此时它持有`mutex`，消费者就无法进入缓冲区取产品，`empty`信号量也就永远无法增加，导致生产者和消费者都永久阻塞。通过这三个信号量的配合，`empty`和`full`负责同步生产者和消费者的行为，确保了“生产了才能消费，消费了才能再生产”的逻辑；`mutex`则负责保证在任何时刻，只有一个进程（生产者或消费者）能够访问缓冲区这个临界资源，从而避免了数据竞争和不一致。这便是信号量机制解决经典同步互斥问题的精髓所在。内存管理篇内存管理直接关系到系统的性能和多道程序设计的效率，其核心在于如何高效地分配和回收内存空间，并为用户程序提供一个简洁、一致的内存视图。经典习题三：分页存储管理的地址转换题目：在一个采用分页存储管理方式的系统中，页面大小为4KB。某进程的页表如下所示（部分）：页号物理块号:---:-------0511023......请问：1.逻辑地址的结构是怎样的？（即页号占多少位，页内偏移占多少位）2.若给定一个逻辑地址为`0x1234`（十六进制），其对应的物理地址是多少？请写出计算过程。解析：分页存储管理是将进程的逻辑地址空间和内存的物理地址空间皆划分为大小相等的块，前者称为页面，后者称为物理块（或页框）。地址转换的核心就是将逻辑地址中的页号转换为对应的物理块号，再结合页内偏移得到物理地址。1.逻辑地址结构分析：题目中给出页面大小为4KB。我们知道，1KB=2^10字节，所以4KB=4*2^10=2^12字节。因此，页内偏移量需要12位二进制来表示，因为2^12=4096，正好对应4KB的偏移范围（0到4095）。逻辑地址的总位数取决于系统的寻址能力，但题目未直接给出。不过，页号的位数=逻辑地址总位数-页内偏移位数。但对于本题的第一问，我们只需明确页内偏移是12位，页号则占据剩余的高位部分即可。通常，我们会说逻辑地址由“页号（高位）”和“页内偏移（低位）”两部分组成，其中页内偏移为12位。2.逻辑地址到物理地址的转换：给定逻辑地址`0x1234`（十六进制）。首先，我们需要将其转换为二进制，以便分离出页号和页内偏移。十六进制的每一位对应4位二进制：`0x1`→`0001``0x2`→`0010``0x3`→`0011``0x4`→`0100`所以`0x1234`的二进制表示为：`0001001000110100`。总共有16位二进制。如前所述，页内偏移占12位（低12位）。因此，我们将这16位二进制数的低12位作为页内偏移，高4位（16-12=4）作为页号。*页内偏移（低12位）：`001000110100`。将其转换为十进制：`0*2^11+0*2^10+1*2^9+0*2^8+0*2^7+1*2^6+1*2^5+0*2^4+1*2^3+0*2^2+0*2^1+0*2^0`=512+64+32+8=616。或者更简单的，十六进制的低三位`0x234`就是页内偏移，`0x234`转换为十进制是2*16^2+3*16+4=2*256=512+48=560+4=564？等等，这里需要小心，我刚才的二进制分解是否正确？`0x1234`是一个16位的数吗？在32位或64位系统中，逻辑地址通常是32位或64位，但题目没有明确。不过，`0x1234`本身是4位十六进制数，即16位二进制。我们就按16位来处理。16位二进制数：`0001001000110100`。低12位是`001000110100`，对应的十六进制是`0x234`。`0x234`转换为十进制：2*16²+3*16+4=2*256=512+48=560+4=564。对，刚才算错了，是564。高4位是`0001`，对应的页号是1（十进制）。现在，我们查页表，页号1对应的物理块号是10。物理地址的计算方法是：物理块号×页面大小+页内偏移量。页面大小是4KB=4096字节。所以，物理地址=10*4096+564=____+564=____。如果用十六进制表示，物理块号10是`0xA`，页面大小4KB是`0x1000`。所以物理块号左移12位（即乘以`0x1000`）得到`0xA000`，再加上页内偏移`0x234`，结果是`0xA000+0x234=0xA234`（十六进制）。`0xA234`转换为十进制也是10*4096+564=____。因此，逻辑地址`0x1234`对应的物理地址是____（十进制）或`0xA234`（十六进制）。这个过程清晰地展示了分页系统中逻辑地址到物理地址的映射，关键在于理解页表的作用以及页号和页内偏移的分离。经典习题四：页面置换算法题目：在请求分页存储管理系统中，常用的页面置换算法有FIFO、LRU等。现有一个进程，其页面走向为：1,2,3,4,1,2,5,1,2,3,4,5。假设系统为该进程分配了3个物理块，并且初始时物理块均为空。请分别计算采用FIFO和LRU算法时，该进程的缺页次数和缺页率。解析：页面置换算法是虚拟存储技术的核心，其目标是尽可能减少缺页次数，从而提高系统性能。FIFO（先进先出）和LRU（最近最久未使用）是两种最具代表性的置换算法。FIFO算法：FIFO算法的思想非常直接：当需要置换一个页面时，选择在内存中驻留时间最长的那个页面（即最先进入内存的页面）予以淘汰。我们来模拟这个过程，物理块数为3，初始为空。页面走向：1,2,3,4,1,2,5,1,2,3,4,51.访问1：内存空，缺页。物理块：[1]。缺页次数=1。2.访问2：内存未满，缺页。物理块：[1,2]。缺页次数=2。3.访问3：内存未满，缺页。物理块：[1,2,3]。缺页次数=3。4.访问4：内存满。最早进入的是1。置换1。物理块：[4,2,3]。缺页次数=4。5.访问1：不在内存，缺页。最早进入的是2。置换2。物理块：[4,1,3]。缺页次数=5。6.访问2：不在内存，缺页。最早进入的是3。置换3。物理块：[4,1,2]。缺页次数=6。7.访问5：不在内存，缺页。最早进入的是4。置换4。物理块：[5,1,2]。缺页次数=7。8.访问1：在内存。物理块不变。缺页次数不变。9.访问2：在内存。物理块不变。缺页次数不变。10.访问3：不在内存，缺页。最早进入的是5。置换5。物理块：[3,1,2]。缺页次数=8。11.访问4：不在内存，缺页。最早进入的是1。置换1。物理块：[3,4,2]。缺页次数=9。12.访问5：不在内存，缺页。最早进入的是2。置换2。物理块：[3,4,5]。缺页次数=10。所以，FIFO算法的缺页次数为10次。页面访问总次数为12次。缺页率=10/12≈83.3%。LRU算法：LRU算法的思想是：当需要置换一个页面时，选择最近一段时间内最久没有被访问过的页面予以淘汰。它基于程序的局部性原理，认为最近被访问过的页面在不久的将来仍可能被访问。同样，物理块数为3，初始为空。我们需要记录页面的访问顺序，以便确定哪个是“最久未使用”的。页面走向：1,2,3,4,1,2,5,1,2,3,4,51.访问1：内存空，缺页。物理块：[1](最近访问:1)。缺页次数=1。2.访问2：内存未满，缺页。物理块：[1,2](最近访问:2,1)。缺页次数=2。3.访问3：内存未满，缺页。物理块：[1,2,3](最近访问:3,2,1)。缺页次数=3。4.访问4：内存满。最久未使用的是1（根据最近访问顺序3,2,1）。置换1。物理块：[4,2,3](最近访问:4,3,2)。缺页次数=4。5.访问1：不在内存，缺页。最久未使用的是2（最近访问:4,3,2）。置换2。物理块：[4,1,