travian
操作系统作业
5.2 Discuss how the following pairs of scheduling criteria conflict in certain ttings.
a.CPU utilisation and respon time
b.Average turnaround time and maximum waiting time
c.I/O device utilisation and CPU utilisation
a
CPU utilisation and respon time: CPU utilisation is incread if the
overheads associated with context switching is minimid. The context
switching overheads could be lowered by performing context switches
infrequently. This could however result in increasing the respon time for
process.
b
Average turnaround time and maximum waiting time: Average turnaround time is minimid by executing the shortest tasks first. Such a scheduling
policy could however starve long-running tasks and thereby increa their
waiting time.
c
I/O device utilisation and CPU utilisation: CPU utilisation is maximid by running long-running CPU-bound tasks without performing context
switches. I/O device utilisation is maximid by scheduling I/O-bound jobs as soon as they become ready to run, thereby incurring the overheads of
context switches.
5.5 Which of the following scheduling algorithms could result in starvation?
a.First-come, first-rved
b.Shortest job first
c.Round robin
the girl next doord. Priority
Answer：Short time first and Priority scheduling algorithms may contribute to starvation.(Starvation is situation that thread has arrived but have to wait for the CPU to be executed becau of CPU occupied by other threads an the
same time)
.
5.7问： long-running tasks 有什么区别
Consider a system running ten I/O-bound tasks and one CPU-bound task.
Assume that the I/O-bound tasks issue an I/O operation once for every
millicond of CPU computing and that each I/O operation takes 10
milliconds to complete. Also assume that the context switching overhead is
0.1 millicond and that all process are long-running tasks. What is the CPU
utilisation for a round-robin scheduler when:
a.The time quantum is 1 millicond
•The time quantum is 1 millicond: Irrespective of which process is scheduled, the scheduler incurs a 0.1 millicond context-switching
pplivecost for every context-switch. This results in a CPU utilisation of 1/1.1
* 100 = 91%.
b.The time quantum is 10 milliconds
smoke gets in your eyes•The time quantum is 10 milliconds: The I/O-bound tasks incur a context switch after using up only 1 millicond of the time quantum.
The time required to cycle through all the process is therefore 10*1.1
+ 10.1 (as each I/O-bound task executes for 1 millicond and then
incur the context switch task, whereas the CPU-bound task executes for
10 milliconds before incurring a context switch). The CPU utilisation
updatedata
is therefore 20/21.1 * 100 = 94%.
（CPU利⽤用率计算⽅方法：假设⼀一段时间total内，该任务的运⾏行时间为idle，cpu利⽤用率的计算公式为（total-idle）%total。这⼀一种⽅方法实现起来很简单，但是它只能算得整个系统的cpu使⽤用情况，不能得到单个任务的cpu使⽤用情况！同时它
会使cpu满负荷⼯工作。题⽬目中，提到的“that the I/O-bound tasks issue an I/O operation once for every millicond of CPU computing”意思是I/O-bound
tasks’每个耗时是1毫秒，有⼗〸十个这样的任务。⽽而“each I/O operation takes 10 milliconds to complete”意思是每个CPU-bound task每个耗时10毫秒，但是只有⼀一个。）
优先级转换速率是什么？
.5.9 Consider a preemptive priority scheduling algorithm bad on dynamically changing priorities. Larger priority numbers imply higher priority. When a process is waiting for the CPU (in the ready queue, but not running), its
priority changes at a rate !; when it is running, its priority changes at a rate !. All process are given a priority of 0 when they enter the ready queue.
The parameters !and !can be t to give many different scheduling
datastructure
algorithms.
a.What is the algorithm that results from ℬ > > 0?
学而不思则罔思而不学则殆的翻译unitedstatesb.What is the algorithm that results from ℬ < < 0?
Answer：
a. FCFS （先来先服务：从就绪队列中选择⼀一个或若⼲干个最先进⼊入该队列的进程，将
他们调⼊入内存运⾏行）
b. LIFO （后进先出：从就绪队列中选择⼀一个或若⼲干个最后进⼊入该队列的进程，
将它们调⼊入内存运⾏行）
. 5.10 Explain the differences in the degree to which the following scheduling algorithms discriminate in favour of short process:
a.FCFS法国航空公司
b.RR
c.Multilevel feedback queues
.Answer:
a.FCFS — discriminates against short jobs since any short jobs arriving
after long jobs will have a longer waiting time.
（秉承先来先服务原则，所以，短程任务如果在长程任务之后到来，就
必须等待，这样⼦子就等待蛮长时间的，所以对短程任务不利）
b.RR — treats all jobs equally (giving them equal bursts of CPU time) so
short jobs will be able to leave the system faster since they will finish
first.
c.Multilevel feedback queues — work similar to the RR algorithm —
chopper
they discriminate favourably toward short jobs.
