Multiprogramming

• way to improve cpu utilization
  • one process has to wait -> CPU can execute different process
• CPU utilization: $1 - p^n$
  • p := fraction of time spent wating for IO
  • n := degree of multiprogramming

The Scheduler

• handles interrupts and scheduling
• decides which process is run next

Interrupts

• signal that in event has occured that needs attention
  • e.g.: input ready, output complete, error condition, clock interrupts
• CPU checks interrupt-request line after each instruction
• an interrupt is detected:
  1. save machine state
  2. dispatch ISR
  3. return to interrupted process

Process Activity

• CPU-Bound: CPU speed is the limiting factor
• IO-Bound: IO-Wait times are the limiting factor

Direct Memory Access (DMA)

• the DMA controller facilitates memory transfers, the CPU only has to initiate the transfer
• DMA issues an interrupt uppon finished transfer

Cost of Context Switching

• saving and restoring the machine state takes time -> milliseconds!

Scheduling Strategies

• Non-Preemptive: each process runs until it is blocked of voluntariliy releases CPU
• Peemptive: context switch after maximum time slice is reached

Scheduling Environments

Batch

• used in business systems for big tasks
• non-preemptive scheduling or preemptive with long time slices -> less context switches
• Goals:
  • maximize throughput: jobs/hour
  • minimise turnaround time: average time one jops needs
  • high CPU utilisation

Scheduling Strategies for Batch Systems

First Come, First Served

• executes always in the order the processes where submitted

• easy implemented (linked list)

• problematic when mixing different types of processes (some processes need shorter response times)

Shortest Job First (SJF)

• executes process that has lowest estimated execution time

• provides optimal average turnaround times

Shortest Remaining Time Next

• preemptive version of SJF: executes process with the lowest estimated remaining execution time

• long processes may need to wayt very long

Interactive

• active users
• Goals:
  • minimise response time (turnaround) for processes the user interacts with directly
  • enforce proportionality: quick jobs complete fast | big jobs take longer

Scheduling Strategies for Interactive Systems

Round-Robin Scheduling

• each process gets timeslice called quantum
  • after quantum finished -> moves to the back of the queue
• selecting time of quantum assessment...

• easy to implement

Priority Scheduling

• each process has priority number $P$ (Lower is better) -> processes get sorted in seperate priority queues
• Process with lower $P$ get more quanta (always double of one higher) -> whole queue with lower $P$ gets processed first
• after process gets preempted it gets demoted to next higher $P$ (gets less execution time for the next cycle)

Multiple Queues

Shortest Process Next

• process with estimated shortest running time scheduled next
• estimation based on previous oversvations
  • $T_n = \alpha T_{n-1} + (1 - \alpha)T_{prev}$
    • $T_n$ runtime estimate for round $n$
    • $T_{prev}$ measured run time during previous round
    • $\alpha$ ageing parameter determining how quickly run times from older rounds are "forgotten"

• good for interactive processes following alternating pattern of command entry – execution

Guaranteed Scheduling

• each user out of $n$ users is guaranteed $\frac{1}{n}$ CPU time
• scheduler keeps track of used entitled time
• process with least used entitled time gets scheduled next

Lottery Scheduling

• processes get tickets
• scheduler chooses ticket randomly

Fair-Share Scheduling

• each user gets a specified fraction of CPU time, regardless of how many processes he has

Real-Time

• hard timing requirement
• Operation must complete in time
• Predictability: timings should be relatively consistent

Scheduling Requirements

• Fairnes: Each process with same priority gets same time
• Policy enforcement: follows specified rules
• Balance: whole system should always be busy | mix of computation bound & IO bound

Threads

• one process can have multiple threads
• enables parallelity in one process
• no need for shared memory, as threads share same memory space

POSIX Threads

• Pthread_create: Create a new thread
• Pthread_exit: Terminate the calling thread
• Pthread_join: Wait for a specific thread to exit
• Pthread_yield: Release the CPU to let another thread run
• Pthread_attr_init: Create and initialize a thread's attribute structure
• Pthread_attr_destroy: Remove a thread's attribute structure

User-Level Threads

• implemented entirely in user space | -> Operatin System does not need ability to handle threads
• process needs private thread table

• thread switchin in user space much faster

• problem with blocking syscalls

Kernel-Level Threads

• Thread Table managed by Kernel
• Thread creation and destruction have higher cost
• can manage block syscalls gracefully