Operating Systems: Fundamentals

• These notes cover the fundamentals of operating systems, including their definition, goals, components, functions, types, and related concepts like process management and synchronization

What is an Operating System (OS)?

• An OS is software that acts as an interface between user applications and hardware - CPU, Memory and I/O devices
• It plays the role of a resource manager by simplifying application development and execution
• It is a system program
• Examples include Windows, Linux, and Mac OS
• In short act like government

Goals of an OS

• User Convenience: How easily a user can interact with hardware
• Efficiency: How well the OS utilizes resources, evaluated in terms of throughput
• Throughput indicates the number of tasks executed per second
• User convenience is prioritized in Windows OS, while efficiency is secondary aim
• Efficiency is the primary goal of Linux OS, with user convenience considered secondary

Parts of an OS

• Consists of different modules (system programs)
• Shell: Used to interact with the kernel, generally through GUI or CLI
• Kernel: Consists of functions that define the functions of different modules of the OS.
• Each OS has a different kernel
• Some kernels have multiple shells; Windows and Linux support both GUI and CLI, while Linux generally support only CLI

System Call

• The way a user program interacts with the OS
• Involves a transition from Shell to Kernel.
• Implemented using functions like open(), read(), write(), load(), execute(), abort(), fork(), and get pid()
• This process involves two modes of operation: User Mode and Kernel Mode
• A mode bit is used to define whether the OS is in User Mode (1) or Kernel Mode (0)
• In kernel mode the executing program can access all resources

Functions of an OS

• Resource Management: Mapping hardware resources to multiple applications simultaneously.
• Process Management: How to run multiple processes on system hardware using CPU scheduling.
• Storage Management: How processes are stored in secondary memory using a file system like NTFS or FAT32.
• Memory Management: Storing processes and deciding which process to bring into RAM using multi-programming/tasking
• Security and Privacy: Authentication methods like passwords, user, and admin modes prevent interference between programs
• Accounting: Task manager

Types of OS

• Batch Processing OS
• Multiprogramming
• Multitasking
• Multiprocessing
• Real Time OS
• Embedded
• Distributed OS
• Typically consists of three components: CPU, Memory, and I/O.
• Resides in main memory (RAM)

Batch Processing OS

• This OS does not interact with the computer directly
• An operator takes similar jobs, groups them into batches, and sorts the jobs of similar needs
• Job completion time can be known and multiple users share the batch systems
• The operators are well-versed with batch systems
• Batch systems are hard to debug
• Other jobs will have to wait for an unknown time if any job fails

Multiprogramming OS

• Allows more than one program to reside in RAM to increase CPU Utilisation.
• Increasing the Degree Of Multi-programming increases the CPU utilization.
• Another process is scheduled to the CPU when a process leaves for I/O.
• Only one process is processed by CPU at a time
• Increases the throughput of the System and helps reduce the response time.
• Lacks user interaction with the system resources.

Multitasking OS

• A pre-emptive version of Multiprogramming and is a multiprogramming OS with a Round-Robin Scheduling Algorithm
• Runs multiple programs simultaneously, and has improved user responsiveness
• User interaction is one at a time

Multiprocessing OS

• Multiple CPUs reside in the system, and provides enhanced throughput and robustness
• Two types: tight coupled (shared memory) and loose coupled (each CPU using different memory)

Real Time OS

• Serve real-time systems in a small time interval called response time
• Used for systems that have strict time requirements, like missile systems, air traffic control systems, and robots.
• Two types: Hard RTOS (strict response time e.g. missile, airbag systems) and Soft RTOS (deadline has slight flexibility e.g. banking, streaming)

Distributed Operating System

• Autonomous interconnected computers communicate with each other using a shared communication network.
• Have their own independent memory unit and CPU and are referred to as loosely coupled systems or distributed systems.
• Provides high availability and robustness, scalable and load balanced
• Main downfall is synchronization

Embedded OS

• Designed for a specific purpose, is embedded in a machine to make them smart. E.g. Microwave, AC
• User interaction is minimal and is rigid in nature, not easily reprogrammed once developed

Process Management

• A program under execution. Initially, the program is stored in secondary memory.
• For execution, it has to be brought in Main memory. Text (current activity), Data(information), Stack (local variables) and Heap (dynamic memory allocation)
• Involves identifying the steps involved in completing a task, assessing the resources required for each step, and determining the best way to execute the task.

Process Attributes

• Process Id: A unique identifier assigned to each process allowing for process State that can be ready or running
• Program Counter
• List of General-purpose Registers, Priority Info, List of files, and List of devices.
• The attributes of a process are also known as the context of the process, and are stored in RAM
• Every process has its own process control block(PCB), i.e. each process will have a unique PCB

Process State

• New: A newly created process being created by an app downloaded from secondary memory
• Ready: Ready for execution from main memory, and moves to the Ready state after being created
• Run: Currently running process in CPU, only one process is in execution in a single processor from main memory; uses a dispatcher
• Wait (or Block): Process requests an I/O access from main memory
• Complete (or Terminated): Process completed its execution from main memory
• Suspended Ready: Ready queue becomes full, some processes are moved to a suspended ready state
• Suspended Block: Waiting queue becomes full
• When any process changes its state, a context switching happens

Context Switching

• Saving of one process's context and loading another process's context, with the dispatcher performing it
• Loading and unloading the process from the running state to the ready state
• Happens when:
• High-priority process comes to a ready state
• An interrupt occurs
• User and kernel-mode switch occurs
• Preemptive CPU scheduling is used

CPU-Bound vs I/O-Bound Processes

• A CPU-bound process spends more time in the running state, and requires additional CPU Time
• An I/O-bound process requires more I/O time, less CPU time, and spends more time in the waiting state
• Process planning decides which process to run next to maximize CPU utilization, minimize execution time, and improve system response time.

Scheduling Queue

• Job queue: Stores processes of the new state.
• Ready queue: Stores processes of the ready state.
• Device queue: Stores processes of the wait state.

Types of Schedulers

• Long term scheduler (Job): Bring job from new to ready state.
• Short term scheduler (CPU): Bring job from ready to running state.
• Middle term scheduler: from ready to suspended state.

Objectives of Process Scheduling Algorithm

• Maximum CPU Utilization and allocation should be fair
• Maximum Throughput with minimum turnaround time and minimum waiting time
• The process produces the first response as quickly as possible

Scheduling terminologies

• Arrival Time: Time at which the process arrives in the ready queue
• Completion Time: Time at which process completes its execution
• Burst Time: Time required by a process for CPU execution
• Turn Around Time: = Completion Time - Arrival Time
• Waiting Time (WT) = Turn Around Time - Burst Time

Types of Scheduling

• Preemptive Scheduling: Process switches from running state to ready state, or from waiting state to ready state
• Non-Preemptive Scheduling: Process terminates or switches from running state to waiting state

Scheduling Algorithms

• FCFS (First Come First Serve)

  • Scheduled based on arrival time, and tie prefer process with low process id
  • Non-pre-emptive
  • Draw Gantt chart to maintain the process order execution
  • First starts at 0
  • Problems include convoy effect and long waits

• Shortest Job First (SJF)

• Burst time or execution time based, in the instance of the tie arrival time and process ID is important

• As SJF reduces the average waiting time, it is more efficient than FCFS.

• One of the demerits of SJF is starvation

• Not practically implemented as Burst time of process in advance is unknown.

• Shortest Remaining Time First (SRTF)

• SRTF

• Burst time or execution time based, in the instance of the tie arrival time and process ID is important

• Preemptive as the short process pre-empts any running process

• One of the demerits of SJF is starvation

• Priority Based Scheduling

• Scheduled based on Priority. Mostly priority is unique for each process and question always give hint

• Can be Pre-emptive and Non-preemptive. Either a higher or small number can be given as top priority depending on context

• May face starvation

• Round Robin

• Criteria: Arrival time + time quantum.

• time quantum is the maximum time for which a process is assigned the CPU, and after the duration the CPU is pre-empted from the process.

• Preemptive, the process id with lower is always preferred

• Fielding practices.

• Multilevel Queuing Scheduling

• Generally, one scheduling policy is allowed in a given computer system

• For example, a common division is a foreground (interactive) process and a background (batch) process.

• Fixed priority preemptive scheduling method - run all process of high priority and then serve low priority

• Time slicing: Divide the whole CPU into fraction and serve them accordingly.

• Multilevel Feedback Queuing Scheduling

• CPU Scheduling, where a process can move between queues instead of multi-level queue scheduling

• Priorities adjusted dynamically, multiple queues are present

• Allows differing processes to move between different queues and prevents starvation by moving a process that waits too long up top a higher priority queue

Starvation and its Counter Measure

• Starvation occurs when high priority processes keep executing, while low priority processes get blocked for indefinite time.
• Even steady streams of higher-priority processes can cause starvation
• This can be solved using Aging, which will gradually increase the long wait processes priority

Process Synchronization

• The communication for each is needed between each other to achieve an objective
• Involves processes being independent or cooperating, execution of process should not affect
• Coordination of execution of multiple processes in a multi-process system to ensure that they access shared resources in a controlled and predictable manner.
• Main objective is to ensure that various processes access shared resources without interference and to prevent the inconsistency of concurrent access data

Need of Synchronization

• Requires between cooperating processes to obtain the expected result of execution
• To prevent problems of inconsistency, data loss and deadlock.
• Useful where Two process wants to communicate, for sharing common resources to store critical section resources
• Share the shared variables

Race Condition

• Potential of an executing process accessing the same code or sharing a variable to be incorrect
• Process manipulations over data concurrently and depends on the outcome of the particular order which takes place.
• Happens when threads of access in critical sections differ to the order in the thread
• Require mutual exclusion, progress, and bound waiting

Solution using Lock

• Allows for mutual exclusion and to prevent accessing the same data

Critical Section

• Requires Mutual Exclusion – Process won't access same data, avoid race conditions
• It make sure it doesn't prevent other data access and is in progress, if no current access
• If the bound waits if the entry is trying to enter

Petersons Solution

• Uses flags to store any intent process from entering critical section

Semaphore

• Is a normal variable that helps achieving process synchronisation and used for mutual condition and race conditions as well as achieving synchronisation between processes or in access

• Wait() or P() or Downgrade() and Signal() or V() or Upgrade()

• Types include:

• Binary Semaphore

• Only have two values – 0 and 1, its value is initialized to value 1

• It is used to implement the critical sections

• Counting Semaphore

• Its range can range from a unrestricted domain to control access to a resource

Classic Synchronization Problems

• Bounded Buffer Producer/Consumer Problem

• A buffer with a fixed size with producer can produce items and consumers pick items

• Ensure, buffer is the critical section

• Empty/Full conditions used

• Reader Writer Problem

• File shared between people to prevent editing same file or not being read or writers being blocked

• Requires binary semaphore to restrict readers or writers and must restrict or is read count cannot interfere

• Dining Philosophers Problem

• K philosophers around a circle with limited amount of total K chopsticks

• Philosopher is only allowed if they have two chopsticks and can pick up if there followers can pick up

• Can lead to deadlock