マエカワの備忘録的な何か

思い立ったが吉日

オペレーティングシステム 其の九 20170621

相互排除についてもう少し詳しく

ロックの見直し

 ロックは①ロックされているかの確認、②ロックをかけるための値を書く.この二つをアトミックに処理する必要がある.
 ビジーループをかけるスピンロックについてもやったが、これだと長い処理の時CPUの無駄遣いになってしまう.
 そこで出てくるのが次のアイデア

ブロッキングロック

 システムコールによってブロック、起床をOSに依頼する方法
  →ブロックするのでその分CPUが節約できる.ただ、コンテキストスイッチが必要になってくる.

 sys_wait:signalが呼ばれるまでブロック
 sys_signal:ブロックしているスレッドを起床させる

 この命令をtest_and_set命令と組み合わせてロックを実現することができる.

続きを読む

オペレーティングシステム 其の八 20170614

並行プログラミング

並行でないプログラミングのことを逐次プログラミングという.
 →処理の流れが一つしかない.通常のプログラミング言語はこっちのほうを想定している.

並行にして何がいいのか

 ・ブロック状態にあるプロセスを別の処理の流れで出来たらうれしい.
 ・I/O-boundプロセスの待ち時間を有効に使いたい.
 ・マルチコアの性能を活かしたい.

並行にすることにより

 ・プロセスは自分勝手に動く.
  →競合してしまうことがある.
   →相互排除により、プロセス、スレッドの足並みをそろえる機能を付与したい
 ・実行順序が無数にある.
  →ここで別のスレッドが来たらバグになるかななんてことを考えながら描く必要がある.
 ・スレッド間で資源を共有している.
  →別スレッドが共有資源の内容を書き換えてしまうことがある.

続きを読む

オペレーティングシステム 其の七 20170607

CPUスケジューリング

 簡単に言うと、仕事に優先度をつけ、やる順番をつけて実行するということ.これをCPUがやるってだけ.

 プロセスの選び方を理解するためにはプロセスの性質を理解する必要がある.
  ・CPU-boundプロセス
   →CPUをたくさん要求する.数値計算など.
  ・I/O-boundプロセス
   →I/Oデバイスをたくさん使いたいプロセス.ブラウザやシェルなどがその例.

 <評価基準>
  プロセスの良さを知るためには基準が必要.
   ①ターンアラウンド時間:プロセス開始から終了までの時間
   ②スループット:単位時間当たりのプロセス数
   ③応答性:入力に対する応答の速さ(割り込みハンドラに関連する)
   ④資源の利用効率:CPUに遊びがないかどうか
   ⑤公平性:CPUの割り当てに偏りがあってはいけない

続きを読む

オペレーティングシステム 其の六 20170531

スレッドについて(スレッドとはプロセス内の処理の流れ)

写真を挿入

 ブロックされると困ってしまうプログラムがある場合、スレッドという概念が力を発揮する.

 困ってしまう例①
  ユーザーの入力待ちの間、アニメーションが止まってしまう.
   →この場合、入力街でブロックされるスレッドと、アニメーションを動かすスレッドを分岐させれば解決する.

写真を挿入

 困ってしまう例②
  クライアントの応答を待っているとき、ほかのクライアントの接続を要求したい.
   →接続状況に応じてプロセスを派生させたら解決できる.

写真を挿入

 困ってしまう例③
  複数のシステムを管理する場合、一つずつ確認していては時間がかかりすぎる.
   →下の写真のように元から複数に分岐させたら短時間で処理が終了する.

続きを読む

情報通信システム 其の十一 20170629

(7,4)ハミング符号の続き、いきます.

  \displaystyle \begin{cases}c_1&=&&i_1&+&i_2&+&i_3&&&\\c_2&=&&&&i_2&+&i_3&+&i_4&\\c_3&=&&i_1&+&i_2&+&&+&i_4&\end{cases}

こんな規則で検査記号が付加されることを思い出しとく.

シンドローム

 上の式を右辺を0にするように変形しましょう.

   \displaystyle \begin{cases}&i_1&+&i_2&+&i_3&&&+&c_1&&&&&&=&0\\&&&i_2&+&i_3&+&i_4&&&+&c_2&&&&=&0\\&i_1&+&i_2&+&&+&i_4&&&&&+&c_3&&=&0\end{cases}

  \displaystyle iとか \displaystyle cとかややこしいので、全部 \displaystyle x_jでおいてしまいましょう.

続きを読む