Data Structures in Operating Systems

1. Why Data Structures Are Important in an OS

An operating system is itself a program, but a very special one.
To manage multiple programs, users, and hardware devices efficiently, the OS relies heavily on well-designed data structures.

These data structures help the OS to:

  • Track running and waiting processes

  • Allocate and reclaim resources

  • Perform scheduling and context switching

  • Maintain system security and accounting

Without these structures, multitasking and resource sharing would be impossible.

2. Major Data Structures Used in Operating Systems

Some of the most important OS data structures include:

  1. Process List / Task List

  2. Process Control Block (PCB)

  3. Ready Queue and Waiting Queues

  4. Memory Management Data Structures

  5. File System Data Structures

  6. I/O and Device Data Structures

3.Overview of Data Structures in Operating Systems

Operating system uses many important data structures:

1. Process Management Structures

  • Process list / task list

  • Process Control Blocks (PCBs)

  • Ready queues and waiting queues

2. Memory Management Structures

  • Page tables

  • Frame tables

  • Segment tables

  • Free memory lists

3. File System Structures

  • Inodes

  • File control blocks

  • Directory structures

  • Open file tables

4. I/O and Device Management Structures

  • Device queues

  • I/O request buffers

  • Interrupt descriptors

5. Scheduling and Accounting Structures

  • Scheduling queues

  • Priority tables

  • CPU usage statistics


Data Structures for Process Management

An operating system is a program, and like all programs, it relies on data structures to store and manage information. One of the OS’s most important responsibilities is process management, and to do this efficiently, the OS maintains several key data structures.

To manage multiple processes, the OS:

  • Maintains a process list (or task list) to keep track of all active processes

  • Records which process is currently running

  • Keeps track of blocked processes so that when an event (such as I/O completion) occurs, the correct process can be moved back to the ready state

Each process in the system is represented by a data structure called the Process Control Block (PCB). Educational systems such as xv6 use a simplified PCB, while real operating systems like Linux, macOS, and Windows use more complex versions.

Process Control Block (PCB): Core Information Tracked

From the xv6 example, the OS tracks the following information for each process:

1. Process State

  • Indicates the current status of the process

  • States include:

    • UNUSED – entry is free

    • EMBRYO – process is being created

    • SLEEPING – process is blocked, waiting for an event

    • RUNNABLE – ready to run

    • RUNNING – currently executing

    • ZOMBIE – process has finished but not yet cleaned up

2. CPU Context (Register Context)

  • Stores the values of CPU registers (e.g., instruction pointer, stack pointer)

  • Used during a context switch

  • Allows the OS to stop a process and later resume it exactly where it left off

3. Memory Information

  • Starting address of the process memory

  • Size of the process’s address space

  • Kernel stack for executing in kernel mode

4. Process Identification and Relationships

  • Process ID (PID) – unique identifier

  • Pointer to the parent process

  • Supports process creation and termination semantics

5. Blocking and Termination Information

  • Channel on which the process is sleeping

  • Flag indicating whether the process has been killed

6. I/O and File System Information

  • List of open files

  • Current working directory

7. Trap Frame

  • Saves processor state during interrupts or system calls

  • Enables safe transitions between user mode and kernel mode

Zombie State and Process Cleanup

A process that has completed execution but whose parent has not yet collected its exit status enters the zombie state.
This state:

  • Preserves the process’s return value

  • Allows the parent process to call wait()

  • Enables proper cleanup of OS data structures afterward

Comments

Post a Comment

Popular posts from this blog

Operating Systems OS PCCST403 Semester 4 BTech KTU CS 2024 Scheme

 About Me Scheme and Syllabus Module-1 Introduction to OS - 3 important pieces- virtualization, concurrency, persistence Operating System Services Operating System and Kernel Linux Versus Classic Unix Kernels Difference between Linux and Unix Kernels Process and Process Creation- overview Process States in Operating System Data Structures in Operating Systems Key Aspects of a Program and Process in an Operating System-Summary Sharing the Processor Among Processes System Boot Sequence Threads and Concurrency Case Study: Linux Kernel Process management Case Study: Linux Implementation of Threads CPU Scheduling Multi-level feedback Queue ( MLFQ) Scheduler How MLFQ Approximates Shortest Job First (SJF) I/O in MLFQ Problems With the Basic MLFQ Scheduler Solving the Issues with MLFQ Scheduler Case Study: Linux Completely Fair Scheduler (CFS)
Read more

Introduction to Operating System -Virtualization, Concurrency, and Persistence

  How Operating Systems Really Work: Virtualization, Concurrency, and Persistence Have you ever wondered how your laptop can play music, run a web browser, download files, and open a Word document—all at the same time—without melting down? It might look simple, but beneath the surface, your operating system (OS) is doing incredibly sophisticated work. In this , we’ll break down the three most important ideas that make modern operating systems possible: Virtualization Concurrency Persistence These concepts are the foundation of how computers manage programs(applications), memory, and data.  1. Virtualization: Making One Computer Look Like Many Virtualization is all about creating useful illusions . You might have Spotify playing, Instagram open, and a browser loading—all on one phone. It feels like all apps run simultaneously, but the phone is rapidly switching between them so smoothly you don’t notice. Virtualization = making one CPU appear like many. Ev...
Read more

Operating Systems PCCST403 Scheme and Syllabus

  OPERATING SYSTEMS (Common to  CS/CD/CM/CR/CA/AD/AI/CB/CN/CC/CU/CI/CG)   Course  Code PCCST403 CIE Marks 40 Teaching Hours/Week (L: T:P: R)   3:1:0:0   ESE Marks   60 Credits 4 Exam Hours 2Hrs.30 Min. Pre requisites(if  any) None Course Type Theory Course  Objectives: 1. To introduce the structure of a typical operating system and its core functionalities. 2. To impart to the students, a practical understanding of OS implementation nuances based on the Linux operating system. 1.        SYLLABUS   Module No. Syllabus  Description Contact Hours       1 Introduction to Operating Systems (Book 1 Ch 2 introductory part), Operating System Services (Book 3 Ch...
Read more