首页 > 试题广场 >

Google 公司正准备开发一种专用的操作系统。因为你在操作

[问答题]
Google 公司正准备开发一种专用的操作系统。因为你在操作系统课程取得的优异成绩,Google公司高薪聘用你为这个操作系统的主设计师。Google 从网络上抓来大量的网页,分别保存在数千台主计算机上,以备搜索之用。如果某台主计算机故障,则搜索结果中就会缺少它所保存的数据,所以必须对数据进行备份。Google 打算用几百台专用计算机来承担备份工作。为了最大化地发挥硬件能力,要根据需求的特点来开发专用的操作系统。需求如下:
1. 每台备份机对若干台主计算机提供备份服务,并且只对它们提供服务;
2. 需要备份的数据从网络发送过来,每个网络数据包大小为64KB。每台主计算机会连续发送64 个数据包,把它们按次序连接在一起便构成一个完整的备份数据包,也就是说每个备份数据包的大小是4MB;
3. 因为网络自身的分时特性,当两台以上的主计算机同时发送数据时,它们的数据是以网络数据包为单位交错到达的,而且数据包的交错情况是完全随机的,没有规律。例如:
主计算机A发出的网络数据包为A0、A1、A2、……、A63;
主计算机B发出的网络数据包为B0、B1、B2、……、B63;
备份计算机接受到数据包的一种可能顺序为:
A0、A1、B0、A2、B1、B2、A3、B3、A4、A5、A6、……、B62、A58、B63、A59、
A60、A61、A62、A63
不过,可以通过网络自身的特性准确得知数据包来自那台主计算机;
4. 4MB 备份数据包的前4 个字节是该数据包的唯一的ID,是一个32 位的无符号整型
数;
5. 每台备份机所要处理的备份数据包的ID数值都是在0x00000001—0xFFFFFFFF之间,不会为0;
6. 如果接收到相同ID的备份数据包,无论它是否来自于同一台主机,都说明后到的数据包是原数据包的更新,直接覆盖原数据包即可;
7. 当某台主计算机数据丢失,它会向备份机请求数据恢复。每个请求都会说明它需要恢复的备份数据包的ID。备份机只要把相应的4MB 备份数据包再拆成64 个64KB 的网络数据包发送给主计算机即可;
8. 每台主机都连接着一个64 位的海量存储器,我们可以认为它的空间足够大。它最多有264个扇区(Sector),每个扇区大小为512 Bytes;
9. 备份数据包被写入到海量存储器上,在需要恢复时再读出;
10. 备份数据包发来的频率一般小于海量存储器的写入速度。也就是说,在通常情况下,假设海量存储器1 分钟连续的写入操作可以写3600MB 的数据,但在这1 分钟内,接收到的备份数据包可能仅有400MB甚至更少;
11. 但也有偶然的一小段时间,备份数据包的到达频率达到一个高峰,可能会短暂地超过海量存储器的写入速度。此时如果不把数据包缓存在内存,可能会丢失后续的若干数据包;
12. Google可以满足你对CPU速度和内存容量的任何要求,但它希望你不要浪费。作为Google的新人,你需要设计一个在满足上述需求的前提下没有多余的功能,还可以尽量发挥硬件性能的操作系统,来证明你的能力。这个操作系统包括内存管理、进程管理、网络管理和外存管理四大模块(网络管理在此题中可以不考虑)。这是一个杜撰的故事。上述需求中可能有不合理的地方,但你必须接受;需求中没有明
确说明的事物,你可以按照你自己认为合理的方式进行假定。现在就请开始勾画这个操作系统的蓝图,并用文字、图、表等一切有效手段来描述你的设计。
注意:不仅要说明你是怎么设计的,还要说明这样设计的好处。
需求要点:
 备份数据包被拆分为多个小包从网络交错传来;
 每个备份数据包都有唯一的ID;
 偶尔会有大量数据包在极短的时间内传来,超过海量存储器的写入速度;
 当有恢复备份的请求发来时,把相应ID的备份数据包拆为小包逐一发送;
 我们不用为CPU速度和内存、外存的容量发愁,但不能浪费。
内存管理:保留一部分放OS,其余地方划分为若干4M大小的块,用First Fit的方法申请与回收,用来双向缓存备份数据包。
进程管理:支持共享地址空间的进程,进程A负责接收数据包,按来源依次放入内存的4M块内,进程B当得知有整块数据准备好后,将其存入海量存储器;进程A同时接收备份恢复请求,并把请求交给进程C;进程C根据请求,从海量存储器读出一个4M数据包放入内存,然后拆包发送。它们之间的优先级为A>B=C。所以这是一个支持优先级调度的共享地址空间的系统。
外存管理:格式化外存时,将外存划分为4M的block,每个block的头四个字节为0,表示空闲。每个数据包直接存入其ID所对应的block。
发表于 2019-03-27 17:28:41 回复(0)