习题2.2.1 Megatron 777磁盘具有以下特性： 1、 有10个盘面，每个盘面有100000个磁道。 2、 磁道平均有1000扇区，每个扇区为1024字节。 3、 每个磁道的20%被用于间隙。 4、 磁盘旋转为10000转/min。
5、 磁头移动n个磁道所需要的时间是1+0.0002*n ms。 回答下列关于Megatron 777的问题。 a） 磁盘的容量是多少？
磁盘容量 = 10×100000×100×1024Bytes = 109KB
b） 如果磁道是在直径3.5英寸的圆面上，那么一个磁道的扇区中的平均位密度是多少？ 位密度是指磁道上单位距离可记录的比特数，单位bpi（bits/inch）。
我们选取中间磁道来计算平均位密度，中间磁道的直径为 3.5inch/2 ，该磁道的周长为(3.5π/2)inch，扇区所占的周长是80%×(3.5π/2)inch。同时，每个磁道的容量是1000×1024×8 bits
所以一个磁道的扇区中的平均位密度是（1000×1024×8）bits/(80%×3.5π/2)inch = 1861733.6 bpi
c） 最大寻道时间是多少？
当磁头移动100000个磁道时，寻道时间最大 1+0.0002×100000 ms = 21ms d） 最大旋转等待时间是多少？
当所需要块的起点刚好从磁头下面越过，则要等待旋转一周的时间。最大旋转等待时间 = （1r）/（10000r/min）= 6 ms/r
e） 如果一个块是65536字节（即64扇区），一个块的传输时间是多少？ 磁头必须越过64个扇区和扇区之间的63个间隙。 被64个扇区和63个间隙覆盖的圆弧的总度数为：360×80%×64/1000+360×20%×63/1000 = 22.968 度
传输时间是（22.968/360）×6 ms = 0.3828 ms f） 平均寻道时间是多少？
平均移动距离是移动整个磁盘的1/3，所以平均寻道时间为：（100000×1/3）×0.0002+1 ms = 7.67 ms
g） 平均旋转等待时间是多少？
平均旋转等待时间为旋转半周所需的时间，由d）可知，为：6/2 ms = 3 ms 习题2.2.3 证明如果我们将磁头从一个随机的柱面移动到另一个随机的柱面上，平均移动距离是扫描过整个磁盘的1/3（忽略因有限柱面数目产生的边际效应）。
假设磁头起初以相同的概率被定为在8192个柱面的任一位置。如果是在柱面1或柱面8192，那么移动的平均磁道数是（1+2+···+8191）/8191，即大约4096磁道。如果是在柱面4096，即中间位置，则磁头移进或移出的可能性是相同的，而且无论移进还是移出，移动距离平均来说大约是总磁道数的四分之一，即2048磁道。计算表明，当磁头的初始位置从柱面1到柱面4094变化时，磁头需要移动的平均距离按二次方回升到4096，如上图所示。 我们令r = 8192，初始磁道x，平均行进距离y，则计算该二次函数可得y = (1/r)x2 – x + r/2 对所有初始位置进行积分∫0r(x2/r– x + r/2)dx = (x3/3r - x2/2 + rx/2)|0r = r2/3 所以平均行进距离 = r2/3/r = r/3，即越过整个磁盘的1/3 习题2.3.1 假设我们正在为Megatron 747磁盘调度I/O请求，磁头的初始位置在磁道32000，图2-9的请求已经产生。在下面两种情况下，每一种请求在何时完全得到服务？
请求的柱面 到达时间 8000 48000 4000 40000 0 1 10 20 a）我们采用电梯算法（起初朝任一方向开始移动都是允许的）。 请求的柱面 完成时间 计算说明 8000 4000 48000 40000 11.3 17.6 33.9 41.2 1+(32000-8000)/4000+4.3+0 1+(8000-4000)/4000+4.3+11.3 1+(48000-4000)/4000+4.3+17.6 1+(48000-40000)/4000+4.3+33.9 b）我们采用先到达先服务调度。 请求的柱面 完成时间 计算说明 8000 48000 4000 40000
11.3 26.6 42.9 57.2 1+(32000-8000)/4000+4.3+0 1+(48000-8000)/4000+4.3+11.3 1+(48000-4000)/4000+4.3+26.6 1+(40000-4000)/4000+4.3+42.9 习题2.3.4 如果我们要从一个柱面上读k个随机选定的块，在我们经过所有的块之前，平均来说我们必须绕着柱面走多远？
设k个块的位置分别以圆周的分数标识x1，x2，...，xk
x1，x2，...，xk均小于0—1之间某个t值的概率为tk，t的概率密度为ktk-1，t的平均值为∫01(ktk-1)tdt = k/(k+1)
因此平均来说必须绕着柱面走k/(k+1)磁道长度。 习题2.4.2 如果我们在一个串末附加一个位作为该串各奇数位置的奇偶校验位，另一个位作为该串各偶数位置的奇偶位，我们就有了与一个串关联的两个奇偶位。对于下列位序列，找出这种方法计算的两个位。 a) 00111011 10
b) 00000000 00
c) 10101101 10 习题2.4.3 假设我们使用例2.8中的镜像盘，每年故障率为5%，更换一个盘要花10小时。导致数据丢失的磁盘平均故障时间是多少？
替换故障磁盘的过程花10小时，相当于一年的10/（24×365）= 1/876
由于我们假定磁盘的平均寿命是20年，拷贝过程中发生故障的可能性是5%×1/876 = 1/17520
如果一个磁盘每20年年发生一次故障，那么两个磁盘之一平均10年发生一次故障。这些故障的每17520个中有一个导致数据丢失。换句话说，导致数据丢失的平均时间是10×17520 = 175200年。 习题2.4.5 假设我们使用RAID 4级方案，有4个数据盘和一个冗余盘。与例2.9一样，假设块为单字节，如果数据盘的相应块如下，给出冗余盘的块。 a) 01010110，11000000，00101011和10111011 00000110
b) 11110000，11111000，00111100和01000001 01110101 习题2.4.7 采用和习题2.4.5一样的RAID 4级方案，假设数据盘1有故障。在下列情况下恢复该磁盘的块：
a) 盘2至盘4的内容为01110110，11000000和00101011，同时冗余盘保存着11110011 01101110
b) 盘2至盘4的内容为11110000，11111000和00110011，同时冗余盘保存着10000001 10111010
习题2.5.1 假设一条记录有如下顺序的字段：一个长度为23的字符串，一个2字节整数，一个SQL日期，一个SQL时间（无小数点）。如果
a） 字段可以在任何字节处开始，
b） 字段必须在8的倍数的字节处开始， c） 字段必须在4的倍数的字节处开始， 这条记录占用多少字节？
长度为23的字符串占用23字节，整数2字节，一个SQL日期10字节，一个SQL时间8字节。
a）23+2+10+8 = 43字节 b）24+8+16+8 = 56字节 c) 24+4+12+8 = 48字节 习题2.5.2 假设字段同习题2.5.1，但是记录有一个首部，它由两个4字节的指针和一个字符组成，对习题2.5.1中字段对齐的（a）至（c）3种情况，计算记录长度。 假设字符为英文字符，则占1字节。首部长度为4+4+1 a）4+4+1+43 = 52字节 b）8+8+8+56 = 80字节 c) 4+4+4+48 = 60字节 习题2.6.5 现在，IP地址有4个字节，假设一个全球范围的地址系统中块地址由主机IP地址，1到10000之间的设备号以及各个设备号（假设为Megatron 747磁盘）上的块地址组成。块地址需要多少字节？ IP地址4字节
213< 10000 <214，磁盘的设备id 14位，设备号占用2字节 有16384个柱面——>柱面号2字节 磁道号 16位——>2字节 磁道内块号 8位——>1字节
综上，块地址需要 4+2+2+2+1 = 11字节 习题2.6.7 假设我们自动混写所有指针，所用的总时间是单独混写每一个指针所用总时间的一半。如果主存中一个指针被至少跟踪一次的概率为p，p为何值时自动混写比按需混写更有效？
设c是单独混写每一个指针所用总时间。则自动混写总时间为c/2，按需混写的总时间是pc，根据题意，则得到关系pc>c/2，从而p>1/2 习题2.6.9 假设我们有4096字节块，块中存储200字节长的记录。块首部由一个偏移量表组成，如果2-19所示，它使用2字节长指针指向块内记录。通常，每天向每块插入两条记录，删除一条记录。删除记录必须使用一个“删除标记”代替它的指针，因为可能会有悬挂指针指向它。更明确地说，假设任何一天删除记录总发生在插入之前。如果刚开始时块是空的，多少天之后，不再有插入记录的空间？
第一天，只做插入操作，插入两条记录，同时使用2个指针指向记录，总计增加了2×（2+200） = 404字节。
之后的每一天都先删除一条记录再增加两条记录，净增404-200 = 204字节 由于（4096-404）/204 = 18···20，即在1+18 = 19天之后，块中剩余空间为20字节。 在第20天，先删除一条记录，余下200+20=220字节空间，这时候只能够再插入一条记录（202字节）。 习题2.7.1 一个病人记录包含以下定长字段：病人的出生日期，社会保险号码，病人ID，每一个字段都是9字节长。它还有下列变长字段：姓名，住址和病史。如果记录内一个指针需要8字节，记录长度是一个2字节整数，不包括变长字段空间，这条记录需要多少字节？你可以假设不需要对字段进行对齐。
定长字段需要 3×9=27字节，记录长度2字节，指向“住址”的指针8字节，指向“病史”的指针8字节，所以一共需要27+2+8+8 = 45字节。 习题2.7.3 假设在习题2.7.1的病人记录上添加另外的可重复字段，表示胆固醇化验，每一次胆固醇化验需要一个24字节的日期和化验的整数结果。如果 a) 重复化验保存在记录中。
b) 化验存储在另外一个块中，记录中存储指向化验的指针。 分别给出病人记录的格式。 a）
b）