[OS] Scheduling2

4005 ワード
OS テキストリンク

Scheduling


Scheduling in Interactive systems

  • A scheduling algorithm with four proiority classes
  • A scheduling algorithm with four priority scheduling among the classes
    - Use round-robin scheduling within each class
  • As long as there are runnable processes in the higher prioriy class, just run each one for one quantum, round robin fashion
  • If priority are not adjusted occasionally, lower priority classes can all starve to death

    • Multiple queues


    CTSS

  • It's nore effiecient to give CPU-bound processes a large quantum.
  • But giving all processes a large quantum would mean poor resoinse time.
  • Sets up priority classes
    • 優先度スケジューリングと同様です.cpu-boundはcontext-switchの発生を避けるために大量のサブを処理する.
    ** I/O bound process takes over CPU for using it. And change it to Blocked state
    ->I/O ready stateを同じクラスに変更しました.

    Shortest Process Next(important)


  • minimum average response time

  • make estimates based on past behavior and run the process with the shortest estimated running time.
  • Ageing
  • Estimate: aT0 + (1-a)T1
  • T0 :estimated time per command
  • T1 :next run measured
    - with a = 1/2, we get successive extimates of
  • T0, T0/2+T1/2, T0/4+T1/4+T2/2 ,...

    • Guarenteed scheduling

  • with n processes running, each one should get 1/n of the CPU cycles
  • keeps track of how much CPU each process has had since its creation
  • computes
    ratio = actual CPU time consumed/CPU time entitled
  • runs the process with the lowest ratio until its ratio has moved above its closest competitor

    • Lottery scheduling


    Gives processes lottery tickets for various system resources, such as CPU time.

    Fair-share scheduling

  • previous scheduling

  • owner of the process not considered

  • in round robin
  • user 1 with 9 processes
  • user 2 with 1 process gets only 10 % of the CPU
  • takes into account who owns a process before scheduling it
  • user 1 with A, B, C, D:50%
  • user 2 with E :50%
    => AEBECEDEAEBE...

    • Scheduling in Real-time Systems


  • A real-time system must react appropriately to external events by the deadline

  • Having the right answer too late is often just as bad as not having it at all.

  • Hard real time - absolute deadlines must be met

  • Soft real time - misiing an occasional deadline is undesirable, but nevertheless tolerable.

  • Real time behavior - predictable

  • Events
  • Periodic :occuring at regular intervals
  • Aperiodic :occring unpredictably

  • Scheduling real-time system(important)
  • CPU being used by each process <= 1

    • Policy versus Mechanism


    機械主義と政策を分ける.以前のスケジューリングアルゴリズムはメカニズムの面で
  • separate what is allowed to be done with how it is done
  • a process knows which of its children are the most important
  • Scheduling algorithm parameterized
  • mechanism in the kernel
  • Parameters filled in by user processes
  • policy set by a user process
    • user process追加->parameter
    優先度を設定できるシステム呼び出しは、パラメータに割り当てられます.

    Thread scheduling in user level

  • High performance
  • ユーザレベルスレッド
    - 50-msec process quantum
- threads run 5 msec/CPU burst
    プロセス間での切り替えは不可能です.

    • Thread schduling in kernel level


  • A thread block on I/O doesn't suspend the entire process

  • Possible scheduling of kernel level threads
    	- 50-msec process quantum
  • threads run 5 msec/CPU burst
    • kernelがthreadの存在を知っている場合は、プロセス間を移動して実行できます.
    ゼロからAdaを学ぶ(入門)
    [プログラマー]紛失した記録を探す