操作系统相关试题和答案解读|S2

GATE CS考试中提出了以下问题。
1.考虑一台具有64 MB物理内存和32位虚拟地址空间的计算机。如果页面大小为4KB, 则页面表的大致大小是多少？ (GATE 2001)
(a)16 MB
(b)8 MB
(c)2 MB
(d)24 MB
回答：
(C)
说明：
页面条目用于获取物理内存的地址。在这里, 我们假设正在发生单一级别的分页。因此, 结果页表将包含虚拟地址空间的所有页的条目。

Number of entries in page table = (virtual address space size)/(page size)

使用上面的公式, 我们可以说页面表中将有2 ^(32-12)= 2 ^ 20个条目。
解决64MB物理内存所需的位数= 26。
因此, 物理内存中将有2 ^(26-12)= 2 ^ 14页帧。页表需要存储所有这些2 ^ 14页帧的地址。因此, 每个页表条目将包含页帧的14位地址和1个有效/无效位。
由于内存是字节可寻址的。因此, 我们认为每个页表条目都是16位, 即2个字节长。

Size of page table = (total number of page table entries) *(size of a page table entry) = (2^20 *2) = 2MB

为了使概念更清晰, 请参见下图。根据我们的问题, 这里p = 20, d = 12, f = 14。

文章图片
2.考虑一下两个并发进程i和j之间相互排斥的Peterson算法。通过进程执行的程序如下所示。

repeat flag [i] = true; turn = j; while ( P ) do no-op; Enter critical section, perform actions, then exit critical section flag [ i ] = false; Perform other non-critical section actions. until false;

为了保证程序互斥, while循环中的谓词P应该为(GATE 2001)
a)flag[j] = true, turn = i
b)flag[j] = true, turn = j
c)flag[i] = true, turn = j
d)flag[i] = true, turn = i
回答：(b)
基本上，Peterson的算法通过使用以下两个构造——flag[]和turn——提供了有保证的互斥。flag[]控制进程进入关键部分的意愿。而turn控制的过程，是允许进入的关键部分。用下面的式子替换P，
flag[j] = true, turn= j
如果进程j想进入临界区，现在轮到进程j进入临界区，则进程i不会进入临界区。同一个概念可以扩展到两个以上的过程。详细信息请参考以下内容。
参考文献：
http://en.wikipedia.org/wiki/Peterson%27s_algorithm
3在一个高速缓存块中放入一个以上的字(GATE 2001)
(a)利用程序中引用的时间局部性
(b)利用程序中引用的空间局部性
(c)减少未命中惩罚
(d)以上都不是
回答：
(b)
时间局部性是指在相对较小的持续时间内重用特定数据和/或资源。空间局部性是指在相对靠近的存储位置内使用数据元素。
为了利用空间局部性, 将超过一个字放入高速缓存块中。
参考文献：
http://en.wikipedia.org/wiki/Locality_of_reference
4.以下哪个陈述是错误的？ (GATE 2001)
a)虚拟内存将程序的地址空间转换为物理内存地址空间
b)虚拟内存允许每个程序超出主内存的大小
c)虚拟内存增加了多重编程的程度
d)虚拟内存减少了上下文切换开销
回答：
(d)
在具有虚拟内存的系统中, 上下文切换包括地址空间切换中的额外开销。
参考文献：
http://www.itee.adfa.edu.au/~spike/CSA2/Lectures00/lecture.vm.htm
5.考虑一组已知运行时为r1, r2, …rn的n个任务, 这些任务将在单处理器计算机上运行。以下哪个处理器调度算法将导致最大的吞吐量？ (GATE 2001)
(a)轮循
(b)最短作业优先
(c)最高响应比优先
(d)先到先服务
回答：
【操作系统相关试题和答案解读|S2】(b)