操作系统算法题

1. 在信号量机制中，若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，是不应该被阻塞的，现在却被阻塞了。

2. 何谓临界区？下面给出的两个进程互斥的算法是安全的吗？为什么？

＃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），则这两个进程可同时进入临界区。

3. 当进程X和进程Y共享某个资源r，进程并发执行时的程序如下：

Begin

S:semaphore:=1;

Cobegin

Process X

Begin

L1:P(S);

使用资源r;

V(S);

Goto L1;

End;

Process Y

Begin

L2:P(S);

使用资源r;

V(S);

Goto L2;

End;

Coend;

End;

请回答：

（1）两个进程并发执行时，能否保证互斥地使用资源？为什么？

（2）若要使用两个进程交替使用资源，仍使用P、V操作来进行管理，写出应定义的信号量及其初值。

（3）修改上述程序，使两个进程能交替使用资源r。

答：当进程X和进程Y共享某个资源r，回答各问如下：

（1）能保证互斥使用资源。因为在两个进程中，"使用资源r"都是作为临界区，由于P(S) 和V(S)操作保证了互斥执行，S的初值定义为1，符合要求。

（2）要使两个进程交替使用资源，仅仅保证互斥使用是不够的，必须要两个进程互相等待互相通知。为此，必须定义新的信号量。定义两个私有信号量S1和S2。假定进程X先使用资源，那么进程X的私有信号量S1的初值定义为1，进程Y的私有信号量S2的初值定义为0。轮流使用可以保证互斥，因此信号量S可以不要。

（3）两个进程可以改写为：

Begin

S1:semaphore:=1;

S2:semaphore:=1;

Cobegin

Process X

Begin

L1:P(S1);

使用资源r;

V(S2);

Goto L1;

End;

Process Y

Begin

L2:P(S2);

使用资源r;

V(S1);

Goto L2;

End;

Coend;

End;

4. 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：

（1）用P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。

（2）根据所定义的信号量，把应执行的P、V操作填入下述程序中，以保证进程能够正确地并发执行。

Cobegin PROCESS Pi(i=1,2,…)

Begin

进入售票厅；

购票；

退出；

End;

Coend

(3)若欲购票者最多为n个人，写出信号量可能的变化范围（最大值和最小值）。

答：售票厅问题解答如下：

（1）定义一信号量S，初始值为20。

S>0 S的值表示可继续进入售票厅的人数；

S=0 表示售票厅中已有20名购票者；

S<0 |S|的值为等待进入售票厅中的人数。

（2）上框为P(S)，下框为V(S)。

（3）S的最大值为20，S的最小值为20－N，N为某一时刻需要进入售票厅的最多人数。

5. 已经系统中有四个缓冲池M0，M1，M2，M3。其容量分别为3、2、3、2，现各缓冲区分别存在0、1、0、2个数据。现同时有四个进程P0、P1、P2、P3分别在各缓冲区间不断地移动数据（见图3.5）。例如，P0进程从M0向M1移动数据。试用信号量及其P、V（或signal，wait）操作及类Pasic/C 语言描述各进程之间的同步关系，并给出各信号量的含义和初值。

答：（1）互斥信号量和初值

M(0)=1，M(1)=1，M(2)=1，M(3)=1，

（2）同步信号量

Full(i)表示buffer(i)是否有数据；

初值为full(0)=0，full(1)=1，full(2)=0，full(3)=2；

Empty(i)表示buffer(i)是否有空间；

初值为empty(0)=3，empty(1)=1，empty(2)=3，empty(3)=0

（3）进程i的程序

Process Proc(i)

{ p(full(i));

p(empty(i+1) mod 5);

p(m(i));

move;

v(m(i));

v(m(full(i+1) mod 5));

v(empty (i));

}

6. 设有两个优先级相同的进程P1和P2如下，信号量S1和S2的初值均为0。试问P1、P2并发执行结束后，x=?,y=?,z=?

<进程P1>

Y:=1;

Y:=y+2;

V(S1);

Z:=y+1;

P(S2);

Y:=z+y;

＜进程P2＞

X:=1;

X:=x+1;

P(S1);

X:=x+y;

V(S2);

Z:=x+z;

答：因为P1和P2是两个并发进程，所以进程调度程序调度P1 和P2的顺序是不确定的。

这里不妨假设P1先执行。进程P1执行到语句P(S2)时，S2＝－1，进程P1阻塞。此时y=3,z=4。当进程调度程序调度到进程P2时，由于进程P1已执行了V(S1)，进程P2在执行P(S1)时并未阻塞而继续执行，当执行到V(S2)时，将P1唤醒，然后执行最后一个语句z:=x+z，此时x=5,z=9。当进程P1再次被调度时，继续执行P1的最后一个语句，此时y=12，最终结果是：x=5,y=12,z=9。

如果当P2进程执行到V(S2)时，将P1唤醒，然后P2进程被中断，此时x=5,y=3,z=4。P1进程开始执行然后执行最后一个语句y:=z+y，此时x=5,y=3,z=7。然后P2进程被调度，执行z:=x+z，此时x=5,y=3,z=12。

如果P2先执行，则执行结果与上面相同。

7. 在批处理系统、分时系统和实时系统中，各采用哪几个进程（作业）调度算法？

答：（1）批处理系统中的作业调度算法有：先来先服务算法（FCFS）、短作业优先算法（SJF）、优先级调度算法（HPF）和高响应比优先算法（RF）。批处理系统的进程调度算法有：先进先出算法（FIFO）、短进程优先算法（SPF）、优先级调度算法（HPF）和高响应比优先算法（RF）。

（2）分时系统中只设有进程调度（不设作业调度），其进程调度算法只有轮转法（RR）一种。（3）实时系统中只设有进程（不设作业调度），其进程调度算法调度有：轮转法、优先级调度算法。前者适用于时间要求不严格的实时系统；后者用于时间要求严格的实时系统。后者又可细分为：非抢占式优先级调度、抢占式优先级调度、基于时钟中断的抢占式优先级调度。

注意，一个纯粹的实时系统是针对特定应用领域设计的专用系统。作业提交的数量不会超过系统规定的多道程序的道数，因而可全部进入内存。若将实时系统与批处理系统结合的话，就可以让作业量超过多道程序道数，使优先级低的作业呆在外存的后备队列上。

8. 假设系统中有5个进程，它们的到达时间和服务时间见下表1，忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，完成表2。

表2 进程的完成时间和周转时间

答：

9. 一个逻辑空间最多可有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储器。问：（1）有效的逻辑地址由多少位？（2）有效的物理地址由多少位？

答：一个逻辑空间有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储嚣。64＝26，则：

（1）逻辑地址有16位。

（2）物理地址有15位。

说明：解此题的关键是要知道在分页管理中，"页"和"块"是一样大小的，这样才知道物理存储器是32KB。

10. 在某分页系统中，测得CPU和磁盘的利用率如下，试指出每种情况下的问题和措施。

（1）CPU的利用率为15%，磁盘利用率为95%。

（2）CPU的利用率为88%，磁盘利用率为3%。

（3）CPU的利用率为13%，磁盘利用率为5%。

答：在某分页虚存系统中，在题中的CPU和磁盘的利用率的情况下，出现的问题和应采取的措施如下：

（1）可能已出现了抖动现象，应减少系统的进程数。

（2）系统比较正常，可考虑适当增加进程数以提高资源利用率。

（3）CPU和磁盘的利用率都较低，必须增加并发进程数。

11. 对访问串：1，2，3，4，1，2，5，1，2，3，4，5，指出在驻留集大小分别为3，4时，使用FIFO 和LRU替换算法的缺页次数。结果说明了什么？

答：首先采用FIFO，当m=3时，缺页次数＝9，当m=4时，缺页次数＝10。

采用LRU算法，当m=3时，缺页次数＝10；当m=4时，缺页次数＝8。

结果说明：FIFO有Belady奇异现象，即不满足驻留集增大，缺页次数一定减小的规律；另外在m=3时，LRU的缺页次数比FIFO要多，所以LRU算法并不总优于FIFO，还要看当前访问串的特点。

12. 一个分页存储器的页表存放在内存。

（1）若内存的存取周期为0.6ms，则CPU从内存取一条指令（或一个操作数）需多少时间？

（2）若使用快表且快表的命中率为75%，则内存的平均存取周期为多少？

答：一个分页存储器的页表存放在内存

（1）因为页表放在内存，故取一条指令（或一个操作数）须访问两次内存，所以需0.6ms×2=1.2ms 的时间。

（2）这里家假设访问快表的时间忽略不计，命中快表时，取数只要一次访问，故此时的平均存取周期为0.6ms×0.75+1.2ms×(1-0.75)=0.75ms

13. 在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过

程中所发生的缺页次数和缺页率，并画出页面置换图。

解：

访问过程中缺页情况（M=3）

页面走向 4 3 2 1 4 3 5 4 3 2 1 5 最近最长时间未使用的页面 4 3 3 2 4 3 5 4 3 2

4 3 2 1 4 3

5 4 3 2 1

最近刚使用过的页面 4 3 2 1 4 3 5 4 3 2 1 5 缺页√ √ √ √ √ √ √ √ √ √当M=3时，缺页次数为10次，缺页率为10/12=0.83=83%。

访问过程中缺页情况（M=4）

页面走向 4 3 2 1 4 3 5 4 3 2 1 5 最近最长时间未使用的页面 4 3 2 1 1 1 5 4 3

4 3 2 1 4 3

5 4 3 2

4 3 2 1 4 3

5 4 3 2 1

最近刚使用过的页面 4 3 2 1 4 3 5 4 3 2 1 5 缺页√ √ √ √ √ √ √当M=4时，缺页次数为8次，缺页率为8/12=0.66=66%。

可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。

14. 对于一个使用快表的页式虚存，设快表的命中率为70%，内存的存取周期为1ns；缺页处理时，若内存有可用空间或被置换的页面在内存未被修改过，则处理一个缺页中断需8000ns，否则需20000ns。假定被置换的页面60%是属于后一种情况，为了保证有效存取时间不超过2ns，问可接受的最大缺页率是多少？

答：设可接受的最大缺页率位p，则有

1ns×0.7+2ns×(1-0.7-p)+0.4p×8000ns+0.6p×20000ns=2ns

即0.7+0.6-2p+3200p+12000p=2

15198p=0.7

P=0.000046

15. 在分页存储管理系统中，存取一次内存的时间是8ns，查询一次快表的时间是1ns，缺页中断的时间是20ns。假设页表的查询与快表的查询同时进行，当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。一个作业最多可保留3个页面在内存。现在开始执行一作业，系统连续对作业的2，4，5，2，7，6，4，8页面的数据进行一次存取，如分别采用FIFO 算法和最优页面置换算法，求每种上存取这些数据需要的总时间。

答：（1）FIFO

第2页面：20＋8×3

第4页面：20＋8×3

第5页面：20＋8×3

第2页面：8＋1

第7页面：20＋8×3

第6页面：20＋8×3

第4页面：20＋8×3

第8页面：20＋8×3

因此总的时间是（20＋8×3）×7＋（8＋1）ns

(2) OPT

第2页面：20＋8×3

第4页面：20＋8×3

第5页面：20＋8×3

第2页面：8＋1

第7页面：20＋8×3

第6页面：20＋8×3

第4页面：8＋1

第8页面：8＋1

因此总的时间是（20＋8×3）×5＋（8＋1）×3ns

16. 在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为1、3、2、1、1、3、5、1、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。

解：

访问过程中缺页情况（M=3）

页面走向 1 3 2 1 1 3 5 1 3 2 1 5 最近最长时间未使用的页面 1 3 3 2 1 3 5 1 3 2

1 3

2 2 1

3 5 1 3 2 1

最近刚使用过的页面 1 3 2 1 1 3 5 1 3 2 1 5 缺页√ √ √ √ √ √当M=3时，缺页次数为6次，缺页率为6/12=0.5=50%。

访问过程中缺页情况（M=4）

页面走向 1 3 2 1 1 3 5 1 3 2 1 5 最近最长时间未使用的页面 2 2 2 5 5 3

1 3 3

2 1

3 5 1 3 2

1 3

2 2 1

3 5 1 3 2 1

最近刚使用过的页面 1 3 2 1 1 3 5 1 3 2 1 5 缺页√ √ √ √

当M=4时，缺页次数为4次，缺页率为4/12=0.33=33%。

可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。

17. 在一个请求分页系统中，采用OPT页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。

解：

访问过程中缺页情况（M=3）

页面走向 4 3 2 1 4 3 5 4 3 2 1 5 最近最长时间未使用的页面 2 1 1 1 5 4 4/3 3/2 1/2

3 3 3

4 3 3 5

最近刚使用过的页面 4 4 4 4 3 4 4 3 5 5 5

缺页√ √ √ √ √ √ √

当M=3时，缺页次数为7次，缺页率为7/12=0.583=58.3%。

访问过程中缺页情况（M=4）

页面走向 4 3 2 1 4 3 5 4 3 2 1 5 最近最长时间未使用的页面 1 1 1 5 4 4/3 4/3/2 1/3/2

2 2 2 2 2 5

3 3 3

4 3 3 2 5

最近刚使用过的页面 4 4 4 4 3 4 4 3 2 5 5

缺页√ √ √ √ √ √

当M=4时，缺页次数为8次，缺页率为6/12=0.5=50%。

可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。

18. 在一个请求分页系统中，采用FIFO页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。

解：

访问过程中缺页情况（M=3）

页面走向 4 3 2 1 4 3 5 4 3 2 1 5 最近最长时间未使用的页面 4 3 2 1 4 4 4 3 5 5

4 3 2 1 4 3 3 3

5 2 2

最近刚使用过的页面 4 3 2 1 4 3 5 5 5 2 1 1 缺页√ √ √ √ √ √ √ √ √

当M=3时，缺页次数为9次，缺页率为9/12=0.75=75%。

访问过程中缺页情况（M=4）

页面走向 4 3 2 1 4 3 5 4 3 2 1 5 最近最长时间未使用的页面 4 4 4 3 2 1 5 4 3

4 3 3 3 2 1

5 4 3 2

4 3 2 2 2 1

5 4 3 2 1

最近刚使用过的页面 4 3 2 1 1 1 5 4 3 2 1 5 缺页√ √ √ √ √ √ √ √ √当M=4时，缺页次数为10次，缺页率为10/12=0.86=83%。

可见，增加分配给作业的内存块数并不能减少缺页次数，降低缺页率，这种现象叫抖动现象（Belady）。

19. 利用信号量机制描述前趋关系：

S={S1,S2,S3,S4,S5,S6,S7}={(S1,S2),(S1,S3),(S2,S4),(S2,S5),(S3,S5),(S3,S6),(S4,S7),(S5,S7),(S6,S7)}

解：

Var a,b,c,d,e,f,g,h,i,:semaphore:=0,0,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(b);S3;signal(e);signal(f);end;

Begin wait(c);S4;signal(g);end;

Begin wait(d);wait(e);S5;signal(h);end;

Begin wait(f);S6;signal(i);end;

Begin wait(g);wait(h);wait(i);S7;end;

Parend

end

20. 利用记录型信号量解决经典同步问题：生产者——消费者

解：

Var mutex,empty,full:semaphore:=1,n,0;

buffer:array[0,...,n-1] of item;

in,out:integer:=0,0;

begin

parbegin

proceducer:

begin

repeat

...

producer an item nextp;

...

wait(empty);

wait(mutex);

buffer(in):=nextp;

in:=(in+1) mod n;

signal(mutex);

signal(full);

until false;

end

consumer:

begin

repeat

wait(full);

wait(mutex);

nextp:=buffer(out);

out:=(out+1) mod n;

signal(mutex);

signal(empty);

consumer the item in nextc;

until false;

end

patend

end

21. 利用记录型信号量解决经典进程同步问题：读者——写者

解：

Var rmutex,wmutex:semaphore:=1,1;

Readcount:integer:=0;

Begin

parbegin

Reader:

begin

repeat

wait(rmutex)

if Readcount=0 then wait(wmutex);

Readcount:=Readcount+1;

signal(rmutex)

...

perform read operation;

...

wait(rmutex);

Readcount:=Readcount-1;

if Readcount=0 then signal(wmutex);

signal(rmutex);

until false;

end

Writer:

begin

repeat

wait(wmutex);

perform write operation;

signal(wmutex);

until false

end

parend

End

22. 有一个车间不断取A和B进行装配，每次各取一个。为避免零件锈蚀，遵循先入库者先出库的原则。有两组供应商分别不断供应A和B（每次1个）。为保证齐套和合理库存，当某种零件的数量比另一种零件的数量多得超过n（n

解：

var mutex,emptya,emptyb,fulla,fullb,sa,sb:semaphore:=1,m,m,0,0,n,n;

Begin

cobegin

provider_A();

provider_B();

assembiling_shop();

coend

provider_A()

begin

repeat

wait(emptya);

wait(sa);

wait(mutex);

put A into the storehouse;

signal(mutex);

signal(fulla);

signal(sb);

until false;

end

provider_B()

begin

repeat

wait(emptyb);

wait(sb);

wait(mutex);

put B into the storehouse;

signal(mutex);

signal(fullb);

signal(sa);

until false;

end

asemmbling_shop()

begin

repeat

wait(fulla);

wait(fullb);

wait(mutex);

asemmbling A and B;

signal(mutex);

signal(emptya);

signal(emptyb);

until false;

end

corend

End

23. 一个主修动物行为学，辅修计算机科学的学生参加了一个课题，调查花果山的猴子能否被教会理解死锁。他找到一处峡谷，横跨峡谷拉了一根绳索（假设为南北方向），这些猴子就可以攀登着绳索跨过峡谷。只要它们朝着相同的方向，同一时刻可以有多个猴子通过。但是如果在相反方向商同时有猴子通过则会发生死锁（这些猴子卡在绳子中间，假设这些猴子无法在绳索商从另一只猴子身上翻过去）。如果一只猴子想跨越峡谷，他必须看当前是否有别的猴子在逆向通过。请使用信号量写一个避免思索的程序来解决该问题。

解：

Begin

var Smutex,Nmutex,SMonkeyCount,NMonkeyCount:Semaphore;

SMonkeyCount:=0;

NMonkeyCount:=0;

Smutex:=1;

Nmutex:=1;

mutex:=1;

ParBegin

Southi(i=1,2,3,...)

Begin

wait(Smutex);

if SMonkeyCount=0 then wait(mutex);

SMonkeyCount:=SMonkeyCount+1;

signal(Smutex);

Cross the cordage;

wait(Smutex);

SMonkeyCount:=SMonkeyCount-1;

if SMonkeyCount=0 then signal(mutex);

signal(Smutex);

End

Northi(i=1,2,3,...)

Begin

wait(Smutex);

if NMonkeyCount=0 then wait(mutex);

NMonkeyCount:=NMonkeyCount+1;

signal(Nmutex);

Cross the cordage;

wait(Nmutex);

NMonkeyCount:=NMonkeyCount-1;

if NMonkeyCount=0 then signal(mutex);

signal(Nmutex);

End

parEnd

End

24. 设有两个生产者进程A和B和一个销售进程C，它们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售者销售；销售者每次循环从仓库中取出一个产品销售。如果不允许同时入库，也不允许同时出库；而且要求生产和销售A产品和B产品数量都满足以下关系：-n<=A 的件数-B的件数<=m，其中n，m是正整数。请用信号量机制写出A，B，C三个进程的工作流程。

解：

Var difference:integer:=0;

SAB,SBA,S,SA,SB,mutex:semaphore:=m,n,0,0,0,1;

Begin

parbegin

process A:

begin

repeat

wait(SAB);

produce a product A;

signal(SBA);

wait(mutex);

add the product A to the storehouse;

signal(mutex);

signal(SA);

signal(S);

until false;

end

process B:

begin

repeat

wait(SBA);

produce b product B;

signal(SAB);

wait(mutex);

add the product B to the storehouse;

signal(mutex);

signal(SB);

signal(S);

until false;

process C:

begin

repeat

wait(S);

if difference<=-n then

begin

wait(SA);

wait(mutex);

take a product A from storehouse;

signal(mutex);

difference:=difference+1;

end

elseif difference>=m then

begin

wait(SB);

wait(mutex);

take a product B from storehouse;

signal(mutex);

difference:=difference-1;

end

else

wait(mutex);

take a product A or B from storehouse;

signal(mutex);

if (product_type=A) then

begin

wait(SA);

difference:=difference+1;

end

else

begin

wait(SB);

difference:=difference-1;

end

sell the product;

until false;

parend

End

25. 试证明：如果系统作业几乎同时到达，则使系统平均作业周转时间最短的算法是短作业优先。

解：

设有n个作业j1,j2,j3,...,jn，其运行时间分别为t1,t2,t3,...,tn。不妨假设t1<=t2<=t3<=...<=tn，则短作业优先的作业调度算法的平均周转时间为：

T=(t1+(t1+t2)+(t1+t2+t3)+....(t1+t2+t3+...+tn))/n

=(n*t1+(n-1)*t2+...+tn)/n

考虑其他不同调度算法，设在此调度算法下的作业调度次序为ji1,ji2,...jin,其中（i1,i2,...,in）是（1,2,3,...,n）的一个排列，则类似上面可以得出：

T1=((n*ti1+(n-1)*ti2+...+tin)/n)

根据不等式结论：如果有a1<=a2<=...<=an 且b1<=b2<=...<=bn，则

a1bn+a2bn-1+...+anb1<=a1bi1+a2bi2+...+anbn<=a1b1+a2b2+...+anbn

其中（i1,i2,...,in）是（1,2,3,...,n）的一个排列，不难得出T<=T1。

26. 采用银行家算法防止死锁，用Pi→n表示Pi 进程申请n个资源，用Pi←n表示Pi 进程占有n

个资源。如果占有n个资源的进程被阻塞，可以用Pi*←n 来表示，假设系统中有某类资源10个，进程P1, P2, P3各自的最大需求量为3,7,10个,各进程T0时刻开始运行:

T1时刻发生: P1→2, P2→3, P3→3

T2时刻发生: P2→1, P3→2

T3时刻发生: P1→1, P2→1

根据银行家算法,填写三个时刻的进行占有和阻塞情况.

进程T0 T1 T2 T3

P1

P2

P3

P2

P3

解：

进程T0 T1 T2 T3

P1 P1←0 P1←2 P1←2 P1←3

P2 P2←0 P2←3 P2←4 P2*←4

P3 P3←0 P3←3 P3*←3 P3*←3

27. 有两个用户进程A和B，在运行过程中都要使用系统中的一台打印机输出计算结果。

(1)试说明A、B两进程之间存在什么样的制约关系？

答：A、B两进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用

(2)为保证这两个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。

答：mutex：用于互斥的信号量，因为只有一台打印机，所以初值为1

进程A 进程B

... ...

... ...

P(mutex)；P(mutex)；

申请打印机；申请打印机；

使用打印机；使用打印机；

V(mutex)；V(mutex)；

28. 设input进程不断向缓冲区Q写入信息，output进程不断地将刚由input进程写入的信息读出。试问：

（1）这两个进程有何相互制约关系？

（2）试用P、V操作写出这两个进程完成这项任务的代码段和信号量的含义及初值。

答：（1）这两个进程的相互制约关系为同步关系；

（2）设两个信号量S1和S2。其中S1表示Q是否为空，初值为1，表示Q是空的；S2表示Q中是

否有信息，初值为0，表示Q中无信息。

两进程的代码段如下：

input进程output进程

…… ……

While 信息未处理完毕While 信息未处理完毕

{ 加工一个信息；{ P（S2）；

P（S1）；从Q中读出一个信息；

将信息放入Q中；V（S1）；}

V（S2）；} ……

29. 假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：

(1)

（2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。

30. 在请求分页系统中，某用户的编程空间为16个页面，每页1K，分配的内存空间为8K。假定某时刻该用户的页表如下图所示，试问：

（1）逻辑地址084B（H）对应的物理地址是多少？（用十六进制表示）

（2）逻辑地址5000（十进制）对应的物理地址是多少？（用十进制表示）

（3

答：(1)104B(H)

(2)13192

(3)24A0（H）的页号为9，而其页面当前不在内存，所以会发一个缺页中断，请求系统调页。

31. 两个并发执行的进程A和B的程序如下：

进程A

Repeat

N=N+5;

Until false;

进程B

Repeat

打印N的值；

N=0；

Until false;

其中N为整数，初值为4。若进程A先执行了三个循环后，进程A和进程B又并发执行了一个循环，写出可能出现的打印值。正确的打印值应该是多少？请用P、V操作进行管理，使进程A和B并发执行时不会出现与时间有关的错误。

答：因为N初值为4，若进程A先执行了三个循环，此时N的值为19。当进程A和进程B并发执行时可能会有如下两种执行次序，即进程A先执行一次循环，然后再进程B执行一次循环，此时打印的是正确值24，执行后N中的值为0。但若进程B先执行一次循环，然后再进程A执行一次循环，则打印的值是19，执行后N中的值是5。这是错误的，即发生了与时间有关的错误。用P、V操作进行管理，使进程A和B并发时不会出现与时间有关的错误的程序如下：（S为互斥信号量，初值为1），

进程A

Repeat

P(S);

N=N+5;

V(S);

Until false;

进程B

Repeat

P(S);

打印N的值；

N=0；

V(S);

Until false;

（1）求出逻辑地址为0，100的物理地址并将其的合法性填入上表适当位置；

（2）求出逻辑地址为3，100的物理地址并将其的合法性填入上表适当位置；

答：(1)物理地址为：300+100=400(2)答：物理地址为：2000+100=2100

33.设有六个进程P1、P2、P3、P4、P5、P6,它们有如图所示的并发关系。试用P、V操作实现这些进程间的同步。

P1

P2 P3

P4 P5

P6

解： BEGIN

s1,s2,s3,s4: semaphore;

s1:=s2:=s3:=s4:=O

COBEGIN

Process P1:

Begin

do all work；

V(s1);

V(sl);

End

Process P2:

Begin

P(s1)

do all work;

V(s2);

End

Process P3:

Begin

P(s1);

do all work;

V(s3);

End

Process P4:

Begin

P(s2);

do all work;

V(s4);

End

prorcess P5:

Begin

P(s3);

do all work;

V(s4);

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 void menu(int arr[][5]) { int i,j; printf("*******进程调度：*******\n"); for(i =0;i<5;i++) { switch(i) { case 0: printf("ID:");for(j=0;j<5;j++)printf("%d ",arr[i][j]);printf("\n");break; case 1: printf("PRI :");for(j=0;j<5;j++)printf("%d ",arr[i][j]);printf("\n");break; case 2: printf("CPUTIMEL:");for(j=0;j<5;j++)printf("%d ",arr[i][j]);printf("\n");break; case 3: printf("NEADTIME:");for(j=0;j<5;j++)printf("%d ",arr[i][j]);printf("\n");break; case 4: printf("STATE :");for(j=0;j<5;j++)printf("%d ",arr[i][j]);printf("\n");break; }

操作系统经典习题+解释

●假定一个阅览室最多可容纳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.时针分针重合几次 表面上有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;

C语言经典算法100例(1---30)

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）运动会开了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。组成所有的排

操作系统课程设计(银行家算法的模拟实现)剖析.doc

操作系统课程设计 （银行家算法的模拟实现） 一、设计目的 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并行工作的

操作系统课程设计任务书

《操作系统》课程实验指导书 一、设计题目 题目一：模拟实现页式虚拟存储管理页面置换算法 题目二：模拟实现虚拟存储管理（请求分页存储管理） 题目三：模拟实现可变分区存储管理 题目四：模拟实现算法多级反馈队列进程调度算法 题目五：模拟银行家算法 二、设计目的 《操作系统》课程实验是计算机类专业的集中实践性环节之一，是学习完《操作系统》课程后进行的一次全面的综合练习。其目的在于加深对操作系统课程的理解，使学生更好地掌握操作系统的基本概念、基本原理、及基本功能，理解操作系统在计算机系统中的作用、地位和特点，具有分析实际操作系统，设计、构造和开发现代操作系统的基本能力，为今后从事的各种实际工作，如设计、分析和改进各种系统软件和应用软件提供必要的软件理论基础。 、设计内容 设计内容一页式虚拟存储管理页面置换算法 1．目的和要求 在熟练掌握计算机虚拟存储技术的原理的基础上，利用一种程序设计语言模拟实现几种置换算法，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。

2．设计内容 阅读教材《计算机操作系统》第四章，掌握存储器管理相关概念和原理。 模拟实现页式虚拟存储管理的三种页面置换算法（OPT、FIFO和LRU），并通过比较性能得出结论。 前提： （1）页面分配采用固定分配局部置换。 （2）作业的页面走向和分得的物理块数预先指定。可以从键盘输入也可以从文件读入。 （3）置换算法的置换过程输出可以在显示器上也可以存放在文件中，但必须清晰可读，便于检验。 3．设计环境 Windows操作系统、VC++6.0 C语言 4．设计提示 （1）基础知识 存储管理是操作系统进行资源管理的一个重要功能。现代操作系统广泛采用虚拟存储的技术对内存进行扩充。实现虚拟存储的一个主要技术手段就是将辅存和主存统一管理，在二者之间进行对换，从而形成物理上两级而逻辑上一级的存储管理系统。一个置换算法的好坏对这个逻辑上的单级虚存的性能起着极其重要的作用，而且会影响处理机的调度性能。 对于本任务规定的前提：页面分配采用固定分配局部置换，则置换发生的时机是作业已经将操作系统分配的固定数目的物理块全部用完且发生缺页的时候。此时必须要将已经装入内存的部分逻辑页面换出以便将所缺的页面调入内存。置换算法就是一个决定将内存中“哪一个”页面换出的算法。 （2）数据结构

操作系统经典习题

习题：1.进程同步，信号量机制实现 设有6个程序s1,…,s6，它们在并发系统中执行时如图所示的制约关系，试用wait和signal原语来实现它们之间的同步。（10分） begin parbegin beginS1;signal(a);signal(b);signal(c);end; beginwait(a);S2;signal(d);end; beginwait(b);S3;signal(f);end; beginwait(c);S4;signal(g);end; beginwait(d);S5;signal(e);end; beginwait(e);wait(f);wait(g);S6;end; parend end 2.进程同步，信号量机制实现。详见上课讲的例题 3.有如下进程，后一个依次比前一个晚一个时间单位到达，

（1）画出下列调度算法下的调度时间图：FCFS、抢占式\非抢占式SPF、抢占式\非抢占式HPF、HRRN和RR（q=1,q=2） （2）对于上述每种算法，各个作业的周转时间是多少？平均周转时间是多少？ （3）对于上述每种算法，各个作业的带权周转时间和平均带权周转时间各是多少？ 相应比=【(等待时间=现在时刻减去到达时间)+服务时间】/服务时间

4.作出页式存储管理系统中地址变换机构图。已知某作业页表如下： 02 15 29 38 试借助地址变换机构图求出逻辑地址对应的物理地址（1页为1024字节） (1)2968（2）4599（3）0FCCH 解：分析逻辑地址除以页面大小=商是页号：余数是页内地址偏移 根据页号查找页表中的页号判断是（缺页中断，越界中断...）

C语言经典算法题目及答案

题目：有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) 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) bonus=i*0.1; else if(i<=200000) bonus=bonus1+(i-100000)*0.075; else if(i<=400000) bonus=bonus2+(i-200000)*0.05; else if(i<=600000) bonus=bonus4+(i-400000)*0.03;

操作系统(一个小型操作系统的设计与实现)课程设计

南通大学计算机科学与技术学院操作系统课程设计报告 专业： 学生姓名： 学号： 时间：

操作系统模拟算法课程设计报告 设计要求 将本学期三次的实验集成实现： A.处理机管理； B.存储器管理； C.虚拟存储器的缺页调度。 设计流程图 主流程图 开始的图形界面 处理机管理存储器管理缺页调度 先来先服务时 间 片 轮 转 首 次 适 应 法 最 佳 适 应 法 先 进 先 出 L R U 算 法

A.处理机调度 1)先来先服务FCFS N Y 先来先服务算法流程 开始 初始化进程控制块，让进程控制块按进程到达先后顺序让进程排队 调度数组中首个进程，并让数组中的下一位移到首位 计算并打印进程的完成时刻、周转时间、带权周转时间 其中：周转时间 = 完成时间 - 到达时间 带权周转时间=周转时间/服务时间 更改计时器的当前时间,即下一刻进程的开始时间 当前时间=前一进程的完成时间+其服务时间 数组为空 结束

2)时间片轮转法 开始 输入进程总数 指针所指的进程是 否结束 输入各进程信息 输出为就绪状态的进程的信息 更改正在运行的进程的已运行时间 跳过已结束的程序 结束 N 指向下一个进程 Y 如果存在下一个进程的话 Y N 输出此时为就绪状态的进程的信息 时间片轮转算法流程图

B.存储器管理(可变式分区管理） 1)首次适应法 分配流程图 申请xkb内存 由链头找到第一个空闲区 分区大小≥xkb？ 大于 分区大小=分区大小-xkb，修改下一个空闲区的后向指针内容为（后向指针）+xkb;修改上一个空闲区的前向指针为（前向指针）+xkb 将该空闲区从链中摘除：修改下一个空闲区的后向地址=该空闲区后向地址，修改上一个空闲区的前向指针为该空闲区的前向指针 等于 小于延链查找下 一个空闲区 到链尾 了？ 作业等待 返回是 否 登记已分配表 返回分配给进程的内存首地址 开始

操作系统原理计算题及答案

一、某系统对主存采用页式管理，供用户使用的主存区域共640K字节，被分成160块，块号为0,1,2……159。现有一作业的地址空间共占4页，其页号为0,1,2,,3，被分配到主存的第2，4，1，5块中，回答： (1)作业每一页的长度为多少字节？ 4K (2)写出该作业被装入主存时，其对应的页表。 逻辑页号主存块号 0 2 1 4 2 1 3 5 (3)把该作业的每一页在主存中的起始地址(用16进制表示)填在下表中 页号起始地址 1 2 3 二、两个并发进程的程序如下： begin N:integer; N:=1; cobegin process A begin L1:N:=N+1; go to L1; end; process B begin L2:print(N); N:=0; go to L2; end; coend; end; 请回答： (1)指出这两个并发进程的临界区。 进程A的临界区：N:=N+1 进程B的临界区: N:=0

(2)指出它们并发执行时可能出现的“与时间有关的错误”。 进程B执行了print（N）后被中断；在执行N：＝0之前插入了进程A执行N：＝N+1，则出现“与时间有关的错误”。 (3)用PV操作进行管理，写出使它们能正确并发执行的程序。 begin N:=integer； N：＝1； s:＝semaphore；s:=1 cobegin process A begin L1:p（s）； n:=N+1； V（s）； go to L1； end； process B begin L2：p（s）； end； Print（N）； coend； N：＝0； end； V（s）； go to L2 三．桌子有一个盘子，每次只能放入一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子，女儿专等吃盘中的苹果，儿子专等吃盘中的桔子，试用P，V操作写出他们能正确同步的并发过程。答案： 解：设公用信号量S=1表示盘子，私用信号量S1=0表示苹果，私用信号量S2=0表示桔子。他们能正确同步的并发过程如下： 爸爸P1 妈妈P2 女儿P3 儿子P4 P(S) P(S) P(S1) P(S2) 放苹果放桔子取苹果取桔子 V(S1) V(S2) V(S) V(S) 四.假定一个阅览室可供50个人同时阅读。读者进入和离开阅览室时都必须在阅览室入口处的一个登记表上登记，阅览室有50个座位，规定每次只允许一个人登记或注销登记。 要求：（1）用PV操作描述读者进程的实现算法（可用流程图表示，登记、注销可用自然语言描述）； （2）指出算法中所用信号量的名称、作用及初值。

C语言经典算法题目及答案

盛年不重来，一日难再晨。及时宜自勉，岁月不待人。 题目：有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) 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) bonus=i*0.1; else if(i<=200000) bonus=bonus1+(i-100000)*0.075; else if(i<=400000) bonus=bonus2+(i-200000)*0.05; else if(i<=600000)