Operating System Lecture 5/21

先週の復習

       % ( du -s /usr/local ; echo end ) & 

• () で新しい tcsh が起動される
• & では、wait は起きない
• ; では、wait した後に、再び同じ構造で fork-exec-wait が起きる

       tcsh           du
        |
        +---- fork --> new
        |              |
       wait           running
        :              |
        :              v
     completion    <--interrupt-terminated
        |
        v
      runnning

軽量プロセス

軽量プロセスは、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

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では、一つのプロセス内部 に閉じているっため、その内部でのスケジューリングを自由に管理することが できる。

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

Real-time Scheduling Algorithm

• Deterministic model
• Queueing models

• Dead line scheduling
• Rate monotinic scheduling

宿題

問題

以下の定期的に要求されるPeriodical プロセスをRate monotonic shcedulingと Dead line scheduling により実行するとどうなるかをGunt chartを 使って表せ。

情報実験Iの一部として、 5 プロセスの概念とその基本操作 の

4.3 軽量プロセスの生成 の 課題11-14 を行いなさい。その結果を、E-Mail で提出すること。 実験のレポート、この授業の宿題は、 kono@ie.u-ryukyu.ac.jp まで、

    Subject: Report on Operating System Lecture 5/21

として提出すること。授業に出席しなかったものは、この授業の問題を

    Subject: Practice on Operating System Lecture 5/21

E-Mailで提出すること。