Operating Systems Concurrency Quiz

Concurrency

• Operating systems architectures are covered
• Process life cycle is discussed
• Process execution is detailed
• Scheduling techniques are explained
• Threads are examined
• Process synchronization including mutual exclusion and critical sections is covered
• Semaphores are detailed
• The Producer-Consumer problem is explained
• Deadlocks are examined, including circular wait
• The Dining Philosophers problem is provided as an example
• Different scheduling algorithms including FCFS, SJF, SRT, HRRN, and Round Robin are discussed
• Multi-level queue scheduling algorithms are explained
• An overview of distributed systems and scheduling is given

Operating Systems Architecture (Windows)

• The architecture of Windows operating systems is shown graphically
• User-mode and Kernel-mode layers in the architecture are displayed
• Different functionalities of the layers are described
• The key components within each layer are identified
• The architecture of Linux Operating Systems is shown graphically
• The key components of the Linux kernel are identified and described
• The components of the Minix operating system architecture are displayed

Operating Systems Structure (Minix)

• The architecture of the Minix operating system is displayed
• The layers and their functionality are described
• Processes in the bottom layer can use privileged kernel-mode instructions

Areas of the Kernel Covered in this Topic

• Processes and threads are covered
• Process life cycle is examined
• Process execution is explained
• Process scheduling is detailed
• Inter-process communication and sharing
• Critical sections are examined
• Semaphores are detailed
• Buffers are described

Programs and Processes

• A program is the code written by a programmer
• A process is a program in execution
• Data are stored values used for computations
• Multiple instances of the same program code may be executable
• Processes use their address space to store program instructions

Process Life Cycle

• A process can be created by executing a program via a GUI or console command, (e.g. double-click or typing commands) or through spawning/forking by another process.

• The process creating the new process is the parent, and the new process is the child

• This forms a tree of processes

Process Life Cycle - Process Table

• Every process is given a unique process identification number (PID)
• A Process Control Block (PCB) is created, holding information about the process
• The components of a PCB are listed
• Process states and their respective queues (ready, running, and blocked) are described graphically
• Information in each process control block in the table is listed

Process Life Cycle - Process Descriptors

• Fields in process management, memory management, and file management are presented and explained.
• Specific examples within the MINIX system are used

Process Life Cycle - State Queues

• Processes have states: ready, running, blocked.
• Processes are managed in queues according to their state
• Queues for each state are presented

Process Life Cycle - Three State Model

• Detailed description of three process states
• Relevant states are ready, running, and blocked
• States are stored in the PCB

Process Life Cycle - Process Termination

• Voluntary termination includes processes completing their work (normal exit) or reporting errors (error exit)
• Involuntary termination details scenarios such as OS-detected errors and process termination at the request of another process.

Process Execution - Fetch-Execute Cycle

• The basic steps (fetch, execute, terminate) of processor process execution are described.
• Context about processors execution of programs is presented

Process Execution - Interrupts

• Description of interrupts and their functions
• Types of causes for interrupts (I/O, timer, program, etc.)
• Interrupts switch execution between tasks
• Execution of interrupts is facilitated by the interrupt handling routine

Process Execution – Updated Fetch-Execute Cycle

• Diagrammatic description of the fetch-execute cycle.
• Handling of interrupts is described with a flow diagram.

Concurrency

• A single-core processor can only execute one instruction at a time
• Execution of a process continues until the thread requires I/O or an interrupt
• Interruption to a user process lets the OS control execution
• The program's concurrent execution is called multitasking and does not require parallel execution

Process Scheduling - The Scheduler

• The scheduler controls process execution in response to events
• The scheduler determines whether or not a process should continue execution
• The steps for when the scheduler takes over are shown
• Context switches are needed to switch between tasks

Process Scheduling - Scheduling

• CPU utilization and efficiency are maximized
• Fair treatment is provided to all users

Process Scheduling - Scheduling Policies and Algorithms

• Non-preemptive and preemptive scheduling is outlined
• Different types of scheduling algorithms like priority based, first come first served, shortest job first etc are presented

Process Scheduling - Scheduling Algorithms - Case Study

• Process data tables to track arrival time, service time, waiting time
• Case study example data is provided

Process Scheduling Algorithms - FCFS/FIFO

• Scheduling policy for first-come, first-served (FCFS) or first-in, first-out (FIFO) ordering is given.
• Details of scheduling criteria and job processing order are clarified
• The job processing sequence is shown in a graph example

Process Scheduling Algorithms - SJF

• Selection of jobs with the shortest estimated run time is given as the scheduling criterion
• Favoring short jobs, and potential starvation of longer jobs is described

Process Scheduling Algorithms - SRT (Shortest Remaining Time)

• A preemptive-based scheduling algorithm is described, favoring short jobs.

• Potential starvation of long jobs is a consideration

Process Scheduling Algorithms - HRRN (Highest Response Ratio Next)

• Algorithm derivation is based on SJF and avoids bias against long jobs
• Priority assignment is based on a weighting formula.
• Priority changes are possible when new jobs are introduced

Process Scheduling Algorithms - Round Robin

• Time quantum assignment for processes is a key feature
• When a process exceeds the time quantum it is interrupted
• Context switching overhead is a factor in the algorithm's performance

Process Scheduling - Multi-Level Queues

• Multi-level queues are organized by groups of processes.
• Priority is assigned to these groups
• I/O jobs versus CPU jobs are separated

Distributed Systems and Scheduling

• Distributed systems introduce complexities to scheduling, particularly in coordinating processes across geographically dispersed locations
• Various scheduling methods for distributed systems are detailed

Threads

• Threads are sequential execution paths within a process
• A process is typically executed as a single thread, although situations can benefit from splitting the process up into multiple threads
• Multi-threading allows more efficient and usable programs

Threads vs Processes

• Threads and process properties are similar
• Threads share process properties
• Threads can be faster to create

Threads vs Processes (comparison)

• Differences between threads and processes in terms of properties and resources
• Lists features of Threads and Processes, providing a table comparison

Threads – Concurrent Vs Sequential Programming

• Sequential programming executes instructions in a sequence.
• Concurrent programming takes advantage of concurrency or splitting a program up into different executing parts
• Concurrent programming utilizes multiple threads running parallel in a single CPU system or on multiple CPU systems

Sequential Execution - Order and Precedence

• Sequential execution sequences are ordered
• The order of instructions is important and determined by the user or program

Sequential Execution - Order and Precedence (High-Level)

• An example from a high-level programming language, where the order of statements affects the result is included
• Importance of order is highlighted

Sequential Execution - Order and Precedence (System-Level)

• Compilation of high-level instructions into multiple machine instructions is described
• Instruction execution steps are detailed

Sequential execution – The Nature of Sequential Execution

• The processing steps are described, highlighting the deterministic nature of sequential execution
• Sequential approach always generates the same result

Concurrent Execution - Interleaving

• In single-core systems, threads in a concurrent program are interleaved in unpredictable order
• The ordering of operations is in each thread, but not in the interleaved executions

Concurrent Execution - Interleaving (further explanation)

• Example program run with multiple threads is provided.
• Different execution sequences (interleavings) are highlighted to emphasize unpredictability

Concurrent Execution - Thread Interference

• In multi-threaded applications output can be unexpected due to the ordering of thread operations
• There are several possible methods that might occur during interleaving

User and Kernel Threads - User Threads

• User-level threads are handled by a thread library; the kernel is unaware of them
• Switching between user-level threads is fast.
• If one thread is blocked, all threads in the process are blocked

User Threads and Kernel Threads - Kernel Threads

• Kernel-level threads operate directly with the operating system.
• Thread creation is slower
• If one thread is blocked another thread can still be executed.
• Parallel execution on multiple CPUs is supported

Multi-threading models - Thread Mapping

• Thread scheduling on multiple processors varies
• Thread mapping mechanisms of multi-threading are presented
• Different methods for thread mapping are described

Mutual Exclusion on Critical Sections

• Code sections requiring single-process access are critical sections.
• Race conditions arise from simultaneous attempts to access a single resource
• Mutual exclusion ensures an orderly solution to accessing a single resource and avoid race conditions

Race Conditions (examples)

• Example 1: Processes race to access a single register or memory location
• Example 2: Processes race to access shared resources like a printer or a file

Mutual Exclusion with Semaphores

• Semaphores use integer values to control resource access, allowing only one process at a time into a critical section.
• A single-process operation.
• Wait (wait) and Signal (signal) operations for Semaphores are described.
• Semaphores for various use cases are explored, emphasizing the single-process operations

Semaphores in Distributed Systems

• Semaphores are used to control resources in distributed systems

The Producer-Consumer Problem

• The producer-consumer problem describes a scenario where a producer creates data and a consumer consumes it.
• Requirements specify a FIFO buffer.
• The problem's complexity increases with multiple producers or consumers

Deadlocks

• A deadlock is a situation where two or more threads are blocked indefinitely, waiting for each other to release resources that they hold.
• Four conditions for a deadlock to occur are identified (mutual exclusion, hold and wait, no preemption, circular wait)
• Deadlock situations are shown as graph examples

The Dining Philosophers Problem

• The dining philosophers problem illustrates the challenges of concurrent processes competing for shared resources.

• Requirements specify mutual exclusion (each philosopher can only use two forks).

• Potential for deadlock is presented

• A solution of the problem using semaphores to overcome the deadlock is provided

Memory Management

• Memory and its management within the operating system were a consideration.
• Several factors contributing to memory management
• Directed study activities were presented to learn about the topic