デッドロック

In document 新潟大学学術リポジトリ (Page 182-187)

Buffer[next_vacant]=new_record;

V(n occupied);

next_vacant = (next_vacant+1)%N;

V(mutex_producer);

} }

/*---*/

/* consumerのプロセス */

void consumer(void) {

struct record new_record;

while (TRUE) {

P(mutex_consumer);

P(n occupied);

new_record=Buffer[next_occupied];

V(n vacant);

next_occupied = (next_occupied+1)%N;

V(mutex_consumer);

読み出したレコード new_record に関する処理を行う;

/*共有資源を確保する時間を出来るだけ短くするため*/

/*に、Buffer上のレコードを直接処理するのは避けた*/

} }

13.3. デッドロック 177

例 13.1 (デッドロックの発生) デッドロックの状況は、例えば次の様にして発生する。

プロセスA R1共有資源R2 プロセスB 空き 空き

(1)lock(R1); ∼∼∼∼→ プ ロ セ スAが確保

(ディスパッチ) ⇓ ⇓

プ ロ セ ス

Bが確保 ←∼∼ (1)lock(R2);

⇓ ⇓ ←∼∼ (2)lock(R1);

⇓ ⇓ (イベント待ち状態に)

(再開) ⇓ ⇓

(2)lock(R2); ∼∼∼∼→ ⇓ ⇓

(イベント待ち状態に) ⇓ ⇓

... ...

デッドロックの回避: デッドロックを回避するには、単に次のような方法で資源確保を 行うだけで良い。

(方法1) どの資源を先に確保するかの絶対的な優先順位を、全てのプロセス間で共通に 定める。そして、複数の資源を必要とする場合は、その共通の順序に従った順序 で必要な資源を確保していく。

(方法2) 複数の資源を必要とする場合は、一度にまとめて資源の確保を試みる。

'

&

$

% そのためには、

一度にまとめて資源の確保を試み、

全てが揃わなければ何れも確保しない、

というタイプの操作、言わばAND条件付P( )操作 用意する必要がある。

資源確保の際の作法: プロセスをうまく協調させた上で、システム全体を効率良く運営 するためには、さらに次の点に留意すべきである。

• 使用済の資源は直ちに解放する。

• 資源を排他的に使用する時は、資源が空いていることを確かめてから確保の要求を行

う。 '

&

$

% 補足:

この工夫はp.167の「CS命令を用いたlock( )の実装」例の中で見受けられる。

要するに、lock( ) にしろ P(sem) にしろ、資源を排他的に確保しようとする 命令/操作は内部にTest-and-Set命令 やCS命令の様な、多くのマシンサイク ルを要する命令を含んでいるので、頻繁に実行するのは避けた方が良いという こと。

• 共用(share)なのか排他的(exclusive)な利用なのかをはっきりと見極めた上で、資源 要求を行う。

演習問題

□演習 13.2 デッドロックとは何か?

□演習 13.3 デッドロックを回避する方法を述べよ。

179

14 UNIX プロセス間通信 (1) — パイプ

コマンドインタープリタにおけるパイプ機能(吉 7.5.1-2節),

pipe( )システムコール(吉沢7.5.3-4節),

食事する哲学者達,

dup( )システムコール(吉沢7.5.5節),

popen( ), pclose( )ライブラリ関数,

名前付きパイプ(吉沢7.5.6節),

この節では、UNIXで最も手軽なプロセス間通信の手段となっているパイプ(pipe)につ いて説明する。

14.1 コマンドインタープリタにおけるパイプ機能の利用

{吉沢7.5.1-2節} tcsh や bash といったコマンドインタープリタ上においても、パイプを用いたプロセ ス間通信の機能を利用することがある。

例 14.1 (コマンドライン上でのパイプ機能の利用) UNIXにおいては、1つのコマンドの 標準出力がそのまま別のコマンドの標準入力に向かうことを指定して、2つのコマンドを 並行して実行させることが出来る。このためには、単に2つのコマンドを縦棒(|)で繋ぐ だけである。例えば次の通り。

[motoki@x205b]$ ls -l /bin | grep sh

-rwxr-xr-x 1 root root 60592 Feb 4 2000 ash*

-rwxr-xr-x 1 root root 263064 Feb 4 2000 ash.static*

-rwxr-xr-x 1 root root 334960 Feb 16 2001 bash*

-rwxr-xr-x 1 root root 492720 Sep 8 2000 bash2*

lrwxrwxrwx 1 root root 3 Jan 22 2002 bsh -> ash*

lrwxrwxrwx 1 root root 4 Jan 22 2002 csh -> tcsh*

-rwxr-xr-x 1 root root 165072 Feb 8 2000 ksh*

lrwxrwxrwx 1 root root 4 Jan 22 2002 sh -> bash*

-rwxr-xr-x 1 root root 269072 Dec 11 2000 tcsh*

lrwxrwxrwx 1 root root 14 Jan 22 2002 zsh -> ../usr/bin/zsh*

[motoki@x205b]$

ここでは、2つのコマンドの間に縦棒(|)を置くことによって、前に現れるコマンド “ls

-l /bin” の標準出力がそのまま後のコマンド“grep sh”の標準入力として処理される、

とした上で2つのコマンドを並行処理することを指定している。

コマンド ls -l /bin

コマンド grep sh パイプ

標準出力 標準入力 標準出力

例 14.2 (3つのコマンドをパイプで繋げる) 3つ以上のコマンドをパイプで繋げることも 可能である。例えば次の通り。

[motoki@x205b]$ ls /usr/bin | grep 2 | more a2p*

addr2line*

afm2tfm*

...

gif2ps*

...

latex2html*

...

pdf2ps*

...

ps2epsi*

ps2pdf*

...

wx2_conv

[motoki@x205b]$

パイプ処理の中味: パイプの実体は2つのプロセスの間で共有するメモリバッファで ある。

• メモリバッファの共有の仕方は、生産者と消費者の問題(13.2.2節)におけるproducer

と consumerの間のデータ領域の共有の仕方と同じである。1つのプロセスがメモリ

バッファに次々と書き込み、書き込まれたデータを別のプロセスが順に読み出して処 理してゆく。

• パイプの両端のプロセスはOSの監視の下で並行に実行される。 (=⇒ 高性能化)

文字 (空き)

(空き)

(空き)

(空き) 共通のメモリ バッファ領域

次の書込み位置

次の読出し位置

(consumer 1 と共有する)

(producer 1 と共有する)

プロセス ls /usr/bin

プロセス grep 2 書込み

読出し (producer 1)

(consumer 2) 文字

文字

文字 (空き)

(空き)

(空き)

(空き) 共通のメモリ バッファ領域

次の書込み位置

次の読出し位置

(consumer 2 と共有する)

(producer 2 と共有する)

プロセス more 書込み

読出し

(producer 2)

文字

文字 (consumer1)

In document 新潟大学学術リポジトリ (Page 182-187)