１．トランザクション処理
会計システムの一つの特徴はトランザクション処理である。会計システムにおいては、仕訳伝票が処置の一つの対象となる。ウェブベースのシステムであれば、ユーザの事務所にある端末、あるいは、コンピュータから伝票が入力され、それは、ウェブサーバーのシステムに送られ、さらにはデータベースのシステムに記憶される。この一連の作業が、正しく行われることを保証するのが、トランザクション処理である。もし、途中で、電源断などの故障が起こり、処理が途中で中断されたときには、その処理は再試行されるか、あるいは、そこまでに行われた処理をすべて取り消して、処理が行われなかったことをユーザに伝えなければならない。
オンラインショップでの決算や、航空券の購入などはすべてトランザクション処理である。もし、ユーザが一人しかいないのであれば、トランザクション処理を安全に実現することはそれほど難しいことではないが、複数のユーザが存在すると、その処理は格段に複雑になる。
例えば、航空券を購入する場面を考えることとする。残っている航空券は一枚であるとする。航空券がまだあることを一人のユーザが確認して、購入手続きを始めたとする。購入手続きにもたもたしている間に、他のユーザが購入手続きを始めたとする。システムが不備だと、二人のユーザに同時に売ってダブルブッキングを起したり、航空券を渡した人と請求先の人とが違ったりと、とんでもない事件を引き起こしてしまう。
トランザクション処理を安全に行えるようにするために、Javaの環境ではEnterprise Java Beans (EJB)というとても大きな支援ツールを用意している。しかし、この処理にはかなりのオーバヘッドがかかる(本質的な処理と、トランザクションに起因するオーバヘッドの比が1：10にも上るという調査結果もあった)。このため、実際にはあまり利用したくないというのが、本当のところである。
トランザクション処理をもっと簡単に行えるようにするために、最近では、言語の中に、Software Transaction Memory (STM)を装備させたものがある。関数型言語ではClojure, Haskellなどがそうである。また、将来計画ではハードウェアでメモリにトランザクション機能を持たるというものもある。トランザクション機能は、簡単にいうと、あるプロセス（あるいはスレッド）がデータを書き換えようとしている間は、他のプロセスはデータを読み出すことも書き換えることもできないようにすることである。STMはそれをソフトウェア的にサポートしたものである。
２．STMの利用法
Computational Thoughts にSTMの利用の仕方が記述されているので、このホームページから利用の仕方を引用する。このホームページには、セマフォ―、バッファー、リソースの三つの紹介がある。
2.1 セマフォ
セマフォは、信号機を意味する。最近の首都圏の鉄道網の整備は素晴らしく、小田急線のように複々線などもあり、列車同士の運行表を作成するのに面白さがなくなってきたが、かっては首都圏にも単線の区間がいくつかあった。横浜線はその例である。単線の路線では、別々の方向に向かう電車が同じ線路を走る。このため、うまい仕掛けを作らないと、電車が正面衝突してしまう。仕掛けの一つとして使われたのがタブレットである。単線の路線はいくつかの区間に分けられ、それぞれの区間には一つだけタブレットが用意されていた。そして、タブレットを持った電車だけがその区間を走ることができた。
タブレットの引き渡しは、子供たちの興味を引いたものである。新しい区間の始まりとなっている駅では、子供たちが集まって、どのようにタブレット(通常は丸い輪で、一か所に革製の袋が付いていた)が引き渡されるかを見ていた。新しい電車がその駅に入ってくると、タブレットを持っている対向の電車が来るのを待つ(もちろん、この駅では、上り線と下り線のホームは別々になっている)。対向の電車が到着すると、この電車の車掌さんが待機していた電車の車掌さんにタブレットを渡す(この時、対向の車掌さんも待機していた車掌さんから次の区間のタブレットをもらうので、交換するといった方が正しい)。
セマフォはタブレットと同じような働きをしてくれる。何人かの人で一つの資源(先ほどの単線区間)を使おうとするとき、セマフォはその資源が使用中かそうでないかを教えてくれる。このため、セマフォはTrueかFaiseの二つの値を持っている。Trueが使える状態、Falseが使えない状態である。セマフォにはpとvの操作がある。pの操作では、Trueであれば、即ち、使える状態であれば、Falseにして他の人が使えないようにする。Falseであれば、値が変わった時に、同じ操作をする(値が変わるまでこのプロセスは休止状態となるので、プロセッサの時間が無駄に使われることはない)。vの操作は、資源を使い終わった時にそれを開放するために、Trueにする。Haskellでの関数は以下の通りである。
TValはトランザクション機能を有するデータであり、以下の関数では、Semaphore型はブール値を持つトランザクションメモリである。newSemは値を設定するものである。値の設定はIOの世界で行われている。次にpとvの操作が定義されている。
type Semaphore = TVar Bool newSem :: Bool -> IO Semaphore newSem available = newTVarIO available p :: Semaphore -> STM () p sem = do b <- readTVar sem if b then writeTVar sem False else retry v :: Semaphore -> STM () v sem = writeTVar sem True
2.2 バッファ
バッファは処理スピードの異なるプロセス(あるいはスレッド)が、データを転送する時に用いられる。リーダー・ライター問題として知られているものである。リーダー・ライター問題はキーボードからの入力をプリンターに出力することを考えるとわかりやすい。プリンターは一行ごとに印刷するものとする。キーボードのプロセスは、改行が行われるとその一行をプリンターのプロセスに送信する。プリンターのプロセスはそれを出力する。これをスピードの異なるどのようなプリンターにも、キーボードにも対応できるようにしようとすると、プリンターが遅い場合にはキーボードプロセスからの依頼を処理できなくなってしまう。
処理速度が異なるプロセスの間で、間違いなくデータの授受を行えるようにしようというのが、バッファである。無限に長いバッファを用意しておき、キーボードプロセスはバッファにデータを送信する。プリンタプロセスはバッファにデータがあればそこからデータを受信する。どんなにキーボードが速くても、どんなにプリンタが遅くても、無限の長さのバッファがあれば足りるというのがこの仕掛けである。
並行処理の優れた理論的根拠になっているのはホア教授のCommunication Sequential Processes (CSP)だが、CSPはこのようなバッファがあると実現可能となる。
バッファをHaskellで記述すると次のようになる。バッファの型は、リストの形をしたトランザクション・メモリである。newBufferは空のリストを作成する。作成はIOの世界で行われている。操作としては、putとgetがあり、putはバッファにデータを送信するもので、実際には、新たなデータ(item)をこれまでのリストの最後にくっつける。getはデータを受信するもので、リストの先頭からデータ(item)を取り出す。もし、バッファにデータがなければ、データが来るのを待って再試行する(データが来るまでこのプロセスは休止状態になっているので、プロセッサの時間が無駄に使われることはない)。
type Buffer a = TVar [a] newBuffer :: IO (Buffer a) newBuffer = newTVarIO [] put :: Buffer a -> a -> STM () put buffer item = do ls <- readTVar buffer writeTVar buffer (ls ++ [item]) get :: Buffer a -> STM a get buffer = do ls <- readTVar buffer case ls of [] -> retry (item:rest) -> do writeTVar buffer rest return item
2.3 リソース
これはオペレーティングシステム(OS)の本を読むと出てくる問題である。OSの主要な目的は、それぞれのプロセス(あるいはスレッド)にプロセッサやメモリを割り当てて実行環境を与えなくてはいけない。一昔前のコンピュータであればプロセッサは時分割で、メモリは空間分割で割り当てていた。現在のコンピュータはメモリをふんだんに積んでいるので、メモリが不足するということはあまり起きなくなってきたが、一昔前までのコンピュータはメモリの容量が限られていたので、各プロセスがメモリ不足にならないように、スケジューリングするのが大変であった。
このような状況は、日常生活でも起きる。複数の店舗があった時に、それぞれのお店に過不足なく従業員を配置しようとするときにこれと同じ問題が生じる。
リソースには、acquireとreleaseの操作が存在する。acquireは\(n\)個のリソースを要求する。それ以上のリソースがあれば要求のあった数のリソースを渡してあげる。もし、ない場合にはリソースの数が変わるまで待ち続ける。もし、リソースの数が変われば、再試行する。releaseは\(n\)個のリソースを解放する。なお、リソースはどのように作成したらよいかは考えること。解答は、会計システムを作成するところで出てくる。
type Resource = TVar Int acquire :: Resource -> Int -> STM () acquire res nr = do n <- readTVar res if n < nr then retry else writeTVar res (n - nr) release :: Resource -> Int -> STM () release res nr = do n <- readTVar res writeTVar res (n + nr)
３．食事する哲学者
Computational Thoughtsには食事する哲学者の問題が例として出ている。
食事する哲学者の問題は、1965年にダイクストラが提示したもので、以下の通りである。5人の哲学者は円卓についてまま、思索を巡らしたり食事をとったりしている。円卓の中央にスパゲッティが置かれている。食事をするときは、哲学者の左右におかれたフォークの両方を必要とする。不幸なことに、隣り合う哲学者の間にはフォークは一本しか置かれていない。ある哲学者が食事をしているときは、その両隣の哲学者は食事をしている側の人との間にあるフォークをとることができない。このため、この哲学者たちは食事をとることができない。このような状況ではデッドロックに陥ることがある。例えば、すべての哲学者が左側のフォークをつかんでしまったとすると、誰も食事をすることができない。哲学者たちがうまく食事をとれるようにしなさいというのがこの問題である。一つの解法は、Computational Thoughtsに掲載されているが、この問題を独自に解きなさい。
なお、この問題を解くにはSTMのモジュールと乱数発生のモジュールを必要とする。これらは、以下でロードできる。
import System.Random import Control.Monad import Control.Concurrent import Control.Concurrent.STM
