CS 111 Lecture 7 4/23

By: Kacey Ryan, Greg Futami, Nick Westman, Alex Sanciangco

 Access to time / CPU

• Many apps want the CPU, we must decide which ones get it
• The number of apps <= The number of CPUs --> EASY
• The number of apps > The number of CPUs --> HARD (er)
• Ask Yourself:
  • Are they cooperative? (share CPU)
  • Or are they hostile, don't work along, try to take the CPU
  • The answer will affect how you design scheduling algorithm
• Answer:
  • Usually, YES they are cooperative (for embedded systems)
  • Unfortunately, in the general case, you have to assume NO
    • Example: SEASnet (they serve hundreds of students in different courses at random times)

 Threads (Review from last time)

• Like processes except that they share memory
  • They share "as much as possible" without stepping on each others' toes

• POSIX threads
  • int pthread_create(pthread_t * threadid, pthread_attr_t const * attar, void *(*pfn)(void*), void * arg);
    • Creates a new thread
    • Arguments: pointer where thread will be stored, attributes, function, arguments
    • Like fork or posix_spawnvp
  • int pthread_join(pthread_t threaded, void * status);
    • wait for another thread
    • Like waitpid
  • int pthread_exit(void * status);
    • Exit the thread
    • Like _exit

• In linux, don't consider "apps <= CPUs", rather "threads <= CPUs"
• It's possible to have an application that doesn't like threads
  • One thread per process
  • pthread_create fails!

Scheduling the CPU (solving the above "hard" problem)

• Things to solve:
  • Dispatch mechanism - a way of actually switching from one thread to another
    • Often OS or machine specific
  • Scheduling Policy - policy for decided when to switch
    • Tend to be sharable among Operating Systems
• Assume 1 CPU for now…

  
  The figure above shows the tasks of the CPU per thread and the scheduler with respect to time.

  • Going from one thread to another is really 2 transitions:
    • Thread1 --> scheduler --> Thread2
  • Threads run in user-mode: can't run system operations
  • Scheduler runs in kernel mode
  • When considering dispatch mechanism, switching from scheduler to thread is easy
    • RTI function for sys calls, for example
  • Assuming cooperative threads:
    • A cooperative thread occasionally calls the schedulers, periodically volunteers to give up the CPU… nice guy!
      • e.g. yield()
  • Another method:
    • Call the scheduler at every sys call
      • This often suffices, but…
        • buggy applications
        • CPU-intensive loops with no system calls
        • We need a better way of doing this…
    • Timer interrupt
      • Trap once every…(10ms for example)
      • Motherboard sends CPU a signal
      • CPU traps (like INT instruction)
      • Saves thread state, registers, etc.
      • Scheduler can run in between any line of machine code
      • RTI (Runtime Interrupt)
      • Can put interrupts (or rather possible interrupts) between assembly code functions
      • What if we set the timer to 10s rather than 10ms?
        • + less overhead
        • - latency increases
      • What if 10 miroceconds instead?
        • + latency decreases
        • - more overhead

Scheduling Issues

• Scale
  • Longterm: which processes or threads will be admitted to the system?
  • Medium term: which processes or threads reside in RAM?
    • It's possible they don't all fit in RAM at once
    • The ones that are in RAM then will run faster
    • The decision "which process to put in RAM" is an important part of scheduling
  • Short term: which runnable thread
• Multiple Scheduling Algorithms
  • one for long, one for short, etc
• OR application classes (each application is in own class)
  • e.g. system, interactive, batch user, or student (SEASnet)
• Realtime scheduling
  • operating ON TIME (timely behavior) is big part of program
  • Hard realtime
    • e.g. pace maker, brake system of car, controller of nuclear power plant
    • applications cannot miss deadlines
    • predictability is more important than CPU performance
      • unoptimized bubble sort (always same time)
      • don't use cache
      • "Its a different world!" (Swapping speed for predictability)
    • use polling, not interrupts / traps
  • Soft realtime
    • e.g. video playback
    • some deadlines can be missed, at some cost
    • example policies:
      • earliest deadline 1st
      • deadline > current time
      • give up otherwise
    • rate-monotonic scheduling
      • assign higher priority to tasks that run more frequently
      • but overall load doesn't exceed CPUs

How to measure quality of a scheduler

The figure above shows measurements for scheduling, metrics which were pulled from classic manufacturing.

• Things to worry about:
  • Expected (average) times
  • worst-case times
• Utilization:
  • percentage of time the CPU is doing useful work
• Throughput:
  • Rate of useful work being done
• Fairness
  • give each request a "fair" share of service
    • "fair" is debatable
  • but at least no request should starve
  • avoid starvation!

Types of Schedulers

1. First Come First Serve (FCFS / FIFO)
   • Earliest arrival time is chosen
   
   

   Job	Arrival	Run	Wait	Turnaround Time
   A	0	5	0	5
   B	1	2	4+S	6+S
   C	2	9	5+2S	14+2S
   D	3	4	13+3S	17+3S

   let S=scheduling time

   Average run time: 5
   Average wait time: 5.5 + 1.5S
   Average turnaround time: 10.5 + 1.5S
   
   + fair
   - convoy effect (long/slow jobs slow down shorter jobs after it)
   

   
   
2. Shortest Job First (SJF)
   • Minimizes and optimizes average wait time
   • BUT: if little jobs keep coming in and theres a big order, big jobs will starve
   
   

   Job	Arrival	Run	Wait	Turnaround Time
   A	0	5	0	5
   B	1	2	4+S	6+S
   C	2	9	9+3S	18+3S
   D	3	4	4+2S	8+2S

   let S=scheduling time

   Average run time: 4.25
   Average wait time: 5.5 + 1.5S
   Average turnaround time: 9.25 + 1.5S
   
   + optimizes wait time
   - fairness issue (big jobs can starve)
   

3. Priority scheduling
   • associated each job is a priority
     • priority 1 --> highest priority
     • priority 2 --> less
     • num ^ is called niceness
     • $nice --> can change niceness of process
   • External priorities - set by user
   • internal priorities - set by scheduler
   • FCFS: priority = arrival time
   • SJF: priority = run time
   • FCFS + SJF: priority = arrival time + run time
   • Linux: priority = niceness + …
4. Preemption + scheduling
   • wait time is even less than SJF
     • (wait response time better!)
   • utilization thought put goes down because the deltas add up