22.能引起外部中断的事件是:键盘输入(人的干预)或外请求。（外中断都是强迫中断） 23.单处理机系统中，可并行的是（II、III和IV）
I 进程与进程 II 处理机与设备 III 处理机与通道 IV 设备与设备
24.进程调度算法中，综合考虑进程等待时间和执法世间是:(高响应比优先调度算法). FCFS:谁先到就绪队列,将处理机分给谁;
时间片轮转调度法:以先来后到的次序+时间片轮转;
优先级调度:选优先级最高的进程占用处理机(优先级可动态改变);
短进程优先:取所需的运行时间最短的进程(该算法能使平均等待时间最短).
25.某计算机系统有8台打印机，有K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是(4)
26.分区分配内存管理方式的主要保护措施是(界地址保护)
27.一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是(2^24). 分页与分段的区别：
分页:信息的物理单位 大小一样，由系统固定 地址空间是一维的 分段:信息的逻辑单位 大小不等，由用户确定 地址空间是二维的 28.文件物理结构中，适合随机访问且易于文件扩展的是(索引结构).
连续结构:将一个文件中逻辑上连续的信息存放到存储介质的依次相邻的块上便形成顺序结构，这类文件叫连续文件，又称顺序文件。
优点：简单;支持顺序存取和随机存取；顺序存取速度快；所需的磁盘寻道次数和寻道时间最少.
缺点：建立文件前需要能预先确定文件长度，以便分配存储空间；修改、插入和增生文件记录有困难；对直接存储器作连续分配，会造成少量空闲块的浪费。
链接结构：一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。
优点：提高了磁盘空间利用率,不存在外部碎片问题；有利于文件插入和删除；有利于文件动态扩充. 缺点：存取速度慢，不适于随机存取；可靠性问题，如指针出错；更多的寻道次数和寻道时间；链接指针占用一定的空间.
索引结构：一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构----索引表。表中每一栏目指出文件信息所在的逻辑块号和与之对应的物理块号。索引表的物理地址则由文件说明信息项给出。
优点：保持了链接结构的优点,又解决了其缺点；即能顺序存取,又能随机存取；满足了文件动态增长、插入删除的要求；也能充分利用外存空间。
缺点：较多的寻道次数和寻道时间；索引表本身带来了系统开销 如：内外存空间，存取时间。
29.SCAN调度(电梯调度)算法: 电梯调度算法基于日常生活中的电梯工作模式：电梯保持按一个方向移动，直到在那个方向上没有请求为止，然后改变方向。反映在磁盘调度上，总是沿着移动臂的移动方向选择距离磁头当前位置最近的I/O请求作为下一次调度的对象。如果该方向上已无I/O请求，则改变方向再做选择。
假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现在一个磁道访问请求序列为35，45，12，68，110，180，170，195，采用SCAN调度（电梯调度）算法得到的磁道访问序列是：110,170,180,195,68,45,35,12。
30.文件系统中，文件访问控制信息存储的合理位置是(文件控制块)。
31.硬链接：在磁盘上有一份内容一样的文件产生，但不改变文件的Inode,也就是与原文件共用Inode。 软链接：不在磁盘上有一份内容一样的文件产生，但产生新的Inode。
11
设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2，再建立F1的硬链接文件F3，然后删除F1。此时，F2和F3的引用计数值分别是（1，1）。
32.程序员利用系统调用打开I/O设备时，通常使用的设备标识是（逻辑设备名）。 33.在OSI参考模型中，自下而上第一个提供端到端服务的层次是（传输层）。 自下而上方法的一般从检查物理层开始。
自下而上分别称为：物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。 传输层是两台计算机经过网络进行数据通信时,第一个端到端的层次，具有缓冲作用。 34.1924年奈奎斯特(Nyquist)就推导出在理想低通信道的最高大码元传输速率的公式:
理想低通信道的最高大码元传输速率C=2W.log2 N (其中W是想低通信道的带宽,N是电平强度) 信道带宽与数据传输速率的关系可以奈奎斯特(Nyquist)准则与香农(Shanon)定律描述。
奈奎斯特定理描述了有限带宽、无噪声信道的最大数据传输速率与信道带宽的关系。香农定理则描述了有限带宽、有随机热噪声信道的最大传输速率与信道带宽、信噪比之间的关系。
奈奎斯特准则指出：对于二进制数据信号的最大数据传输速率Rmax与通信信道带宽B（B=f,单位Hz)的关系可以写为： Rmax＝2*B(bps)
香农定理指出：在有随机热噪声的信道上传输数据信号时，数据传输速率Rmax与信道带宽B、信噪比S/N的关系为：
Rmax＝B*log2(1+S/N)) [以2为底,1+S/N的对数]
式中，Rmax单位为bps,带宽B单位为Hz，信噪比S/N通常以dB（分贝）数表示。若S/N=30(dB),那么信噪比根据公式：S/N(dB)=10*lg(S/N) 则S/N=1000。若带宽B=3000Hz，则Rmax≈30kbps。
（1）对于带宽为6MHz的信道，若用4种不同的状态来表示数据，在不考虑热噪声的情况下，该信道的最大数据传输速率是多少？
答：由无热噪声的奈奎斯特公式: C=2Hlog2N=2*6M*log24=24Mbps，即该信道的最大数据传输速率是24Mbps
（2）在无噪声情况下，若某通信链路的带宽为3KHz,采用4个相位，每个相位具有4种振幅的QAM调制技术，则该通信链路的最大数据传输速率是(24kbps) C=2Hlog2N=2*3k*log216=24kbps.
35.后退N帧ARQ就是从出错处重发已发出过的N个帧。
数据链路层采用了后退N帧（GBN）协议，发送方已经发送了编号为0~7的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是(4)。 36.以太网交换机进行转发决策时使用的PDU地址是(目的物理地址)。
ARP协议是“Address Resolution Protocol”（地址解析协议）的缩写。在局域网中，网络中实际传输的是“帧”，帧里面是有目标主机的MAC地址的。在以太网中，一个主机要和另一个主机进行直接通信，必须要知道目标主机的MAC地址。但这个目标MAC地址是如何获得的呢？它就是通过地址解析协议获得的。所谓“地址解析”就是主机在发送帧前将目标IP地址转换成目标MAC地址的过程。ARP协议的基本功能就是通过目标设备的IP地址，查询目标设备的MAC地址，以保证通信的顺利进行。
37.CSMA/CD是一种分布式介质访问控制协议，网中的各个站（节点）都能独立地决定数据帧的发送与接收。每个站在发送数据帧之前，首先要进行载波监听，只有介质空闲时，才允许发送帧。这时，如果两个以上的站同时监听到介质空闲并发送帧，则会产生冲突现象，这使发送的帧都成为无效帧，发送随即宣告失败。每个站必须有能力随时检测冲突是否发生，一旦发生冲突，则应停止发送，以免介质带宽因传送无效帧而被白白浪费，然后随机延时一段时间后，再重新争用介质，重发送帧。CSMA/CD协议简单、可靠，其网络系统（如Ethernet）被广泛使用。
在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps,电缆中的信号传播速度是200 000km/s。若最小数据帧长度减少800比特，则最远的两个站点之间的距离至少需要(减少80)。 来源：(http://blog.sina.com.cn/s/blog_48fff7f90100f8a2.html) - 2009计算机真题详解知识点(2)_毛子牛_新浪博客
最短帧长=2*L*10^9(b/s)÷200 000000m/s=10*L(bit).
12
38.主机甲和主机乙之间建立一个TCP连接,主机甲向主机乙发送了两个连续的TCP段,分别含300字节和500字节的有效载荷,第一个段的序列号为200,主机乙正确接收到两个段后,发送给主机甲的确认序列号是(1000)。
例如，序列号等于前一个报文段的序列号与前一个报文段中数据字节的数量之和。例如，假设源主机发送3个报文段，每个报文段有100字节的数据，且第一个报文段的序列号是1000，那么接收到第一个报文段后，目的主机返回含确认号1100的报头。接收到第二个报文段（其序号为1100）后，目的主机返回确认号1200。接收到第三个报文段后，目的主机返回确认号1300。
39.确定拥塞窗口的大小的过程：在刚建立连接时，将拥塞窗口的大小初始化为该连接所需的最大连接数据段的长度值，并发送一个最大长度的数据段（当然必须是接收窗口允许的）。如果在定时器超时前得到确认，将拥塞窗口的大小增加一个数据段的字节数，并发送两个数据段，如果每个数据段在定时器超时前都得到确认，就再在原基础上增加一倍，即为4个数据段的大小，如此反复，每次都在前一次的基础上加倍。当定时器超时或达到发送窗口设定值，停止拥塞窗口尺寸的增加。这种反复称为慢速启动，所有的TCP协议都支持这种方法。
一个TCP连接总是以1KB的最大段发送TCP段，发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时，如果接下来的4个RTT（往返时间）时间内的TCP段的传输都是成功的，那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时，拥塞窗口大小是(9KB)。
40.FTP客户和服务器间传递FTP时，使用的连接是(建立在TCP之上的控制连接)。
二． 综合应用题
41.该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则， 从A到C的最短路径为A→B→C，事实上其最短路径为 A→D→C。
42. （1）算法基本思想如下：从头至尾遍历单链表，并用指针P指向当前节点的前K个节点。当遍历 到链表的最后一个节点时，指针P所指向的节点即为所查找的节点。
（2）详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针P1指向当
前遍历的节点，指针P指向P1所指向节点的前K个节点，如果P1之前没有K个节点，那么P指向表头 节点。用整型变量i表示当前遍历了多少节点，当i>k时，指针p随着每次遍历，也向前移动一个节 点。当遍历完成时，p或者指向表头就节点，或者指向链表中倒数第K个位置上的节点。 （3）算法描述：
Int LocateElement(linklist list,int k) { P1=list->link; P=list; i=1; while(P1)
{ P1=P1->link; i++;
13
if(i>k) p=p->next; //如果i>k,则p也往后移 }
if(p==list)return 0; //说明链表没有k个结点 else {
printf(“%d\\n“,p->data); return 1; } }
43. （1）在中断方式下，每32位（4B）被中断一次，故每秒中断 0.5MB/4B=0.5×106/4=12.5×104次
要注意的是，这里是数据传输率，所以1MB=106B。因为中断服务程序包含18条指令，中断服务的 其他开销相当于2条指令的执行时间，且执行每条指令平均需5个时钟周期，所以，1秒内用于中断 的时钟周期数为
（18+2）×5×12.5×104=12.5×106
（2）在DMA方式下，每秒进行DMA操作
5MB/5000B=5×106/5000=1×103 次因为DMA预处理和后处理的总开销为500个时钟周期，所以1秒 钟之内用于DMA操作的时钟周期数为 500×1×103=5×105
故在DMA方式下，占整个CPU时间的百分比是 （（5×105）/（500×106））×100%=0.1%
44.指令执行阶段每个节拍的功能和有效控制信号如下所示 时钟 功能 有效控制信号
C5 MAR←(R1) PCout,MARin
C6 MDR←M(MAR) MemR,MDRinE C7 A←(R0) R0out,Ain
C8 AC←(MDR)+(A) MDRout,Addr,ACin C9 MDR←(AC) ACout,MDRin
C10 M(MAR) ←MDR MDRoutE,MemW
45.定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty控制生产者与消费者
之间的同步；mutex控制进程间互斥使用缓冲区。程序如下： Var s1=0,s2=0,empty=N,mutex=1; Parbegin P1:begin
X=produce(); P(empty); P(mutex);
14
Put();
If x%2==0 V(s2); else V(s1); V(mutex); end. P2:begin P(s1); P(mutex); Getodd();
4KB,页内占12位，即16机制的3位 Countodd():=countodd()+1;
则2362H的最高位就是页号 V(mutex); V(empty); 2:10不命中+100页表+100内存地址 end.
1：10不命中+100页表+108缺页+100内P3:begin
存地址 P(s2)
2：10命中+100内存地址 P(mutex);
Geteven();
1号页内偏移565H，缺页，置换0， Counteven():=counteven()+1;
V(mutex); 101565H V(empty); end. Parend. 46.
（1）根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB，即212，则得到页内位移占虚地址的低12位，页号占剩余高位。可得三个虚地址的页号P如下（十六进制的一位数字转换成4位二进制，因此，十六进制的低三位正好为页内位移，最高位为页号）：
2362H：P=2，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计10ns+100ns+100ns=210ns。
1565H：P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理108ns，合成物理地址后访问主存100ns，共计10ns+100ns+108ns+100ns≈108ns。
25A5H：P=2，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns+100ns=110ns。
（2）当访问虚地址1565H时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。 47.
（1）无类IP地址的核心是采用不定长的网络号和主机号，并通过相应的子网掩码来表示（即网络号部分为1，主机号部分为0）。本题中网络地址位数是24，由于IP地址是32位，因此其主机号部分就是8位。因此，子网掩码就是11111111 11111111 11111111 00000000，即255.255.255.0。
根据无类IP地址的规则，每个网段中有两个地址是不分配的：主机号全0表示网络地址，主机号全1表示广播地址。因此8位主机号所能表示的主机数就是2的8次方—2，即254台。
该网络要划分为两个子网，每个子网要120台主机，因此主机位数X应该满足下面三个条件：
15