Important Formulas — Operating Systems

Introduction

Operating Systems is not just theory — many concepts require precise mathematical calculations. Whether you are solving CPU scheduling problems, analyzing memory performance, or optimizing disk access, you need to know the right formulas. This page collects every critical formula you will encounter in an OS course, organized by topic with clear explanations of when and how to use each one.

CPU Scheduling Formulas

These formulas measure how efficiently the CPU serves processes.

Turnaround Time (TAT)

This measures the total time a process spends in the system, from the moment it arrives in the ready queue until it finishes execution. A lower turnaround time means the system is more responsive.

Waiting Time (WT)

Waiting time is how long a process sits idle in the ready queue. In FCFS scheduling, early-arriving short processes may have low waiting time, but in convoy effect scenarios, short processes behind a long process suffer high waiting time.

Response Time

This is particularly important in interactive systems. It measures how quickly a process gets its first slice of CPU time after arriving. Round Robin scheduling optimizes for low response time.

Throughput

Throughput measures system productivity. A scheduling algorithm with higher throughput completes more work per unit time.

CPU Utilization

In practice, CPU utilization between 40-90% is typical. Below 40% suggests the system is underloaded; above 90% may cause excessive queuing delays.

Average Waiting Time (for n processes)

This is the most common metric used to compare scheduling algorithms in exam questions.

Memory Management Formulas

Logical to Physical Address Translation (Paging)

For example, if logical address is 3456 and page size is 1024 bytes:

• Page Number = 3456 / 1024 = 3
• Offset = 3456 % 1024 = 384
• If page 3 maps to frame 7: Physical Address = 7 × 1024 + 384 = 7552

Number of Pages and Frames

Note that Page Size always equals Frame Size.

Page Table Size

If a system has 2²⁰ pages and each entry is 4 bytes, the page table requires 4 MB — which is why multi-level paging exists.

Effective Access Time (EAT) with TLB

With a TLB hit, you access memory once. With a TLB miss, you access memory twice — once for the page table and once for the actual data.

Effective Access Time with Page Faults

Where p is the page fault rate. If memory access takes 200ns and page fault handling takes 8ms, even a 0.001 page fault rate significantly impacts performance: EAT = 0.999 × 200 + 0.001 × 8,000,000 = 199.8 + 8000 = 8199.8 ns

Internal Fragmentation

If process size is exactly divisible by page size, fragmentation is zero.

Disk Scheduling Formulas

Total Seek Time

Average Seek Time

Disk Access Time

• Seek Time: Time to move disk arm to the correct track
• Rotational Latency: Time for the desired sector to rotate under the head (average = half rotation time)
• Transfer Time: Time to actually read/write the data

Rotational Latency

For a 7200 RPM disk: Average Rotational Latency = (1/7200) × 60 × 0.5 = 4.17 ms

Deadlock Detection Formulas

Banker's Algorithm — Safety Check

A state is safe if there exists at least one safe sequence where each process can obtain its maximum needed resources and complete.

Process Synchronization

Bounded Buffer Capacity

Semaphore Invariant

A process blocks when S becomes negative. |S| when negative equals the number of blocked processes.

Virtual Memory Formulas

Working Set Size

Belady's Anomaly Detection

In FIFO page replacement, increasing frames can increase page faults. Stack algorithms (LRU, Optimal) never exhibit this anomaly.

Page Fault Rate Bounds

RAID Performance Formulas

Quick Reference Table

Tips for Using These Formulas

1. Always check units — do not mix milliseconds with nanoseconds
2. Draw timelines for scheduling problems before calculating
3. Verify with boundary cases — what happens when page fault rate is 0 or 1?
4. Remember integer division — page numbers are always whole numbers
5. In exam problems, write the formula first, then substitute values

These formulas appear repeatedly in university exams, GATE, and technical interviews. Practice them with numerical problems until the calculations become automatic.