计算机阅读填空题

1、阅读填空题1、设有无穷多个信息，输入进程把信息逐个写入缓冲区，输出进程逐个从缓冲区中取出信息。针对下述两种情况： 缓冲区是环形的，最多可容纳n个信息； 缓冲区是无穷大的。试分别回答下列问题： 输入、输出两组进程读/写缓冲区需要什么条件？ 用p、v操作写出输入、输出两组进程的同步算法，并给出信号量含义及初值。 针对容量为n的环形缓冲区，输入、输出两组进程读/写缓冲区需要的条件为：Ø 输入进程和输出进程需同步执行，即输入进程写缓冲区后，输出进程才可以读；Ø 由于缓冲区容量有限，因此任一时刻所有输入进程存放信息的单元数不能超过缓冲区的总容量（n）；Ø 同理，所有输出进程

2、取出信息的总量不能超过所有输入进程当前写入信息的总数。设缓冲区的编号为0n-1，in和out分别是输入进程和输出进程使用的指针，指向下面可用的缓冲区，初值都是0。为使两类进程实行同步操作，应设置三个信号量：两个计数信号量full和empty，一个互斥信号量mutex。full：表示放有信息的缓冲区数，其初值为0。empty：表示可供使用的缓冲区数，其初值为n。mutex：互斥信号量，初值为1，表示各进程互斥进入临界区，保证任何时候只有一个进程使用缓冲区。下面是解决这个问题的算法描述。输入进程input： while (true) p(empty); p(mutex); 信息送往buffer(i

3、n); in=(in+1)mod n; /*以n为模*/ v(mutex); v(full); 输出进程output：while (true) p(full); p(mutex);从buffer(out)中取出信息; out=(out+1)mod n; /*以n为模*/v(mutex);v(empty); 当缓冲区是无穷大时，输入进程存放信息的单元数不再受缓冲区总容量的限制，因此，可以不设信号量empty。另外，算法中的in=(in+1)mod n; 和out=(out+1)mod n; 修改为in=in+1；和out=out+1；即可，其余的算法不变。输入进程input： while (tr

4、ue) p(mutex); 信息送往buffer(in); in=in+1; v(mutex); v(full); 输出进程output：while (true) p(full); p(mutex);从buffer(out)中取出信息; out=out+1; v(mutex); 2、系统中只有一台打印机，有三个用户的程序在执行过程中都要使用打印机输出计算结果。设每个用户程序对应一个进程。问：这三个进程间有什么样的制约关系？试用p、v操作写出这些进程使用打印机的算法。因为打印机是一种临界资源，所以这三个进程只能互斥使用这台打印机，即一个用户的计算结果打印完之后，另一个用户再打印。 设三个进程分别

5、为a、b和c。 设一个互斥信号量mutex，其初值为1。 进程a 进程b 进程c p(mutex) p(mutex) p(mutex) 使用打印机 使用打印机 使用打印机 v(mutex) v(mutex) v(mutex) 3、设有一台计算机，有两条i/o通道，分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓冲区b1中，加工处理后再搬到缓冲区b2中，并在打印机上打印结果。问： 系统要设几个进程来完成这个任务？各自的工作是什么？ 这些进程间有什么样的相互制约关系？ 用p、v操作写出这些进程的同步算法。解答：从“卡片机”到“打印机”共需要3个操作，即输入、处理、输出。这3个动作就是

6、完成任务的3个进程。系统可设三个进程来完成这个任务：r进程负责从卡片输入机上读入卡片信息，输入到缓冲区b1中；c进程负责从缓冲区b1中取出信息，进行加工处理，之后将结果送到缓冲区b2中；p进程负责从缓冲区b2中取出信息，并在打印机上印出。r进程受c进程影响，b1放满信息后r进程要等待等c进程将其中信息全部取走，才能继续读入信息；c进程受r进程和p进程的约束：b1中信息放满后c进程才可从中取出它们，且b2被取空后，c进程才可将加工结果送入其中；p进程受c进程的约束：b2中信息放满后p进程才可从中取出它们,进行打印。信号量含义及初值：b1full 缓冲区b1满，初值为0；b1empty缓冲区b1空

7、，初值为0；b2full 缓冲区b2满，初值为0；b2empty缓冲区b2空，初值为0； r进程 c进程 p进程 输入信息写入缓冲区b1 p(b1full) p(b2full) v(b1full) 从b1中取出信息 从b2中取出信息进行打印 p(b1empty) 加工信息 v(b2empty) 结果送入b2 v(b1empty) v(b2full) p(b2empty) 4、给出几个作业的提交时间和运行时间，指出按照某种作业调度算法时各个作业的调度次序，并求各个作业的周转时间和平均周转时间。一个作业从进入系统到运行结束要经历四种状态：提交状态、后备状态、执行状态和完成状态。5、下表给出作业l，

8、2，3的提交时间和运行时间。采用先来先服务调度算法和短作业优先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位：小时，以十进制进行计算。）作业号提交时间运行时间1230.00.41.08.04.01.0解：采用先来先服务调度策略，则调度次序为l、2、3。作业号提交时间 运行时间 开始时间 完成时间周转时间1 0.08.00.08.0 8.02 0.44.08.0 12.0 11.63 1.01.0 12.0 13.0 12.0平均周转时间t（811.612）/310.53采用短作业优先调度策略，则调度次序为l、3、2。作业号提交时间运行时间开始时间完成时间周转时间1 0.0 8.0

9、 0.0 8.0 8.03 1.0 1.08.09.08.02 0.4 4.0 9.0 13.0 12.6平均周转时间t（8812.6）/39.53【例6】今有三个批处理作业。第一个作业10:00到达，需要执行2小时；第二个作业在10:10到达，需要执行1小时；第三个作业在10:25到达，需要执行25分钟。分别采取如下两种作业调度算法：调度算法1：作业号到达时间开始执行时间执行结束时间12310:0010:1010:2510:0012:0013:0012:0013:0013:25调度算法2：作业号到达时间开始执行时间执行结束时间12310:0010:1010:2511:5010:5010:25

10、13:5011:5010;50 （1）计算各调度算法下的作业平均周转时间。 （2）调度算法1是什么作业调度算法？解：（1）采用调度算法1时： 作业1的周转时间为2小时；作业2的周转时间为2.83小时；作业3的周转时间为3小时；平均周转时间为：（22.833）32.61小时。 采用调度算法2时： 作业1的周转时间为3.83小时；作业2的周转时间为1.67小时；作业3的周转时间为0.42小时；平均周转时间为：（3.83l.670.42）3l.97小时。（2）调度算法1是按照作业到达的先后次序执行的，所以它是先来先服务调度算法。习题：假定在单cpu条件下有下列要执行的作业：作业运行时间优先级1103

11、211323414552 作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。 用一个执行时间图描述在下列算法时各自执行这些作业的情况：先来先服务法fcfs、时间片轮转法rr（时间片1）和非抢占式优先级。 对于上述每种算法，各个作业的周转时间是多少？平均周转时间是多少？ 对于上述每种算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？答： 先来先服务法（fcfs） 作业1 作业2 作业3 作业4 作业5 0 10 11 13 14 19 t 时间片轮转法（rr） 作业 1 2 1 3 4 1 5 3 1 5 1 5 1 5 1 5 1 1 1 0 1 2

12、 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 t 非抢占式优先级: 作业1 作业4 作业3 作业5 作业2 0 10 11 13 18 19 t和 先来先服务法（fcfs） 作业到达时间运行时间完成时间周转时间带权周转时间101010101.0211111010.032213115.5431141111.054519153.0平均周转时间11.4平均带权周转时间6.1时间片轮转法（rr）作业到达时间运行时间完成时间周转时间带权周转时间101019191.9211211.0322863.0431522.054516122.4平均周转时间8.0平均带权周

13、转时间2.06非抢占式优先级作业到达时间运行时间完成时间周转时间带权周转时间101010101.0211191818.032213115.54311188.054518142.8平均周转时间12.2平均带权周转时间7.06 注意：本教材按照linux系统的约定，优先数小的优先级高。本试题给出的条件中直接给出的是优先级，数大的则优先级高。如果试题给出的是优先数，则数小的优先级高。如果将本试题改为：作业运行时间优先数1102214322411553 则作业2-5优先级从高到低次序为：作业4、作业3、作业5、作业2。上面的解答仍然正确。【例4】若在一分页存储管理系统中，某作业的页表如下所示。已知页面

14、大小为1024字节，试将逻辑地址1011，2148，4000，5012转化为相应的物理地址。页号块号01232316 解 本题中，为了描述方便，设页号为p，页内位移为d，则：（1）对于逻辑地址1011，pint（1011/1024）0，d1011 mod 10241011。查页表第0页在第2块，所以物理地址为1024´210113059。（2）对于逻辑地址2148，pint（2148/1024）2，d2148 mod 1024100。查页表第2页在第1块，所以物理地址为10241001124。（3）对于逻辑地址4000，pint（4000/1024）3，d4000 mod 10249

15、28。查页表第3页在第6块，所以物理地址为1024´69287072。（4）对于逻辑地址5012，pint（5012/1024）4，d5012 mod 1024916。因页号超过页表长度，该逻辑地址非法。 分析 页式存储管理的地址结构是一维的，即逻辑地址/物理地址只用一个数值即可表示。若给定的逻辑地址a，页面的大小为l，则页号p和页内地址d可按照下式求得：p=int (a/l) d=a mod l拼接块内地址10 0101 1100，得01 0010 0101 1100，即125c（h）。习题 某虚拟存储器的用户编程空间共32个页面，每页为1kb，内存为16kb。假定某时刻一用户页表

16、中已调入内存的页面的页号和物理块号的对照表如下：页号物理块号051102437计算逻辑地址0a5c(h)所对应的物理地址。解：页式存储管理的逻辑地址分为两部分：页号和页内地址。由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1kb”，1k=210，可知内页地址占10位。由“内存为16kb”，可知有16块，块号为4位。逻辑地址0a5c（h）所对应的二进制表示形式是：000 1010 0101 1100 ，根据上面的分析，下划线部分为页内地址，编码“000 10”为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4（十进制），即物理块地址为：01 00 ，拼接块内地

17、址10 0101 1100，得01 0010 0101 1100，即125c（h）。习题1考虑下述页面走向： 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当内存块数量分别为3，5时，试问lru、fifo、opt这三种置换算法的缺页次数各是多少？（注意，所有内存块最初都是空的，所以，凡第一次用到的页面都产生一次缺页。）答：淘 汰 算 法内存块数lrufifoopt315161158107习题1文件系统中的目录结构有哪几种基本形式？各有何优缺点？unix/linux系统中采用哪种目录结构？文件系统中的目录结构有：单级目录结构，二级目录结构，树形目录结构，非循环图目

18、录结构。各自的优缺点如下表：目录结构优 点缺 点单级目录简单，能实现按名存取。查找速度慢；不允许重名；不便于共享。二级目录允许重名；提高了检索目录的速度。仍不利于文件共享。树形目录文件的层次和隶属关系很清晰，便于实现不同级别的存取保护和文件系统的动态装卸。只能在用户级对文件进行临时共享。非循环图目录具有树形结构的优点，而且实现对文件的永久共享。管理较复杂。unix系统中采用非循环图目录结构，即带链接的树形目录结构。【例3】考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问： （1）逻辑地址需要多少二进制位表示？ （2）物理地址需要多少二进制位表示？

19、解 因为页面数为8=23，故需要3位二进制数表示。每页有1024个字节，1024=210，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示（32=25）。（1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。（2）页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。分析 在分页存储管理中，逻辑地址结构如下图所示。页号p页内地址d 它由两个部分组成：前一部分表示该地址所在页面的页号p；后一部分表示页内地址（页内位移）d。页号的地址位数决定了页的多少，假设页号有20位，则地址空间中最多可容纳的页面数为220，即1mb个页面。页内地址位数确定了每页的大小，若页内地址为12位，则每页大小为212，即2kb。同理，物理地址中块号的地址位数决定了块的多少，由于页式存储管理内存空间块的大小与页