Operating Systems: Processes

Process Model

• Multiprogramming allows multiple programs to run concurrently
• A process switch enables transitioning between processes
• A conceptual model consists of four independent, sequential processes
• Only one program stays active at any given moment

Process Creation

• System initialization starts processes
• A running process can make a system call to create another process
• A user can request a new process be created
• Initiation of a batch job creates processes

Process Termination

• Normal exit is a voluntary termination
• Error exit is a voluntary termination
• Fatal error is an involuntary termination
• It is possible for a process to be killed by another process involuntarily

Process States

• A process can be in one of three states at a time:
• Running: Currently using the CPU
• Ready: Runnable but temporarily stopped
• Blocked: Unable to run until an external event occurs
• A process can transition between running, blocked and ready states
• The lowest layer of a process-structured OS handles interrupts and scheduling
• Sequential processes reside above that layer

Implementation of Processes

• Process management includes registers, program counter, program status word, stack pointer, process state, priority, scheduling parameters, process ID, parent process, process group, signals, start time, CPU time used, children's CPU time, and next alarm time
• Memory management includes pointers to text, data, and stack segment information
• File management includes root directory, working directory, file descriptors, user ID, and group ID

Interrupt Handling

• A hardware stacks its program counter
• The hardware loads a new program counter from the interrupt vector
• Assembly language procedures save registers and sets up a new stack
• A C interrupt service reads/buffers input
• A scheduler decides which process to run next
• A C procedure returns to the assembly code
• Assembly language procedures start a new current process

Multiprogramming Model

• CPU utilization is a function of the number of processes in memory
• CPU utilization = 1 – p^n

Thread Usage

• A multithreaded Web server has a dispatcher thread, worker thread, and Web page cache
• The dispatcher thread gets requests and hands off work
• The worker thread waits for work, looks for pages in cache, reads from disk if needed, and returns pages

Threads vs Processes

• Threads feature parallelism with blocking system calls
• Single-threaded processes don't allow parallelism with blocking system calls
• Finite-state machines allow parallelism with nonblocking system calls and interrupts

Classical Thread Model

• Process describes any program that is in execution
• A process can have multiple threads inside it
• Each thread has its own stack
• Per-process items include address space, global variables, open files, child processes, pending alarms, signals and signal handlers, and accounting information
• Per-thread items include program counter, registers, stack, and state

POSIX Threads

• The Pthreads function calls include:
• Pthread_create: Creates a new thread
• Pthread_exit: Terminates the calling thread
• Pthread_join: Waits for a specific thread to exit
• Pthread_yield: Releases the CPU for another thread
• Pthread_attr_init: Creates/initializes a thread's attribute structure
• Pthread_attr_destroy: Removes a thread's attribute structure

Race Conditions

• Competition for shared memory leads to race conditions

Critical Regions

• To avoid race conditions:
  • No two processes can be inside their critical regions simultaneously
  • No assumptions can be made about CPU counts or speeds
  • No process outside its critical region can block other processes
  • No process should wait forever to enter its critical region
• Mutual exclusion makes use of critical regions

Mutual Exclusion with Busy Waiting

• Busy waiting with strict alternation can be a proposed solution to critical region problems

Producer-Consumer Problem

• Sleep and wakeup are used in the producer-consumer problem
• The producer generates and puts items in buffer, the consumer takes them
• Semaphores also solve the producer-consumer problem

Semaphores

• When using semaphores:
  • Mutex controls access to critical region
  • One counts empty buffer slots
  • One counts full buffer slots

Mutexes in Pthreads

• Mutexes in Pthreads offers function calls such as:
  • Pthread_mutex_init: Creates a mutex
  • Pthread_mutex_destroy: Destroys an existing mutex
  • Pthread_mutex_lock: Acquires a lock or block
  • Pthread_mutex_trylock: Acquires a lock or fail
  • Pthread_mutex_unlock: Releases a lock
• Pthreads calls relating to condition variables include:
  • Pthread_cond_init: Creates a condition variable
  • Pthread_cond_destroy: Destroys a condition variable
  • Pthread_cond_wait: Blocks waiting for a signal
  • Pthread_cond_signal: Signals another thread and wakes it
  • Pthread_cond_broadcast: Signals multiple threads and wakes them all
• Threads can be used to solve the producer-consumer problem

Process Behavior

• CPU usage alternates with I/O waiting periods
• A CPU-bound process mainly uses the CPU with few I/O waits
• An I/O-bound process spends a lot of time waiting for I/O

Scheduling Algorithm Categories

• Batch
• Interactive
• Real time

Scheduling Algorithm Goals

• All systems have to be fair, enforce policy, and keep the system busy
• Batch systems maximize throughput, minimize turnaround time, and keep the CPU busy
• Interactive systems have to respond quickly, and meed users expectations
• Real-time systems avoid losing data by meeting deadlines and avoid degradation by being predictable
• Average turnaround time vs Average wait time

Scheduling in Batch Systems

• Scheduling algorithms for batch systems:
  • First-Come First-Served
  • Shortest Job First
  • Shortest Remaining Time Next
• Preemptive vs. Non-Preemptive
  • Preemptive = Interrupting
  • Non-Preemptive = Not interrupting
  • Execution of a process only stops when completed

Shortest Job First

• The shortest jobs are scheduled first

Scheduling in Interactive Systems

• Interactive systems uses the following scheduling mechanisms:
  • Round-Robin Scheduling
  • Priority Scheduling
  • Multiple Queues
  • Shortest Process Next
  • Guaranteed Scheduling
  • Lottery Scheduling
  • Fair-Share Scheduling
• Preemptive or Non-Preemptive

Round-Robin Scheduling

• Each process is assigned a time interval, called its quantum, during which it is allowed to run
• If the process is still running at the end of the quantum, the CPU is preempted and given to another process

Priority Scheduling

• Each process is assigned a priority, and the runnable process with the highest priority is allowed to run

Scheduling in Real-Time Systems

• Time is essential
• Scheduling categories include:
  • Hard real time
  • Soft real time
  • Periodic or aperiodic m
  • Schedulable satisfies Σ≤1 i=1

Thread Scheduling

• User-level threads and kernel picks a process
• Kernel-level threads picks a thread

Dining Philosophers Problem

• Illustrates the challenges of resource allocation and concurrency control in operating systems
• Code given shows a faulty and correct implementation of solution

Readers and Writers Problem

• Models concurrent access to a database
• Shows code implementation