オペレーティングシステム

オペレーティングシステム
(プロセス管理とスケジューリング)
2006年10月5日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/OS/2006/
ハードウェアのリセット処理によりプロセッ
サが働き始める。つまり、リセットベクタで
指定されたプログラムを実行する
電源オン
初期化中
POST
稼動状態
ブートストラップ
I/Oのチェック
メモリチェック
初期化
IPL
OS
IPLを読み込む
コマンド
インタプリタ
OSを読み込み
システムタスクとして稼動
OSの初期化終了後、コマン
ド・インタプリタを起動
ユーザーからのコマ
ンドを処理する
ユーザ・
タスク1
ユーザ・
タスク2
ユーザ・
タスクｎ
プロセスの概念(23ページ)
• プロセッサを抽象化したもの
– プログラム、データ、レジスタの中身… を含む
• 固有の記憶空間が与えられる
– 記憶空間などを共有しているもの→スレッド
– スレッドとプロセスを明確に区別しない→タスク
• 実行のひとつの単位
• プロセスは（理想的には）複数が同時に走行
• （現実にはプロセッサはプログラムを処理するため
に使われる資源で、複数のプロセスで共有）→次回
並行処理と並列処理
• 並行処理(Concurrent Processing)
– 複数のプロセスにより処理すること
– 複数のジョブが互いに独立したプロセスになる
• 並列処理(Parallel Processing)
– 複数のプロセスにより処理すること
– ひとつのジョブを複数のプロセスに分割
タスクとジョブ
• タスクはコンピュータからみた仕事の単位
– シングルタスクOS
• ひとつのタスクしか扱わないOS
– マルチタスクOS
• 複数のタスクを扱えるようにしたOS
• ジョブは人間からみて目的のある一区切りの仕事
– 逐次的なジョブ処理
• シングルタスクOSでもマルチタスクOSでも処理できる
– 並行的なジョブ処理
• マルチタスクOSでないと処理できない
※ タスクはプロセスとスレッドを区別しない言い方
ジョブ管理とタスク管理の関係
• ジョブ実行のスケジューリング
– 並行的（マルチジョブ）
• 資源の量と全体の処理時間をもとに、優先度をつけて処理
– 逐次的（シングルジョブ）
• ただ順番に処理する。スケジューリングの必要がない。
• タスク実行のスケジューリング
– 機械的に処理される。
• タスクはOSからみた仕事の単位であるから。
• OSが資源の利用状況を見ながら、スケジューリング
ハードウェアの管理
• Uni-Processor
– 管理する主体(=プロセッサ)がひとつ
• つまり、プロセスの実行管理だけを考えればよい
• Multi-Processor
– 管理する主体が複数ある
• どのプロセッサが何を管理するか、という管理も必要！
– 計算機の実装方式が複数ある
• OS内部の管理表は唯一でなければならないが、
• 複数プロセッサ間で管理のための方法が単一ではない！
プロセスの構造(25ページ)
• テキストセグメント
• データセグメント
• ヒープ領域
• スタックセグメント
• 共有セグメント
• レジスタコンテキスト
レジスタコンテキスト
• プロセッサの持つレジスタの内容
– 汎用レジスタ
– 浮動小数点数レジスタ
– プログラムカウンタ、リンクレジスタ
– スタックポインタ、フレームポインタ
– ステータスレジスタ
– マルチメディア拡張のためのレジスタ
プロセス管理
• プロセス制御ブロックPCB(Process Control Block)
– プロセスの状態
• 実行可、待ち、消滅中、など
– コンテキスト
• レジスタ、資源管理表
– 優先順位
• タイムスライス、実行優先度、経過時間、など
– PCBは線形リストを形成する
• 線形リストによりキューを実現
• 線形リストはタスクの状態ごとに存在する
タスク構造体
•プロセスやスレッドの状態
•スケジューリングポリシー
•仮想記憶
•スレッドの情報
•/usr/src/linux/include/linux/sched.h
struct task_struct がLinux OSのタスク構造体
•current が参照するタスクが現在実行中のタスク
•タスク構造体型のデータはカーネル空間に存在
•タスク構造体から参照される管理表は多い
プロセスの存在形態(27ページ)
実行中タスク
実行可能タスク
実行待ちタスク
仮想記憶処理
登録済タスク
タスク
未登録タスク
入出力
条件待ちタスク
通信
異常停止タスク
同期
生成中タスク
その他条件
実行不可能タスク
消滅中タスク
[sakai@star linux]$
USER
PID %CPU
root
1 0.0
root
1300 0.0
root
1304 0.0
rpc
1314 0.0
root
1403 0.0
named
1417 0.0
root
1456 0.0
ntp
1469 0.0
lp
1487 0.0
root
1563 0.0
root
1630 0.0
xfs
1688 0.0
root
1697 0.0
root
1701 0.0
daemon
1719 0.0
root
1857 0.0
root
1858 0.0
sakai
1881 0.0
sakai
1910 0.0
root
1911 0.5
sakai
1915 0.0
sakai
1921 0.0
sakai
1931 0.0
sakai
1943 0.0
root
436 0.0
smmsp
444 0.0
sakai
18193 0.0
sakai
30076 0.1
sakai
32189 0.0
ps aux
%MEM VSZ RSS TTY
0.0 1368 444 ?
0.1 1444 580 ?
0.0 1364 420 ?
0.1 1544 600 ?
0.1 1484 536 ?
0.7 39980 3836 ?
0.1 2076 856 ?
0.4 2392 2384 ?
0.8 11800 4412 ?
0.2 2520 1528 ?
0.1 1416 552 ?
0.9 9780 4944 ?
0.2 5800 1532 ?
0.2 4636 1312 ?
0.0 1408 508 ?
0.1 2280 752 ?
0.0 1344 340 tty2
0.1 5352 980 tty1
0.0 2332 484 tty1
9.2 95476 47424 ?
0.3 7076 1560 tty1
1.0 13416 5304 tty1
1.6 25148 8668 tty1
0.1 5348 972 pts/4
0.4 6220 2544 ?
0.4 6016 2308 ?
0.5 8960 2628 tty1
8.8 121468 45784 tty1
0.1 2724 776 pts/12
STAT
S
S
S
S
S
S
S
SL
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
R
R
プロセスの状態
START TIME COMMAND
Sep03 0:04 init [3]
Sep03 0:02 syslogd -m 0
Sep03 0:00 klogd -x
Sep03 0:00 portmap
Sep03 0:00 /usr/sbin/automou
Sep03 0:00 /usr/sbin/named Sep03 0:00 xinetd -stayalive
Sep03 0:08 ntpd -U ntp -g
Sep03 0:13 lpd Waiting
Sep03 0:01 /usr/sbin/dhcpd e
Sep03 0:02 crond
Sep03 0:21 xfs -droppriv -da
Sep03 0:00 smbd -D
Sep03 0:14 nmbd -D
Sep03 0:00 /usr/sbin/atd
Sep03 0:00 login -- sakai
Sep03 0:00 /sbin/mingetty tt
Sep03 0:00 -bash
Sep03 0:00 xinit
Sep03 344:10 X -auth /home/sak
Sep03 0:00 kterm -fn 8x16 -f
Sep03 1:43 gkrellm -g -0+0
Sep03 0:14 twm
Sep03 0:00 bash
Sep13 0:00 sendmail: accepti
Sep13 0:00 sendmail: Queue r
Oct09 0:01 aumix-X11
Oct19 1:54 /usr/lib/mozilla11:44 0:00 ps aux
例: プロセスの待ち状態
入出力待ちの場合、デバイスのほうにキューを持たせる
struct lp_struct {
struct pardevice *dev;
unsigned long flags;
unsigned int chars;
unsigned int time;
unsigned int wait;
char *lp_buffer;
#ifdef LP_STATS
unsigned int lastcall;
unsigned int runchars;
struct lp_stats stats;
#endif
wait_queue_head_t waitq;
unsigned int last_error;
struct semaphore port_mutex;
wait_queue_head_t dataq;
long timeout;
unsigned int best_mode;
unsigned int current_mode;
unsigned long bits;
};
struct __wait_queue {
unsigned int flags;
#define WQ_FLAG_EXCLUSIVE
0x01
struct task_struct * task;
struct list_head task_list;
#if WAITQUEUE_DEBUG
long __magic;
long __waker;
#endif
};
typedef struct __wait_queue wait_queue_t;
struct __wait_queue_head {
wq_lock_t lock;
struct list_head task_list;
#if WAITQUEUE_DEBUG
long __magic;
long __creator;
#endif
};
typedef struct __wait_queue_head wait_queue_head_t;
スケジューリング（２８ページ）
• 現実にはCPU数がプロセス数より少ない
– プロセススケジューリングのアルゴリズム
• プロセスにCPUを割付たり取り上げたりする
– プロセスのディスパッチャー
B-sh系
/usr/bin/time gogo -test 1000 >a 2>&1 & nice -19 /usr/bin/time gogo -test 1000 >b
2>&1 &
C-sh系
/usr/bin/time gogo -test 1000 > & a & nice +19 /usr/bin/time gogo -test 1000 > & b &

Download Report