Clever Geek Handbook

シンプルなOSスケジューラモデル

少し前に、ここでWindowsスケジューラーに関する情報を見つけようとしましたが、驚いたことに、一般的なスケジューラーに関する具体的なものは何も見つかりませんでした。そこで、このスケジューラーの例をここに投稿することにしました。 コードは、8086アセンブラーインサートを使用してTurbo Pascalで記述されています。



スケジューラは実際に何を計画していますか？


スケジューラ-タスク、スレッド、プロセスの（疑似）並列実行を担当するオペレーティングシステムの一部。 スケジューラは、スレッドのプロセッサ時間、メモリ、スタック、その他のリソースを割り当てます。 スケジューラーは、スレッドから強制的に制御を取得することができます（たとえば、タイマーまたは優先度の高いスレッドが表示されるとき）、または単にスレッド自体を明示的に（システムプロシージャを呼び出すことによって）または暗黙的に（完了時に）スケジューラーに制御を与えるまで待機します。

スケジューラの作業の最初のバージョンは、リアルまたはプリエンプティブと呼ばれ、2番目のバージョンは、それぞれプリエンプティブではありません。



スケジューリングアルゴリズム


いくつかのプリエンプティブおよび非プリエンプティブスケジューラアルゴリズムがあります。 最初に、どちらのメカニズムが優れているかを把握しましょう。 一見すると、プリエンプティブマルチタスクがノンプリエンプティブよりも常に優れていることは明らかです。 しかし、これは完全に真実ではありません。 ノンプリエンプティブなマルチタスキングは、問題を切り替えたり、準備したり、待機したりするのではなく、プロセッサが常に問題の解決に専念する必要がある場合に、混雑の大きなスタートを切ります。 例は、バッチ処理システムです。 また、最新のユーザーOSでは、プリエンプティブマルチタスクなしでは想像するのが困難です（Windows NTのリリース前は、誰もがそれなしで実行できました）。

したがって、主要な非プリエンプティブレイアウトアルゴリズムを検討します。



最初のものに関しては、すべてが明確だと思います。最初のものが来た-最初の左です。 最も単純なアルゴリズムですが、残念ながら、最も効率的なアルゴリズムではありません。1つのスレッドに誰かのキロメートルが統合されているため、他のスレッドは2つの数字を加算するのに1時間待つ必要があるためです



効率を向上させる明白な方法は、キュー内の短いスレッドをスキップすることです。 そのため、最初に計算する必要のあるすべてのフロー2 * 2が実行され、その後、そのキロメートル積分が計算されます。 確かに、ここにも欠点があります。たとえば、入力/出力のために中断された長いストリームは、キューの最後に再び配置されます。

3番目のアルゴリズムは、この状況を排除します。現在、最短時間を必要とするスレッドがキューの先頭に配置されます。

バッチ処理システムでは、通常、3つのレベルのスケジューリングが使用されます。最初は、タスクキューがディスクメモリに形成され（メモリスケジューリング）、そこからストリームがメインメモリに入り、上記のアルゴリズムのいずれかが並べられます。 ここでは、プロセスが多すぎる状況が発生し、一部のプロセスがディスクに戻されます（アクセススケジューラー）。 実際、3番目のスケジューラ（プロセススケジューラ）は、スレッドのプロセッサ制御へのアクセスを整理しています。

明らかなこと-非プリエンプティブマルチタスクは、ユーザーアクションへの即時応答が必要なオペレーティングシステムには適していません。 さらに、このようなメカニズムでは、プログラマがシステムの内部構造を理解する必要があり、プログラムの動作だけでなく、システム全体の動作にも責任を割り当てます。 結局のところ、1週間システムをハングさせたとしても、だれもあなたの製品を使いたくありませんよね？

いくつかのプリエンプティブレイアウトアルゴリズムを検討します。



最初のアルゴリズムは、キューの直接的な類似物です。つまり、これはキューです。最初に来た-最初にタイムスライスを受信し、再びキューの最後に立っていました。 1つの明らかな、しかし非常に迷惑なマイナスは、時間クォンタムの1/10を使用するストリームは、クォンタム全体を使用するストリームと同じくらいのプロセッサー時間を持つことです。

2番目のアルゴリズムはこの問題を解決します。各スレッドには、使用されるクォンタムの割合に反比例する優先順位が割り当てられます。 優先度の高いスレッドが先にキューに入れられます。

3番目のアルゴリズムは、ユーザー要求の処理が最前線にある対話型（サーバー）オペレーティングシステムに一般的です。 優先フローは、実行するタスクに応じて割り当てられます。 ここでは、たとえば、httpリクエストの処理が最高の優先度を持ち、オペレータコマンドの処理などがわずかに少なくなります。このアルゴリズムを使用すると、ストリームへの制御のまれな転送を補充し、より大きなタイムスライスを割り当てることができます。 そのため、優先順位が低く、キュー内で最長の可能性があるスレッドは、ほとんどのプロセッサー時間を受け取ります。

プリエンプティブマルチタスクでは、プログラマがスケジューラの複雑さを理解する必要はありませんが、落とし穴もあります。



クリティカルセクション


プロセッサ時間またはスタックを使用すると、すべてが単純に思えますが、スレッドが子猫をプリンタなどで印刷する必要がある場合はどうでしょうか？ しかし、そのようなフローが2つある場合はどうでしょうか？ 非プリエンプティブマルチタスクでは、すべてが時計仕掛けのようになります。1つのスレッドが子猫を出力し、終了してスケジューラに制御を与え、2番目のスレッドが印刷できるようにします。 ただし、マルチタスクがプリエンプティブである場合、スケジューラーはスレッドが印刷を完了していないときにスレッドを切り替えることができ、次のようになります。



これを防ぐために、クリティカルセクションのメカニズムが導入されています。 いくつかの非共有リソースが占有したいスレッドは、これについてスケジューラーに通知します。 リソースが別のスレッドによってまだ占有されていない場合、スケジューラーはスレッドが動作し続けることを許可し、リソースをビジーとしてマークします。 リソースがビジーの場合、スレッドはキューに置かれ、そこで空きになるのを待ちます。 そのようなリソースでの作業が完了すると、スレッドは、他のスレッドがリソースを使用できるようになったことをスケジューラに通知する必要があります。 これらの2つのアクション：リソースを奪取しようとする試み、およびリソースを使用した作業の終了に関するメッセージは、クリティカルブラケットと呼ばれます。 ちなみに、それらの不適切な配置では、フローの相互ブロッキングの状況が発生する可能性がありますが、これは常に十分かつ迅速に診断されるわけではなく、製品のリリース後に開発者とユーザーからのあいまいな非難を引き起こす可能性があります。



デッドロック


分割されていないリソースAおよびBと、これらのリソースを使用するフローX、Yがあるとします。 特定の曲がりくねった能力の不十分なプログラマーが次のような重要な括弧を付けた場合：

...

ストリームx

リソースを取る（A）

リソースを取る（B）

...

リソースを与える（A）

リソースを提供（B）

ストリームy

リソースを取る（B）

リソースを取る（A）

...

リソースを提供（B）

リソースを与える（A）



しばらくすると、この状況が発生します。





甘い


まあ、実際にはそれがすべて書かれたもののために。 すでに述べたように、プランナーのコードはTurbo Pascalで実行されます。

クリティカルセクションのメカニズムは、EnterCritical（）、LeaveCritical（）の各手順で実装されています。 もう一度思い出してください。クリティカルセクションに入るには、ビジーかどうかを確認し、その結果、スレッドを使用してスレッドを使用できるようにするか、ストリームをキューに入れて他の誰かに制御を転送する必要があります。 

procedure EnterCritical(num:TCriticalNum); {   } begin asm cli end; if num<=maxCritical then begin if criticalTable[num]<>0 then begin inc(criticalTableWait[num]); {    } while criticalTable[num]>0 do begin {   -} {       } asm sti end; SwitchThreads; asm cli end; end; dec(criticalTableWait[num]); end; criticalTable[num]:=1; end; asm sti end; end;


LeaveCritical（）を使用すると、すべてが明確になります。 

 procedure LeaveCritical(num:TCriticalNum); {  } begin asm cli end; if num<=maxCritical then criticalTable[num]:=0; asm sti end; if criticalTableWait[num]>0 then { -  } switchThreads; end;


フローを切り替える手順は、アセンブラー挿入を使用して記述されているため、マシンコマンドの精度でフローを切り替えるタイミングを確認できます。 

 procedure TimerHandler(flags,cs,ip,ax,bx,cx,dx,si,di,ds,es,bp:word); interrupt; {         ,            } const ThreadNumber:byte=0; const NumPrev:byte=0; const tsoffset:word=0; mainSP:word=0; mainSS:word=0; begin if not DisableHardwareEvents then begin asm pushf end; oldvec8; {     .    .} end; if preemptiveSwitch or DisableHardwareEvents then if (ThreadsRegistered>1) or (parallelStart) then begin {   } asm cli end; if ParallelStart then begin {     } StepCount:=0; asm mov ParallelFinished,false {  } mov mainsp,bp {      } mov mainss,ss {  } end; end; inc(StepCount); if {ts[ThreadNumber].active and} not ParallelStart then begin {   () .      ParallelStart, .. ,        } {      } tsoffset:=ThreadNumber*sizeof(TThreadStateWord); asm push ds { ,    DS     !} mov ax,seg ts mov es,ax mov di,offset ts add di,tsoffset mov ax,ss mov ds,ax mov si,bp {ds:si   ,   } cld mov cx,12 rep movsw {    ( )} pop ds {es:di   24          } mov ax,bp {BP     12  } add ax,12*2 stosw {SP } mov ax,ss stosw {SS } end; end; {   } NumPrev:=ThreadNumber; repeat ThreadNumber:=(ThreadNumber+1) mod ThreadsRegistered; until (ThreadNumber=NumPrev) or TS[ThreadNumber].active; if ts[ThreadNumber].active and ((ThreadNumber<>NumPrev) or parallelStart) then begin {  ,     .     ParallelStart,       , ..  ,          0} tsOffset:=(ThreadNumber+1)*sizeof(TThreadStateWord) - 3; asm mov dx,ds mov ax,seg TS mov ds,ax mov si,offset TS add si,tsOffset {ds:si     } std lodsw mov ss,ax lodsw mov sp,ax mov bp,ax {    } sub bp,12*2 {       .          ,         } mov cx,12 @m1: lodsw push ax loop @m1 cld mov ds,dx end; end else if (not ts[Threadnumber].active) and (Threadnumber=NumPrev) then begin {  } setintvec($8,@oldvec8); asm mov parallelfinished,true mov ax,mainss mov ss,ax mov bp,mainsp mov sp,bp end; end; parallelstart:=false; end; DisableHardwareEvents:=false; end;


プロシージャ自体は、割り込みディレクティブを使用してコンパイルされます。つまり、割り込みハンドラです。 次のように、int 08hを呼び出すことで、ハードウェアとソフトウェアの両方をトリガーできます。 

 procedure SwitchThreads; begin if not parallelFinished then asm cli mov DisableHardwareEvents,1 int 08h sti end; end;




また、フローを含め、フローを停止する登録手順自体を記述することも必要です。 興味のある方は、ソースプロシージャRegistrThread、RunThread、StopThreadをご覧ください。

以上です！ プランナーの準備が整いました。

この計画とdosovsky turbik用に作成されたマルチスレッドプログラムの例とソースは、 ここからダウンロードできます 。 試してみて、プリエンプティブおよび非プリエンプティブマルチタスク（ExecuteRegisterThreads（true / false）プロシージャ）でスレッドがどのように実行されるかを確認し、デッドロック状況をシミュレートし、常に診断されないことを確認できます（デッドロックが発生するまで1分間待ちました）。

DOSboxから新しいWin98システムで実行することをお勧めします。


More articles:


All Articles