Operating System Lecture 11/20
Menu Menu
ファイルディスクリプタ
dup の役割
CPU Scheduling
CPU-I/O Burst cycle- CPU burst
- I/O burst
- Buffering
- I/O bound
- CPU bound
- Interactive
スケジューリングの種類
- preemptive
- non-preemptive
- CPU utilizatoin
- Throughput
- Turnaround time
- Waiting time
- Reponse time
Scheduling Algorithm
- First-Come, First Served
きたものから順に処理する
- Shortest-Job-First
一番早く終わるものから処理する
- Priority Scheduing
順番を決めておく
- Round-Robin Scheduling
Quantum の時間で一旦中断し、公平に処理する
- Multilevel Queue Scheduling
Priorityをより一般的にする
- Multilevel Feedback Queue Scheduling
Priorityを可変にする
問題
Write Gantt charts for a set of processes below using scheduling algorithms: FIFO, SJF, Priority, RR. In case of RR, use priority and quantum 12, 6 and 1. Calculate avarage waiting time and turnaround time for each case.| Process | CPU time | Priority |
| 1 | 10 | 3 |
| 2 | 1 | 1 |
| 3 | 2 | 3 |
| 4 | 1 | 4 |
| 5 | 5 | 2 |
軽量プロセス
軽量プロセスは、Threads または LWP (Light weight process )と呼ばれる、メモリ空間を切り替えない仮想プロセッサのみのプロセスである。これは仮想的に複数の計算の流れを実現する並行プログラム(Concurrrent Programming)を高速に実装することができる。最近のOSでは必ず採用されている重要な機能である。| Windows | Win32 APIに Threads が含まれている |
| Mach | Threads を採用したOSの元祖 C-Threads |
| Solaris | Kernel Threads を実装している。Pthreads APIもある |
| BSD/OS | Posix 準拠 PThreads を ユーザレベルで実装している |
| Java | User level threads を VM により実装している |
| MP | 前琉大講師の新城先生が実装したLWP |
Threadsといってもさまざまな実装がある。| 種類 | 実装 | スケジュール |
| User level threads | プロセス内部でCPUコンテキストを手動切り替えるライブラリを提供する | 手動 non-preemptive |
| Kernel level threads | OSのKernelによりthreadsを管理する | Kernel によるpreemptive |
| Parallel threads | Threadsを複数のCPUに割り当てる | Kernel による |
Process と Threads の使い分け
Process は、独立したメモリ空間を持つために、他のProcessの影響を受けにくい。しかし、Processの切り替えにはメモリ空間の切り替えを伴うために、複数の並行プログラムの同期、通信は一般的に遅い。したがって、Bufferring を中心としたThrourghput 優先のプログラムを行う必要がある (select/socket/pipe)Process は、他のプロセスにより実行の優先順位や、singalによる状態切り替えを行うことができる。Threads は、一つのメモリ空間/Processの中に複数存在し、お互いの切り替えは関数呼び出しより若干重い程度で可能である。お互いの同期や通信もメモリを通して直接行うことができるので高速である。例えば、JavaやNetscapeで絵を動かす場合などに使うこともできる。しかし、User level threadsでは、外からのThreadsの制御をおこなうことはできない。
Threadsからは通常のライブラリ (libc など) を呼び出すことになるが、そのライブラリが固有の状態を持っていると、複数のThreadsから呼び出した時に不都合なことになる。そういう不都合が起きないライブラリを Re-entrant (自己再入可能)または、Threads safe という。printf は一般には Threads safeでないことが多い。また、I/O関係のライブラリもThreads safeでない場合がある。User level threads では、Re-entry は起きないので、このような問題は生じない。
Processのスケジューリングは、一般的におこなう必要があるためユーザが制御できる部分は限られている。しかし、Threadsでは、一つのプロセス内部に閉じているっため、その内部でのスケジューリングを自由に管理することができる。
宿題
「軽量プロセスの作成とスケジューリング」を、さ来週までに、おこなうこと。レポートはメールで
Subject: Practice on Operating System Lecture 11/20
というように、課題を出した日付をサブジェクトに入れたメールで提出して下さい。サブジェクトを間違えないこと!
宿題は毎週出るので提出が延びるとはまりますので気を付けてください。