Disk Scheduling: FCFS and SSTF

Given Data

• Cylinder range: 0 to 199
• Current head position: 143
• Request queue (FIFO): 25, 17, 119, 197, 194, 15, 182, 115, 183

a) FCFS (First Come First Served)

Service order: 143 → 25 → 17 → 119 → 197 → 194 → 15 → 182 → 115 → 183

$$\text{Total} = 118+8+102+78+3+179+167+67+68 = 790$$

FCFS total head movement = 790 cylinders

b) SSTF (Shortest Seek Time First)

Always move to the nearest pending request.

At every step the head jumps to whichever pending cylinder is closest, so the distances to all remaining requests are compared before each move.

Service order: 143 → 119 → 115 → 182 → 183 → 194 → 197 → 25 → 17 → 15

$$\text{Total} = 24+4+67+1+11+3+172+8+2 = 292$$

SSTF total head movement = 292 cylinders

Note that 119 has to be taken before 115, since $|143-119| = 24$ is smaller than $|143-115| = 28$. Servicing 115 first would violate the shortest-seek rule even though the two requests sit close together.

Summary

SSTF greatly reduces head movement versus FCFS, at the risk of starvation for distant requests.

--- Virtual memory is a memory management technique that allows a computer to execute programs that are larger than the available physical memory (RAM). It creates an illusion of a very large memory space for each process by using a port...

Best: The Optimal (OPT / Belady's) algorithm replaces the page that will not be used for the longest time in the future. This produces the minimum possible number of page faults for any reference string and frame count. It is the theoret...

Parameter Value ------------------ Disk Size 2 GB Block Size 4 KB FAT Entry Size 4 bytes $$\text{Disk Size} = 2 \text{ GB} = 2 \times 2^{30} = 2^{31} \text{ bytes}$$ $$\text{Block Size} = 4 \text{ KB} = 4 \times 2^{10} = 2^{12} \text{ by...

Types of Operating Systems and Difference Between Real-Time and Batch OS

Types of Operating Systems

An Operating System (OS) is system software that manages hardware and software resources and provides services to computer programs. Operating systems are classified into the following types:

1. Batch Operating System

• Jobs with similar requirements are grouped (batched) together and executed without user interaction.
• A job scheduler picks jobs from the batch and submits them to the CPU one by one.
• Example: Early IBM mainframe systems, payroll processing.

2. Time-Sharing (Multitasking) Operating System

• CPU time is shared among multiple users/processes simultaneously.
• Each process gets a small time slice (quantum) in a round-robin fashion.
• Provides fast response time and interactive use.
• Example: UNIX, Linux, Windows.

3. Real-Time Operating System (RTOS)

• Designed to process data and respond within a strict, guaranteed time constraint (deadline).
• Used in time-critical applications.
• Example: Air traffic control, medical devices, missile guidance systems, VxWorks.

4. Distributed Operating System

• Manages a group of independent computers and makes them appear as a single system to the user.
• Resources (CPU, memory, storage) are distributed across multiple machines.
• Example: LOCUS, Amoeba.

5. Network Operating System

• Provides features to manage data, users, groups, security, and applications over a network.
• Each machine has its own local OS but can share resources over the network.
• Example: Windows Server, Novell NetWare.

6. Multiprocessor Operating System

• Supports systems with more than one CPU sharing the same memory and I/O devices.
• Increases throughput and reliability.
• Example: Symmetric Multiprocessing (SMP) systems.

7. Embedded Operating System

• Designed to operate on small machines (embedded systems) with limited resources.
• Highly specialized and resource-efficient.
• Example: Android (mobile), FreeRTOS, Windows CE.

8. Mobile Operating System

• Designed specifically for smartphones and tablets.
• Manages mobile hardware such as touchscreen, GPS, camera.
• Example: Android, iOS.

Difference Between Real-Time OS and Batch OS

Summary

Operating systems are classified based on how they manage processes, respond to users, and handle time constraints. Batch OS focuses on throughput and sequential job processing with no real-time constraints, while Real-Time OS focuses on correctness within strict time limits, making it essential for safety-critical and time-sensitive applications.

Disk Scheduling: FCFS and SSTF

Given Data

• Cylinder range: 0 to 199
• Current head position: 143
• Request queue (FIFO): 25, 17, 119, 197, 194, 15, 182, 115, 183

a) FCFS (First Come First Served)

Service order: 143 → 25 → 17 → 119 → 197 → 194 → 15 → 182 → 115 → 183

$$\text{Total} = 118+8+102+78+3+179+167+67+68 = 790$$

FCFS total head movement = 790 cylinders

b) SSTF (Shortest Seek Time First)

Always move to the nearest pending request.

At every step the head jumps to whichever pending cylinder is closest, so the distances to all remaining requests are compared before each move.

Service order: 143 → 119 → 115 → 182 → 183 → 194 → 197 → 25 → 17 → 15

$$\text{Total} = 24+4+67+1+11+3+172+8+2 = 292$$

SSTF total head movement = 292 cylinders

Note that 119 has to be taken before 115, since $|143-119| = 24$ is smaller than $|143-115| = 28$. Servicing 115 first would violate the shortest-seek rule even though the two requests sit close together.

Summary

SSTF greatly reduces head movement versus FCFS, at the risk of starvation for distant requests.

System Call: Definition and Objectives

Definition

A system call is a programmatic way in which a computer program requests a service from the kernel of the operating system. It provides an interface between a user-level process and the operating system, allowing user programs to request OS services that require higher privilege levels (kernel mode) than the user mode in which normal programs run.

In simple terms, a system call is a controlled entry point into the kernel through which a running program can ask the OS to perform operations on its behalf.

Example: When a program wants to read a file, it issues a read() system call rather than directly accessing the hardware.

Objectives of System Calls

System calls serve the following key objectives:

1. Hardware Abstraction

System calls hide the complexity of hardware from user programs. Programmers do not need to know the details of hardware devices; they simply call standard system call interfaces.

2. Protection and Security

They ensure that user programs cannot directly access hardware or critical OS resources. The OS validates each request, preventing unauthorized or harmful operations.

3. Resource Management

System calls allow the OS to manage and allocate resources (CPU, memory, I/O devices, files) in a controlled and fair manner among multiple processes.

4. Mode Switching (User Mode to Kernel Mode)

System calls provide a safe and controlled mechanism to switch from user mode to kernel mode, so that privileged instructions can be executed only under OS supervision.

5. Process Control

They allow user programs to create, terminate, and manage processes and threads (e.g., fork(), exec(), exit()).

6. Inter-Process Communication (IPC)

System calls provide mechanisms for processes to communicate and synchronize with each other (e.g., pipes, message queues, shared memory).

7. File and I/O Operations

They provide a standard interface for file management and input/output operations such as open(), read(), write(), and close().

Summary Table

In conclusion, system calls act as the bridge between user applications and the operating system kernel, ensuring security, abstraction, and controlled access to system resources.

--- Virtual memory is a memory management technique that allows a computer to execute programs that are larger than the available physical memory (RAM). It creates an illusion of a very large memory space for each process by using a port...

Best: The Optimal (OPT / Belady's) algorithm replaces the page that will not be used for the longest time in the future. This produces the minimum possible number of page faults for any reference string and frame count. It is the theoret...

Parameter Value ------------------ Disk Size 2 GB Block Size 4 KB FAT Entry Size 4 bytes $$\text{Disk Size} = 2 \text{ GB} = 2 \times 2^{30} = 2^{31} \text{ bytes}$$ $$\text{Block Size} = 4 \text{ KB} = 4 \times 2^{10} = 2^{12} \text{ by...

Types of Operating Systems and Difference Between Real-Time and Batch OS

Types of Operating Systems

An Operating System (OS) is system software that manages hardware and software resources and provides services to computer programs. Operating systems are classified into the following types:

1. Batch Operating System

• Jobs with similar requirements are grouped (batched) together and executed without user interaction.
• A job scheduler picks jobs from the batch and submits them to the CPU one by one.
• Example: Early IBM mainframe systems, payroll processing.

2. Time-Sharing (Multitasking) Operating System

• CPU time is shared among multiple users/processes simultaneously.
• Each process gets a small time slice (quantum) in a round-robin fashion.
• Provides fast response time and interactive use.
• Example: UNIX, Linux, Windows.

3. Real-Time Operating System (RTOS)

• Designed to process data and respond within a strict, guaranteed time constraint (deadline).
• Used in time-critical applications.
• Example: Air traffic control, medical devices, missile guidance systems, VxWorks.

4. Distributed Operating System

• Manages a group of independent computers and makes them appear as a single system to the user.
• Resources (CPU, memory, storage) are distributed across multiple machines.
• Example: LOCUS, Amoeba.

5. Network Operating System

• Provides features to manage data, users, groups, security, and applications over a network.
• Each machine has its own local OS but can share resources over the network.
• Example: Windows Server, Novell NetWare.

6. Multiprocessor Operating System

• Supports systems with more than one CPU sharing the same memory and I/O devices.
• Increases throughput and reliability.
• Example: Symmetric Multiprocessing (SMP) systems.

7. Embedded Operating System

• Designed to operate on small machines (embedded systems) with limited resources.
• Highly specialized and resource-efficient.
• Example: Android (mobile), FreeRTOS, Windows CE.

8. Mobile Operating System

• Designed specifically for smartphones and tablets.
• Manages mobile hardware such as touchscreen, GPS, camera.
• Example: Android, iOS.

Difference Between Real-Time OS and Batch OS

Summary

Operating systems are classified based on how they manage processes, respond to users, and handle time constraints. Batch OS focuses on throughput and sequential job processing with no real-time constraints, while Real-Time OS focuses on correctness within strict time limits, making it essential for safety-critical and time-sensitive applications.

--- Aspect Process Thread --------- Definition An independent program in execution with its own address space A lightweight unit of execution within a process Memory Has its own separate memory space Shares memory (code, data, heap) with...

Direct Memory Access (DMA)

Definition

DMA (Direct Memory Access) is a feature of computer systems that allows certain hardware subsystems (such as disk controllers, network cards, or sound cards) to access main memory (RAM) independently of the CPU. It enables data transfer between I/O devices and memory without continuous CPU involvement, freeing the CPU to perform other tasks during the transfer.

Why DMA is Needed

Without DMA, the CPU must supervise every byte transferred between an I/O device and memory (programmed I/O), which wastes CPU cycles. DMA offloads this work to a dedicated DMA Controller (DMAC).

Key Components

How DMA Works (Step-by-Step)

Step 1: CPU Initialization

• The CPU programs the DMA controller by providing:
  • Source address
  • Destination address
  • Number of bytes to transfer
  • Direction of transfer (read/write)
• The CPU then continues its own tasks.

Step 2: DMA Request

• The I/O device signals the DMAC that it is ready to transfer data (via DMA Request line - DREQ).

Step 3: Bus Request

• The DMAC requests control of the system bus from the CPU by asserting the Bus Request (BR) signal.

Step 4: Bus Grant

• The CPU completes its current bus cycle and grants the bus to the DMAC by asserting Bus Grant (BG). The CPU is now temporarily disconnected from the bus (CPU is in a "hold" state).

Step 5: Data Transfer

• The DMAC takes control of the address bus, data bus, and control bus.
• Data is transferred directly between the I/O device and memory, one block at a time, without CPU involvement.
• The address and count registers are updated after each transfer.

Step 6: Transfer Complete

• When the count reaches zero (all data transferred), the DMAC sends an interrupt to the CPU to notify it that the transfer is complete.
• The CPU resumes control of the bus.

Diagram

        +------------------+
        |       CPU        |
        +--------+---------+
                 |  BR / BG (Bus Request / Bus Grant)
                 |
        +--------+---------+
        |  DMA Controller  |<-------- DREQ (from I/O Device)
        | (Source Addr Reg)|
        | (Dest  Addr Reg) |
        | (Count Reg)      |
        +---+----------+---+
            |          |
     Address/Data/Control Bus
            |          |
    +-------+--+    +--+--------+
    |  Main    |    | I/O Device|
    |  Memory  |    | (Disk,NIC)|
    +----------+    +-----------+

Data Flow:

I/O Device  ----[DMA Controller]---->  Main Memory
                  (No CPU needed
                   during transfer)

Advantages of DMA

• CPU is free to execute other instructions during data transfer.
• Faster data transfer compared to programmed I/O or interrupt-driven I/O.
• Suitable for high-speed, bulk data transfers (e.g., disk to memory).

Summary

DMA allows I/O devices to transfer data directly to/from memory by temporarily taking control of the system bus, with the CPU only involved at the start (initialization) and end (interrupt) of the transfer.

CPU Scheduling: RR (q=3) and Priority

STEP 1 - Given Data

All arrive at time 0, in order A, B, C, D.

Formulas: $TAT = CT - AT$, $WT = TAT - Burst$.

STEP 2 - Solve

1. Round Robin (Quantum = 3)

Ready queue starts: A, B, C, D. A process that still has remaining burst rejoins the tail of the queue after its slice.

Tracing execution (remaining bursts A=8, B=9, C=10, D=6):

Gantt:

| A | B | C | D | A | B | C | D | A | B | C | C |
0   3   6   9  12  15  18  21 24  26  29  32  33

$$\text{Avg TAT} = \frac{26+29+33+24}{4} = \frac{112}{4} = 28 \text{ ms}$$ $$\text{Avg WT} = \frac{18+20+23+18}{4} = \frac{79}{4} = 19.75 \text{ ms}$$

2. Priority Scheduling (Non-Preemptive)

Higher number = higher priority. Execution order: D (4) → A (3) → C (2) → B (1)

Gantt:

| D | A | C | B |
0   6  14  24  33

$$\text{Avg TAT} = \frac{6+14+24+33}{4} = \frac{77}{4} = 19.25 \text{ ms}$$ $$\text{Avg WT} = \frac{0+6+14+24}{4} = \frac{44}{4} = 11 \text{ ms}$$

Summary

Page Fault and Page Replacement Algorithms

When Does a Page Fault Occur?

A page fault occurs when a process references a page that is not currently present in main memory (RAM). The CPU generates a trap, and the OS must bring the required page from secondary storage into a frame. If no free frame exists, a page replacement algorithm chooses a victim to evict.

Given Data

• Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3
• Number of frames: 4
• Total references: 14

1. Optimal Page Replacement

Replace the page not needed for the longest time in the future.

At ref 3 (index 6), page 1 is never used again → evict 1.
At ref 4, remaining future refs: 2,3,0,3,2,3. Page 7 never used again → evict 7.

Optimal Page Faults = 6

2. FIFO Page Replacement

Replace the oldest loaded page.

FIFO Page Faults = 7

3. Second Chance (Clock) Page Replacement

FIFO order maintained, but on a hit the reference bit R is set to 1. When selecting a victim, if the oldest page has R=1, clear it to 0 and move it to the back (give it a second chance); if R=0, replace it.

Notation: page(R).

Step detail at ref 4: clock pointer at oldest = 0 (R=1) → set R=0, advance; page 1 (R=0) → victim. Result frames = {2,3,0,4}. This matches FIFO's replacement here because giving 0 a second chance saved it.

Second Chance Page Faults = 6

Summary

The Banker's Algorithm, proposed by Dijkstra, is a deadlock avoidance algorithm used in operating systems. It is named after a banking system where a banker grants loans only if the total amount requested does not exceed available resour...