ねぇうしくんうしくん

今週のまとめ (一週間で自分が見た技術系サイトのログ)が今のところメインです。プログラミング言語、人工知能、セキュリティ 等

🎸 ライブロック 🎸について

この記事は rogy Advent Calendar 2018 - Adventar の 9日目の記事です。

みなさんはデッドロックについてはご存知かと思われます。

// thread A
void doA() {
   lock1.lock(); // (A1)
   lock2.lock(); // (A2)
     // クリティカルセクション
   lock2.unlock();
   lock1.unlock();
}

// thread B
void doB() {
   lock2.lock(); // (B1)
   lock1.lock(); // (B2)
     // クリティカルセクション
   lock1.unlock();
   lock2.unlock();
}

2つのスレッドの処理が A1 → B1 のように進んだ場合、ロック解放待ちのブロックが発生し処理が停止してしまうという現象です。

ところで、デッドロックの親戚の概念としてライブロック(livelock)というものがあります。

A thread often acts in response to the action of another thread. If the other thread's action is also a response to the action of another thread, then livelock may result. As with deadlock, livelocked threads are unable to make further progress. However, the threads are not blocked — they are simply too busy responding to each other to resume work. Starvation and Livelock (The Java™ Tutorials > Essential Classes > Concurrency)

(訳) スレッドは時に別のスレッドの挙動に反応することがあります。一方で、そのスレッドがまた元のスレッドに影響を及ぼしあうとき、ライブロックが起こるかもしれません。デッドロックと同様に、ライブロックしたスレッドは処理を進めることができません。しかし、スレッドは実際にはブロックされていません ――― お互いの処理を再開するために永遠に反応しあうビジー状態に陥っています。

これを説明する比喩として面白い例がよく参照されます。

あなたが狭い道を歩いてるとき、向こうから人がやってきました。あなたはその人を見て右によけようとしますが、相手も同じ側によけられました。今度は左側によけようとしますが、あいてもまた左側によけようとします。結果としてお互いがまるで反復横跳びをしあうように運動し続け、前に進むことはありません。

こういった行動は日常生活でよくあると思いますので、その際はライブロックのことを思い出してください。*1

ライブロックするコードの例についてみてみましょう。

// thread A
void doA() {
  lock1.lock(); // (A1)
  while (lock2.locked()) // (A2)
  {
    lock1.unlock(); // (A3)
    sleep(); // (A4)
    lock1.lock(); // (A5)
  }
  lock2.lock(); // (A6)
  // クリティカルセクション
  lock2.unlock();
  lock1.unlock();
}

// thread B
void doB() {
  lock2.lock(); // (B1)
  while (lock1.locked()) // (B2)
  {
    lock2.unlock(); // (B3)
    sleep(); // (B4)
    lock2.lock(); // (B5)
  }
  lock1.lock(); // (B6)
  // クリティカルセクション
  lock1.unlock();
  lock2.unlock();
}

スレッドAで、A2 ~ A5 でlock2がロックされている場合、lock1 のロックを解除して「もう一方のスレッドに譲る(一旦ロックを解除し(A3)、少し待ってから(A4) 再ロックを行う (A5) )」行為を行っています。しかしながらスレッドBも同じことをしているため、最悪の場合お互い譲り合いをしあう状態が続き、whileループを抜け出せなくなってしまいます。

では、実際にこのようなバグが発生するのでしょうか?オープンソースの並行バグを調べた研究によると、ライブロックの割合は少ないものの Hadoop といった有名なフレームワークにも存在したようです。*2

f:id:z_kro:20181208164744g:plain

ライブロックを起こさない解決方法として以下のものがあげられます。

  • 譲るときの待ち時間をランダムにする
    • 現実世界の例で言っても譲るタイミングはいつかはずれてお互い通れるようになります。先ほどの例でも sleep の待ち時間をランダムにするという修正が考えられます。これは非常にアドホックでナイーブな修正ですが、ネットワークプロトコルの世界では「ランダムな待ち時間で衝突回避をする」といったことはよく行われています。
  • ロックの順番を適切に行う
    • デッドロックの解決策としても挙げられるやつです。lock1 の後に lock2 をする、というルールを定めればそのようなバグが起きることはありません。ルールに完璧に従ってプログラムを書ければ、ですが。
  • ロックを使わない。
    • ロックを使わなければデッドロック・ライブロックが起きることはありません。例えば、アトミック変数、ノンブロッキングデータ構造を使う、イベントドリブン(アクターモデル*3)なプログラムにすることなどが挙げられます。

他にも、ライブロック検出のためのアルゴリズムや手法がいくつかの論文で提唱されています。

*1:これを表現するスラングとしてSchlumperdinkというものがあるらしいです https://www.urbandictionary.com/define.php?term=schlumperdink

*2:Concurrency bugs in open source software: a case study https://jisajournal.springeropen.com/articles/10.1186/s13174-017-0055-2

*3:これでも暗黙のデッドロックみたいなものが生じるんですが、これについてはここでは述べません

まとめ

今週のまとめ

「今週の」という prefix は不要な気がしてきた.

今週のまとめ

お久しぶりです.

TweetDeckの配色を元のものに戻す

2月の初め頃、TweetDeck のダークテーマの色が全体的に変わりました。

f:id:z_kro:20180204043532p:plain

彩度が2倍になり、非常に目が疲れる配色となりました。 このままでは視力が無限に下がるのでユーザーCSSで元の彩度に戻したいと思います。

解決策1. Filter を使う

CSS3 には filter というプロパティがあり簡単な画像処理を行うことができます。 filter - CSS | MDN この場合全体の彩度を半分にすればいいだけです。画像については彩度を元に戻します。

body { filter: saturate(50%) !important; }
img  { filter: saturate(200%) !important; }

一応これでも良さげなんですが、全体にフィルタをかけているのでやはり動作が遅くなる問題点があります。あと画像が元の色と若干違って見えます。

解決策2. CSS プロパティの色の定義を上書きする

元々の CSS 定義されている色の彩度を下げて全て再定義するという力技です。 力技なのでプログラミングで解決します。

方針としては、ダークテーマを識別するクラス .dark が含まれるルールの全ての色の値を書き換えることをします。 幸い css をパースするツールや、Webにおける色定義を扱うツール等は npm に転がっているのでそれを用います。

やり方

前準備として最新の node の環境を用意しましょう。 そして適当なディレクトリを作り、 npm install color css でライブラリをインストールします。 そのディレクトリに対し以下のプログラムを gen_css.js のように適当な名前をつけて保存してください。

// gen_css.js
const fs = require('fs');
const css = require('css');
const Color = require('color');

let cssText = fs.readFileSync('bundle.css', 'utf-8');
let cssObj  = css.parse(cssText);
let rules   = cssObj.stylesheet.rules;

const colorRegex = /(#(?:[0-9a-f]{2}){2,4}|(#[0-9a-f]{3})|(rgb|hsl)a?\((-?\d+%?[,\s]+){2,3}\s*[\d\.]+%?\))/ig;
let output = '';

function procColor(colText) {
  return Color(colText).desaturate(0.5).rgb()
}

for(let rule of rules) {
  if(rule.type === 'rule') {
    if(rule.selectors.some(s => s.includes('.dark'))) {
      let colorProps = 
        rule.declarations.filter(d => d.value.match(colorRegex));
      if(colorProps.length > 0) {
        output += `${rule.selectors.join(', ')} {\n`
        output += colorProps.map(m => `    ${m.property}: ${m.value.replace(colorRegex, procColor)};`).join('\n');
        output += `\n}\n`;
      }
    }
  }
}

fs.writeFileSync('bundle.out.css', output);

その後、 https://ton.twimg.com/tweetdeck-web/web/dist/bundle.????.css (TweetDeckのHTMLソースに書いてあります) をダウンロードしてきて、 bundle.css として同ディレクトリに配置します。あとは node gen_css.js と実行すれば、 bundle.out.css として出力されます。 出力されたCSSは、Stylish などのブラウザ拡張でユーザー定義を行えばOKです。

f:id:z_kro:20180204045929p:plain 適用後はこんな感じです。若干おかしい部分がありますが動作自体に影響がないので大丈夫かと思います。細かい点は自分で修正してください。

一応2/4 5:00時点での出力結果はこちらにありますが、TweetDeck は頻繁に更新されているためすぐ使い物にならなくなる可能性が高いです。

††† この記事は需要があれば詳細を追記いたします。 †††

今週のまとめ

🎂

今週のまとめ

Java

Others