[OS] Scheduling2

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

priority scheduling과 유사하다. 계속 context-switch가 일어나지 않게 cpu-bound가 large quantum을 process한다.

** I/O bound process takes over CPU for using it. And change it to Blocked state
-> I/O ready state로 바뀌었다 같은 class로 들어온다.

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

메카니즘과 policy를 분리한다. 이전의 scheduling 알고리즘은 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
priority setting 가능하게 system call 하여 argument에 값을 준다.

Thread scheduling in user level

• High performance
• Possible scheduling of user level thread

  - 50-msec process quantum
  - threads run 5 msec/CPU burst

  process간에 왔다 갔다 불가능하다.

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의 존재를 알고 있다면 process간 이동하면서 수행할 수 있다.