Operating System Notes for Interviews
Published: 2022-12-12 06:58:25

---
title: Operating System Notes for Interviews
published: true
date: 2022-12-12 03:30:42 UTC
tags: 
canonical_url: https://satejbidvai.hashnode.dev/operating-system-notes-for-interviews
---

These are just for revision and are not exhaustive. You should learn the concepts in depth before following the notes! Do let me know if I have missed any topics :)

# Overview

### Kernel v/s OS

- **Kernel:** A bridge between the software and hardware of the system.
- **OS: A** system program to provide an interface to the computer user so that they can easily operate on the computer.

## Types of OS

1. **Batch Operating System**
    - An operator takes similar jobs and groups them into batches.
    - The next job gets assigned only after the previous job is executed.
2. **Multiprogramming**
    - When the current job is waiting for I/O, another process is assigned to the CPU.
    - The CPU is never idle.
3. **Multitasking / Time-Sharing**
    - Fixed time slice for different processes.
    - Quick response time.
4. **Distributed Operating System**
    - Remote access is enabled within the network.
    - User has access to files not on his system.
5. **Real-Time Operating System**
    - Complete set of tasks within deadlines.
    - eg. Airline traffic control systems

# Process Management

## Overview

### Types of Processing

1. **Preemptive:** CPU is allocated to processes for a limited time.
2. **Non Preemptive:** CPU is allocated to processes till the process terminates or waits for I/O.

### Types of Schedulers

1. **Long Term Schedulers:**
    - Loads processes from secondary memory to ready queue.
2. **Short Term Scheduler:**
    - Assigns a process from ready queue to the CPU.
    - Selects processes according to a scheduling algorithm.
3. **Mid Term Scheduler**
    - Swaps process from main memory to secondary memory.
    - It can again swap the process to resume execution.

### System call:  `fork()`

- Creates a child process
- For ‘n’ `fork()` calls:  `2^n - 1` child processes are created
- Returns an integer
    - **0:** Child Process
    - **+ve:** Parent Process
    - **-ve:** Error; No process created

### Context Switching

- Saving the context of one process and loading another process.
- Allows multiple processes to share CPU.
- Interrupts cause CPU to switch to a kernel routine from the current task. (Switch done by OS)

### Process v/s Threads

| Processes | User Level Threads |
| --- | --- |
| System calls | No System calls |
| Own memory space | Use the memory of parent process |
| Do no share data or code | Share same copy of code and data |
| Can be divided into multiple threads | Smallest unit of execution |
| Blocking one process does not affect the other | Blocking a thread blocks the entire process |
| Slow context switching  | Fast context switching |

### User Level v/s Kernel Level Threads

| User Level Threads | Kernel Level Threads |
| --- | --- |
| Managed by user level library | Managed by OS |
| Fast context switching  | Slow context switching |
| Blocking a thread blocks the entire process | Blocking a thread has no affect on other threads |

# CPU Scheduling

## Key terms

1. **Throughput:** The number of processes that are completed per time unit.
2. **Turnaround Time:** Sum of the periods spent waiting to get into memory,
waiting in the ready queue, executing on the CPU, and doing I/O.
3. **Arrival Time:** Time at which a process arrives in the ready queue.
4. **Waiting Time:** Sum of periods spent waiting in the ready queue.
5. **Burst Time:** Time required for a process to get executed on the CPU.
6. **Completion Time:** Time at which a process completes its execution.
7. **Response Time:** Time from submission of a request till the first response is produced.

`Turn Around Time = Completion Time - Arrival Time`

`Waiting Time = Turn Around Time - Burst Time`

## Scheduling Algorithms

1. **First Come First Serve (FCFS)**
    - The process that requests CPU first is allocated the CPU first (FIFO).
    - Non preemptive.
    - Avg. waiting time varies substantially according to the burst times of the processes.
    - Not ideal for for time-sharing systems.
2. **Shortest Job First Scheduling (SJFS)**
    - ***Shortest Next CPU Burst Algorithm***
    - When the CPU is available, the process that has the smallest CPU burst is assigned first.
    - Preemptive or non preemptive
    - Preemptive SJFS is also called ***Shortest Remaining Time First Scheduling**.*
    - Problems:
        - Knowing the length of next CPU request.
        - Although optimal, cannot be implemented at level of short term scheduling.
        - There is no way to know the length of the next CPU burst.
    - We expect the next CPU burst to be similar in length to the previous ones.

**3. Priority Scheduling**

- A priority is associated with each process, and the CPU is allocated to the process with the highest priority.
- Equal priority processes are scheduled in FCFS order.
- Preemptive or nonpreemptive
- Problem of Indefinite Blocking (Starvation)
    - Solution: Aging (Gradually increasing the priority of processes that wait in the system for a long time)
1. **Round Robin Scheduling (RR)**
    - Similar to FCFS scheduling, but preemption is added to switch between processes.
    - The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.
2. **Multilevel Queue Scheduling**
    - Partitions the ready queue into several separate queues.
    - The processes are permanently assigned to one queue, generally based on some
    property of the process, such as memory size, process priority, or process type.
    - Each queue has its own scheduling algorithm.
    - In addition, there must be scheduling among the queues, which is commonly
    implemented as fixed-priority preemptive scheduling.
3. **Multilevel Feedback Queue Scheduling**
    - Allows a process to move between queues.
    - Separates processes according to the characteristics of their CPU bursts.
    - If a process uses too much CPU time, it will be moved to a lower-priority queue.
    - This scheme leaves I/O-bound and interactive processes in the higher-priority queues.
    - In addition, a process that waits too long in a lower-priority queue may be moved to a higher-priority queue.

# Processes Synchronization

## Interprocess Communication (IPC)

### Types of Processes

1. **Independent Process:** Do not affect / get affected by other processes.
2. **Cooperating Processes:** Affect and get affected by other processes.

### **Shared Memory**

- Processes can exchange information by reading and writing to the shared region.
- Memory resides in address space of the process creating the shared memory.
- Other process that want to communicate must attach this to their address space.

### **Message Passing**

- Communication takes place by exchanging messages.
- **Types of Messages**
    - **Fixed:** Easy **s**ystem level implementation.
    - **Variable:** Complex system level implementation.
- **Direct Communication**
    1. Explicitly name the sender or receiver.
        - `send(P, message)`
        - `receive(Q, message)`
    2. Explicitly naming only the receiver.
        - `send(P, message)`
        - `receive(id, message)` : id is set to name of process with which it is communicating
- **Indirect Communication**
    - Messages are sent and received from a mailbox.
    - Mailbox may be owned by a process or the OS.
    - `send(A, message)` : Send to mailbox A
    - `receive(A, message)` : Receive from mailbox A
- **Synchronous Communication**
    - **Blocking Send:** Sending process is blocked until message is received by the mailbox.
    - **Blocking Receive:** Receiver is blocked until the message is available.
- **Asynchronous Communication**
    - **Non-blocking Send:** Sending process sends the message and resumes operation.
    - **Non-blocking Receive:** Receiver retrieves a valid message or NULL. 
- Buffers (Queue) can be implemented in 3 ways:
    1. **Zero capacity:** Blocking send
    2. **Bounded capacity:** Blocking send if queue is full
    3. **Unbounded capacity:** Sender is never blocked

## Synchronization

### Terms

1. **Race Condition:** A situation where several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place.

### Critical Section Problem

Critical section is a code segment where the shared data can be accessed. 

**Requirements for solution:**

1. **Mutual exclusion:** Only one process can access the critical section at any time.
2. **Progress:** If a process is not using the critical section, then it should not stop any other process from accessing it.
3. **Bounded waiting:** Each process must have a limited waiting time. It should not wait endlessly to access the critical section.

**Solution:**

1. **Lock Variable**
    - Executed in user mode.
    - Applicable for more than two processes also.
    - No gurantee for mutual exclusion.

```cpp
while (lock == 1);
lock = 1;

// Critical section

lock = 0;
```

1. **Test and Set Lock**
    - Satisfies mutual exclusion.
    - Does not satisfy bounded waiting.

```cpp
while(TestAndSet(&lock));
	
// critical section

lock = false;
```

```cpp
boolean TestAndSet(boolean *target) {
		boolean rv = *target;
		*target = true;
		return rv;
}
```

1. **Turn Variable**
    - Runs in user mode.
    - Applicable only for two processes.
    - Strict Alteration (Alternate turns to execute critical section)

```cpp
while (turn != 0);
// Critical section.
turn = 1;
```

```cpp
while (turn != 1);
// Critical section.
turn = 0;
```

1. **Semaphores**
    
    Integer variable used by cooperative processes for synchronization.
    
    1. **Counting Semaphore**
        - -∞ to +∞
        - Value of semaphore < 0: No. of processes in suspend list
        - Value of semaphore ≥ 0: No. of processes that can enter critical section
            
            ```cpp
            // Entry Code: P / Wait / Down 
            Wait(Semaphore S) {
            		--S;
            		if (S < 0) {
            			// Put process in suspend list
            		}
            }

            // Exit Code: V / Release / Up / Signal 
            Signal(Semaphore S) {
            		++S;
            		if (S <= 0) {
            			// Wake one process in suspend list
            		}
            }
            ```
            
    
    2. **Binary Semaphore (Mutex)**
        - 0 / 1
        
        ```cpp
        // Entry Code: P / Wait / Down 
        Wait(Semaphore S) {
        		if (S == 1) {
        				S = 0;
        		} else {
        			// Put process in suspend list
        		}
        }

        // Exit Code: V / Release / Up / Signal 
        Signal(Semaphore S) {
        		if (<Suspend List is empty>) {
        				S = 1;
        		} else {
        				// Wake one process in suspend list		
        		}
        }
        ```
        

## Deadlock

### **Necessary Conditions**

1. **Mutual Exclusion** - At least one resource must be in a non sharable mode; that is only one process at a time can use the resource.
2. **No preemption** - A resource can be released only voluntarily by the process holding it, after that process has completed its task.
3. **Hold & Wait** - A process holding at least one resource is waiting to acquire additional resources held by other processes.
4. **Circular Wait**

- In a single instance RAG (Resource Allocation Graph):
    - Circular wait ⇒ ***Deadlock.***
    - No cycle ⇒ ***No deadlock.***

### Methods of prevention

1. **Deadlock Ignorance (Ostrich Method)** - Ignore the problem and pretend that deadlocks never occur in the system.
2. **Deadlock Prevention** - At least one of the 4 necessary conditions is prevented.
    - Mutual Exclusion: Make resources shareable
    - No preemption: Allow preemption
    - Hold and Wait:
        - Must guarantee that whenever a process requests a resource, it does not hold any other resources.
        - Require process to request and be allocated all its resources before it begins execution.
    - Circular Wait: Impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.
        
        Eg. A process cannot request resource no. 2 after resource no. 3.
        
3. **Deadlock Avoidance** - A decision is made dynamically whether the current resource allocation request will, if granted, potentially lead to a deadlock.
    
    Disadvantages:
    - Low device Utilisation
    - Reduced system throughput
4. **Deadlock Detection** - Deadlock situation may occur. The system may provide:
    - An algorithm that examines the state of the system to determine whether
    a deadlock has occurred.
    - An algorithm to recover from the deadlock.
    - Banker's Algo (Columns: Allocated, Maximum, Remaining)
    
    **Deadlock Free condition:**
    

`Total Resources + Total Processes > Total Demand` 
`R > (d1) + (d2 - 1) + ... + (dn - 1)`

# Memory Management

## Terms

1. **Degree of Multiprogramming -** The number of processes currently in memory.
2. **Internal Fragmentation -** The memory allocated to a process may be slightly larger than the requested memory. The difference between these two numbers is ******internal fragmentation ***-*** unused memory that is internal to a partition.
3. **External fragmentation -** It exists when there is enough total memory space to satisfy a request but the available spaces are not contiguous: storage is fragmented into a large number of small holes.

## Memory Management Techniques

## Contiguous Partitioning

1. **Fixed Partitioning (Static)**
    - No. of partitions are fixed.
    - Size of each partition may/may not be same.
    - Spanning is not allowed.
    - Problems:
        - Limit in process size.
        - Limit in degree of multiprogramming.
        - **Internal Fragmentation:** Diff. between allocated and requested memory.
        - **External Fragmentation: P**rocess’s memory request cannot be fulfilled because the memory offered is in a non-contiguous manner.
2. **Variable Partitioning (Dynamic)**
    - No internal fragmentation.
    - No limit in degree of multiprogramming.
    - No limit in process size.
    - Problems:
        - External Fragmentation - Must use compaction to shift processes so
        they are contiguous and all free memory is in one block.
        - Allocation/Deallocation is complex.
    - **Dynamic Partitioning Placement Algorithm**
        1. **First Fit -** Allocate the first hole that is big enough.
        2. **Next Fit -** Same as first fit but start search from last allocated hole.
        3. **Best Fit -** Allocate the smallest hole that is big enough.
        4. **Worst Fit -**  Allocate the biggest hole. 

## Paging

Memory management technique that allows OS to retrieve processes from secondary storage into main memory.

`Logical Address = Page No. + Page Size (Offset)`
`Physical Address = Frame no. + Frame Size`

- Frame Size = Page Size
- No. of entries in page table = No. of Pages
- **Page Table Entry:**
    
    
    | Frame No. | Valid(1) / Invalid(0) | Protection (RWX) | Reference (0/1) | Caching | Dirty (Modified) |
    | --- | --- | --- | --- | --- | --- |
- **Inverted Paging:**
    
    
    | Frame No. | Page No. | Process ID |
    | --- | --- | --- |

## Some Important Topics

### Thrashing

CPU spends more time swapping or paging activities rather than its execution.

### Segmentation v/s Paging

| Paging | Segmentation |
| --- | --- |
| Invisible to programmer | Visible to programmer |
| Fixed page size | Segment sizes may vary |
| Faster | Slower |
| OS need to maintain list of free frames | OS needs to maintain a list of free holes |
| Internal fragmentation | External Fragmentation |

### Overlays

- Running a program that is bigger than the size of the physical memory by keeping only those instructions and data that are needed at any given time.
- Divide the program into modules in such a way that not all modules need to be in the memory at the same time.
- **Advantages**
    - Reduce memory requirement
    - Reduce time requirement
- **Disadvantages**
    - Overlap map must be specified by programmer
    - Overlapped module must be completely disjoint

# Important Terms

1. **Zombie Process**
    - A process whose execution is completed but it still has an entry in the process table.
    - Child processes becomes a zombie before being removed from the process table.
2. **Orphan Process :** A process whose parent process no more exists i.e. either finished or terminated without waiting for its child process to terminate is called an orphan process.
3. **Cascading Termination:** If the parent process is exiting or terminating then the children process will also get terminated.
4. **Starvation**
    - When a process has not been able to get the required resources it needs for progress with its execution for a long period of time.
    - Low priority processes get blocked and only high priority processes are executed.
5. **Aging:** To overcome starvation, increase the priority of processes that wait in the system for resources for a long period of time.
6. **Virtual Memory:** Storage allocation scheme in which secondary memory can be addressed as though it were part of the main memory.

---

## References

- GeeksForGeeks
- Gate Smashers - [YouTube](https://www.youtube.com/c/GateSmashers)
- Neso Academy - [YouTube](https://www.youtube.com/c/nesoacademy)
- InterviewBit
- [TutorialsPoint](https://www.tutorialspoint.com/)