質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
排他制御

排他制御とは、特定のファイル・データへのアクセスや更新を制御することです。特にファイルやデータベースへ書き込みを行う際、データの整合性を保つため別のプログラムによる書き込みを一時的に制御することを指します。

セマフォ

セマフォは、並行プログラミングにおいて同期のサポートを行うための機構。また、それによりプロセス間で交換される信号を指します。複数のプロセスでファイルなどを共有している際の同時アクセスによる破壊や不整合を防ぐことが可能です。

OS

OS(オペレーティングシステム)は、システムソフトウェアの一種であり、一般的に、ハードウェアを直接的に管理・操作する最も中心的な機能を有するソフトウェアがオペレーティングシステムとして呼ばれます。

Linux

Linuxは、Unixをベースにして開発されたオペレーティングシステムです。日本では「リナックス」と呼ばれています。 主にWebサーバやDNSサーバ、イントラネットなどのサーバ用OSとして利用されています。 上位500のスーパーコンピュータの90%以上はLinuxを使用しています。 携帯端末用のプラットフォームAndroidは、Linuxカーネル上に構築されています。

マルチスレッド

マルチスレッドは、どのように機能がコンピュータによって実行したのかを、(一般的にはスレッドとして参照される)実行の複合的な共同作用するストリームへ区分することが出来ます。

Q&A

解決済

2回答

7239閲覧

セマフォ、ロックの実装について

kkkmokotan

総合スコア45

排他制御

排他制御とは、特定のファイル・データへのアクセスや更新を制御することです。特にファイルやデータベースへ書き込みを行う際、データの整合性を保つため別のプログラムによる書き込みを一時的に制御することを指します。

セマフォ

セマフォは、並行プログラミングにおいて同期のサポートを行うための機構。また、それによりプロセス間で交換される信号を指します。複数のプロセスでファイルなどを共有している際の同時アクセスによる破壊や不整合を防ぐことが可能です。

OS

OS(オペレーティングシステム)は、システムソフトウェアの一種であり、一般的に、ハードウェアを直接的に管理・操作する最も中心的な機能を有するソフトウェアがオペレーティングシステムとして呼ばれます。

Linux

Linuxは、Unixをベースにして開発されたオペレーティングシステムです。日本では「リナックス」と呼ばれています。 主にWebサーバやDNSサーバ、イントラネットなどのサーバ用OSとして利用されています。 上位500のスーパーコンピュータの90%以上はLinuxを使用しています。 携帯端末用のプラットフォームAndroidは、Linuxカーネル上に構築されています。

マルチスレッド

マルチスレッドは、どのように機能がコンピュータによって実行したのかを、(一般的にはスレッドとして参照される)実行の複合的な共同作用するストリームへ区分することが出来ます。

2グッド

1クリップ

投稿2017/02/04 20:43

カーネル内の実装について、普段プログラマはセマフォやロックを用いて排他制御を行うと思うのですが、これらのセマフォやロックの実装について勉強致しました。
その結果、スピンロックという手法が取られていることがわかりました。ビジーウエイトによる実装ということがわかりました。そこで二つほど疑問ができました。

こちらのサイトを見る限りだと、そもそもカーネルの割り込みをさせないことが前提になっています。
つまりこれらの処理は単一プロセサに対しては割り込みさせないという処理が大前提になっているのでしょうか?

またスピンロックはあくまでロックの獲得の1手法であり、スピンロックのみ使えばロックが安全に取れる(マルチプロセサ環境で)ということはありませんよね?

よろしくお願いいたします。

kazuyakazuya, maisumakun👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

こんにちは。

こちらのサイトを見る限りだと、そもそもカーネルの割り込みをさせないことが前提になっています。

つまりこれらの処理は単一プロセサに対しては割り込みさせないという処理が大前提になっているのでしょうか?

アトミック命令を使ってロックを取得できるので、別に割り込みを禁止する必要はないと思います。アトミック命令実行中に割り込みはかかりませんから。
実際の実装を見たことはないですが、恐らくアトミック命令を使えるプロセッサでは態々割り込み禁止していない筈です。
昔は、ロック取得に使えるようなアトミック命令がないシングル・プロセッサが主流でしたので、割り込み禁止して対応してました。

あと、リンク先の図9は一見アトミック命令でロック確保できるまでビジー・ウェイトするようにも読み取れますが、書きにくかったのだろうと思います。
そのような実装は非常に危険(ロック解放されなければCPUはアトミック命令から抜け出せない)なので、実際に使われるケースはあまりない筈です。

  1. ロック変数をチェックしてアンロックならロックする
  2. ロックを取得できなかったら、1.をリトライする

1.がアトミック命令で実行され、2.の処理は別の命令に分かれていると思います。

またスピンロックはあくまでロックの獲得の1手法であり、スピンロックのみ使えばロックが安全に取れる(マルチプロセサ環境で)ということはありませんよね?

ロックを取得する方法とロック取得のリトライ操作は分けて考えた方が良いです。
ロックを取得できなかった場合、ロック取得をリトライする場合が多いですが、その時、直ぐにリトライするのがスピン・ロックですね。CPUを無駄に消費するのであまり使われないと思います。
一定時間スリープしてリトライすることも考えられます。ポーリングと呼ばれます。応答時間とCPU消費のトレード・オフになりますが、デッドロックを避けやすいです。(待ちの間に処理を挟めますので。)
そして、他のイベントの発生によりリトライする方法が最も良く使われます。例えば、ミューテックスの場合はミューテックス解放イベントによりロック取得をリトライします。CPUを無駄に消費しないので効率的です。しかし、待っている間何もできないため、デッドロックを避けるのが結構たいへんです。


【スピンロック補足】
もしかすると、セマフォやミューテックスを実装する際に使われている場合もあるかも知れません。
セマフォやミューテックス自身がアトミックにアクセスできないくらい多くのメモリを使うような場合、それらを一旦ロックする必要があります。使うメモリが多少多めとは言え、数命令でアクセスが完了する筈なので一旦CPUを解放するより、ビジー・ウェイトした方が効率が良い場合がありますので。

投稿2017/02/05 03:35

編集2017/02/05 03:38
Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kkkmokotan

2017/02/05 05:46

回答ありがとうございます! 補足について疑問なのですが、セマフォやミューテックスの実装にスピンロックが使われているのならば結局ロック獲得のリトライにビジーウェイトが使われるのだから、セマフォも元をたどればスピンロックとパフォーマンスが変わらないので意味がな区なるように思うのですがどうなのでしょうか?
Chironian

2017/02/05 06:24

問題はロックを獲得できるまでの時間です。それが非常に短い(数命令程度)であれはsleep()処理の負荷の方が大きいので、sleep()するよりビジー・ウェイトの方が効率があがります。 そして、セマフォやミューテックスの内部変数を操作するための時間は数命令程度で済むことが事前にわかっているのでスピンロックを使うことも有りえます。 それに対して、セマフォやミューテックスが排他制御する資源のロック期間はアプリケーション側の決定事項ですので事前に分かりません。数秒間ロックしっぱなしもあります。それをスピンロックで待つのは正直なところナンセンスな話です。
kazuyakazuya

2020/06/02 05:20

横から失礼します >アトミック命令を使ってロックを取得できるので ここでいうところのロックとはバスロックのことですか? intelアーキテクチャーマニュアル 7.1.2.2 https://www.intel.co.jp/content/dam/www/public/ijkk/jp/ja/documents/developer/IA32_Arh_Dev_Man_Vol3_i.pdf inc,decなどの命令にLOCKプリフィックスをつけることでバスロックをかけてアトミックス性を保証している。。。みたいに書かれていますが
kazuyakazuya

2020/06/09 05:33

すみません 何でもないです。 このバスロックと言うのはキャッシュ関係であり アトミック操作とは直接的な関係はありませんね
guest

0

単一プロセッサで割り込みを禁止するのは、そのほうが楽だからです。マルチプロセッサと同様な方法でロックを獲得することも可能ではありますが、シングルプロセッサの場合は割り込みを止めれば途中に別な書き換えが起きるようなことはありませんので、それで必要十分です。

マルチプロセッサの場合、「テスト・アンド・セット」「コンペアアンドスワップ」というような、既存の値のチェックと、新しい値への書き換えをアトミックに行う命令があって、そのような命令を使ってロックを構築していきます。

投稿2017/02/04 23:24

maisumakun

総合スコア145121

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問