计算机考试算法题二.doc
操作系统是方便用户、管理和控制计算机软硬件资源的系统软件（或程序集合）。从用户角度看，操作系统可以看成是对计算机硬件的扩充；从人机交互方式来看，操作系统是用户与机器的接口；从计算机的系统结构看，操作系统是一种层次、模块结构的程序集合，属于有序分层法，是无序模块的有序层次调用。操作系统在设计方面体现了计算机技术和管理技术的结合。 windows7操作系统 windows xp操作系统操作系统在计算机系统中的地位： 操作系统是软件，而且是系统软件。它在计算机系统中的作用，大致可以从两方面体会：对内，操作系统管理计算机系统的各种资源，扩充硬件的功能；对外，操作系统提供良好的人机界面，方便用户使用计算机。它在整个计算机系统中具有承上启下的地位计算机考试算法题二21今有三个并发进程R，M，P，它们共享了一个可循环使用的缓冲区B，缓冲区B共有N个单元。进程R负责从输入设备读信息，每读一个字符后，把它存放在缓冲区B的一个单元中；进程M负责处理读入的字符，若发现读入的字符中有空格符，则把它改成“，”；进程P负责把处理后的字符取出并打印输出。当缓冲区单元中的字符被进程P取出后，则又可用来存放下一次读入的字符。请用PV操作为同步机制写出它们能正确并发执行的程序。 （10分）解：（10分）begin Var mutex,input,calculate,output:semaphore:=1,n,0,0; buffer:array0,n-1 of item; in,mid,out:integer := 0,0,0;proR() do wait (input);wait (mutex);buffer(in):=input data;in := (in+1) mod n ;signal (calculate);signal (mutex);while true ; proM() do wait (calculate);wait (mutex);buffer(middle):=calculate data ;mid := (mid+1) mod n ;signal (output);signal (mutex); while true ; proP() do wait (output);wait (mutex);buffer(out):=calculate data ;out := (out+1) mod n ;signal (input);signal (mutex); while true ; 22.理发店里有一位理发师、一把理发椅子和五把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉。当一个顾客到来时，他必须先叫醒理发师，如果理发师正在理发时又有顾客来到，而如果有空椅子可坐，他们就坐下来等，如果没有空椅子，他就离开。这里的问题是为理发师和顾客各编写一段程序来描述他们行为，并用wait和signal原语操作实现其同步。（10分）解：理发师问题 #define CHAIRS 5 /*为等候的顾客准备椅子数*/ typedef int semaphore; /* 运用你的想像力*/ semphore customers=0; /*等候服务的顾客数*/ semaphore barbers=0 /*等候服务的理发师数*/ semaphore mutex=1; /*用于互斥*/int waiting=0; /*还没理发的等候顾客*/ void barber (void) while(TRUE) wait(customers); /*如果顾客数是0，则睡觉*/ wait(mutex); /*要求进程等候*/ waiting=waiting-1; /*等候顾客数减1*/ signal(barbers); /*一个理发师现在开始理发*/ signal(mutex); /*释放等候*/cut_hair(); /*理发（非临界区操作）*/ void customers (void) wait(mutex);if (waiting<CHAIRS) waiting=waiting+1;signal(customers);signal(mutex);wait(barbers); else signal(mutex); 23、根据如下的前趋图写出可并发执行的程序：（10分）1234567解：（10）评分：变量、进程、程序主体每项一分。var a,b,c,d,e,f,g,h,i:semaphore := 0,0,0,0,0,0,0,0;beginparbegin begin S1;signal(a); signal(b); end begin wait(a); S2; signal(c);signal(d); end begin wait(c); S3; signal(e);signal(f); end begin wait(b); S4; signal(g); end begin wait(d);wait(e) S5; signal(h); end begin wait(f); wait(g); S6 ; signal(i); end begin wait(h); wait(i); S7; endparendend24、在公共汽车上，乘客上完后，售票员关门，驾驶员开车，售票员售票，到站汽车停稳后，售票员开门，乘客上下车，售票员和驾驶员之间密切配合，直到下班。请用信号量描述公共汽车上售票员与驾驶员的工作过程。（10分）解：建立驾驶员和售票员两进程，驾驶员进程执行过程如下：（1） 判售票员关门没有（2） 开车（3） 到站后停车（4） 重复（1）（3）售票员执行过程如下：（1） 判断乘客上完没有（2） 关门（3） 售票（4） 判车停稳没有（5） 开门（6） 重复（1）（5）评分标准：执行过程完善3分， 驾驶员与售票员合作消息正确3分 售票员与驾驶员合作消息正确3分 书写格式1分25、设某作业占有7个页面，如果在主存中只允许装入4个工作页面(即工作集为4)，作业运行时，实际访问页面的顺序是：1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 1。试用FIFO、LRU和CLOCK页面置换算法，列出各自的页面淘汰顺序和页面置换次数。 (10分)解：FIFO：1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 11 1 1 1 4 4 4 4 5 5 2 2 2 2 7 7 7 7 63 3 3 3 2 2 2 26 6 6 6 1 1 1页面置换次数为：6次LRU：1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 11 1 1 1 4 4 4 1 1 1 1 6 6 6 2 2 2 2 7 7 7 4 4 4 4 2 23 3 3 3 3 3 3 7 7 7 7 16 6 6 2 2 2 2 5 5 5 5页面置换次数为：10次CLOCK：1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 11 1 1 1 4 4 4 1 1 1 1 6 6 6 2 2 2 2 7 7 7 4 4 4 4 2 23 3 3 3 3 3 3 7 7 7 7 16 6 6 2 2 2 2 5 5 5 5页面置换次数为：10次26、某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：(1)用wait和signal操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。(2)根据所定义的信号量，加上wait和signal原语，写出购票者进程的算法，以保证进程能够正确地并发执行。 (3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。解：(1)定义一信号量S，初始值为20。意义：S>0S的值表示可继续进入售 票厅的人数S=0表示售票厅中已有20名顾 客(购票者) S<0|S|的值为等待进入售票 厅的人数(2) int S=20; COBEGINPROCESSPI(I=1，2，) begin进入售票厅； wait(S)；购票；signal(S);退出； end； COEND(3)S的最大值为20 S的最小值为20n27.设正在处理器上执行的一个进程的页表如下表所示，表中的虚页号和物理块号是十进制数，起始页号（块号）均为0。所有的地址均是存储器字节地址。页的大小为1024字节。（10分） 详述在设有快表的请求分页存储管理系统中，一个虚地址转换成物理内存地址的过程。 下列虚地址对应于什么物理地址：5499，2221。 进程的页表虚页号状态位访问位修改位物理块号01104111172000-310024000-51010解：5499的物理地址为：3792221的物理地址为 ：3*1024+173=324528、假定系统有三个并发进程read, move和print共享缓冲器B1和B2。进程read负责从输入设备上读信息，每读出一个记录后把它存放到缓冲器B1中。进程move从缓冲器B1中取出一记录，加工后存入缓冲器B2。进程print将B2中的记录取出打印输出。缓冲器B1和B2每次只能存放一个记录。要求三个进程协调完成任务，使打印出来的与读入的记录的个数，次序完全一样。请用wait和signal原语写出它们的并发程序。（10分）解：begin SR,SM1,SM2,SP:semaphore;B1,B2:record;SR:=1;SM1:=0;SM2:=1;SP:=0Cobeginprocess readX:record;begin R: (接收来自输入设备上一个记录)X:=接收的一个记录；waiut(SR)；B1:=X;signal(SM1);goto R;end;Process moveY:record;BeginM:wait(SM1);Y:=B1;signal(SR)加工 Ywait(SM2)；B2:=Y;signal(SP);goto M;end;Process printZ:record;BeginP:wait(SP);Z:=B2;signal(SM2)打印Zgoto P;end;coend;end;29、考虑下述页面走向： 12，3，42，1，56，2，12，3，76，3，21，2，36当内存块数量分别为3时，试问FIFO、LRU、OPT答：所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。3时： FIFO 1，23，4，21，5，6，2，12，3，76，3，21，2，36 1 1 1 4 4 4 6 6 6 3 3 3 2 2 2 6 2 2 2 1 1 1 2 2 2 7 7 7 1 1 1 3 3 3 5 5 5 1 1 1 6 6 6 3 3发生缺页中断的次数为16在FIFO64、1、56之前调入的页面，分别为5、1、24，可见4为最先进入内存的，本次应换出，然后把页6 LRU 1，23，4，21，5，6，2，12，3，76，3，21，2，36 1 1 1 4 4 5 5 5 1 1 7 7 2 2 2 2 2 2 2 2 6 6 6 3 3 3 3 3 3 3 3 1 1 1 2 2 2 2 6 6 1 6发生缺页中断的次数为15在LRU65、2、16之前调入的页面，分别为5、1、22为最近一段时间内使用最少的，本次应换出，然后把页6调入内存。 OPT 1，23，4，21，5，6，2，12，3，76，3，21，2，36 1 1 1 1 1 1 3 3 3 3 6 2 2 2 2 2 2 7 2 2 2 3 4 5 6 6 6 6 1 1发生缺页中断的次数为11在OPT61、2、56后面要调入的页面，分别为2、1、2，可见5为最近一段时间内使用最少的，本次应换出，然后把页64、答：引入缓冲技术的主要目的是：（123）使得一次输入的信息能多次使用。30若干个等待访问磁盘的进程依次要访问的磁道为27，63，57，24，107，35，106当前磁头的位置为57号磁道，根据下面的磁盘调度算法，请给出调度的顺序，并计算平均寻道长度。（10分）1. 先来先服务算法2. 最短寻道时间优先3. 扫描算法（当前磁头移动的方向为磁道递增）4. 循环扫描算法（当前磁头移动的方向为磁道递增）解：一系统中具有S类资源150个，在T0时刻按下表所示分配给3个进程：进程Maximum demandCurrent allocationP17025P26040P36045对下列请求应用银行家算法逐步分别分析判定是否安全, 如果是安全的，请给出一个可能的进程安全执行序列；如果不是安全的，请说明原因。（10分）1. 第4个进程P4到达，对资源S的最大需求为60个，当前请求分配25个；2第4个进程P4到达，对资源S的最大需求50个，当前请求分配35个。31一个采用请求式存储管理的计算机系统，其主存（实存）容量为256M字节，虚存容量（给用户的最大地址空间）为4G字节，页面大小为4K字节，试问：（10分）1. 主存物理地址应设为多少位？2. 主存中有多少物理块？3. 虚拟地址应该设多少位？4. 虚拟地址空间最多可以有多少页？5. 页内最大和最小偏移量是多少？
