操作系统算法题
算法题
1. 这是一个从键盘输入到打印机输出的数据处理流图，其中键盘输入进程通
过缓冲区buf1 把输入数据传送给计算进程，计算进程把处理结果通过缓冲
buf2 传送给打印进程。buf1 和buf2 为临界资源，试写出键盘输入进程，计
算进程及打印进程间的同步算法。（10分）
输入进程→buf1 →计算进程→buf2 →打印进程
解答：从键盘输入到打印机输出的数据传送过程，可以看作是由键盘输入进程到计算进程，以及由计算进程到打印输出进程这两个数据传送进程所组成。其中，对键盘输入进程而言，计算进程是消费者进程；而对打印输出进程而言，计算进程又是生产者进程。据此可将它们之间的同步问题描述如下：
var：mutex1，mutex2，empty1，empty2，full1，full2：=1，1，1，1，0，0；
IP:begin
repeat
P(empty);
P(mutex1);
input a charcter from keyboard;
Add to buffer;
V(mutex1);
V(full);
until false
end
CP:begin
repeat
P(full);
P(mutex1);
Take a charactor form buffer1;
Add to ch1;
V(mutex1);
V(empty1);
P(empty2);
P(mutex2);
Take a charactor form ch1;
Add to buffer2;
V(mutex2);
V(full2);
until false
end
OP:begin
repeat
p(full2);
P(mutex2);
Take a charactor from buffer2;
Add to printer controler;
start printer;
V(mutex2);
V(empty2);
until false
end
2．设在一个页面大小为1K的系统中，正在处理器上执行的一个进程的页表如图所示：页号状态位访问位修改位物理块号
0 1 1 0 4
1 1 1 1 7
2 0 0 0 -
3 1 0 0 2
4 0 0 0 -
5 1 0 1 0
起始页号和块号均为0。
1．详述在设有快表的请求分页存储管理系统中，一个虚地址转换成物理内存地址的过程2. 设系统有三种类型的资源，数量为(4，2，2)，系统中有进程A，B，C按如下顺序请求资源：
进程A申请(3，2，1)
进程B申请(1，0，1)
进程A申请(0，1，0)
进程C申请(2，0，0)
请你给出一和防止死锁的资源剥夺分配策略，完成上述请求序列，并列出资源分配过程，指明哪些进程需要等待，哪些资源被剥夺。(10分)
解：(10分)
①分配策略为：当进程P i申请r i类资源时，检查r i中有无可分配的资源：有则分配给P i；否则将P i占有的资源全部释放而进入等待状态。(P i等待原占有的所有资源和新申请的资源)
②资源分配过程：剩余资源
进程A：(3，2，1)(1，0，1)
进程B：(1，0，1)(0，0，0)
进程A：(0，1，0)(不满足)(3，2，1)
A的所有资源被剥夺，A处于等待
进程C：(2，0，0)(1，2，1)
C，B完成之后，A可完成。
4．设公共汽车上，司机和售票员的活动分别是：
司机：启动车辆售票员：上乘客
正常行车关车门
到站停车售票
开车门
`下乘客
在汽车不断地到站，停车，行使过程中，这两个活动有什么同步关系？并用wait和signal 原
语操作实现它们的同步。
解：BEGIN integer stop,run;
Stop:=0;
Run:=0;
COBEGIN
Driver: BEGIN
L1: wait(run);
启动车辆；
正常行车；
到站停车；
signal(stop);
Goto L1;
END
Conductor: BEGIN
L2：上乘客；
关车门；
signal(run);
售票；
wait(stop);
开车门；
下乘客；
Goto L2;
END
COEND
END
5、某虚拟存储器的用户编程空间共321KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：
页号物理块号
15
210
34
47
则逻辑地址0A5C（H）所对应的物理地址是什么？
答：逻辑地址0A5CH）所对应的二进制表示形式是：0000 1010 0101 1100 ，由于1K=210，下划线部分前的编码为000010，表示该逻辑地址对应的页号为3查页表，得到物理块号是4（十进制），即物理块地址为：0001 0010 0000 0000 ，拼接块内地址0000 0000 0101 1100，得0001 0010 0101 1100，即125C（H）。
6、某段表内容如下：
段号段首地址段长度
0120K40K
1760K30K
2480K20K
3370K20K
一逻辑地址为（2，154）的实际物理地址为多少？
答：逻辑地址（2154）表示段号为2，即段首地址为480K，154为单元号，则实际物理地址为480K+154。
7、设系统中有三种类型的资源（A，B，C）和五个进程（P1，P2，P3，P4，P5），A资源的数量为17，B资源的数量为5，C资源的数量为20。在T0时刻系统状态如表1和表2所示。（共10分）
系统采用银行家算法实施死锁避免策略。
①T0时刻是否为安全状态？若是，请给出安全序列。
②在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？
③在②的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？
④在③的基础上，若进程P1请求资源（0，2，0），是否能实施资源分配？为什么？
表1 T0时刻系统状态
最大资源需求量已分配资源数量
A B C A B C
P1 5 5 9 2 1 2
P2 5 3 6 4 0 2
P3 4 0 11 4 0 5
P4 4 2 5 2 0 4
P5 4 2 4 3 1 4
表2 T0时刻系统状态
A B C
剩余资源数 2 3 3
8．系统中有五个进程P1、P2、P3、P4、P5，有三种类型的资源：R1、R2、和R3。在T0时刻系统状态如表所示。若采用银行家算法实施死锁避免策略，回答下列问题：（共9分，每小题3分）
1．T0时刻是否为安全状态？为什么？
2．若这时P4请求资源（1，2，0），是否能实施资源分配？为什么？
3．在上面的基础上，若进程P3请求资源（0，1，0），是否能实施资源分配？为什么？
T0时刻系统状态
已分配资源数量最大资源需求量
R1 R2 R3 R1 R2 R3
P1 0 0 1 0 0 1
P2 2 0 0 2 7 5
P3 0 0 3 6 6 5
P4 1 1 5 4 3 5
P5 0 3 3 0 6 5
R1 R2 R3
剩余资源数 3 3 0
解：（共9分，每小题3分）
1．T0时刻是安全的，安全序列为：P1，P4，P5，P2，P3
2．P4请求资源（1，2，0），根据银行家算法，预分配后系统是安全的，安全序列为：P1，P4，P5，P2，P3
3．P3请求资源（1，1，0），根据银行家算法，预分配后系统不安全，所以不能实施资源分配。
9．一个进程的大小占5个页面，每页的大小为1K，系统为它分配了3个物理块。当前进程的页表如图所示：（共8分）
块号存在位P 访问位R 修改位M
0x1C 1 1 0
0x3F 1 1 1
- 0 0 0
0x5D 1 0 0
- 0 0 0
1．有那些页面不在内存？（2分）
2．请分别计算进程中虚地址为0x3B7、0x12A5、0x1432单元的物理地址（用十六进制表示），并说明理由。（6分）
解：（共8分）
不在内存的是第2和4页（按页号），或第3和5页（按序号）。（2分）
0x3B7的物理地址=0x 73 B7 （2分）
0x12 A5的物理地址=0x 176 A5，缺页，换出第三页。（2分）
0x1432地址越界，出错。（2分）
11．在一个请求分页系统中，有一个长度为5 页的进程，假如系统为它分配3 个物理块，并且此进程的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。试用FIFO 和LRU 两种算法分别计算出程序访问过程中所发生的缺页次数。（10分）
解：FIFO：
2 3 2 1 5 2 4 5 3 2 5 2
第1页 2 2 2 5 5 5 3 3 3
第2页 3 3 3 2 2 2 5 5
第3页 1 1 1 4 4 4 2
缺页中断次数= 6
LUR：
2 3 2 1 5 2 4 5 3 2 5 2
第1页 2 2 2 2 5 5 5 3
第2页 3 3 5 2 3 3 5
第3页 1 1 4 4 2 2
缺页中断次数= 5
12. 进程A1，A2，…，An 通过K 个缓冲区向进程B1，B2，…，Bm 不断地发送消息。发送和接收工作遵循如下规则：
1．每个发送进程一次发送一个消息，写入缓冲区，缓冲区大小与消息长度一致；2．对每个消息，B1，B2，…，Bm 都需接收一次，读入各自的数据区内；
3．K 个缓冲区都满时，发送进程等待，没有可读的消息时，接收进程等待。
试用wait 和signal 原语操作组织正确的发送和接收操作。（10分）
解：
BEGIN
Integer Mutex, Avail[n], Full[m];
Integer I;
Mutex:=1;
FOR i:=1 TO m DO
BEGIN
Avail[I] := k;
Full[I] := 0;
END
PROCEDURE Send(K)
Integer I;
BEGIN
13．一个进程的大小为5个页面，为它分配了四个物理块。当前每个块的情况如下表所示（都为十进制数，且从0开始计数。）。当虚页4发生缺页时，使用下列的页面置换算
法，哪一个物理块将被换出？并解释原因．（10分）
页号块号加载时间访问时间访问位R 修改位M
2 0 60 161 0 1
1 1 130 160 0 0
0 2 26 162 1 0
3 3 20 163 1 1
１．IFO算法
２．LRU算法
３．CLOCK算法
４．当页面的访问串为：“4，0，0，0，2，4，2，1，0，3，2”的OPT算法
解：1．换出第3号虚页，因为它加载的时间最早；
2．换出第1号虚页，因为它最近最久没被访问；
3．换出第1号虚页，因为它最近既没被访问，又没被修改；
4．换出第3号虚页，因为它离访问点最远。
16. Jruassic 公园有一个恐龙博物馆和一个公园.有m个旅客和n辆车,每辆车只能容纳
一个旅客。旅客在博物馆逛了一会儿，然后排队乘坐旅行车。当一辆车可用时，它载
入一个旅客，然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩，则想坐
车的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用
信号量同步m个旅客和n辆车的进程。（10分）
解：
visitors=m; cars=n; mutex=1;
Pvi() Pci()
{ repeat { repeat
wait(cars); wait(visitors);
wait(mutex); wait(mutex);
get on; start;
travell; run;
get off; stop;
signal(cars); signal(visitors);
wait(mutex); wait(mutex);
until false; until false;
} }
18、若干个等待访问磁盘者依次要访问的磁道为20，44，40，4，80，12，76，假设每移动一个磁道需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。
（1）先来先服务算法；
（2）最短寻道时间优先算法。
（3）扫描算法（当前磁头移动的方向为磁道递增）（10分）
解：
（1）磁道访问顺序为：20，44，40，4，80，12，76
寻道时间=（20+24+4+36+76+68+64）*3=292*3=876
（2）磁道访问顺序为：40，44，20，12，4，76，80
寻道时间=（0+4+24+8+8+72+4）*3=120*3=360
（3）磁道访问顺序为：40，44，76，80，20，12，4
寻道时间=（0+4+32+4+60+8+8）*3=116*3=348
19、生产者和消费者问题（10分）
有一组生产者P1，P2，……，PM和一组消费者C1，C2，……，CK，他们通过由n个环形缓冲区构成的缓冲池进行通信，生产者把产品放入缓冲区，消费者从缓冲区取产品来消费。请用wait和signal原语实现他们的同步操作。
解：生产者和消费者问题
begin
Var mutex,empty,full:semaphore:=1,n,0;
buffer:array[0,…,n-1] of item;
in,out:integer := 0,0;
parbegin
producer: begin
repeat
produce next product ;
wait (empty);
wait (mutex);
buffer(in):=nextp ;
in := (in+1) mod n ;
signal (full);
signal (mutex);
until false ;
end
consumer: begin
repeat
wait (full);
wait (mutex);
nextc := buffer(out);
out := (out+1) mod n;
signal (empty);
signal (mutex);
consume the item in nextc;
until false ;
end
parend end
20、请用信号量描述哲学家进餐问题。（15分）
解：哲学家进餐问题（15分）
public void philosopher (int i) {
while (true) {
think();
wait (fork[i]);
wait (fork [(i+1) % 5]);
eat();
signal(fork [(i+1) % 5]);
signal(fork[i]);
} }
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:array[0,…,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 waiting=waiting+1; signal(customers); signal(mutex); wait(barbers); } else { signal(mutex); } } 23、根据如下的前趋图写出可并发执行的程序：（10分） 1 2 3 4 5 6 7 解：（10） 评分：变量、进程、程序主体每项一分。 var a,b,c,d,e,f,g,h,i:semaphore := 0,0,0,0,0,0,0,0; begin parbegin 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; end parend end 24、在公共汽车上，乘客上完后，售票员关门，驾驶员开车，售票员售票，到站汽车停稳后，售票员开门，乘客上下车，售票员和驾驶员之间密切配合，直到下班。请用信号量描述公共汽车上售票员与驾驶员的工作过程。（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，1 1 1 1 1 4 4 4 4 5 5 2 2 2 2 7 7 7 7 6 3 3 3 3 2 2 2 2 6 6 6 6 1 1 1 页面置换次数为：6次 LRU： 1，2，3，6，4，7，3，2，1，4，7，5，6，5，2，1 1 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 2 3 3 3 3 3 3 3 7 7 7 7 1 6 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，1 1 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 2 3 3 3 3 3 3 3 7 7 7 7 1 6 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>0 S的值表示可继续进入售票厅的人数 S=0 表示售票厅中已有20名顾客(购票者) S<0 |S|的值为等待进入售票厅的人数 (2) int S=20; COBEGIN PROCESS PI(I=1，2，……) begin 进入售票厅； wait(S)； 购票； signal(S); 退出； end； COEND (3)S的最大值为20 S的最小值为20－n 27.设正在处理器上执行的一个进程的页表如下表所示，表中的虚页号和物理块号是十进制数，起始页号（块号）均为0。所有的地址均是存储器字节地址。页的大小为1024字节。（10分） ①详述在设有快表的请求分页存储管理系统中，一个虚地址转换成物理内存地址的过程。 ②下列虚地址对应于什么物理地址：5499，2221。 进程的页表 虚页号状态位访问位修改位物理块号 0 1 1 0 4 1 1 1 1 7 2 0 0 0 - 3 1 0 0 2 4 0 0 0 - 5 1 0 1 0 解： 5499的物理地址为：379 2221的物理地址为：3*1024+173=3245 28、假定系统有三个并发进程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:=0 Cobegin process read X:record; begin R: (接收来自输入设备上一个记录) X:=接收的一个记录； waiut(SR)； B1:=X; signal(SM1); goto R; end; Process move Y:record; Begin M:wait(SM1); Y:=B1; signal(SR) 加工Y wait(SM2)； B2:=Y; signal(SP); goto M; end; Process print Z:record; Begin P:wait(SP); Z:=B2; signal(SM2) 打印Z goto P; end; coend; end; 算法经典面试题 世界上第一位程序员是英国著名诗人拜伦的女儿AdaLovelace曾设计了巴贝奇分析机上解伯努利方程的一个程序。她甚至还建立了循环和子程序的概念。下面就由X为大家介绍一下程序员面试算法题的文章。 程序员面试算法题篇1 题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。 思路一：当我们到达某一个节点准备调整以该节点为根节点的子数时，先调整其左子树将左子树转换成一个排好序的左子链表，再调整其右子树转换成右子链表。最近链接左子链表的最右节点、当前节点和右子链表的最左节点。从树的根节点开始递归调整所有节点。 思路二：我们可以中序遍历整个树。按照这个方式遍历树，比较小的节点优先访问。如果我们每访问一个节点，假设之前访问过的节点已经调整为一个排序的双向链表，我们再把调整当前节点的指针链接到链表的末尾。当所有的节点都访问过之后，整棵树也就转换成一个排序的双向链表了。 参考代码： 二元查找树的节点数据结构： structBSTreeNode{ int value; BSTreeNode *m_left; BSTreeNode *m_right; } 思路二对应的代码： void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList) { if(pNode == NULL) return; BSTreeNode *pCurrent = pNode; // Convert the left sub-tree if (pCurrent->m_pLeft != NULL) ConvertNode(pCurrent->m_pLeft, pLastNodeInList); ①实验题目； 进程调度算法设计与实现 ②程序中所用数据结构及说明； 界面设计：使用switch语句，采用调用二维数组中的数据； 进程排序：采用冒泡排序法，将优先级高的进程调换； While循环重复执行进程调度，优先级高的进程调换，每运行一个时间片优先数减3，进程占用时间加1，进程尚需时间减1。 ③程序清单及描述； #include ●假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的 一个登记表上进行登记，而且每次只允许一人进行登记操作，请用记录型信号量机制实现上述问题的同步。 定义信号量sum,mutex，初值分别为100，1。（3分）则第i个读者的活动描述为：procedure P i(i=1,2,3……) begin wait(sum); wait(mutex); 登记； signal(mutex); 进入阅览室； 阅读; wait(mutex); 登记； signal(mutex); 离开阅览室； signal(sum); end ●请用信号量解决以下的“过独木桥”问题：同一方向的行人可连续过桥，当某一方向 有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。 将独木桥的两个方向分别标记为A和B；并用整形变量countA和countB分别表示A、B 方向上已在独木桥上的行人数，初值为0；再设置三个初值都1的互斥信号量：SA用来实现对countA的互斥访问，SB用来实现对countB的互斥访问，mutex用来实现两个方向的行人对独木桥的互斥使用。则具体描述如下： Var SA,SB,mutex:semaphore:=1,1,1; CountA,countB:integer:=0,0: begin parbegin process A: begin wait(SA); if(countA=0) then wait(mutex); countA:=countA+1; signal(SA); 过独木桥； wait(SA); countA:=countA-1; if (countA=0) then signal(mutex); signa(SA); end process B: begin wait(SB); 操作系统第三章总复习题 一、单选题 1、进程调度又称低级调度，其主要功能是（ D ）。 A．选择一个作业调入内存B．选择一个主存中的进程调出到外存 C．选择一个外存中的进程调入到主存D．将一个就绪的进程投入到运行 2、若进程P 一旦被唤醒就能够投入运行，系统可能为（ D ）。 A．分时系统，进程P 的优先级最高 B．抢占调度方式，就绪队列上的所有进程的优先级皆比P 的低 C．就绪队列为空队列 D．抢占调度方式，P 的优先级高于当期运行的进程。 3、一个进程P 被唤醒后,（ D ）。 A．P 就占有了CPU。B．P 的PCB 被移到就绪队列的队首。 C．P 的优先级肯定最高D．P 的状态变成就绪 4、若当前运行进程（）后，系统将会执行进程调度原语。 A 执行了一个转移指令 B 要求增加主存空间，经系统调用银行家算法进行测算认为是安全的。 C 执行了一条I/O 指令要求输入数据。 D 执行程序期间发生了I/O 完成中断。 5、当系统中（）时，系统将不会执行进程调度原语。 A．一个新进程被创建B．当前进程执行了P 操作。C．在非抢占调度中，进程A 正在运行而进程B 恰好被唤醒。D．分时系统中时间片用完。 6、在分时系统中，若当期运行的进程连续获得了两个时间片，原因可能是（）。 A 该进程的优先级最高 B 就绪队列为空 C 该进程最早进入就绪队列 D 该进程是一个短进程 7、实时系统中采用的调度算法可以有如下几种： 1、非抢占优先权调度算法 2、立即抢占优先权调度算法 3、时间片轮转调度算法 4、基于时钟中断抢占的优先权调度算法 按实时要求的严格程度由低到高的顺序（）。 A 1-3-2-4 B 3-1-4-2 C 3-1-2-4 D 1-3-4-2 8、三种主要类型的OS 中都必须配置的调度（）。 A 作业调度 B 中级调度 C 低级调度 D I/O 调度 9、设系统中n 个进程并发，共同竞争资源X，且每个进程都需要m 个X 资源，为使该系统不会发生死锁，资源X 最少要有（ C ）个。 A m*n+1 B n*m+n C n*m+1-n D 无法预计 10、死锁的预防方法中，不太可能的一种方法使（）。 1.时针分针重合几次 表面上有60个小格,每小格代表一分钟， 时针每分钟走1/12小格,分针每分钟走1小格,从第一次重合到第二次重合分针比时针多走一圈即6０小格，所以 ６０／(1-1/１2）=７20/１1 每隔７２0/１1分才重合一次(而并不是每小时重合一次） １440里有２2个72０/１1，如果说算上0点和24点,那也是重合2３次而已,但我觉得0点应该算到前一天的2４点头上，所以每一天循环下来重合２2次啊 2.找出字符串的最长不重复子串，输出长度 建一个2５6个单元的数组，每一个单元代表一个字符，数组中保存上次该字符上次出现的位置； 依次读入字符串,同时维护数组的值; 如果遇到冲突了,就返回冲突字符中保存的位置，继续第二步。也可以用ｈaｓhm ａp保存已经出现的字符和字符的位置 3. 说是有一个文本文件,大约有一万行，每行一个词，要求统计出其中最频繁出现的前十个词。 先用哈希，统计每个词出现的次数,然后在用在N个数中找出前K大个数的方法找出出现 次数最多的前１0个词。 ４. 如题3，但是车次文件特别大，没有办法一次读入内存。 1)直接排序,写文件时，同时写入字符串及其出现 次数。 2)可以用哈希，比如先根据字符串的第一个字符将字符串换分为多个区域,每个区域的字符串写到一个文件内,然后再用哈希+堆统计每个区域内前10个频率最高的字符串，最后求出所有字符串中前１0个频率最高的字符串。 5.有一个整数n，将ｎ分解成若干个整数之和,问如何分解能使这些数的乘积最大，输出这个乘积m。例如:ｎ＝12 (１)分解为１+1+１+…＋1,12个１, m=1*１*1……*１＝1 (2）分解为２＋2+…+2，6个2，m=64 （3）分解为3+3+３+3，4个3, m=8１ （4)大于等于4时分解时只能分解为2和3,且2最多两个 f(ｎ) =3*f（n-3）n>4 f（4)＝２*２ ｆ(３) = 3 ｆ（2) = 2分解为４+4+4,３个4，ｍ=6４ 6. 求数组ｎ中出现次数超过一半的数 把数组分成［n/2]组,则至少有一组包含重复的数，因为如果无重复数，则最多只有出现次数等于一半的数。算法如下: 6. 算法题（共32个题目） 200348. 在信号量机制中，若P（S）操作是可中断的，则会有什么问题？ 此题答案为：答： P（S）的操作如下： Begin S.Value:= S.Value-1; ① If S.Value<0 Then ② Begin Insert(*,S.L); Block(*) ③ End End. 若P（S）可中断的，例如进程A在执行了语句①之后从CPU上退 下了，假定此时S.Value＝0；这时换另一进程B，B又将S.Value 的值减1使之为－1，在执行语句③时，B被阻塞；然后又换回A执行，由于A的"断点"是语句①之后，当它执行语句②时，由于这时S.Value已经是－1，故进程继续执行而被阻塞。这就出现了错误： 本来A操作P（S）操作后，S.Value＝0，是不应该被阻塞的，现在却被阻塞了。 200350. 何谓临界区？下面给出的两个进程互斥的算法是安全的吗？为什么？ ＃define true; # define false; Int flag[2]; flag[1]=flag[2]=false; enter-crtsec(i) int i; { While(flag[1-i]) flag[i]=true; } feave-crtsec(i) Int i; { flag[i]=false; } process I; … Enter-crtsec(i); In critical section; Leave-crtsec(i); 此题答案为：答：一次仅允许一个进程使用的资源称为临界资源，在进程中对临界资源访问的程序段称为临界区。 从概念上讲，系统中各进程在逻辑上是独立的，它们可以按各自的速度向前推进。但由于它们共享某些临界资源，因而产生了临界区问题。对于具有临界区问题的并发进程，它们之间必须互斥，以保证不会同时进入临界区。 这种算法不是安全的。因为，在进入临界区的enter-crtsec（）不是一个原语操作，如果两个进程同时执行完其循环（此前两个flag均为false），则这两个进程可同时进入临界区。 200353. 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题： （1）用P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。 （2）根据所定义的信号量，把应执行的P、V操作填入下述程序中，以保证进程能够正确地并发执行。 Cobegin PROCESS Pi(i=1,2,…) Begin 进入售票厅； 购票； 退出； End; 操作系统之调度算法和死锁中的银行家算法习 题答案 集团文件发布号：（9816-UATWW-MWUB-WUNN-INNUL-DQQTY- 1. 有三个批处理作业，第一个作业 10:00 到达，需要执行 2 小时；第二个作业在10:10到达，需要执行 1 小时；第三个作业在 10:25 到达，需要执行 25 分钟。分别采用先来先服 务，短作业优先和最高响应比优先三种调度算法，各自的平均周转时间是多少？解： 先来先服务： （结束时间=上一个作业的结束时间+执行时间 周转时间=结束时间-到达时间=等待时间+执行时间） 按到达先后，执行顺序：1->2->3 短作业优先： 1)初始只有作业1，所以先执行作业1，结束时间是12:00，此时有作业2和3； 2)作业3需要时间短，所以先执行； 3)最后执行作业2 最高响应比优先： 高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。 1)10:00只有作业1到达，所以先执行作业1； 2)12:00时有作业2和3， 作业2：等待时间=12:00-10:10=110m;响应比=1+110/60=2.8； 作业3：等待时间=12:00-10:25=95m，响应比=1+95/25=4.8； 所以先执行作业3 3)执行作业2 2. 在一单道批处理系统中，一组作业的提交时刻和运行时间如下表所示。试计算一下三种 作业调度算法的平均周转时间 T 和平均带权周转时间 W。 （ 1）先来先服务；（ 2）短作业优先（ 3）高响应比优先 解： 先来先服务： 作业顺序：1,2,3,4 短作业优先： 作业顺序： 2008-02-18 18:48 【程序1】 题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。 2.程序源代码： main() { int i,j,k; printf("\n"); for(i=1;i<5;i++) ／*以下为三重循环*/ for(j=1;j<5;j++) for (k=1;k<5;k++) { if (i!=k&&i!=j&&j!=k) /*确保i、j、k三位互不相同*/ printf("%d,%d,%d\n",i,j,k); } } ============================================================== 【程序2】 题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高 于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提 成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于 40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于 100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ 1.程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。 2.程序源代码： main() { long int i; int bonus1,bonus2,bonus4,bonus6,bonus10,bonus; scanf("%ld",&i); bonus1=100000*0.1;bonus2=bonus1+100000*0.75; bonus4=bonus2+200000*0.5; bonus6=bonus4+200000*0.3; bonus10=bonus6+400000*0.15; if(i<=100000) 上海电力学院 计算机操作系统原理 课程设计报告 题目名称：编写程序模拟虚拟存储器管理 姓名：杜志豪.学号： 班级： 2012053班 . 同组姓名：孙嘉轶 课程设计时间：—— 评语： 成绩： 目录 一、设计内容及要求 (4) 1. 1 设计题目 (4) 1．2 使用算法分析： (4) 1． FIFO算法（先进先出淘汰算法） (4) 1． LRU算法（最久未使用淘汰算法） (5) 1. OPT算法（最佳淘汰算法） (5) 分工情况 (5) 二、详细设计 (6) 原理概述 (6) 主要数据结构(主要代码) (6) 算法流程图 (9) 主流程图 (9) Optimal算法流程图 (10) FIFO算法流程图 (10) LRU算法流程图 (11) ．1源程序文件名 (11) . 2执行文件名 (11) 三、实验结果与分析 (11) Optimal页面置换算法结果与分析 (11) FIFO页面置换算法结果与分析 (16) LRU页面置换算法结果与分析 (20) 四、设计创新点 (24) 五、设计与总结 (27) 六、代码附录 (27) 课程设计题目 一、设计内容及要求 编写程序模拟虚拟存储器管理。假设以M页的进程分配了N 块内存（N 操作系统期末考试（A） 一、单项选择题（在每小题的四个备选答案中，只有一个是正确的，将其写在题干的括号中。每小题2分，共20分） 1、文件系统的主要组成部分是（） A、文件控制块及文件 B、I/O文件及块设备文件 C、系统文件及用户文件 D、文件及管理文件的软件 2、实现进程互斥可采用的方法（） A、中断 B、查询 C、开锁和关锁 D、按键处理 3、某页式管理系统中，地址寄存器的低9位表示页地址，则页面大小为（） A、1024字节 B、512字节 C、1024K D、512K 4、串联文件适合于（）存取 A、直接 B、顺序 C、索引 D、随机 5、进程的同步与互斥是由于程序的（）引起的 A、顺序执行 B、长短不同 C、信号量 D、并发执行 6、信号量的值（） A、总是为正 B、总是为负 C、总是为0 D、可以为负整数 7、多道程序的实质是（） A、程序的顺序执行 B、程序的并发执行 C、多个处理机同时执行 D、用户程序和系统程序交叉执行 8、虚拟存储器最基本的特征是（） A、从逻辑上扩充存容量 B、提高存利用率 C、驻留性 D、固定性 9、飞机定票系统是一个（） A、实时系统 B、批处理系统 C、通用系统 D、分时系统 10、操作系统中，被调度和分派资源的基本单位，并可独立执行的实体是（） A、线程 B、程序 C、进程 D、指令 二、名词解释（每小题3分，共15分） 1.死锁: 2.原子操作: 3.临界区: 4.虚拟存储器: 5.文件系统: 三、判断改错题（判断正误，并改正错误，每小题2分，共20分） 1、通道是通过通道程序来对I/O设备进行控制的。（） 2、请求页式管理系统中，既可以减少外零头，又可以减少零头。（） 3、操作系统中系统调用越多，系统功能就越强，用户使用越复杂。（） 4、一个进程可以挂起自已，也可以激活自已。（） 5、虚拟存储器的最大容量是由磁盘空间决定的。（） 6、单级文件目录可以解决文件的重名问题。（） 7、进程调度只有一种方式：剥夺方式。（） 8、程序的顺度执行具有顺序性，封闭性和不可再现性。（） 9、并行是指两个或多个事件在同一时间间隔发生，而并发性是指两个或多个事件在同 一时刻发生。（） 10、进程控制一般都由操作系统核来实现。（） 四、简答题（每小题5分，共25分） 1、简述死锁产生的原因及必要条件。 2、什么是多道程序技术，它带来了什么好处？ 第三章处理机调度与死锁 1，高级调度与低级调度的主要任务是什么？为什么要引入中级调度？ 【解】（1）高级调度主要任务是用于决定把外存上处于后备队列中的那些作业调入内存，并为它们创建进程，分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。（2）低级调度主要任务是决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。（3）引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存空间，而将它们调至外存上去等待，称此时的进程状态为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件，且内存又稍有空闲时，由中级调度决定，将外存上的那些重又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上，等待进程调度。 3、何谓作业、作业步和作业流？ 【解】作业包含通常的程序和数据，还配有作业说明书。系统根据该说明书对程序的运行进行控制。批处理系统中是以作业为基本单位从外存调入内存。作业步是指每个作业运行期间都必须经过若干个相对独立相互关联的顺序加工的步骤。 作业流是指若干个作业进入系统后依次存放在外存上形成的输入作业流；在操作系统的控制下，逐个作业进程处理，于是形成了处理作业流。 4、在什么情冴下需要使用作业控制块JCB？其中包含了哪些内容？ 【解】每当作业进入系统时，系统便为每个作业建立一个作业控制块JCB，根据作业类型将它插入到相应的后备队列中。 JCB 包含的内容通常有：1) 作业标识2)用户名称3)用户账户4)作业类型（CPU 繁忙型、I/O芳名型、批量型、终端型）5)作业状态6)调度信息（优先级、作业已运行）7)资源要求8)进入系统时间9) 开始处理时间10) 作业完成时间11) 作业退出时间12) 资源使用情况等 5．在作业调度中应如何确定接纳多少个作业和接纳哪些作业？ 【解】作业调度每次接纳进入内存的作业数，取决于多道程序度。应将哪些作业从外存调入内存，取决于采用的调度算法。最简单的是先来服务调度算法，较常用的是短作业优先调度算法和基于作业优先级的调度算法。 7．试说明低级调度的主要功能。 【解】（1）保存处理机的现场信息（2）按某种算法选取进程（3）把处理机分配给进程。 8、在抢占调度方式中，抢占的原则是什么？ 【解】剥夺原则有：（1）时间片原则各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。这种原则适用于分时系统、大多数实时系统，以及要求较高的批处理系统。（2）优先权原则通常是对一些重要的和紧急的作业赋予较高的优先权。当这种作业到达时，如果其优先权比正在执行进程的优先权高，便停止正在执行的进程，将处理机分配给优先权高的进程，使之执行。（3）短作业（进程）优先原则当新到达的作业（进程）比正在执行的作业（进程）明显地短时，将剥夺长作业（进程）的执行，将处理机分配给短作业（进程），使之优先执行。 9、选择调度方式和调度算法时，应遵循的准则是什么？ 【解】应遵循的准则有（1）面向用户的准则：周转时间短，响应时间快，截止时间的保证，优先权准则。（2）面向系统的准则：系统吞吐量高，处理机利用率好，各类资源的平衡利用。 10、在批处理系统、分时系统和实时系统中，各采用哪几种进程（作业）调度算法？ 【解】 批处理系统：FCFS算法、最小优先数优先算法、抢占式最小优先数优先算法 2 分时系统：可剥夺调度、轮转调度 实时系统：时间片轮转调度算法、非抢占优先权调度算法、基于时钟中断抢占的优先权调度算法、立即抢占的优先权调度。 11、何谓静态和动态优先权？确定静态优先权的依据是什么？ 【解】静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。确定静态优先权的依据是：（1）进程类型，通常系统进程的优先权高于一般用户进程的优先权。（2）进程对资源的需要。（3）用户要求，用户进程的紧迫程度及用户所付费用的多少来确定优先权的。 12、试比较FCFS和SPF两种进程调度算法。 【解】FCFS算法按照作业提交或进程变为就绪状态的先后次序，分派CPU。当前作业或进程占有CPU，直到执行完或阻塞，才让出CPU。在作业或进程唤醒后，并不立即恢复执行，通常等到当前作业或进程让出CPU。FCFS比较有利于长作业，而不利于短作业；有利于CPU繁忙的作业，而不利于I/O繁忙的作业。SPF有利于短进程调度，是从就绪队列中选出一估计运行时间最短的进 算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i; 课程设计报告 题 目 操作系统算法设计 课 程 名 称 操作系统课程设计 院 部 名 称 计算机工程学院 专 业 计算机科学与技术 班 级 14计算机科学与技术单 学 生 姓 名 邵佳楠 学 号 141320100 课程设计地点 A107 课程设计学时 20学时 指 导 教 师 潘 金陵科技学院教务处制 成绩 目录 摘要 (2) 一、课程设计的目的和要求 (3) 二、系统需求分析 (3) 三、总体设计 (3) 四、详细设计 (4) 五、测试、调试过程 (7) 六、结论与体会 (16) 附录：源程序 (17) 摘要 (32) 一、课程设计的目的和要求 (33) 二、系统需求分析 (33) 三、总体设计 (33) 四、详细设计 (33) 五、测试、调试过程 (34) 六、结论与体会 (38) 附录：源程序 (39) 摘要 (47) 一、设计的目的和要求 (47) 二、系统需求分析 (48) 三、总体设计 (48) 四、详细设计 (48) 五、测试、调试过程 (50) 六、结论与体会 (54) 附录：源程序 (55) 操作系统算法设计-进程调度程序 摘要 随着计算机的普及，人们生活得到极大改善，人们在精神方面也同样需要提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大的扩展计算机的功能，充分发挥系统中的各种设备的使用效率，提高系统的可靠性。由于操作系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性，要学好这门课程，必须把理论和时间紧密结合，才能取得较好的学习效果。 本次课程设计师在学习完《操作系统教程》后，进行的一次全面的综合训练，通过课程设计，让学生更好的掌握操作系统的原理以及实现方法，加深对操作系统基础理论和重要算法的理解，加强对学生的动手能力。 熟悉“最高优先级优先调度算法”、“基于时间片轮转法”、“多级反馈队列调度算法”、“最高优先级优先算法”，虽然不用全部每一个都弄清楚，但是了解其中的算法思想也是有好处的。 关键词：最高优先级优先调度算法、基于时间片轮转法、多级反馈队列调度算法、最高优先级优先算法 华南农业大学数学与信息学院（软件学院） 《操作系统分析与设计实习》成绩单 开设时间：2015学年第一学期 评价指标： 题目内容和要求完成情况 优□ 良□ 中□ 差□ 对算法原理的理解程度 优□ 良□ 中□ 差□ 程序设计水平 优□ 良□ 中□ 差□ 程序运行效果及正确性 优□ 良□ 中□ 差□ 课程设计报告结构清晰 优□ 良□ 中□ 差□ 报告中总结和分析详尽 优□ 良□ 中□ 差□ 一、需求分析 (1)输入的形式和输入值的范围： 在文本框输入序列长度，输入值为int 类型 (2)输出的形式： 输出每种磁盘调度算法的服务序列； 输出每种算法的平均寻道长度。 (3)程序所能达到的功能： 模拟实现FCFS 、SSTF 、SCAN 、C-SCAN 算法，并计算及比较磁头移动道数。 （4）测试数据： 包括正确的输入及其输出结果和含有错误的输入及其输出结果： 二、概要设计 1）主程序流程图： 输出随机生成 400个磁道号序 列 主菜单选择算法 开始 FCFS SSTF SCAN C-SCAN 结束 （2）各程序模块之间的调用关系 磁头初始位置输入及 合法性检查 冒泡排序算法 由外向内输出磁道序列 由内向外输出磁道序列 由当前位置向内再向 外 输出磁道序列由当前位置向外再向 内 输出磁道序列 由当前位置向内再由 外向内输出磁道序列由当前位置向外再由 内向外输出磁道序列 就近选择 主函数 FCFS SSFT SCAN C-SCAN 三、详细设计 1）各操作伪码算法 （1）实现磁头初始位置的输入并进行合法性检查 int printstarter()//磁头初始位置输入 { 输入：磁头初始位置; if输入小于0或大于1500 { 输出："输入数据类型有误，请重新输入！" < 【程序1】 题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ 1.程序分析：兔子的规律为数列1,1,2,3,5,8,13,21.... public class exp2{ public static void main(String args[]){ int i=0; for(i=1;i<=20;i++) System.out.println(f(i)); } public static int f(int x) { if(x==1 || x==2) return 1; else return f(x-1)+f(x-2); } } 【程序2】 题目：判断101-200之间有多少个素数，并输出所有素数。 1.程序分析：判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除， 则表明此数不是素数，反之是素数。 【程序3】 题目：打印出所有的 "水仙花数 "，所谓 "水仙花数 "是指一个三位数，其各位数字立方和等于该数本身。例如：153是一个 "水仙花数 "，因为153=1的三次方＋5的三次方＋3的三次方。 1.程序分析：利用for循环控制100-999个数，每个数分解出个位，十位，百位。 【程序4】 题目：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。 程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成： (1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。 (2)如果n <> k，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数你n,重复执行第一步。 (3)如果n不能被k整除，则用k+1作为k的值,重复执行第一步。 【程序5】 题目：利用条件运算符的嵌套来完成此题：学习成绩> =90分的同学用A表示，60-89分之间的用B表示，60分以下的用C表示。 1.程序分析：(a> b)?a:b这是条件运算符的基本例子。 【程序6】 题目：输入两个正整数m和n，求其最大公约数和最小公倍数。 1.程序分析：利用辗除法。 【程序7】 题目：输入一行字符，分别统计出其中英文字母、空格、数字和其它字符的个数。 1.程序分析：利用while语句,条件为输入的字符不为 '\n '. 【程序8】 题目：求s=a+aa+aaa+aaaa+aa...a的值，其中a是一个数字。例如 2+22+222+2222+22222(此时共有5个数相加)，几个数相加有键盘控制。 1.程序分析：关键是计算出每一项的值。 【程序9】 题目：一个数如果恰好等于它的因子之和，这个数就称为 "完数 "。例如6=1＋2＋3.编程找出1000以内的所有完数。 【程序10】 题目：一球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在第10次落地时，共经过多少米？第10次反弹多高？ 【程序11】 题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排 操作系统课程设计 （银行家算法的模拟实现） 一、设计目的 1、进一步了解进程的并发执行。 2、加强对进程死锁的理解。 3、用银行家算法完成死锁检测。 二、设计内容 给出进程需求矩阵C、资源向量R以及一个进程的申请序列。使用进程启动拒绝和资源分配拒绝（银行家算法）模拟该进程组的执行情况。 三、设计要求 1、初始状态没有进程启动。 2、计算每次进程申请是否分配,如：计算出预分配后的状态情况（安全状态、不安全状态）,如果是安全状态,输出安全序列。 3、每次进程申请被允许后,输出资源分配矩阵A和可用资源向量V。 4、每次申请情况应可单步查看,如：输入一个空格,继续下个申请。 四、算法原理 1、银行家算法中的数据结构 (1)、可利用资源向量Available,这是一个含有m个元素的数组,其中的每个元素代表一类可利用资源的数目, 其初始值是系统中所配置的该类全部资源的数目,其数值随该类资源的分配和回收而动态改变。如果Available[j]=K,则表示系统中现有Rj 类资源K个。 （2）、最大需求矩阵Max,这是一个n*m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。 （3）、分配矩阵Allocation。这也是一个n*m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,则表示进程i当前已经分得Rj类资源的数目为K。 （4）、需求矩阵Need。这也是一个n*m的矩阵,用以表示每个进程尚需要的各类资源数。如果Need[i,j]=K,则表示进程i 还需要Rj类资源K个,方能完成其任务。上述三个矩阵间存在以下关系： Need[i,j]=Max[i,j]-Allocation[i,j] 2、银行家算法应用 模拟实现Dijkstra的银行家算法以避免死锁的出现,分两部分组成：一是银行家算法（扫描）；二是安全性算法。 （1）银行家算法（扫描） 设Requesti是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Ri类型的资源。当Pi发出资源请求后,系统按下述步骤进行检查： 计算机操作系统经典题库及答案 一填空： 1．操作系统为用户提供三种类型的使用接口，它们是(命令方式)和(系统调用)和图形用户界面。 2．主存储器与外围设备之间的数据传送控制方式有程序直接控制、(中断驱动方式)、(DMA方式)和通道控制方式。 3．在响应比最高者优先的作业调度算法中，当各个作业等待时间相同时，(运行时间短)的作业将得到优先调度；当各个作业要求运行的时间相同时，(等待时间长)的作业得到优先调度。 4．当一个进程独占处理器顺序执行时，具有两个特性：(封闭性)和可再现性。5．程序经编译或汇编以后形成目标程序，其指令的顺序都是以零作为参考地址，这些地址称为(逻辑地址)。 6．文件的逻辑结构分(流式文件)和记录式文件二种。 7．进程由程度、数据和(FCB)组成。 8．对信号量S的操作只能通过(原语)操作进行，对应每一个信号量设置了一个等待队列。 9．操作系统是运行在计算机(裸机)系统上的最基本的系统软件。 10．虚拟设备是指采用(SPOOLING)技术，将某个独享设备改进为供多个用户使用的的共享设备。 11．文件系统中，用于文件的描述和控制并与文件一一对应的是(文件控制块)。12．段式管理中，以段为单位，每段分配一个(连续区)。由于各段长度(不同)，所以这些存储区的大小不一，而且同一进程的各段之间不要求连续。 13．逻辑设备表（LUT）的主要功能是实现(设备独立性)。 14在采用请求分页式存储管理的系统中，地址变换过程可能会因为(缺页)和(越界)等原因而产生中断。 16. 段的共享是通过（共享段）表实现的。 17．文件的物理结构分为顺序文件、（索引文件）和（索引顺序文件）。 18．所谓（设备控制器），是一块能控制一台或多台外围设备与CPU并行工作的 第四章处理机调度 4.3 习题 4.3.1 选择最合适的答案 1．某系统采用了银行家算法，则下列叙述正确的是（）。 A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁 C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁 2．银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项正确的是（）。 A.Max[i,j]=Allocation[i,j]+Need[i,j] B.Need[i,j]= Allocation[i,j]+ Max[i,j] C.Max[i,j]= Available[i,j]+Need[i,j] D.Need[i,j]= Available[i,j]+ Max[i,j] 3．下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。 A.非抢占式静态优先权法 B.抢占式静态优先权法 C.时间片轮转调度算法 D.非抢占式动态优先权法 4．在下列选项中，属于预防死锁的方法是（）。 A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法 5．在下列选项中，属于检测死锁的方法是（）。 A.银行家算法 B.消进程法 C.资源静态分配法 D.资源分配图简化法 6．在下列选项中，属于解除死锁的方法是（）。 A．剥夺资源法 B.资源分配图简化法 C．银行家算法 D.资源静态分配法 7．为了照顾紧迫型作业，应采用（）。 A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法 8．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则 《操作系统》课程实验指导书 一、设计题目 题目一：模拟实现页式虚拟存储管理页面置换算法 题目二：模拟实现虚拟存储管理（请求分页存储管理） 题目三：模拟实现可变分区存储管理 题目四：模拟实现算法多级反馈队列进程调度算法 题目五：模拟银行家算法 二、设计目的 《操作系统》课程实验是计算机类专业的集中实践性环节之一，是学习完《操作系统》课程后进行的一次全面的综合练习。其目的在于加深对操作系统课程的理解，使学生更好地掌握操作系统的基本概念、基本原理、及基本功能，理解操作系统在计算机系统中的作用、地位和特点，具有分析实际操作系统，设计、构造和开发现代操作系统的基本能力，为今后从事的各种实际工作，如设计、分析和改进各种系统软件和应用软件提供必要的软件理论基础。 、设计内容 设计内容一页式虚拟存储管理页面置换算法 1．目的和要求 在熟练掌握计算机虚拟存储技术的原理的基础上，利用一种程序设计语言模拟实现几种置换算法，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。 2．设计内容 阅读教材《计算机操作系统》第四章，掌握存储器管理相关概念和原理。 模拟实现页式虚拟存储管理的三种页面置换算法（OPT、FIFO和LRU），并通过比较性能得出结论。 前提： （1）页面分配采用固定分配局部置换。 （2）作业的页面走向和分得的物理块数预先指定。可以从键盘输入也可以从文件读入。 （3）置换算法的置换过程输出可以在显示器上也可以存放在文件中，但必须清晰可读，便于检验。 3．设计环境 Windows操作系统、VC++6.0 C语言 4．设计提示 （1）基础知识 存储管理是操作系统进行资源管理的一个重要功能。现代操作系统广泛采用虚拟存储的技术对内存进行扩充。实现虚拟存储的一个主要技术手段就是将辅存和主存统一管理，在二者之间进行对换，从而形成物理上两级而逻辑上一级的存储管理系统。一个置换算法的好坏对这个逻辑上的单级虚存的性能起着极其重要的作用，而且会影响处理机的调度性能。 对于本任务规定的前提：页面分配采用固定分配局部置换，则置换发生的时机是作业已经将操作系统分配的固定数目的物理块全部用完且发生缺页的时候。此时必须要将已经装入内存的部分逻辑页面换出以便将所缺的页面调入内存。置换算法就是一个决定将内存中“哪一个”页面换出的算法。 （2）数据结构算法经典面试题
操作系统-进程调度算法设计与实现
操作系统经典习题+解释
第三版操作系统第3章习题
经典算法面试题及标准答案
计算机操作系统算法题(最全)
操作系统之调度算法和死锁中的银行家算法习题答案
C语言经典算法100例(1---30)
操作系统课程设计报告
操作系统精彩试题及问题详解
计算机操作系统课后习题答案第三章(第四版)
算法设计及分析递归算法典型例题
操作系统算法设计操作系统课程设计大学论文
操作系统课程设计报告-磁盘调度算法
经典算法题目
操作系统课程设计(银行家算法的模拟实现)剖析.doc
计算机操作系统经典题库及答案
操作系统原理第四章 处理机调度习题
操作系统课程设计任务书