BSc CSIT (TU) Science Operating System (BSc CSIT, CSC259) Question Paper 2074 Nepal

Process

A process is a program in execution. A program is a passive entity (a file on disk), whereas a process is an active entity with a program counter, registers, stack, data section and a set of associated resources. Each process is uniquely identified by a Process ID (PID).

Process State Diagram

During its lifetime a process passes through several states:

Transitions (described as a diagram):

  New ──admitted──▶ Ready ──scheduler dispatch──▶ Running ──exit──▶ Terminated
                     ▲   ▲                          │   │
                     │   └──── interrupt ───────────┘   │
          I/O or event completion                 I/O or event wait
                     │                                  ▼
                     └─────────── Waiting ◀─────────────┘

• New → Ready: the process is admitted by the long-term scheduler.
• Ready → Running: the short-term scheduler (dispatcher) selects the process.
• Running → Ready: a timer interrupt / higher-priority preemption occurs.
• Running → Waiting: the process requests I/O or waits for an event.
• Waiting → Ready: the awaited event completes.
• Running → Terminated: the process finishes or is killed.

Process Control Block (PCB)

The PCB is a data structure maintained by the OS for every process; it is the repository of all information needed to manage and control that process. Key fields:

• Process state – new, ready, running, waiting, terminated.
• Process ID (PID) – unique identifier.
• Program counter – address of the next instruction.
• CPU registers – accumulators, index/stack pointers, general registers.
• CPU-scheduling information – priority, pointers to scheduling queues.
• Memory-management information – base/limit registers, page/segment tables.
• Accounting information – CPU time used, time limits, process numbers.
• I/O status information – list of open files, allocated I/O devices.

Role in process management: The PCB is the kernel's representation of a process. During a context switch, the state of the running process is saved into its PCB and the state of the next process is restored from its PCB, allowing many processes to share one CPU and to be resumed exactly where they left off.

Since the paper did not print a process table, a standard representative data set is assumed (state this assumption in the exam if the table is missing):

Turnaround Time (TAT) = Completion − Arrival; Waiting Time (WT) = TAT − Burst.

(a) FCFS (non-preemptive, order of arrival P1,P2,P3,P4)

Gantt: | P1 0-5 | P2 5-8 | P3 8-16 | P4 16-22 |

(b) SJF Preemptive (SRTN)

Gantt: |P1 0-1|P2 1-4|P1 4-8|P4 8-14|P3 14-22|

• At t=1 remaining: P1=4, P2=3 → run P2. P2 finishes at 4.
• t=4 remaining: P1=4, P3=8, P4=6 → run P1, finishes at 8.
• t=8: P4=6, P3=8 → run P4, finishes at 14; then P3 finishes at 22.

(c) Round Robin (quantum = 2)

Gantt: |P1 0-2|P2 2-4|P3 4-6|P4 6-8|P1 8-10|P2 10-11|P3 11-13|P4 13-15|P1 15-16|P3 16-18|P4 18-20|P3 20-22|

Summary

SRTN gives the minimum average waiting time; RR gives the worst here because of frequent context switches, but offers best responsiveness/fairness.

Deadlock

A deadlock is a situation in which a set of processes are blocked because each process is holding a resource and waiting to acquire a resource held by another process in the set, so none can ever proceed.

Four Necessary (Coffman) Conditions

All four must hold simultaneously for a deadlock to occur:

1. Mutual Exclusion – at least one resource is non-sharable; only one process can use it at a time.
2. Hold and Wait – a process holds at least one resource while waiting to acquire additional resources held by others.
3. No Preemption – a resource cannot be forcibly taken away; it is released only voluntarily.
4. Circular Wait – a circular chain $P_0 \to P_1 \to \dots \to P_n \to P_0$ exists where each process waits for a resource held by the next.

Deadlock Avoidance – Banker's Algorithm

The Banker's algorithm avoids deadlock by never entering an unsafe state. Before granting a request it checks whether the resulting state is safe (i.e. there exists a sequence in which all processes can finish).

Data structures: Available, Max, Allocation, Need = Max − Allocation.

Example (3 resource types A, B, C; total = 10, 5, 7)

Total allocated = (7,2,5), so Available = (3,3,2).

Safety check (find a process whose Need ≤ Available, run it, release its resources):

• Work = (3,3,2). P1 Need (1,2,2) ≤ Work → run P1 → Work = (5,3,2).
• P3 Need (0,1,1) ≤ Work → run → Work = (7,4,3).
• P4 Need (4,3,1) ≤ Work → run → Work = (7,4,5).
• P0 Need (7,4,3) ≤ Work → run → Work = (7,5,5).
• P2 Need (6,0,0) ≤ Work → run → Work = (10,5,7).

A safe sequence ⟨P1, P3, P4, P0, P2⟩ exists, so the state is safe and requests can be granted along this path. If a request would leave no such sequence, the Banker's algorithm makes the requesting process wait, thereby avoiding deadlock.

An operating system (OS) is system software that acts as an intermediary between the user/application programs and the computer hardware. It manages hardware resources and provides a convenient and efficient environment in which programs can run.

Main functions:

• Process management – creation, scheduling, synchronization and termination of processes.
• Memory management – allocation/deallocation of main memory, virtual memory.
• File management – creating, deleting, organizing files and directories, access control.
• Device (I/O) management – controlling peripheral devices via drivers and buffering.
• Storage/secondary-storage management – disk scheduling and allocation.
• Security and protection – authentication and controlling access to resources.
• Networking and communication – managing data exchange between systems.
• User interface – providing CLI or GUI for user interaction.

In short, multiprogramming switches on I/O waits to keep the CPU busy, while multitasking switches rapidly on time slices to give the illusion that many tasks run concurrently.

Summary: A program is just the code; a process is that code loaded into memory and running, together with its current activity and resources, represented by a PCB.

System Call

A system call is a programmatic interface that allows a user-level program to request a service from the operating system kernel (e.g. file I/O, process creation). It is the controlled entry point through which a program switches from user mode to kernel mode.

Types of System Calls

1. Process control – fork(), exit(), wait(), exec(), load, abort: create, terminate and manage processes.
2. File management – open(), read(), write(), close(), create(), delete(): operate on files.
3. Device management – read(), write(), ioctl(), request/release device: access I/O devices.
4. Information maintenance – getpid(), time(), getttimeofday(), set/get system data: obtain or set system and process attributes.
5. Communication – pipe(), shmget(), send(), recv(): inter-process communication via message passing or shared memory.
6. Protection – chmod(), umask(), chown(): control access permissions to resources.

Note: Every deadlock causes starvation for the involved processes, but starvation can occur without deadlock.

Context Switching

Context switching is the mechanism by which the CPU saves the state (context) of the currently running process and loads the saved state of another process so that execution can be switched between processes. The context is held in each process's PCB and includes the program counter, CPU registers, and memory-management information.

Steps:

1. Save the context of the current process P0 into its PCB.
2. Update P0's state (e.g. ready or waiting) and move it to the proper queue.
3. Select the next process P1 via the scheduler.
4. Restore P1's context from its PCB and resume its execution.

When it occurs: on a timer interrupt (preemption), an I/O request/interrupt, a system call, or a higher-priority process becoming ready.

Overhead

Context switching is pure overhead – during the switch the CPU does no useful work. The cost includes:

• Time to save and restore registers and PCB data.
• TLB and cache flushing/refilling (the new process's working set is not yet cached).
• Possible memory-management updates (loading new page tables).

Frequent context switches (e.g. very small Round-Robin quantum) reduce effective CPU utilization, so the quantum/scheduling policy must balance responsiveness against switching overhead.

Producer–Consumer (Bounded-Buffer) Problem

The producer–consumer problem is a classic process-synchronization problem in which:

• A producer process generates data items and puts them into a shared, fixed-size buffer.
• A consumer process removes items from the buffer and uses them.

Requirements (synchronization constraints):

• The producer must not add an item when the buffer is full.
• The consumer must not remove an item when the buffer is empty.
• Access to the shared buffer must be mutually exclusive (only one process modifies it at a time) to avoid race conditions on the count/index.

Standard semaphore solution uses three semaphores:

semaphore mutex = 1;   // mutual exclusion on buffer
semaphore empty = n;   // count of empty slots
semaphore full  = 0;   // count of filled slots

Producer:                     Consumer:
  wait(empty);                   wait(full);
  wait(mutex);                   wait(mutex);
  add item to buffer;            remove item from buffer;
  signal(mutex);                 signal(mutex);
  signal(full);                  signal(empty);

Here empty blocks the producer on a full buffer, full blocks the consumer on an empty buffer, and mutex guarantees mutually exclusive access, preventing race conditions.

Dining Philosophers Problem

Five philosophers sit around a circular table; each alternates between thinking and eating. There are five chopsticks (forks), one between each pair of neighbours. To eat, a philosopher needs both the left and right chopsticks; after eating, both are released. It is a classic model of resource sharing among concurrent processes and illustrates deadlock and starvation.

Naïve solution (each chopstick = a semaphore):

semaphore chopstick[5] = {1,1,1,1,1};

Philosopher i:
  wait(chopstick[i]);          // pick up left
  wait(chopstick[(i+1)%5]);    // pick up right
  eat;
  signal(chopstick[i]);
  signal(chopstick[(i+1)%5]);
  think;

Problem: If all five philosophers simultaneously pick up their left chopstick, each waits forever for the right one → deadlock (circular wait), and a philosopher may also starve.

Solutions to avoid deadlock:

• Allow at most four philosophers at the table at a time.
• Pick up both chopsticks only if both are available (atomically).
• Asymmetric ordering: odd-numbered philosophers pick the left chopstick first, even-numbered pick the right first, breaking the circular-wait condition.

Thrashing

Thrashing is a condition in a virtual-memory system where a process (or the whole system) spends more time swapping pages in and out of memory than executing instructions. It happens when processes do not have enough frames to hold their working set, so each reference causes a page fault, replacing a page that is needed again immediately. The result is a sharp drop in CPU utilization even though the CPU appears busy handling page faults.

Cause: Too high a degree of multiprogramming → not enough frames per process → high page-fault rate → CPU utilization falls → the scheduler admits even more processes, worsening the situation.

Prevention / Control

• Working-set model – allocate each process enough frames to hold its current working set; suspend processes if total demand exceeds available frames.
• Page-Fault Frequency (PFF) control – monitor each process's fault rate; give it more frames if the rate is too high, take frames away if it is too low.
• Reduce degree of multiprogramming – swap out / suspend some processes so the rest have enough memory.
• Use local replacement so one thrashing process cannot steal frames from others.
• Add more physical RAM so working sets fit in memory.