排他制御の基礎の基礎
はじめに システムに存在するリソースには同時にアクセスしてはいけないものが多々あります。身近な例を挙げると、Ubuntuのパッケージ管理システムのデータベースがあります。aptコマンドの動作によってこのデータベースは更新されるのですが、同時に2つ以上のaptが動作できたとすると、データベースが破壊されてシステムが危機的状況に陥ります。 このような問題を避けるために、あるリソースに同時に1つの処理しかアクセスできなくする排他制御というしくみがあります。排他制御はOSが提供する重要な機能の一つです。 排他制御が必要なケース 排他制御は直感的ではなく非常に理解が難しいのですが、ここでは比較的理解が簡単なファイルロックというしくみを使って説明します。説明には、あるファイルの中身を読みだして、その中に書いてある数字に1を加えて終了するincというという単純なプログラムを使います。
時刻印ロック - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "時刻印ロック" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2023年1月） 時刻印ロック（じこくいんろっく）とは、楽観的ロックの概念を用いたロック (情報工学)の手段の一種である。更新開始時点の対象データに記録されている最終更新時刻を記憶しておき、更新処理を行う際に再度対象データの最終更新時刻と比較する。もし異なっていたら、他によって内容が更新されてしまったと判断し、更新をあきらめ、同一であれば、対象データ更新とともに処理をした現在の更新時刻を記録する。 関連情報[編集] 楽観的並行性制御
ソフトウェアトランザクショナルメモリ - Wikipedia
計算機科学において、ソフトウェアトランザクショナルメモリ（英: software transactional memory, STM）は、データベーストランザクションに似た並行性制御機構であり、並列計算を行う際の共有メモリへのアクセス法である。この機構はロックベースの同期を用いた並行性制御の代替手段として機能し、ノンブロッキングな方法で実装される物もある。ここでいうトランザクションとは、共有メモリに対する一連の読み出しと書き込みを実行するコードを意味する。論理的にはこれらの読み出しと書き込みは、時間的なある一点で行われ、他のトランザクションからはその間の状態は見えない。トランザクションを行うためにハードウェアにサポートさせるアイデア(ハードウェアトランザクショナルメモリ)は、1986年に Tom Knight により論文と特許として出された。そのアイデアを普及させたのが Maurice H
Redisで超簡単にReader-Writer-Lockを実装する方法 - Qiita
考え方と原理 私のロック魂をアピールさせてください！（多田李衣菜） RedisでSETNXを使えば簡単に排他ロックが実現できる。MSETNXを使えば、複数のロックを同時に評価できる。それは良いのだが、並行実行性を考えると、なるべく競合しない方が良いよね。データ構造でも、競合しにくいように考えていると思うので、制御の方でも競合しにくい作りにしよう。 その代表が、Reader-Writer-Lock。読み出しはいくらでも競合したまえ。書き込みは別だ。というやつだね。賢いロックの賢いついでにreaderlock獲得中のコンテクストが、writerlockに昇格できるってのいいかも、と思ったけど、それ、ちょっと考えたら、同じことを考えてる奴が複数いたら、デッドロックになるじゃんね？ 書き込みをしたい人が、書き込みをするための情報を得るために読み出す場合、読み出しの段階からwriterlock獲得し
Redis::DistMutex - 時限付き分散ロックで効率良くサイトクロールをしよう - ZOZO TECH BLOG
はじめまして。バックエンドエンジニアの吉田です。 2013年5月末の入社以降、大量のEC2インスタンスのVPC移行を担当した後、今はiQONの商品DBを支えるクローラーの改善に取り組んでいます。今回はその改善の1つとして開発したRedis::DistMutexという分散ロック機構のruby実装を紹介をしようと思います。 Redis::DistMutex 開発の経緯や細かい設計の話は後述するとして、まずはつくったgemの紹介をします。 Redis::DistMutex Redisベースの分散ロック機構 rubyのライブラリにあるMutex互換 スレッド間だけでなく、プロセス間・ホスト間でも共有できるMutex 時限つきロックの作成が可能(redisのsetnxとexpireを活用) namespaceを指定できるので、特定の処理ごとにロックの作成が可能 redis2.6以上のみサポート(1秒
クローラーの並列処理でresqueを捨ててsidekiqに移行した話 - ZOZO TECH BLOG
こんにちは、VASILYエンジニアの塩崎です。 今回はiQONを支えているクローラーの並列処理について紹介したいと思います。 並列処理の効率化をする過程でresqueを見限りsidekiqに移行した理由、移行時に書き換えた部分などについてもお話ししたいと思います。 iQONのクローラーの並列処理の仕組み iQONでは毎日数100万点のアイテムのクローリングを行っています。 一度クローリングしたアイテムも毎日1回再クロールし在庫や値下げをiQON内のDBと同期しているため、大量のアイテムを効率良くクロールする仕組みが必要です。 クロールの処理は「ダウンロード」と「スクレイピング」の2つに大きく分けることができます。 このうち、ダウンロードの部分については、提携ECサイトに対して負荷がかからないようにスケジューリングをする必要があります。 この部分の効率化についてVASILYでは分散Mutex
Lock-freeとWait-freeアルゴリズム - Wikipedia
Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズム
グローバルインタプリタロック(GIL)とは
LL言語がマルチプロセッサ環境のメリットを捨ててまでグローバルインタプリタロックを採用している理由について調べてみた。 その為にはプロセスとスレッドについての前提知識がけっこう必要だったので、ついでにざっくり調べてみた。 LL言語がマルチプロセッサ環境のメリットを捨ててまでGILを実装している理由 結論を先に書くと、LL言語がマルチプロセッサ環境のメリットを捨ててまでGILを実装している一番の理由は、「スレッドセーフではないCで書かれたモジュールをたくさん使っているから」ということになるっぽい。 この結論に至るまでの色々な前提知識についても書いておく。 プロセスとスレッド プロセスとスレッドの特徴をざっくり対比させて書くとこんな感じになる。 ユーザースレッドとカーネルスレッド ユーザースレッド ユーザ空間で実装されたスレッド機構をユーザースレッドと呼ぶ。 1つのプロセス内の複数のスレッドは
Ruby の Monitor と ConditionVariable の使い方 - Mame the hack
Ruby の Monitor と ConditionVariable の使い方 なかなかぐぐっても日本語の資料が見つからなかったので自分で動かしてみた。(ぐぐる能力低い) まずThreadの直列化 require "thread" require "monitor" moni = Monitor.new val = 0 Thread.new { 3.times { puts "thread1 start: #{val}" val+=1 sleep 0.1 puts "thread1 end: #{val}" } } Thread.new { 3.times { puts "thread2 start: #{val}" val+=1 sleep 0.1 puts "thread2 end: #{val}" } } sleep 結果は以下の通り。 start > end, start > en
rubyでカウンティングセマフォ - Qiita
require 'monitor' class CountingSemaphore def initialize(count) @count = count @monitor = Monitor.new @zero_cond = @monitor.new_cond end def synchronize @monitor.synchronize do @zero_cond.wait_while{ @count == 0 } @count -= 1 end ret = yield @monitor.synchronize do @count += 1 @zero_cond.broadcast end ret end end cs = CountingSemaphore.new(10) Array.new(100) do Thread.start do cs.synchronize{ `sle
Rubyで「スレッドの同時実行数を制限する」シンプルな方法 - Qiita
Rubyでスレッドの同時実行数を制限します。 カウンティングセマフォを使えば良いのですが、標準添付ライブラリには入ってない（多分）ので、実装します。 素直にやるとこういう感じ -> rubyでカウンティングセマフォ カウンタとMutexを用意して、カウンタが0の時に待つ機構を作って…と、割とめんどくさいことをしないといけません。 シンプルに 標準添付ライブラリのQueueを使えばこれらの処理がサクッと実装できちゃいます。 require 'thread' locks = Queue.new 2.times { locks.push :lock } Array.new(10) do |i| Thread.new do lock = locks.pop print "#{i}\n" sleep 2 locks.push lock end end.each(&:join) このコードでは10スレ
セマフォ - Wikipedia
語源の腕木式信号機 セマフォ（英: semaphore）とは、計算機科学において、並行プログラミング環境での複数の実行単位（主にプロセス）が共有する資源にアクセスするのを制御する際の、単純だが便利な抽象化を提供する変数または抽象データ型である。 概要[編集] セマフォは、ある資源が何個使用可能かを示す記録と考えればわかりやすく、それにその資源を使用する際や解放する際にその記録を「安全に」（すなわち競合状態となることなく）書き換え、必要に応じて資源が使用可能になるまで待つ操作が結びついている。セマフォは競合状態を防ぐ便利なツールであるが、セマフォを使うことでプログラムにおける競合状態がなくなると保証するものではない。任意個の資源を扱うセマフォをカウンティングセマフォ、値が0と1に制限されている（ロック/アンロック、使用可能/使用不可の意味がある）セマフォをバイナリセマフォと呼ぶ。後者はミュー
)
ロック (計算機科学) - Wikipedia
計算機科学におけるロック (英: lock) とは、計算機システム内に複数の動作主体（プロセスやスレッドなど）のある環境で、データやデバイスなどの計算資源（リソース）へのアクセス制限を課す同期機構。ロックは並行性制御ポリシーを実施する手法のひとつである。アクセス制限を課す動作を「ロックする」、「ロックを取得する」などと表現する。また対義語として、制限を解除することをアンロック（英: unlock）という（ロック解放、ロック解除とも）。 概要[編集] ロックは、複数の動作主体が同一のリソースに対して状態を変更する動作を行うとき、不整合な状態が起こらないように制御する並行性制御において用いられる手法の一つである。ある動作主体がロックしたリソースへは、基本的には他の主体による利用は妨げられる。実際には、完全に利用をさせないロックは性能低下が著しいため、複数の主体が取得可能なロックや、他者の読み出
)
モニタ (同期) - Wikipedia
この記事には参考文献や外部リンクの一覧が含まれていますが、脚注による参照が不十分であるため、情報源が依然不明確です。適切な位置に脚注を追加して、記事の信頼性向上にご協力ください。（2019年3月） 並行計算の分野におけるモニタ（英: monitor）とは、共有オブジェクトの状態が複数のスレッドから同時にアクセスされることを防ぎ、かつ状態が変化するまで待機させるような、同期のための構成概念である。モニタはスレッドに、排他アクセス権を再取得してタスク（英語版）を再開する前に、特定の条件が満たされるまで待機するために、排他アクセス権を一時的にあきらめさせるメカニズムを提供する。モニタはミューテックス（ロック）と、少なくとも1つの条件変数（英: condition variable）から成る。条件変数は、オブジェクトの状態が変化したときに明示的にシグナルされ、このときミューテックスは条件変数を待機
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
sync package - sync - Go Packages
GitHub - mrpepper023/redis-readwritelock: readwritelock with redis
Class: Monitor (Ruby 2.1.2)
Class: MonitorMixin::ConditionVariable (Ruby 2.1.2)
Module: MonitorMixin (Ruby 2.1.2)
RubyのLoggerはスレッドセーフ(＆プロセスセーフ)かどうか調べてみた : sonots:blog
