恐竜本練習問題6章です。問題は著者のページのものです。
6.1 A CPU-scheduling algorithm determines an order for the execution
of its scheduled processes. Given n processes to be scheduled on one
processor, how many different schedules are possible? Give a formula
in terms of n
自身の解答：n!
解答：n!
6.2 Explain the difference between preemptive and nonpreemptive scheduling.
自身の回答：Preemptiveの場合はプロセスにタイムクオンタムを割り当ててその時間以内に終わらなければ強制的にコンテキストスイッチを行う。nonpreemptiveの場合は強制中断がない。
解答：Preemptiveスケジューリングはプロセスが実行の途中で割り込まれ、CPUを取り去り別のプロセスに割り当てることを許容する。Nonpreemptiveスケジューリングはプロセスが現在のCPUバーストを終えたときにのみプロセスがCPUの制御を放棄するということを保証する。1
6.3 Suppose that the following processes arrive for execution at the times
indicated. Each process will run for the amount of time listed. In
answering the questions, use nonpreemptive scheduling, and base all
decisions on the information you have at the time the decision must be
made.
Process Arrival Time Burst Time
P1 0.0 8
P2 0.4 4
P3 1.0 1
a. What is the average turnaround time for these processes with the
FCFS scheduling algorithm?
b. What is the average turnaround time for these processes with the
SJF scheduling algorithm?
c. The SJF algorithm is supposed to improve performance, but notice
that we chose to run process P1 at time 0 because we did not know
15
自身の回答：a. (8+11.6+12)/3=31.6/3
b. (13.2+5.2+1)/3=19.4/3
c. (14+5.6+1)/3=20.6/3
解答：a. 10.53 b. 9.53 c. 6.862
6.4 What advantage is there in having different time-quantum sizes at
different levels of a multilevel queueing system?
自身の回答：早く処理が終わるタスクに短いタイムクオンタムを与える代わりに高い優先度を付与することで、すぐ終わるタスクを大量に処理することができ、システム効率が高くなる。
解答：より高頻度なサービス提供が必要なプロセス、例えばエディターのような対話的なプロセスは短いタイムクオンタムのキューに入る事ができる。高頻度なサービス提供が不必要なプロセスはより長いタイムクオンタムのキューに入ることができ、プロセスを完了するためにコンテキストスイッチが少なくて済み、したがってコンピュータの使用がより効率的になる。
6.5 Many CPU-scheduling algorithms are parameterized. For example, the
RR algorithm requires a parameter to indicate the time slice. Multilevel
feedback queues require parameters to define the number of queues,
the scheduling algorithms for each queue, the criteria used to move
processes between queues, and so on.
These algorithms are thus really sets of algorithms (for example, the
set of RR algorithms for all time slices, and so on). One set of algorithms
may include another (for example, the FCFS algorithm is the RR algorithm
with an infinite time quantum). What (if any) relation holds between the
following pairs of algorithm sets?
a. Priority and SJF
b. Multilevel feedback queues and FCFS
c. Priority and FCFS
d. RR and SJF
自身の回答：a. 優先度の付け方が過去の実行実績にもとづいて実行時間が短いジョブに高い優先度を与えるようになっているなら、経験ベースのSJFがPriorityと一致する。
b. マルチレベルフィードバックキューがキュー個数1個の場合FCFSに一致する
c. 優先度の与え方を到着順にした場合FCFSとPriorityが一致する
d. （RRってなんだ？）
解答：a. 最も所要時間の短いジョブが最も高い優先度を持つ。
b. MLFQの最低レベルがFCFSになっている
c. FCFSは最も存在期間が長いジョブに最も高い優先度を与える。
d. 無関係3
6.6 Suppose that a scheduling algorithm (at the level of short-term CPU
scheduling) favors those processes that have used the least processor
time in the recent past. Why will this algorithm favor I/O-bound
programs and yet not permanently starve CPU-bound programs?
自身の回答：I/OバウンドなプロセスはほとんどI/O待ちを行っており、平均的なCPU使用時間が短くなる。そのため過去のCPU使用時間に基づいたスケジューリングを行うと優先度が上位になる。CPUバウンドなプログラムを飢餓状態にしない理由はI/Oバウンドなプロセスが使うCPU時間の合計が非I/OバウンドプロセスのCPU時間を枯渇させるほど多くない場合が多いため。
解答：比較的短いCPUバーストを要求するのでI/Oバウンドなプログラムをそのスケジューリングアルゴリズムは好む。しかしながらI/OバウンドプログラムはI/Oを行うためにCPUを比較的頻繁に手放すのでCPUバウンドプログラムは飢餓にならない。
6.7 Distinguish between PCS and SCS scheduling
自身の回答：忘れた
解答：PCSスケジューリングはプロセスごとに行われる。それは利用可能なLWPにスレッドライブラリがスレッドをスケジュールする方法である。SCSスケジューリングはOSがカーネルスレッドをスケジュールする状況である。many-to-oneかmany-to-manyを使っているシステムでは2つのスケジューリングは根本的に異なっている。one-to-oneを使うシステムではPCSとSCSは同じである。
6.8 Assume that an operating system maps user-level threads to the kernel
using the many-to-many model and that the mapping is done through
the use of LWPs. Furthermore, the system allows program developers to
create real-time threads. Is it necessary to bind a real-time thread to an
LWP?
自身の回答：必要。リアルタイム性が必要なユーザーレベルスレッドを管理するLWPについてリアルタイム性が保証されるスケジューリングを依頼するため。（前に同じ問題を見た）
解答：（略）
6.9 The traditional UNIX scheduler enforces an inverse relationship between
priority numbers and priorities: the higher the number, the lower the
priority. The scheduler recalculates process priorities once per second
using the following function:
Priority = (recent CPU usage / 2) + base
where base = 60 and recent CPU usage refers to a value indicating how
often a process has used the CPU since priorities were last recalculated.
Assume that recent CPU usage for process P1 is 40, for process P2 is 18,
and for process P3 is 10. What will be the new priorities for these three
processes when priorities are recalculated? Based on this information,
does the traditional UNIX scheduler raise or lower the relative priority
of a CPU-bound process?
自身の回答：P1:(40/2)+60=80
P2:(18/2)+60=69
P3:(10/2)+60=65
P3、P2、P1の順に優先度が高くなる。CPUバウンドなプロセスの優先度は下がる。
解答：プロセスに割り当てられる優先度はそれぞれ80,69,65である。スケジューラはCPUバウンドプロセスの相対的な優先度を落とす。
コメント