操作系统相关试题和答案解读|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)先到先服务

回答：

(b)