Please enable JavaScript.

Coggle requires JavaScript to display documents.

Scheduling (CFS (Completely Fair Scheduler) (Goal is to ensure that each…

- - - - Problems:
        
        Starvation. If there are "too many" interactive jobs in the system, they will combine to consume all CPU time. Long-running jobs will never receive any CPU time.
        
        A developer could abuse this system by performing I/O operations to stay on the highest priority queues
        
        If a job for the beginning of its lifecycle doesn't have much I/O operations it'll be put lower in the queue. This set up doesn't support programs that have I/O operations at a later point.
    - - This fixes 2 problems at once:
        
        Processes are guaranteed not to starve since all jobs will be put on the top-most priority queue and jobs @ the top run in an RR fashion
        
        If a CPU-bound job has become interactive, the scheduler will treat it properly once it has gotten a priority boost
    - - This prevents programs from taking advantage of the scheduler
- - - - Threads are loaded on a core and only run on that core
    - - Scales Well
        As the number of cores increases threads are not affected by contention
      - Cache Affinity
        Does not suffer from cache affinity since when a thread is scheduled for a job the CPU it was scheduled on is the only one it runs on
    - - Load Imbalance
        Queue's may have different lengths which results in load imbalance across cores. Cores with lighter loads may be idle. Threads on cores with lighter loads might get more running time than others
    - - Be able to move threads from one CPU to another
    - - Technique where a CPU queue peaks at other queues when its workload is less to see if it can steal jobs from other queues
  - - - There is a single ready queue that all the CPU's of a system share
    - - Simplicity
        We can extend single CPU policies to work with this scheme
    - - Doesn't scale well
        Since we need to use locks to provide security when accessing shared data increasing the number of jobs will increase contention
      - Cache Affinity
        Since a single ready-queue is being shared among multiple CPU's we have to do extra work to try and ensure threads are run on the same core they were previously run on.
- - - - Turnaround Time =
        Time at which the job completes -
        Time at which the job arrived
        (Performance Metric)
    - - Response Time =
        Time at which the job starts running -
        Time at which the job arrived
    - - The time it takes for a job to complete
    - - The time at which a job is added to the schedule queue
  - - - Advantages
        
        Simple and easy to implement
      - Definition
        
        Scheduling policy handles the first jobs that come in
      - Disadvantage
        
        Convey Effect
        FCFS doesn't work well when jobs have different run times. It has bad performance when shorted jobs are queued after a large job. Since the shorter jobs have to wait for the big one to finsih
    - - Definition
        
        Runs the shortest job first, then the next shortest, etc
      - Advantages
        
        Simple and easy to implement
      - Disadvantages
        
        Also suffers from the convey effect. Since jobs can arrive at anytime, if a big job arrives before the little ones SJF still suffers the same as FCFS
    - - Definition
        
        Schedules the job with the shortest remaining time. If a new process is added which has a lower remaining than the current process, the current process is preempted and the new process is run first
      - Advantages
        
        Doesn't suffer from Convey Effect since we can preempt
      - Disadvantages
        
        Can lead to longer times for jobs to complete if new jobs are added that have less run time than the currently running program
    - - Definition
        
        RR runs a job for a time slice (scheduling quantum) and then switches to the next job in the run queue
      - Advantages
        
        Leads to shorter response time since jobs are cycled more frequently with shorter time slices
      - Disadvantages
        
        Bad for turnaround time since jobs are only worked on in small increments, causing the time it takes for jobs to complete to increase.
        Also bad context switching is costly.