下载文档原格式
操作系统-进程的调度算法操作系统 - 进程的调度算法先到先服务(FCFS)调度算法 : 从就绪队列中选择⼀个最先进⼊该队列的进程为之分配资源，使它⽴即执⾏并⼀直执⾏到完成或发⽣某事件⽽被阻塞放弃占⽤ CPU 时再重新调度。
短作业优先(SJF)的调度算法 : 从就绪队列中选出⼀个估计运⾏时间最短的进程为之分配资源，使它⽴即执⾏并⼀直执⾏到完成或发⽣某事件⽽被阻塞放弃占⽤ CPU 时再重新调度。
时间⽚轮转调度算法 : 时间⽚轮转调度是⼀种最古⽼，最简单，最公平且使⽤最⼴的算法，⼜称 RR(Round robin)调度。
每个进程被分配⼀个时间段，称作它的时间⽚，即该进程允许运⾏的时间。
多级反馈队列调度算法：前⾯介绍的⼏种进程调度的算法都有⼀定的局限性。
如短进程优先的调度算法，仅照顾了短进程⽽忽略了长进程。
多级反馈队列调度算法既能使⾼优先级的作业得到响应⼜能使短作业（进程）迅速完成。
，因⽽它是⽬前被公认的⼀种较好的进程调度算法，UNIX 操作系统采取的便是这种调度算法。
原理：1、设有N个队列（Q1,Q2....QN），其中各个队列对于的是不⼀样的，也就是说位于各个队列中的作业(进程)的优先级也是不⼀样的。
⼀般来说，优先级Priority(Q1) > Priority(Q2) > ... > Priority(QN)。
怎么讲，位于Q1中的任何⼀个作业(进程)都要⽐Q2中的任何⼀个作业(进程)相对于CPU的优先级要⾼（也就是说，Q1中的作业⼀定要⽐Q2中的作业先被），依次类推其它的队列。
2、对于优先级最低的队列来说，⾥⾯是遵循法。
也就是说，位于队列QN中有M个作业，它们的运⾏时间是通过QN这个队列所设定的来确定的；对于其他队列，遵循的是先来先服务算法，每⼀进程分配⼀定的时间⽚，若时间⽚运⾏完时进程未结束，则进⼊下⼀优先级队列的末尾。
3、各个队列的时间⽚是⼀样的吗？不⼀样，这就是该算法设计的精妙之处。
《计算机系统结构》练习测试题库参考答案一、填空题1．仿真，模拟2．并发、同时3．SIMD，MISD4．低，高、5．系统、体系6.空间代价关联7. 寻址方式指令系统8．系统性能，9. CPU时钟周期数，时钟周期10.数据驱动需求驱动11．一次性开发成本每个部件的生产成本12．操作码地址码13．定长操作码、Huffman编码14．程序的存储量程序的执行速度15．程序的指令条数每条指令执行的平均周期数16．功能部件级处理机级17．译码执行18．超标量处理机超流水线处理机执行程序速度19．基于寄存器-寄存器的向量指令基于存储器-存储器的向量指令20．存储器—存储器结构寄存器—寄存器结构21．参加运算操作的向量向量寄存器22．参加运算操作的向量存储器23．两条功能部件流水线一条功能较强的流水线24．向量指令的处理时间向量长度为无穷量处理机的最大性能25．访问时间存储周期26．高速缓冲存储器主存储器27．读操作数冲突读写冲突28．地址码的高位交叉编址地址码的低位交叉编址29．主存按段分配的存储管理方式段表30．分页式请求页式31．计数器法比较对法32．主存周期 Cache周期33．写直达法写回法34．函数表示法图形表示法35．网格网络环形网络36．阻塞网可重排非阻塞网37．单元控制方式终端标记38．线路交换包交换39．单播模式选播模式广播模式40．不应出现死锁循环等待二、单项选择题1、B2、C3、A4、C5、A6、B7、C8、A9、B 0、C 11、B 12、C 13、B 14、A 15、A 16、A 17、A 18、C 19、A 20、B 21、A 22、C 23、B 24、B 25、A 26、B 27、A 28、A 29、B 30、C 31、A 32、C 33、A 34、B 35、B 36、B 37、A 38、B 39、A 40、B三、判断1、错2、对3、错4、对5、对6、错7、对8、对9、对 10、错 11、对 12、对 13、对 14、对 15、对 16、对 17、对 18、对 19、对 20、对 21、对 22、对 23、错 24、错 25、错 26、错 27、错 28、错 29、错 30、错 31、错 32、错 33、错 34、错 35、对 36、对 37、对 38、对 39、对 40、对四、名词解释1、计算机系统结构定义为由程序设计者所看到的一个计算机系统的属性，即概念性结构和功能特性，这里的程序设计者所看到的计算机属性是指为机器语言或编译程序设计者所看到的计算机属性，是硬件子系统的概念性结构及其功能特性，它是计算机系统的软、硬件的界面。
计算程序运⾏时间的⽅法转⾃：1这个是windows⾥⾯常⽤来计算程序运⾏时间的函数；DWORD dwStart = GetTickCount();//这⾥运⾏你的程序代码DWORD dwEnd = GetTickCount();则(dwEnd-dwStart)就是你的程序运⾏时间, 以毫秒为单位这个函数只精确到55ms，1个tick就是55ms。
1 #include <iostream>2 #include <windows.h>3using namespace std;4int main(int argc, char* argv[])5 {6 DWORD start, end;78 start = GetTickCount();9for(int i=0;i<1000;i++)10 cout<<"you are a good child!"<<endl; //your code11 end = GetTickCount()-start;12 cout<<end<<endl;13return0;14 }2timeGetTime()基本等于GetTickCount()，但是精度更⾼1 DWORD dwStart = timeGetTime();23//这⾥运⾏你的程序代码45 DWORD dwEnd = timeGetTime();则(dwEnd-dwStart)就是你的程序运⾏时间, 以毫秒为单位虽然返回的值单位应该是ms,但传说精度只有10ms。
1 #include <iostream>2 #include <windows.h>3#pragma comment(lib,"winmm.lib")45using namespace std;6int main(int argc, char* argv[])7 {8 DWORD start, end;910 start = timeGetTime();11for(int i=0;i<100;i++)12 cout<<"you are a good child!"<<endl;13 end = timeGetTime()-start;14 cout<<end<<endl;15return0;16 }3⽤clock()函数，得到系统启动以后的毫秒级时间，然后除以CLOCKS_PER_SEC，就可以换成“秒”，标准c函数。
CH1 应用题参考答案1有一台计算机，具有1MB内存，操作系统占用200KB，每个用户进程各占200KB。
如果用户进程等待I/O的时间为80%，若增加1MB内存，则CPU的利用率提高多少？答：设每个进程等待I/O的百分比为P，则n个进程同时等待I/O的概率是P n ，当n个进程同时等待I/O期间CPU是空闲的，故CPU的利用率为1-P n 。
由题意可知，除去操作系统，内存还能容纳4个用户进程，由于每个用户进程等待I/O的时间为80%，故：CPU利用率=1-(80%)4 =0.59若再增加1MB内存，系统中可同时运行9个用户进程，此时：CPU利用率=1-(80%)9 =0.87故增加1MB内存使CPU的利用率提高了47%：87%÷59%=147%147%-100%=47%2一个计算机系统，有一台输入机和一台打印机，现有两道程序投入运行，且程序A 先开始做，程序B后开始运行。
程序A的运行轨迹为：计算50ms、打印100ms、再计算50ms、打印100ms，结束。
程序B的运行轨迹为：计算50ms、输入80ms、再计算100ms，结束。
试说明(1)两道程序运行时，CPU有无空闲等待？若有，在哪段时间内等待？为什么会等待？(2)程序A、B有无等待CPU的情况？若有，指出发生等待的时刻。
答：画出两道程序并发执行图如下：(1)(见图中有色部分)。
(2)程序A无等待现象，但程序B有等待。
程序B有等待时间段为180ms至200ms间(见图中有色部分)。
3设有三道程序，按A、B、C优先次序运行，其内部计算和I/O操作时间由图给出。
A B CC11＝30ms C21=60ms C31=20ms∣∣∣I12＝40ms I22=30ms I32=40ms∣∣∣C13＝10ms C23=10ms C33=20ms 试画出按多道运行的时间关系图（忽略调度执行时间）。
完成三道程序共花多少时间？比单道运行节省了多少时间？若处理器调度程序每次进行程序转换化时1ms，试画出各程序状态转换的时间关系图。
应用题1.假定在单CPU条件下有下列要执行的作业：作业到来的时间是按作业编号顺序进行的（即后面的作业依次比前一个作业迟到一个时间单位）（1）用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。
（2）对于上述算法，求各个作业的周转时间、带权周转时间？并求出平均周转时间以及平均带权周转时间是多少？答：（1）作业1 作业3 作业21 11 14 18（2）周转时间：作业1：10 作业2：16 作业3：11平均周转时间：（10＋16＋11）/3＝37/3带权周转时间：作业1：1 作业2：4 作业3：11/3平均带权周转时间：26/9上述题目也可这样求：平均周转时间为：（10+11+16）/3=37/3=12.3平均带权周转时间为：(1+11/3+4)/3=26/9=2.89若将该题改为短作业优先（非抢占式）结果一样。
2.假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：（2）如果应用最短作业优先的作业调度算法，试将下面表格填写实际执行序列为：1 3 2 5 43.有4个进程P1、P2、P3、P4，它们进入系统的时刻和要求的运行（1）画图分别说明，系统采用先来先服务和短进程优先调度算法（非抢占式）时，它们的执行情况。
（2）分别计算上述两种情况下进程的平均周转时间和平均带权周转时间。
(2)平均周转时间为：FCFS（3+7.999+8.999+8.999）/4=28.997/4=7.25 SPF: （3+7.999+4.999+10.999）/4=26.997/4=6.7平均带权周转时间：FCFS（1+7.999/6+8.999/4+8.999/2）/4=9/4=2.25 SPF: （1+7.999/6+4.999/2+10.999/4）/4=5.25/4=1.34.假定系统中有4个进程P1、P2、P3、P4和3类资源R1、R2、R3（资源数量分别为9、3、6），在t0时刻的资源分配情况如下表所示。
第1章绪论5．选择题：CCBDCA6．试分析下面各程序段的时间复杂度。
（1)O（1）（2）O(m＊n）（3）O（n2）（4)O（log3n）（5)因为x++共执行了n—1+n—2+……＋1= n(n—1)/2，所以执行时间为O(n2)（6）O(n）第2章线性表1．选择题babadbcabdcddac2．算法设计题(6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。
ElemType Max （LinkList L ）｛if(L—〉next==NULL) return NULL；pmax=L-〉next；//假定第一个结点中数据具有最大值p=L-〉next—>next；while(p ！= NULL ){//如果下一个结点存在if（p->data > pmax—>data) pmax=p；p=p->next；｝return pmax-〉data;（7)设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间.void inverse(LinkList ＆L) ｛// 逆置带头结点的单链表Lp=L-〉next；L->next=NULL；while （p）｛q=p—>next；// q指向＊p的后继p->next=L—>next;L—>next=p; // *p插入在头结点之后p = q;｝}（10)已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O（1）的算法，该算法删除线性表中所有值为item的数据元素.［题目分析］在顺序存储的线性表上删除元素,通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移)。
本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。
因此可以考虑设头尾两个指针（i=1，j=n）,从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。
计算算法的运⾏时间算法的不同会导致其运⾏时间产⽣⼤幅变化。
使⽤相同的算法，输⼊数据的量不同，运⾏时间也会不同。
⽐如，对10 个数字排序和对1 000 000 个数字排序，很容易就想到后者的运⾏时间更长。
那么，实际上运⾏时间会长多少呢？后者是前者的100 倍，还是1 000 000 倍？就像这样，我们不光要理解不同算法在运⾏时间上的区别，还要了解根据输⼊数据量的⼤⼩，算法的运⾏时间具体会产⽣多⼤的变化。
我们使⽤“步数”来描述运⾏时间。
“1 步”就是计算的基本单位。
通过测试“计算从开始到结束总共执⾏了多少步”来求得算法的运⾏时间。
作为⽰例，现在我们试着从理论层⾯求出选择排序的运⾏时间。
选择排序的步骤如下。
①从数列中寻找最⼩值②将最⼩值和数列最左边的数字进⾏交换，排序结束。
回到①如果数列中有n 个数字，那么①中“寻找最⼩值”的步骤只需确认n 个数字即可。
这⾥，将“确认1 个数字的⼤⼩”作为操作的基本单位，需要的时间设为T c，那么步骤①的运⾏时间就是n×T c。
接下来，把“对两个数字进⾏交换”也作为操作的基本单位，需要的时间设为T s。
那么，①和②总共重复n 次，每经过“1 轮”，需要查找的数字就减少1 个，因此总的运⾏时间如下。
虽说只剩最后1 个数字的时候就不需要确认了，但是⽅便起见还是把对它的确认和交换时间计算在内⽐较好。
虽说我们已经求得了运⾏时间，但其实这个结果还可以简化。
Tc 和Ts 都是基本单位，与输⼊⽆关。
会根据输⼊变化⽽变化的只有数列的长度n，所以接下来考虑n 变⼤的情况。
n 越⼤，上式中的n2也就越⼤，其他部分就相对变⼩了。
也就是说，对式⼦影响最⼤的是n2。
所以，我们删掉其他部分，将结果表⽰成下式右边的形式。
通过这种表⽰⽅法，我们就能⼤致了解到排序算法的运⾏时间与输⼊数据量n 的平⽅成正⽐。
同样地，假设某个算法的运⾏时间如下。
那么，这个结果就可以⽤O(n3) 来表⽰。
如果运⾏时间为这个结果就可以⽤O(nlogn) 来表⽰。
算法导论习题解答2.3-7
•2.3-7 请给出⼀个运⾏为Θ(nlgn)的算法（伪码），使之能在给定⼀个由n个整数构成的集合S和另⼀个整数x时，判断出S中是否存在有两个其和等于x的元素。
解：解题思路：先对集合S进⾏归并排序，然后新建⼀个数组S1，使得S1[i] = x – S[i]，再将两个数组并起来。
如果在并的过程中发现有两个元素相等且两个元素⼀个来⾃S，⼀个来⾃S1，则可以确定S中存在有两个其和等于x的元素。
Find whether x exits
1、Sort(S)
2、for i <- 0 to Length(S) – 1
3、 do S1[i] <- x - S[i]
4、for i <- 0 to Length(S) – 1
5、 do Merge( S,S1 )
6、 if S[p] > S1[q]
7、 S0[k] <- S[p] p++ k++
8、 if S[p] < S1[q]
9、 S0[k] <- S[q] q++ k++
10、 if S[p] == S1[q]
11、 return true
12、return false
在第⼀⾏进⾏排序时，时间代价为Θ(nlgn)，后来的合并过程时间代价为Θ(n)，总的时间代价为Θ(nlgn)。
编译期、运⾏期与常量在Delphi中，有两种常量：⼀种是普通常量（Ordinary Constants），另⼀种是有类型常量（Typed Constants）。
但我个⼈更喜欢根据它们的特点，把它们称作编译期常量（Compile-time Constants）与运⾏期常量（Run-time Constants），因为这种叫法最能体现它们的本质，⽽前⾯的叫法可能会产⽣歧义（为什么这么说我会在本⽂后⾯说明）。
那么，什么是编译期（Compile-time）和运⾏期（Run-time）呢？字⾯上来看，编译期（编译时）就是当程序编译的时候，此时还没形成完整的程序代码，⼀些信息都由编译器掌握；⽽运⾏期（运⾏时）则是程序已经完全形成，并得到了运⾏，在程序执⾏的时期。
其实，运⾏期这个词是⾮常常见的，Delphi的原代码⽬录中，有⼀个RTL⽬录，编译出来的Delphi程序的最底层的代码都在rtl\sys⽬录下，这个RTL是运⾏时库（Rum-Time Library）的缩写。
著名的VCL架构能够在设计设置控件属性、当程序运⾏时恢复属性值，这些得都益于RTTI，即运⾏时类型信息（Run-Time Type Information）。
从字⾯上解释这两个概念是挺头疼的，下⾯还是⽤常量的例⼦来说明吧。
在Delphi中，常量的声明，是在程序的合法的 const 段中，采⽤以下两种形式之⼀声明：identifier = expression;identifier : type = expression;前⾯的形式1声明了⼀个编译期常量，⽽后者则是运⾏期常量的声明。
两者相同的地⽅是，等号右边都是⼀个表达式，⽽且需要注意的是，这⾥的表达式必须在链接期（Link-time）之前就能确定值。
BTW，这⾥的形式2写的稍微简单了些，由于运⾏期常量的类型还可以是数组、结构等，⽽数组、结构常量的等号后并不是⼀个简单的表达式，但复合的数据表⽰中，每个基本元素仍然还是这种能确定值的表达式。
matlab程序运行时间计算方法在matlab中，为了验证比较两个算法直接的效率，我们常常需要计算某段程序的运行时间，而常用的也就是三种方法：1、tic和toc命令对；格式如下面一段程序。
tic;a=0;for i1=1:100000for j1=1:10000a=a+1;endendtoc;tic命令表示开启一个matlab的计时器，toc则表示停止之前与之对应的tic开启的计时器，并得到最后的计时结果，上一段程序结果如下：Elapsed time is 3.720372 seconds.2、clock加etime函数；程序结构如下面一段。
t1=clock;b=0;for i2=1:100000for j2=1:10000b=b+1;endendt2=clock;etime(t2,t1)其中，clock命令是获取系统的时间矢量，而etime函数则是计算两个时间矢量之间的差并以秒单位形式表示。
clock作为时间矢量包含了年月日时分秒六个参数，如在matlab单独执行这一命令可得到：>> clockans =1.0e+003 *2.0120 0.0080 0.0180 0.0140 0.0180 0.05073、cputime命令计算运行时间；m1=cputime;c=0;for i3=1:100000for j3=1:10000c=c+1;endendm2=cputime;m=m2-m1cputime命令是获取matlab自启动后所占用cpu的运行时间，这里需要详细介绍下，cputime不是代表matlab的运行时间，而是指matlab占用cpu的时间。
大家知道，window 系统的多进程管理类似于我们所说的时分复用概念，即cpu完成多进程是通过时间划分来实现的，这一时刻运行的是进程一，下一时刻运行的是进程二，由于速度非常快，所以对于用户来说看起来就是同时运行的。
我们可以做个试验，在一打开matlab的时候，执行cputime 命令得到：>> cputimeans =13.1197说明我们matlab打开用了13秒多的时间，大家可以自我感觉下是不是这个时间。
