Recent posts in Operating System

I love computer science because it is so practical. I recently experienced a real-life example of a context switch. It’s a great analogy to explain what a context switch is and why the time quantum in Round Robin scheduling shouldn't be too small.

Key Concepts

• $Context\  Switch$: is defined as the procedure of Saving the state of the Old Process and Loading the state of the New Process
   
• $PCB (Process\  Control\  Block):$ A PCB is created for every individual process by the OS to track various parameters, such as the last executed statement (using the Program Counter), registers being used, and the data or files accessed by the process and many more things.
   
• $Degree \ of\  Multiprogramming:$ This refers to the number of processes present in the $Ready \ State$.

Exam Analogy

I recently sat for the GATE 2026 exam. Imagine you are in the examination room. A common strategy we follow is this: you start solving a question but realize midway that it will take a huge chunk of your time. If you stayed on it, you would be blocked from answering other, easier questions btw, this is essentially the Convoy Effect seen in FCFS (First-Come, First-Served) scheduling (i.e Process with large burst time blocking processes with significantly lesser burst time) 

To avoid this, you leave the question half-solved and jump to another. This is essentially a context switch. Leaving the question is equivalent to saving its context (i.e., leaving the page in your scribble pad where you were working so the half-solved answer remains there).

In an OS, there are several reasons to perform a context switch:

1. $Higher \ Priority\  Process:$ Similar to realizing the current question is worth 1 mark, but there are 2-mark questions left.

2. $Interrupts:$ Similar to an invigilator coming to your desk for an attendance sheet signature, etc etc...

Saving and Loading Context

• let's say now the next question you are solving is new, i.e you haven't read that question yet, so there is nothing you know about the question and hence nothing to retrieve from brain (except obv the concepts you'd use to solve it) btw this can also be seen as runtime environment

Runtime environment, manages essential tasks like memory allocation, dynamic linking, and resource access (e.g., files, networks, I/O devices), independent of the specific OS.

• coming back, so a this action is same as switching to a new process in terms of OS, you save the context of the current process in its PCB. 
   
• Similarly, in an exam, when you switch to a new question, you are saving the context of your current work simply by leaving it as is. Since the next question is new, there is no need to "load" a previous context because it does not yet exist; instead, you initiate a new context by reading the question and writing down the given data.
   
• However, if you switch back to a question you left earlier, it is equivalent to saving the current context and $loading$ the context of the old, partially executed process in terms of OS. Just as the half-solved answer on your scribble pad is the "context" that needs to be loaded back into your brain to resume solving the earlier left question, the OS retrieves the saved state from the PCB to continue execution of earlier partially executed process.

Small Qt in Round Robbin

Now, imagine there are only 10 minutes left. In a panic, you start a question, realize it’s too long, switch to another, realize the same, and switch again. You are now acting like a Round Robin algorithm with an extremely small time quantum. You end up spending more time switching between questions (the overhead) than actually solving them.

also, If the invigilator takes your paper away because time is up, that is a Preemptive Context Switch. You didn't choose to leave the question; the OS (Invigilator) forced you out because your 'Time Quantum' expired.

also If you’ve ever struggled to differentiate between these two:

Parallel vs. Concurrent Execution

• $Parallel\  Execution:$ This is only possible with multiple CPUs or multiple cores within a CPU. It would mean solving three questions simultaneously at the same time while its possible for CPU's with multiple cores not possible for us humans as we only have 1 brain (cpu)
   
• $Concurrent\  Execution:$ as human being's we only have a single brain(CPU), we can only work on a single task at a time, here i was not solving questions parallelly but concurrently i.e., solving multiple question in an interleaved fashion so i could cover maximum questions and making sure that my time utilization is maximum

which is the sole goal of concurrent programming i.e. executing multiple process concurrently in an interleaved fashion so that the CPU utilization can be maximized

Here is a link to concise notes for the entire OS. The notes are prepared from Galvin

https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/

You can watch the below video for clearing concepts related to multi-level paging:

http://debashishdekanits.blogspot.in/2016/10/n-process-mutual-exclusion-bakery.html

CMSC 421 Operating Systems Lecture Notes
(c) 1994 Howard E. Motteler


Interprocess Communication
===========================

(Section 2.2 in Tannenbaum)

Interprocess communication is fundamental to

  - client-server applications (e.g. X windows)
  - modern threaded operating system design
  - many systems utilities in *any* OS (e.g. print spoolers)
  - parallel processing

There are two general models of interprocess communication

  - Shared memory with synchronization operations
  - Message passing


Shared Memory with Synchronization Operations
==============================================

Shared memory must be managed carefully.

Example of 2 processes writing to a shared buffer:

Suppose that both the pointer p and the buffer it points to are
shared by processes P0 and P1

[ show pix of buffer and pointers ]

Suppose that

      -  P0 contains  *p++  =  a ;
      -  P1 contains  *p++  =  b ;

If both P0 and P1 execute these statements once, we expect

      -  p is incremented twice
      -  both  a  and  b  are saved (in some order)

The statement *p++ = a typically is implemented by at least 
two machine instructions

      -  *p = a ;
      -  p++ ;

Consider the following possible sequence of events, where two
processes both copy data to a buffer

P0:                 P1:
     :                                       |
  *p = a ;                                   |
  (context switch)                         time
                         :                   |
                      *p = b ;               |
                       p++   ;               V
                         :
                      (context switch)
   p++   ;
     :

The value `a' has been overwritten by `b'

This is sometimes called a "race condition," because the
final result depends on instruction timing

The *last* variable assigned "wins", i.e., gets saved


Mutual Exclusion in Critical Sections
--------------------------------------

A ``critical section'' is a part of a program that accesses
shared data

A program can have several critical sections for different
data

The ``mutual exclusion problem'' is to find a way to guarantee
that only one process at a time can access the shared data


A solution to the mutual exclusion problem should satisfy

  1. `mutual exclusion:' only one process in a critical 
      section at a time

  2. `progress:' a process outside a critical section can't
      hold up others that want into that critical section
 
  3. `bounded waiting:' a process waiting to enter a
      critical section eventually gets in

  4. `timing:' no assumptions are made about speed, timing, 
      or number of CPUs
   


Disabling Interrupts
--------------------

The simplest way to get mutual exclusion is to disable
interrupts when a processes enters a critical section

Without clock interrupts, there's no context switch

Problem: user would need special `enter' and `exit' critical
section commands, and these commands could be used to hog the
CPU

Disabling interrupts is sometimes useful for the kernel itself



Two-process software solutions to the Mutual Exclusion Problem
---------------------------------------------------------------

We will try and develop some code to ``guard'' a critical
section, so it can be shared by two processes

All these methods use ``busy waiting'' which is sometimes
unavoidable.


Simple Locks
------------

Suppose we have a shared `lock' variable, initially 0 and set to
1 whenever a process is in its CS

P0, P1:
   while ( lock != 0 ) ;     // wait until lock is 0
   lock = 1                  // set lock
   CS() ;                    // enter the critical section
   lock = 0 ;                // reset lock

Problem:

    P0:                     P1:
    finds lock = 0,
    (context switch)
                            finds lock = 0,
                            sets lock = 1,
                            enters CS
                            (context switch)
    sets lock = 1,
    enters CS

Mutual exclusion fails just as in our initial example
with the shared buffer


Alternation
-----------

Suppose we allow the processes to take `turns'

P0:
while (alive) {
   while ( turn != 0 ) ;     // wait until turn = 0
   CS() ;                    // enter the critical section
   turn = 1 ;                // other process's turn

P1:
while (alive) {
   while ( turn != 1 ) ;     // wait until turn = 1
   CS() ;                    // enter the critical section
   turn = 0 ;                // other process's turn


Mutual exclusion is satisfied, but `progress' fails

Suppose P0 enters and leaves its critical section

Then P0 cannot re-enter the critical section until P1 enters and
leaves its critical section


Flags for `in the CS'
---------------------

Idea: use two flags, both FALSE initially; flag0 is true 
when P0 is in CS, flag 1 is true when P1 is in the CS

P0:
while (alive) {
   while ( flag1 ) ;   // wait until flag1 = false
   flag0 = TRUE ;
   CS() ;
   flag0 = FALSE ;
   }

P1:
while (alive) {
   while ( flag0 ) ;   // wait until flag0 = false
   flag1 = TRUE ;
   CS() ;
   flag1 = FALSE ;
   }

Mutual exclusion fails:

    P0 does `while' test, finds flag1 = FALSE
    P1 does `while' test, finds flag0 = FALSE
    P0 sets flag0 = TRUE and enters CS
    P1 sets flag1 = TRUE and enters CS


Flags for `want to enter' (similar to previous example)
--------------------------------------------------------

P0:
while (alive) {
   flag0 = TRUE ;
   while ( flag1 ) ;   // wait until flag1 = false
   CS() ;
   flag0 = FALSE ;
   }

P1:
while (alive) {
   flag1 = TRUE ;
   while ( flag0 ) ;   // wait until flag0 = false
   CS() ;
   flag1 = FALSE ;
   }

In this case `progress' fails

P0 sets flag0 = true
P1 sets flag1 = true

and both are stuck!


Peterson's Solution
-------------------

Use both a turn and flag variables; both flags are initially
FALSE.   (Flags are for "want to enter")

P0:
while (alive) {
   flag0 = TRUE ;
   turn = 1 ;
   while ( flag1 && turn == 1 ) ;   // wait until flag1 = FALSE 
   CS() ;                           //            or turn = 0
   flag0 = FALSE ;
   }

P1:
while (alive) {
   flag1 = TRUE ;
   turn = 0 ;
   while ( flag0 && turn == 0 ) ;   // wait until flag0 = FALSE
   CS() ;                           //            or turn = 1
   flag1 = FALSE ;
   }


Partial analysis

  -Suppose P0 wants CS, and P1 is not in and does not want CS:
   Then P0 enters CS, as flag1 is FALSE (part of progress)

  -Suppose P0 wants CS, and P1 is in CS.
   Then P0 waits for flag1 to go FALSE (mutual exclusion)

  -Suppose both P0 and P1 want CS
   Then the *first* one to set turn is the one to get in
   (mutual exclusion & progress)


   P0  flag0 = TRUE;
   P1  flag1 = TRUE;
   P0  turn  = 1;
   P1  turn  = 0;                   P1 is second to set turn
   P0  while (flag1 && turn == 1)   false, turn is 0, so enter CS
   P1  while (flag0 && turn == 0)   true, loop until P0 leaves CS,
                                    enter CS when flag0 goes FALSE
Must check bounded waiting:

  - Suppose both P0 and P1 want to enter the CS
  - P0 sets turn=1, P1 sets turn=0, P0 enters CS
  - P1 is waiting in while loop for either flag0 to be FALSE,
    or for turn to be 1

  - Suppose P0 exits CS
  - P0 sets flag0 = FALSE;
  - Suppose P1 is unlucky
  - P0 sets flag0 = TRUE before next P1 test
  - P0 sets turn = 1
  - P1 enters CS on turn = 1



Hardware for Critical Sections
-------------------------------


The `Test & Set Lock' Instruction
---------------------------------

Suppose we have a machine instruction TSL(v)
that `atomically' (i.e., uninterruptibly) 
      - sets v to TRUE
      - returns the old value of v


Then it is very easy to protect a critical section with a
`lock' variable:

entry:   while TSL(lock);     // wait until lock is FALSE
         CS();
exit:    lock = FALSE;

How it works:

Suppose we hit `entry' and lock is

http://www.csl.mtu.edu/cs3331.ck/common/05-Sync-Basics.pdf

Important Ones:

http://gateoverflow.in/questions/operating-system?sort=featured

Some Extra Questions

https://wps.prenhall.com/br_deitel_sistemas_3/39/10059/2575352.cw/index.html

OS: http://www.cse.iitb.ac.in/~krithi/courses/684/osquiz0.pdf

Virtual Memory: http://www.cs.utexas.edu/~lorenzo/corsi/cs372/06F/hw/3sol.html