| 1 |
1月9日 OS
|
|
OS考前复习
1.用户可以使用系统调用创建和销毁进程。
2.无软件 →驻地监察→单元编程→多元编程。
3.系统调用，让用户级进程，以reguest服务的操作系统。
4.
•单片OS是通常难以修改。 （ √ ）
•微内核，使某些系统服务得以应用，如用户程序。 （ √ ）
•虚拟机改善OS开发及测试进程。 （ √ ）
•分层OS比单片操作系统更有效率。 （ × ）
5.进程是动态的一个过程。多进程可能同时执行，但并不是由同一套指令配置。
6.进程调度不需要硬件支持。
7.进程和程序的不同。（前者有状态，后者无。）
8.一个进程从运行状态到准备状态时，其时距完工（time slice is finished.）。
9.不会发生的情况：从等待状态→运行状态。
10.如果等待事件发生，该进程变为准备状态。
11.消息传递系统（概念） ：共享数据，允许进程相互沟通，而不需要诉诸（resort）。
12.rendezvous 汇合、同步：发出者阻塞（blocking）AND接收者阻塞。区别：无阻塞与阻塞
13.该线程的一个单一的进程不能共享：堆栈。
14.对于多对一模式，如果一个线程在单进程发生阻塞，那么整个进程将会受阻（be blocked ）。
15.挑选一个好的进程，将混合输入/输出方向和CPU方向的进程混合，是不正确的。
16.假设RR调度的时间量是固定的话，那么用户数会更多。
17.
window 3.x 非剥夺式的调度
DS 6.0 单进程，无调度
window2000 剥夺式的调度
18.四个必要的死锁条件是hold and wait持有和等待, mutual exclusion互斥条件, no preemption不可抢占, circular wait存在循环.
19.银行家算法是为避免死锁。
****************************
20.下列哪一种方法能够防止死锁发生？ （C）
A 银行家算法
B 死锁检测
C 资源配置Resource allocation in an increasing order of enumeration.
D 简化资源图。
|
|
|
|
|
| |
| 2 |
回复：1月9日 OS
|
|
21.一个系统有3个并发进程，其中每个需要4个项目的资源r什么是最低人数的资源R的，以避免死锁。 （B）
A. 9 B. 10 C. 11 D. 12
22.并行进程之间的关系___ （D）
A 是相互独立的
B 是同步的
C 是相互排斥的。
D 可能需要同步的和/或相互的。
23.下列哪一项是正确的？ （D）
A 信号（semaphore）比监测（monitor）更为有力
B ……和上面反过来
C 临界区（critical region）比信号更为有力
D 这三者一样
24.临界区（critical section）为进程同步的是（D）
A 一个缓冲区
B 一个数据段
C 同步机制
D 一段代码
25.该信号可以用来解决__互斥问题（C）
A 一个
B 有些
C 所有
D 大部分的
26.信号变量互斥是用两个并行进程互斥进入一个共同的变数。如果互斥= 0 ，那么，它表明… …. ↓
不准等候，如果互斥=- 1 ，有等待
27.一个共同的数据，可以允许最多3条进程共享，同时，现在假定五条进程试图访问它，为保护这一数据，请选择初始值为信号量[3]。（B）
A. 5 B.3 C.1 D. 0
28.9个持有者和6个用户共享一个最大容量为8个项目公共的缓冲器。请选择初始值为信号量[1]，以确保互斥性。（A）
A.1 B.6 C.8 D. 9
29.动态迁移依赖于____ （A）
A. a relocation（迁移） B. object code（对象代码……？）
C. address translation（地址转换） D. relocation program（迁移计划）
30.哪一种方法将彻底解决抖动（thrashing）问题？ （D）
A 放入快速磁盘
B 添加更多磁盘
C 放入快速记忆体
D 添加更多的内存（add more memory）
31.哪一种方法，解决了外部碎片（external fragmentation）问题？ （A）
A. paging （分页）
B. segmentation
C. contiguous memory allocation
D. snapping
32.缺页出现后应该实行（B）
A. the instruction just before interruption.（中断之前的那条指令）
B. the instruction caused interruption.（引起中断的那条指令）
C. the instruction just after interruption.（中断之后的那条指令）
D. the first instruction of this process.（整个进程的第一条指令）
33.虚拟内存管理的根本依据是（B）
A. virtually B. locality（位置，现场）
C. globally D. dynamics
|
|
|
|
|
| |
| 3 |
回复：1月9日 OS
|
|
**********SAKURAドロップス(樱花翩翩)**********
62.以下哪一个页面置换算法可以产生belady的现象吗？A
A FIFU B LRU(最近最少使用算法)
B B呢？？？= =
C DPT算法
D Second-chance algorithm(第二机会算法)
63.以下哪个因素页面size较大？A
A interval fragmentation(碎片空隙)
B to improve locality（位置改良）
C the time to read/write a page （页面读写时间）
D prepaging （…）
64.在请求页面调度中，A有最佳的系统性能
A stacks 1 [堆栈]
B lists 3
C hashed tables 4
D arrays 2
********Asian Blue - 月亮畅泳于海上**********
65.在分页内存管理中，分页一般的做法是D
A programmer B user C compiler(编译器) D hardware硬件
66.With页面调度的要求，[C]具有最糟糕的系统性能
A 栈
B 列表
C hashed tables 散列表[混乱表格？？]
D 二维阵列
67.具有64位逻辑地址空间的系统，以下哪个页表结构是适宜的[]****************请寻找答案//
A first fit
B best fit
C worst fit
D fixed equal-sized partitions
68.下列哪一项与分段存储不相关？[B]
A two dimensional(空间) view of memory
B fixed(固定) size
C easy sharing of data or code
D external (外部) fragmentation(碎片)
78.The files on a tape can be read/write D
A in bytes B in words C via(通过) direct(直接) access D via sequential access(顺序存取)
//磁带是顺序存储器来的
79.磁盘文件[C]
A accessed sequentially (继续的)only
B accessed randomly(随意的) only
C accessed both sequentially and randomly[A+B，连续+随机]
D accessed in terms of words
80.为了解决名称冲突，档案系统通常采用[B]
A 路径
B 树般的目录结构
C 索引
D 常规的命名
***********霜钟余响*********
81.一个文件应该[B]，在存取（accessed）之前。
A named B opened C established D backed up
82.which文件配置不容许高效直接存储（随机存取）[B]
A contiguous(邻近的) allocation(分配)
B linked allocation 挂钩分配
C Indexed allocation 索引分配
D hashed allocation 散列分配
83.[A]可用于文件存取的保护
A FCB(格式控制缓冲区)
B ACL
C JCB(作业控制块)
D PCB
94.下列哪种交换空间是最快的？[D]
A a swap file an FAT
B a swap file on ext3
C a partition with sophisticated file system functions
D a raw partition （…原始分割？）
95.[C]可直接进入。
A a tape
B a terminal(终端)
C a hard disk（硬盘）
D ..
96.unix对待I / O设备的方法是[D]
A regular files 定期档案
B directory files 目录文件
C indexed files 索引文件
D special files 特殊档案
97.操作系统的死锁意味着[D]
A A program is looping forever（程序死循环）
B hardware malfunctions(故障)
C system halts （系统停止）
D processes block and wait for each other to finish（进程阻塞并等待完成）
98.哪种提供廉价的高可靠性？[D]
A RAID0
B RAID1
…..
D RAID5
99.以下哪种储存设备不是第三的（tertiary）存储结构？[C]
A CD-ROM B DVD C Hard disk（硬盘） D Tapes
100.UNIX创建文件的系统调用是：[A]
A creat B open C create D new
|
|
|
|
|
| |
| 4 |
回复：1月9日 OS
|
|
**********荒魂**********
在Linux的中，更名文件用fork fstat不会移动文件。The shell is simply[A]
A command-time interpreter(解释程序)
线程的一个单一的进程不能分享[C]
A 代码
B 档案
C 栈
D 优先权
操作系统管理进程使用[B]
(A)JCB (B)PCB (C)PCT (D)CHCT
哪一种方法，将彻底解决抖动问题...加内存加内存！
A 增加快速磁盘B 增加更多的磁盘
C 增加快速记忆体D 添加更多的内存
哪一种方法解决externed碎片的问题[A]
A 分页paging
B 分割
C 连续内存分配
D 交换
缺页后直接执行B 造成中断的指示。= =MS我才整理过呢
fandamental基础上的虚拟内存管理是[B]
A)virtuality (B)locality （位置）
(C)globality (D)dynamic
下列哪种页面替换dgorithms能产生Belady’s phenmmena [A]
A 先进先出FIFO
B LBU
C OPT
D Second-chance dgorithm
下列哪一项因素宁愿较大的页面大小？[B]to improve locality
With the demand paging，[A]栈 has最佳系统性能。
With paging management（页面管理），paging通常是由[D] 硬件 完成。
With the demand（要求）paging,______有最坏的系统性能C 散列表hashed table
系统具有64位逻辑地址空间，哪一页表结构是不恰当的？7-level page table
对于连续的内存分配，让其最好的执行的策略？ (A)First fit第一匹配
**********[再见！故宫]Future Memories*******
下列哪一项与段（segments）不相关？[B]
(A)Two dimensional view of memory
(B)Fixed size（固定大小）
(C)Easy sharing of data or code
(D)Externed fragmentation
Segment Base Length
0 210 600
1 2300 14
2 90 100
3 1327 580
4 1950 90
逻辑地址(1,430)的物理地址是？[C]
(A)illegal address非法地址
(B)430
(C)640
(D)1030
逻辑地址(2,110)的物理地址是？[A]
(A)非法地址
(B)110
(C)200
(D)210
LRU更换，将带来____page faults（缺页）
(A)7 (B)8 (C)9 (D)10
If one access out of 1000 causes a page fault; 有效访问时间将是 _____ns。[A]
A 2500 B 25000 C 125000 D 100000
如果有效访问时间是105ns ，那么我们只可以让很少的内存 存取出_____to page fault
A 250000 B 2500000 C 5000000 D 10000000
对于多对一模式，如果一个线程只有一个单一的blocking进程，then_____
B 整个进程将受阻（The whole process will be blocked）
*******04-Moonlight (BackingTrack)*******
Which of the following is incorrect[错误] for the CPU long-term scheduler[长期..程序机？] (B)It runs as often as short-term scheduler
Suppose the time quantum for RR scheduling is fixed[假设RR的时间量固定] , the _____the longer the response[应答] time (B)the more users
Which of the following operating system use preemptive[先买..] scheduling? (C)Windows 2000
One of the problems with priority scheduling[优先权调度]? (B)Starvation[饿死]
Which of the following scheduling is most flexible（自由度）? (B)multilevel[多级] feed back queue[等候] scheduling[调度]
The four necessary deadlock------------------
The banker’s algorithm is for ----deadlock avoidance[预防]
______can be accessed directly (C)a hard disk
Which kind of swap space is fastest? (D)A raw partition
Which disk space allocation[配置] method[方法] supports direct access without external fragmentation[外部碎片]?---Indexed allocation[索引配置]
UNIX treats I/O device use------- *special files
For operating systems deadlock means _______ (D)processes block and wait for each other to finish
Which provides high reliability inexperiencely? RAID5
Which of the following storage derice is not tortiary? (C)Hard disk
The semaphores can be used to solve ___multual exclusive problems (C)all the
The files on a tape can be read/write______ (D)via sequential access
The files on hard disk can be access--- both sequentially and randomly
In order to solve name collosion, the file system normally adopts_____ (B)tree-link
A file should be ___before it is accessed (B)opened
Which file allocation doesn’t allow direct access efficiently? (B)linked allocation
In order to protect file access, the ____can be used (A)FCB
Which allows supporting multiple file systems? (C)VFS
The cache id usually implementied by _____ (A)registers
One purpose of the buffering technique used to _____ (C)improve I/O device affection
|
|
|
|
|
| |
| 6 |
回复：1月9日 OS
|
|
第六章 CPU 调度
更新时间：2004-10-8
CPU 调度是多道程序操作系统的基础。通过在进程间转换CPU，操作系统可以提高计算机的生产力。在本章，我们要介绍基本的调度概念并例举几种同的CPU 调度算法。我们还要讨论为特定的系统选择调度算法的问题。
6.1 基本概念
为了最大限度的提高CPU 利用率，多道程序设计的目标是保持总是有进程可供执行。在单处理机系统中，一次只能运行一个进程；其它的任何进程都必须等到CPU 空闲时才能够被重新调度。
多道程序设计的思想十分简单。一个进程持续运行直到它必须等待某些操作（I/O 请求是个典型）的完成。在简单的计算机系统中，进程等待时CPU 将处于空闲状态；这浪费了所有的等待时间。利用多道程序设计，我们可以有效地利用这段时间。在内存中同时保留多个进程。当一个进程必须等待时，操作系统将CPU 撤离该进程并把CPU 分配给另一个进程。然后以这种方式继续运行。
调度是一个基本的操作系统功能。几乎所有的计算机资源在使用前都需要调度。当然了，CPU 是首要的计算机资源之一。因此CPU 调度是操作系统设计的核心问题。
6.1.1 CPU-I/O Burst 周期
CPU 调度依赖于进程的这一特性：进程执行包含了CPU 执行周期（cycle）和I/O 等待时间。进程在这两个状态之间交替转换。进程执行开始于一个CPU burst。随后是一个I/O burst，然后是另一个CPU burst，再是一个I/O burst，等等。最终，最后的CPU burst 以一个终止执行的系统请求结束，而不是一个I/O burst（图6.1）。
可以测量CPU burst 的持续时间。虽然对进程和计算机来说它们的差异很大，但是它们趋向于图6.2 所示的频率曲线。由于短的CPU burst 很多长的很少，所以这条曲线通常被表现为指数分布或超指数分布的形式。一个I/O 繁忙型程序通常有很多非常短的CPU burst。一个CPU 繁忙型程序可能有少数非常长的CPU burst。这种分布（distribution）能够帮助我们选择一个合适的CPU 调度算法。
Figure 6.1 Alternating sequence of CPU and I/O bursts.
Figure 6.2 Histogram of CPU-burst times.
6.1.2 CPU 调度程序
只要CPU 空闲，操作系统就必须从就绪队列中选择一个进程执行。进程的选择由短程调度程序（或CPU 调度程序）完成。调度程序从内存中的就绪进程中做出选择，并将CPU 分配给其中之一（调度程序选择的进程）。
就绪队列没有必要是一个先进先出（FIFO）队列。正如在稍后讨论各种调度算法时所见，可以把就绪队列实现为FIFO 队列、优先队列、树或者仅仅是个无序链表（unordered linked list）。然而从概念上讲，就绪队列中的所有进程排队等待获取CPU 执行的机会。队列中的记录通常是进程的进程控制块（PCB）。
|
|
|
|
|
| |
| 7 |
回复：1月9日 OS
|
|
6.1.3 抢占式调度
在如下的四种情况下可能会进行CPU 调度：
1.
当进程从运行状态转换到等待状态时（例如：I/O 请求或等待一个子进程的终止）（for example, I/O request, or invocation of wait for the termination of one of the child processes ）
2.
当进程从运行状态转换到就绪状态时（例如：当发生中断时）
3.
当进程从等待状态转换到就绪状态时（例如：I/O 完成）
4.
当进程终止时
在第一种和第四种情况下没有调度方面的选择。（In circumstances 1 and 4, there is no choice in terms of scheduling.）必须要选择一个新进程（如果就绪队列中有进程存在）执行。然而，在第二种和第三种情况下需要作出选择。（There is a choice, however, in circumstances 2 and 3.）
我们称只在第一种和第四种情况下进行的调度为非抢占式的（nonpreemptive）；否则为抢占式的（preemptive ）。在非抢占式调度下，一旦把CPU 分配给一个进程，那么该进程就会保持CPU 直到终止或
转换到等待状态。Microsoft Windows 3.1 和Apple Macintosh 采用了这种调度方式。因为非抢占式调度不像抢占式调度那样需要专门的硬件（如计时器），所以在某些硬件平台上它是唯一可用的方法。
可是抢占式调度要付出一定的代价。考虑一下两个进程共享数据的情况。当一个进程被抢占时它可能正在更新数据并且第二个进程被运行。（One may be in the midst of updating the data when it is preempted and
the second process is run.）第二个进程可能试图读取这个数据，现在这个数据处在一个不一致的状态。这就需要新的机制来协调对共享数据的访问；第七章讨论这个问题。
抢占（Preemption）也会影响到操作系统内核的设计。在系统调用的处理过程中，内核可能会为某个进程做一些工作。这可能会改变重要的内核数据（如I/O 队列）。如果在这个过程中该进程被抢占，并且内核（或设备驱动程序）需要读取或修改同样的数据结构，那么会怎样呢？结果可能会混乱不堪。有些操作系统（包括大多数UNIX 版本）通过在上下文转换之前等待一个系统调用结束或发生一个I/O 阻塞来处理这个问题。因为当内核数据结构处于不一致状态时不允许内核抢占进程，所以这种机制保持了内核结构的
简单化。问题是这种内核执行模型（kernel-execution model ）并不适于实时计算和多道处理。6.4 节和6.5 节描述了这些问题和它们的解决方案。
在UNIX 中，代码段的使用也有危险。（In the case of UNIX, sections of code are still at risk. ）根据定义中断可以随时发生，而且内核并不能够总是忽视中断，必须要确保首中断影响的代码段不被同时使用。操作系统几乎总是需要接收中断，否则就有可能丢失输入或输出被重写。所以这些代码段就不可以被几个进程同时访问，它们在入口禁止中断，在退出时恢复。但是，禁止和允许中断要耗费时间，尤其是在多处理机系统中。For systems to scale efficiently beyond a few CPUs, interrupt state changes must be minimized and fine-grained locking maximized. For instance, this is a challenge to the scalability of Linux.
6.1.4 调度程序
CPU 调度中的另一个组成部分是调度程序（dispatcher）。调度程序是一个模块，它将CPU 控制提交给短程调度程序选择的进程。其工作包括：
.
转换上下文
.
转换到用户摸式
.
跳转到用户程序中的正确位置重新开始该程序
调度程序应该尽可能的快，因为每次进程转换都要调用它。调度程序停止一个进程并开始运行另一个进程所需的时间被称为调度时间。
|
|
|
|
|
| |
| 8 |
回复：1月9日 OS
|
|
6.2 调度准则
不同的CPU 调度算法有不同的性质并且可能会更适用于某个进程类型（与其它进程类型相比）。在一个特定的环境中采用哪个算法必须要考虑到各种算法的特性。
可以用有多个准则来比较CPU 调度算法。在确定最好的算法中所用的特征可以使各种算法产生实质性的不同。（The characteristics used for comparison can make a substantial difference in the determination of the best algorithm.）这些准则包括：
CPU 利用率：我们希望尽可能的保持CPU 忙碌。CPU 利用率可能在0 到100 之间。在实际的系统中，CPU 利用率的范围应该在40% （系统负荷较轻）到90%（系统负荷较重）之间。
吞吐量：如果CPU 忙于执行进程，那么工作正在进行（就要完成了）。对工作量的一种测量是单位时间内完成的进程数，被称为吞吐量。（If the CPU is busy executing processes, then work is being done. One measure of work is the number of processes completed per time unit, called throughput.）对较长的进程来说吞吐量可能是每小时一个进程；对于较短的事务来说可能是每秒十个进程。
周转时间：对一个进程来说，一个重要的指标是它执行所需要的时间。（From the point of view of a particular process, the important criterion is how long it takes to execute that process.）从进程提交到进程完成的时间间隔为周转时间。周转时间是等待进入内存的时间、在就绪队列中等待的时间、在CPU 中执行的时间和I/O 操作的时间的总和。
等待时间：CPU 调度算法并不能影响进程的执行时间和I/O 操作时间；它只能影响进程在就绪队列中等待的时间。等待时间是进程在就绪队列中耗费时间的总和。
响应时间：在交互式系统中，周转时间可能不是最好的指标。进程通常会很早的产生一些输出，并且在先前的结果输出给用户时继续计算。因此，另一个度量标准是从进程提交请求到产生首次响应的时间。这被称为响应时间，是开始响应所需的时间，而不是到产生输出结果所需的时间。周转时间通常受限于输出设备的速度。
我们希望最大化CPU 利用率和吞吐量，最小化周转时间、等待时间和响应时间。在大多数情况下，我们最优化平均值。然而，在某些情况下我们需要最优化最小或最大值，而不是平均值。例如，为了保证所有的用户获得满意的服务，我们可能需要最小化最大的响应时间。
对于交互式系统（如实时系统）来说，有些分析者建议最小化响应时间的差异（variance in the response time）比最小化平均响应时间更为重要。拥有合理的可预测的（predictable）响应时间的系统比具备更快的平均时间的系统更令人满意。然而，在CPU 调度算法上最小化差异所做的工作很少。
在我们讨论各种CPU 调度算法时会举例说明它们的操作。一个精确的例子应该包含许多进程，每个进程有一个由数百个CPU burst 和I/O burst 组成的序列。为了简化，在例子中我们设想每个进程只有一个CPU burst（以毫秒计）。我们比较平均等待时间。在6.6 节讨论更多精确的评估机制。
|
|
|
|
|
| |
| 9 |
回复：1月9日 OS
|
|
6.3 调度算法
CPU 调度决定了从就绪队列中选择哪个进程并为其分配CPU。本节我们描述几种现有的CPU 调度算法。
6.3.1 先来先服务调度算法
先来先服务（FCFS）调度算法是目前最简单的CPU 调度算法。利用这种策略，先请求CPU 的进程先获得CPU。利用一个FIFO 队列可以很容易实现FCFS。当一个进程进入就绪队列后，它的PCB 被链接到队尾。当CPU 空闲时，处于队列头部的进程获得CPU。然后，运行的进程从该队列中移掉。FCFS 调度算法的代码易写易懂。
然而FCFS 策略的平均时间通常非常长。考虑如下的进程组合，在时间0，给定CPU burst 时间长度（以毫秒计）：
进程Burst 时间
P1 24
P2 3
P3 3
如果进程以P1 、P2、P3 的顺序到达，并且以FCFS 规则服务，我们将获得如下的甘特图：
P1 P2 P3
0 24 27 30
进程P1 的等待时间是0 毫秒，进程P2 是24 毫秒，P3 是27 毫秒。这样，平均时间是(0 + 24 + 27)/3 = 17 毫秒。如果进程到达的顺序是P2、P3、P1，那么结果如下：
P2 P3 P1
0 3 6 30
现在的平均等待时间是(6 + 0 + 3)/3 = 3 毫秒。平均时间很明显的减少了。因而，FCFS 策略下的平均等待时间通常不是最小的，而且如果进程的CPU burst 时间有明显的变化时平均时间也会有很明显的变化。
另外，考虑一下在动态的情况下的FCFS 调度算法的性能。假设有一个CPU 繁忙型进程和许多I/O 繁忙型进程。随着进程在系统中运行，结果可能如下。（As the processes flow around the system, the following
scenario may result.）CPU 繁忙型进程将获得CPU 并持有它。在这段时间内，其它所有的进程将结束它们的I/O 操作并移动到就绪队列中等待CPU。当进程在就绪队列中等待时，I/O 设备空闲。最后，CPU 繁忙型进程结束它的CPU burst 并移动到一个I/O 设备。所有的I/O 繁忙型进程（具有很短的CPU burst）迅速执行并返回到I/O 队列。这时，CPU 空闲。CPU 繁忙型进程将返回到就绪队列并被分配到CPU。再次，所有的I/O 进程在就绪队列中等待，直到CPU 繁忙型进程完成。其它所有的进程等待一个大进程释放CPU， 这就是护送效应（convoy effect）。如果允许更短的进程首先执行，那么相对之下这种影响降低了CPU 和设备的利用率。
FCFS 调度算法是非抢占性的。一旦CPU 被分配给一个进程，该进程将持有CPU 直到它释放CPU（通过终止或请求I/O）。对分时系统来说，FCFS 算法尤其糟糕，因为这种系统中的每个用户以有规则的时间间隔共享CPU。允许一个进程长期的占有CPU 会产生灾难性的后果。
|
|
|
|
|
| |
| 10 |
回复：1月9日 OS
|
|
6.3.2 短作业优先调度算法
另一个CPU 调度方法是短作业优先（SJF）调度算法。这种算法联系到了每个进程下次运行的CPU burst 长度。当CPU 有效时，它将被赋给下一个CPU burst 最小的进程。如果两个进程的下一个CPU burst 相同，就使用FCFS 调度。要注意到一个更恰当的术语是最短的下一个CPU burst（the shortest next CPU burst），因为调度是通过检测进程的下一个CPU burst 长度来完成的，而不是其总长度。我们使用术语SJF是因为大多数人和教科书都是作为SJF提及这种调度类型的。
作为一个例子，考虑如下的一组进程，给定了CPU burst 长度：
进程Burst 时间
P1 6
P2 8
P3 7
P4 3
利用SJF 调度，我们将依照如下的甘特图来调度这些进程：
P4 P1 P3 P2
0 3 9 16 24
P1 的等待时间是3 毫秒，P2 是16 毫秒，P3 是9 毫秒，P4 是0 毫秒。因而，平均等待时间是(3 + 16 + 9 + 0)/4 = 7 毫秒。如果使用FCFS 调度策略，那么平均等待时间是10.25 毫秒。
可证明SJF 调度算法是最佳的算法，因为它为指定的进程组给出了最小的平均等待时间。通过在一个长进程之前移动一个短进程，短进程等待时间的减少要比长进程等待时间的增加更甚。因此而降低了平均等待时间。
SJF 所面临的实际困难在于难以获知下一个CPU 请求的长度。对于批处理系统中的长程调度（或作业调度）来说，我们可以使用用户在提交作业时指定的处理时间限制长度。这样，用户需要准确的估计处理时间，因为越小的值意味着越快的响应速度。（太小的值会造成超时错误（time-limit-exceeded error），需要重新提交作业。）SJF 通常在长程调度中使用。
虽然SJF 算法是最理想的，但是却不能够在短程CPU 调度级实现。没有方法可以获知下一个CPU burst 的长度。一种方案是设法达到一种近似的SJF 调度。我们可能不知道下一个CPU burst 的长度，但是我们可以预测这个值。我们设想进程的下一个CPU burst 与其上一个相近。因此，通过近似估算下一个CPU burst 的长度，我们能够挑选一个拥有最短的预测CPU burst 的进程。
通常可以将下一个CPU burst 作为先前测量的CPU burst 的一个指数平均值来预测。（The next CPU burst is generally predicted as an exponential average of the measured lengths of previous CPU bursts.）令第n 个CPU burst 的长度是tn，我们预测的下一个CPU burst 为Tn+1。那么，对于ɑ（0 <= ɑ <= 1）.. ，定义：Tn+1 = ɑtn + (1 -ɑ)Tn
这个公式定义了指数平均数（exponential average）。tn 包含了最近的信息；Tn 则包含了过去的历史信息。在预测中，参数ɑ控制近来和过去历史的权重。（The parameter ɑcontrols the relative weight of recent and past history in our prediction.）如果ɑ = 0，那么Tn+1 = Tn，近来的历史没有产生影响（假定当前的条件是瞬时的）；如果ɑ= 1，那么Tn+1 = tn,，只有最近的CPU burst 有作用（假设历史记录陈旧了，没有关系了）。更普遍的，ɑ= 1/2，所以最近的历史记录与过去的相当。可以把初始的T0 定义为常数或整个系统的平均值。图6.3 表示了一个指数平均值（ɑ= 1/2，T0 = 10）。
Figure 6.3 Prediction of the length of the next CPU burst.
为了理解指数平均数的行为，代入Tn 的表达式，将式子展开：（To understand the behavior of the exponential average, we can expand the formula for Tn+1 by substituting for Tn , to find）
Tn+1 =ɑtn+ (1 -ɑ) ɑtn-1+ … +( 1 -ɑ)jɑTn-1 + … + (1 -ɑ)n+1T0. 因为ɑ和(1 -ɑ)都小于或等于1，所以每一项都要小于其前一项。
SJF 算法可能是抢占式的或非抢占式的。如果在先前的进程正在执行时有新进程到达，那么就会发生选择操作。新进程的下一个CPU burst 可能会比当前执行进程的剩余量短。在抢占式SJF 算法中，新进程抢占当前的进程；而非抢占式SJF 算法允许当前运行的进程结束其CPU burst。抢占式SJF 调度有时也被称为最短剩余时间优先（shortest-remaining-time-first ）调度。
作为一个例子，考虑如下的四个进程，给定如下的CPU burst 长度：
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
如果进程到达就绪队列的时间和进程执行所需的时间如上所示，那么按照抢占式SJF 调度会产生如下的结果：
P1 P2 P4 P1 P3
0 1 5 10 17 26
因为队列中只有进程P1，所以进程P1 在时间0 开始。P2 在时间1 到达。进程P1 的剩余时间大于进程P2 的时间需求（4 毫秒），所以进程P1 被抢占，P2 被调度。这个例子的平均等待时间是((10 - 1) + (1 - 1) + (17-7- 2) + (5 - 3))/4 = 26/4 = 6.5 毫秒。而采用非抢占式SJF 调度的平均等待时间为7.75 毫秒。
|
|
|
|
|
| |
| 11 |
回复：1月9日 OS
|
|
6.3.3
优先调度算法
SJF 算法是优先调度算法的一个特例。为每个进程赋予一个优先权，把CPU 分配给拥有最高优先权的进程。优先权相等的进程以FCFS 规则调度。
SJF 算法只是一种优先权的大小与（预测的）下一个CPU burst 长度成反比的优先权（p）算法。CPU burst 越大，优先权就越低，反之亦然。
注意，我们按照高低优先权来讨论调度。优先权通常是一些确定范围内的字，比如：0 到7，或0 到4,095。然而，对于0 是最高优先权还是最低优先权并没有一致的观点。有些系统使用小的数字（low number）来表示低优先权；其它的系统则使用小的数字表示高优先权。表示上的这种不同可能会产生混乱。
在本书中，我们使用小的数字来表示高优先权。
作为一个例子，考虑如下的进程组，假设在时间0，到达的顺序为P1、P2、....、P5，CPU burst 长度
给定如下：
Process Arrival Time Burst Time
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
使用优先调度，我们应该依照如下的甘特图来调度这些进程：
P2 P5 P1 P3 P4
0 1 6 16 18 19
其平均等待时间是8.2 毫秒。
可以从内部或外部定义优先权。内部定义优先权可以使用一些可测量的量（quantity or quantities）来计算进程的优先权。（Priorities can be defined either internally or externally. Internally defined priorities use some measurable quantity or quantities to compute the priority of a process. ）例如：时间限制、内存需求、打开
文件的数目和I/O burst 的平均值与CPU burst 的平均值的比，都可用于计算优先权。外部优先权由操作系统外部的标准设定，比如：进程的重要性、计算机的应用类型和投入资金、使用者所在的部门，以及其它的一些方面，经常有政治上因素牵扯其中。
优先调度可以是抢占式的或非抢占式的。当一个进程到达就绪队列时，就把它的优先权与当前运行的进程的优先权作比较。如果新到达的进程的优先权高于当前运行的进程的优先权，那么抢占式优先调度算法将抢占当前运行的进程的CPU；非抢占式优先调度算法只是简单的把新进程放到就绪队列的头部。
优先调度算法的主要问题是无休止的阻塞进程（indefinite blocking）（或饥饿）。进程准备就绪但缺乏CPU 可以被认为是阻塞——等待CPU。优先调度算法可能导致一些低优先权进程无限的等待CPU。在一个负荷重的计算机系统（heavily loaded computer system）中，一个不变的拥有更高优先权的进程流可以阻止一个低优先权进程获得CPU。通常会有两种情况可能发生。一种是该进程最终被运行（在星期天的凌晨两点，系统负载轻（lightly loaded）的时候），另一种是系统最终崩溃并丢失所有未结束的低优先权进程。（有传闻说：1973 年，当工作人员关闭MIT 的IBM 7094 时，他们发现一个在1967 年提交的低优先权进程还没有运行。）
解决无限阻塞一个方法是老化。老化（aging）是指逐渐地提高在系统中长时间等待的进程的优先权。例如，如果优先权从127（低）到0（高），我们可以每隔15 分钟把一个等待进程的优先权减1。最终，甚至一个初始优先权为127 的进程将拥有系统中的最高优先权并被执行。事实上，32 个小时之内一个优先权为127 的进程就会成为优先权为0 的进程。
|
|
|
|
|
| |
