プロセスの同期と反発の概念を簡単に説明します

転載先http://www.cnblogs.com/CareySon/archive/2012/04/14/Process-SynAndmutex.html
概要
    プロセス同期はオペレーティングシステムレベルの概念であり、複数のプログラムの環境下で、異なる制約関係が存在し、このような相互制約の関係を協調し、資源共有とプロセス協力を実現するために、プロセス間の衝突を回避し、プロセス同期を導入した.
 
りんかいしげん
    オペレーティングシステムでは、プロセスはリソースを占有する最小単位です(スレッドはプロセス内のすべてのリソースにアクセスできますが、スレッド自体はリソースを占有していないか、必要なリソースをわずかに占有しています).しかし、一部のリソースでは、同じ時間に1つのプロセスにのみ使用できます.これらが一度に1つのプロセスにのみ占有されるリソースは、いわゆる臨界リソースである.典型的な臨界リソースとしては、物理的なプリンタや、ハードディスク(HDD)やメモリで複数のプロセスで共有されている変数やデータなどがあります(このようなリソースが臨界リソースとして保護されていない場合、データが失われる可能性があります).
    臨界リソースへのアクセスは、相互に訴える必要があります.すなわち、臨界リソースが占有されると、その出願の臨界リソースが解放されるまで、別の出願の臨界リソースのプロセスがブロックされる.プロセス内で臨界リソースにアクセスするコードは臨界領域となる.
    臨界領域へのアクセスプロセスは、次の4つのセクションに分けられます.
    1.エクステントへのアクセス:臨界エクステントがアクセス可能かどうかを確認し、アクセス可能であればステップ2に進み、そうでなければプロセスがブロックされる
    2.臨界区:臨界区で操作する
    3.退出区域:臨界区域が占用された標識を取り除く
    4.余剰領域:プロセスが臨界領域と関連しない部分のコード
 
プロセス間の同期と相互訴えの概念
 
プロセス同期
    プロセス同期もプロセス間の直接的な制約関係であり、あるタスクを完了するために確立された2つ以上のスレッドであり、このスレッドは、ある位置で作業順序を調整して情報を待機し、伝達するために生成された制約関係を必要とする.プロセス間の直接的な制約関係は彼らの間の協力に由来する.
    例えば、プロセスAは、プロセスBが生成した情報をバッファから読み出す必要があり、バッファが空である場合、プロセスBは、情報が読み取れないためにブロックされる.一方、プロセスAが生成した情報がバッファに格納されると、プロセスBが起動する.概念を図1に示す.
    
     図1.プロセス間の同期
 
     C#コードでプロセス間の同期をシミュレートします.コード1に示します.

 class ProcessSyn
    {
        private static Mutex mut = new Mutex();
        
        
        static void Main()
        {
            Console.WriteLine("  1      2    .......");
            Thread Thread1 = new Thread(new ThreadStart(Proc1));
            Thread Thread2 = new Thread(new ThreadStart(Proc2));
            Thread1.Start();
            Thread2.Start();
            Console.ReadKey();   
        }
       
        private static void Proc1()
        {
            mut.WaitOne();
            Console.WriteLine("  1    ....");
            Thread.Sleep(3000);
            mut.ReleaseMutex();//V  

        }
        private static void Proc2()
        {
            

            mut.WaitOne();//P  
            Console.WriteLine("  2    ....");
            mut.WaitOne();
        }
    }

    コード1.C#シミュレーションプロセス間の同期
 
    運転結果を図2に示す.
    
    図2.運転結果
 
プロセス反発
    プロセス反発はプロセス間の間接的な制約関係である.1つのプロセスが臨界領域に入って臨界リソースを使用する場合、別のプロセスは待たなければなりません.このプロセスは、臨界リソースを使用するプロセスが臨界領域を終了すると、ブロック状態を解除します.
    例えば、プロセスBはプリンタにアクセスする必要があるが、プロセスAがプリンタを占有している場合、プロセスBはプロセスAがプリンタリソースを解放するまでブロックされ、プロセスBは実行を継続することができる.概念を図3に示す.
    
     図3.プロセス間の反発
 
     C#シミュレーションプロセス間の反発で、ここでは5つのスレッドを起動しましたが、同じ時間に臨界リソースにアクセスできるスレッドは1つしかありません.コード2に示すように.

class ProcessMutex
    {
        private static Mutex mut = new Mutex();
        private const int numThreads = 5;
        
        static void Main()
        {
            
            for (int i = 0; i <= numThreads; i++)
            {
                Thread myThread = new Thread(new ThreadStart(UseResource));
                myThread.Name = String.Format("  {0}", i + 1);
                myThread.Start();
            }
            Console.ReadKey();
            
        }
        
        
        //  
        private static void UseResource()
        {
            //    P  
            mut.WaitOne();

            
            /*            */
            Console.WriteLine("{0}       ",
                Thread.CurrentThread.Name);
            Random r = new Random();
            int rNum = r.Next(2000);
            
            Console.WriteLine("{0}    ，     {1}ms", Thread.CurrentThread.Name,rNum);
            Thread.Sleep(rNum);

            Console.WriteLine("{0}       \r
",
                Thread.CurrentThread.Name);
            /*      */


            
            //    V  
            mut.ReleaseMutex();
        }
        //  
  


    }

    コード2.C#シミュレーションプロセス間の反発
 
     運転結果を図4に示す.
       
    図4.C#シミュレーションプロセス反発
 
臨界領域の反発を実現するための基本的な方法
 ハードウェア実装方法
    ハードウェアで臨界領域を実現する最も簡単な方法はCPUの割り込みをオフにすることである.コンピュータの原理から,CPUのプロセス切替は割り込みによって行う必要があることが分かった.割り込みを遮断すれば、現在のプロセスが臨界領域コードを順調に実行し、反発を実現することを保証することができる.この方法のステップは、割り込みを遮断する--臨界領域を実行する--割り込みを開く.しかし、これはよくありません.これにより、プロセッサがタスクを交互に実行する能力が大幅に制限されます.そして、割り込みを閉じる権限をユーザーコードに渡すと、ユーザーコードが割り込みを遮断してから開かないと、システムはひざまずいてしまうのではないでしょうか.
    ハードウェアの命令実装方式もあり、これは次に述べる信号量方式と同じである.しかし、ハードウェアによって実現されるので、ここでは詳しくは言いません.
 
信号量実現方式
    これも私たちがP V操作に詳しいことです.リソース個数を表す信号量Sを設定することにより、信号量SのPとVの動作によりプロセスの反発が実現される.
    PおよびV操作は、それぞれオランダ語のPasserenおよびVrijgevenから行われ、それぞれ占有および解放を表す.PV動作はオペレーティングシステムの原語であり,原子性を有することを意味する.
    P動作は、まず信号量を減少させ、プロセスがリソースを占有または待機することを示し、Sが0未満であるか否かを検出し、0未満であるとブロックし、0より大きいとリソースを占有して実行する.
    V動作はP動作とは逆の動作であり,まず信号量を増やし,リソースを占有または待機するプロセスが1つ減少したことを示す.次に、Sが0より小さいかどうかを検出し、0より小さい場合、Sリソースの使用を待つ他のプロセスを起動する.
    前述のC#シミュレーションプロセスの同期と反発は、信号量で実現されています.
 
いくつかの古典的な信号量を利用して同期を実現する問題
生産者-消費者問題
    問題の説明:生産者-消費者問題は古典的なプロセス同期問題であり、この問題はDijkstraによって最初に提案され、彼が提案した信号量メカニズムを実証するために使用される.このジョブでは、同じプロセスアドレス空間内で実行される2つのスレッドを設計する必要があります.生産者スレッドは、物品を生産し、消費者スレッドの消費のために空のバッファに物品を配置する.消費者スレッドは、バッファから物品を取得し、バッファを解放する.生産者スレッドが物品を生産する場合、空バッファが使用可能でない場合、生産者スレッドは、消費者スレッドが空バッファを解放するのを待つ必要がある.消費者スレッドが物品を消費する場合、満タンのバッファがなければ、消費者スレッドは新しい物品が生産されるまでブロックされる.
 
    ここで生産者と消費者は同期して反発する関係で、まず生産者が生産して、消費してこそ消費することができて、ここは同期の関係です.しかし、彼らの臨界領域へのアクセスは反発的な関係である.従って、バッファを同期するために3つの信号量emptyおよびfullが必要であり、mut変数はバッファにアクセスする際に反発するために使用される.
    C#シミュレーションによる生産者と消費者の関係をコード3に示す.

    class ProducerAndCustomer
    {
        //      
        private static Mutex mut = new Mutex();

        private static Semaphore empty = new Semaphore(5, 5);//     
        private static Semaphore full = new Semaphore(0, 5);
        //   -     
         static void Main()
         {
             Console.WriteLine("        ......");
             for (int i = 1; i < 9; i++)
             {
                 Thread Thread1 = new Thread(new ThreadStart(Producer));
                 Thread Thread2 = new Thread(new ThreadStart(Customer));
                 Thread1.Name = String.Format("     {0}", i);
                 Thread2.Name = String.Format("     {0}", i);
                 Thread1.Start();
                 Thread2.Start();
             }
             Console.ReadKey();

         }
         
         private static void Producer()
         {
             Console.WriteLine("{0}    ",Thread.CurrentThread.Name);
             empty.WaitOne();// empty  P  
             mut.WaitOne();// mut  P  
             Console.WriteLine("{0}        ", Thread.CurrentThread.Name);
                 Thread.Sleep(1000);
             mut.ReleaseMutex();// mut  V  
             full.Release();// full  V  
         }
         private static void Customer()
         {
             Console.WriteLine("{0}    ", Thread.CurrentThread.Name);
             Thread.Sleep(12000);
             full.WaitOne();// full  P  
             mut.WaitOne();// mut  P  
             Console.WriteLine("{0}     ", Thread.CurrentThread.Name);
             mut.ReleaseMutex();// mut  V  
             empty.Release();// empty  V  
         }
    }

   コード3.C#を使用して生産者と消費者の関係をシミュレートする
 
    運転結果を図5に示す.
    
     図5.生産者消費者C#シミュレーション結果
 
読者-ライターの質問
    問題の説明:
      1つのデータ・ファイルまたはレコード.データ・オブジェクトと総称され、複数のプロセスで共有できます.一部のプロセスでは、読み取りのみを「読者」と呼び、他のプロセスでは書き込みまたは変更を「ライター」と呼びます.
      規定:複数の読者が同時に1つの共有オブジェクトを読むことを許可するが、読者、ライターが同時に1つの共有オブジェクトにアクセスすることを禁止し、複数のライターが1つの共有オブジェクトにアクセスすることを禁止し、そうしないとBernstein同時実行条件に違反する.
    説明によって分析することができて、ここの読者と書く者は互いに反発して、書く者と書く者も互いに反発して、しかし読者の間は互いに反発しません.
    これにより,3つの変数を設定することができ,1つは読者の数を統計するために用いられ,もう2つは読者の数の読み書きに対する反発,読者と読者の書き手と書き手の反発に用いられる.コード4に示すように.

class ReaderAndWriter
    {
        private static Mutex mut = new Mutex();//              
        private static Mutex rw = new Mutex();//            

        static int count = 0;//    
        
        
        static void Main()
        {
            Console.WriteLine("      ......");
            for (int i = 1; i < 6; i++)
            {

                Thread Thread1 = new Thread(new ThreadStart(Reader));
                Thread1.Name = String.Format("    {0}", i);
                Thread1.Start();
                
            }
            Thread Thread2 = new Thread(new ThreadStart(writer));
            Thread2.Name = String.Format("    ");
            Thread2.Start();
            Console.ReadKey();


        }
        
        private static void Reader()
        {
            
            mut.WaitOne();
            if (count == 0)
            {
                rw.WaitOne();
            }
            count++;
            mut.ReleaseMutex();
            
            Thread.Sleep(new Random().Next(2000));//    1S
            Console.WriteLine("    ");
            
            mut.WaitOne();
            count--;
            mut.ReleaseMutex();
            if (count == 0)
            {
                rw.ReleaseMutex();
            }

        }
        private static void writer()
        {
            
            rw.WaitOne();
            Console.WriteLine("    ");
            rw.ReleaseMutex();
    
        }

   コード4.C#読者とライターの問題をシミュレート
 
    運転結果を図6に示す.

    図6.読者ライターの運転結果
 
哲学者の食事問題
    問題の説明:
    5人の哲学者がいて、彼らの生活様式は交互に思考と食事をしています.哲学者たちは円卓を公用し、周りに椅子を5つ置いて、一人一人が座っている.円卓には5つの茶碗と5本の箸があり、哲学者が考えている間に、他の人と話をしないで、飢えている間に左、右で最も彼に近い箸を取ろうとしたが、彼は1本も持てないかもしれない.彼が2本の箸を手に入れた時だけ、食事ができて、食事が終わった後、箸を置いてまた考え続けます.
    
    図7.哲学者の食事問題
 
    問題の記述によると、5人の哲学者はそれぞれ5つのプロセスと見なすことができる.5本の箸はそれぞれ5つの資源と見なされている.哲学者がそれぞれ左右の資源を持っているときだけ、食事をすることができます.ルールを指定しなければ、哲学者一人一人が箸を1本しか持っていないとデッドロックになり、5人の哲学者がご飯が食べられないので飢え死にする.だから私たちの策略は哲学者に同時に箸を2本持たせることです.したがって、コード5に示すように、リソースごとに信号量を設定する必要があります.また、哲学者が同時に2つの箸を持って反発信号量を設定する必要があります.

class philosopher
    {
        private static int[] chopstick=new int[5];//        5   
        private static Mutex eat = new Mutex();//               
        static void Main()
        {
            //          
            for (int k = 1; k <= 5; k++)
            {
                chopstick[k - 1] = 1;
            }
            //           
            for(int i=1;i<=5;i++)
            {
                Thread Thread1 = new Thread(new ThreadStart(Philosophers));
                Thread1.Name = i.ToString();
                Thread1.Start();
            }
            Console.ReadKey();
        }
        private static void Philosophers()
        {
            
            //       ，   2 
            while (chopstick[int.Parse(Thread.CurrentThread.Name)-1] !=1 || chopstick[(int.Parse(Thread.CurrentThread.Name))%4]!=1)
            {
                Console.WriteLine("   {0}    ", Thread.CurrentThread.Name);
                Thread.Sleep(2000);
            }
            eat.WaitOne();
            //        
            chopstick[int.Parse(Thread.CurrentThread.Name)-1] = 0;
            chopstick[(int.Parse(Thread.CurrentThread.Name)) % 4] = 0;
            eat.ReleaseMutex();
            Thread.Sleep(1000);
            Console.WriteLine("   {0}    ...",Thread.CurrentThread.Name);
            //         
            chopstick[int.Parse(Thread.CurrentThread.Name)-1] = 1;
            chopstick[(int.Parse(Thread.CurrentThread.Name)) % 4] = 1;
            Console.WriteLine("   {0}    ，    ", Thread.CurrentThread.Name);
        }
    }

    コード5.C#シミュレーション哲学者の食事問題
 
    運転結果を図7に示す.
    
    図8.哲学者問題の実行結果
 
 
まとめ
    本論文では,プロセスの同期と反発の概念,臨界領域の概念,およびプロセスの同期反発を実現する方法を紹介し,同期を実現する3つの古典的な問題を解決し,対応するC#シミュレーションコードを与えた.オペレーティングシステムのプロセス管理はコンピュータプログラミングの基礎の一つであるため、この概念を身につけると、あなたの内功をさらに向上させることができます:-D