Signup/Sign In
LAST UPDATED: APRIL 11, 2023

How Data Structures are used in Operating System

    Introduction to Operating System

    Do you ever wonder how your computer performs all its tasks efficiently? It's because it has an Operating system, so let's dive further and learn more about operating system and how data structures are used in it.

    Operating System acts as an interface between the user of the computer and the computer hardware. From turning on the computer to turning off the computer, it is the software that runs at all times.

    The purpose of the Operating System is to take instructions from the user, perform operations using hardware and return the output to the user. Various functions of OS are:

    • It controls the execution of various application programs.
    • It prevents user interference with the hardware.
    • It provides convenient and efficient mechanisms for the correct operation of the computer system.
    • It is responsible for the scheduling and allocation of resources and services like I/O devices, memory, processors, etc.
    • It is also in charge of the privacy and security of the user data and programs.

    Examples of Operating Systems are Windows, macOS, Android, iOS, GNU/LINUX, etc.

    Operating System can be thought of as an agent. For instance, we are buying flight tickets from an agent. We give him the date of travel, boarding and departing points, number of passengers and their details, etc. The agent will check the flights on that date and time, the availability of seats, the nearest airport, cost, etc. He will then return with the most convenient and feasible flight. As we give confirmation, the agent will make reservations and we get our tickets.

    OS works the same way; we will give some data to OS and ask it to perform some tasks. It will check for the resources, devices, and memory. Then it will allocate the resources required to complete the operation. After completion, it will return the output to the user.

    Data Structure

    Data is either values or sets of values. This raw form of data is not very useful and doesn't carry any meaning but the logically related representation of data generates essentially important information. For the identification and storage of data, we need powerful and efficient storage and organization mechanism.

    We use data structures for efficiently storing and retrieving data. The data structure must be capable of handling actual relationships of data in the real world. Also, on the other hand, it should be simple enough to effectively organize, store, process, and retrieve data from it.

    There are various commonly used data structures such as LinkedList, Stack, Queue, Maps, etc. Here is the hierarchy of the data structures.

    DS

    Various Data Structures and their applications in Operating System

    Operating System uses various data structures to schedule jobs, store instructions, perform tasks, allocation and release memory, etc. Let us see various data structures and

    Array

    The array is a linear and homogenous data structure. They store the data in a contiguous block of memory. It is a very basic data structure and is used to implement all the other data structures.

    LinkedList

    LinkedList is a linear homogeneous data structure. It consists of a group of nodes. Each node is made up of two elements i.e. a data, and a link. The data element stores the value and the link store the address to the next element. It organizes data in a logical order and not in physical order. It is a very useful data structure for performing several operations tasks. It is also used to implement many data structures.

    Applications

    • Linked lists in operating systems are used in dynamic Memory Management tasks like allocation and releasing memory during run time.
    • LinkedList allows us to go to previous and next websites on our browsers using the BACK and NEXT buttons. The addresses of the websites are stored in doubly-linked lists.
    • A linked list provides a simple way to manage unbounded memory in a system.

    Stack

    Stack is a homogenous and linear data structure. The elements are inserted and removed from only one end called the TOP. It works on the LIFO principle i.e. Last in First Out. A helpful analogy is to think of a stack as a stack of plates. Only the plate at the top can be removed. Also, a new plate can be added only at the top of the stack.

    Applications

    • The compiler/operating system uses a stack data structure to store local variables used inside a function block, thus they can be discarded once the control comes out of the function block.
    • Stacks are useful in backtracking, which is a process when you need to access the most recent data element in a series of elements.
    • The Stack data structure is used to process function calls and implement recursive functions. The return values and addresses of the function are pushed into the stack and the last called function will first return the value by popping the stack.
    • While processing language, space for parameters and local variables is created internally using a stack.

    Queues

    The queue is a homogeneous linear data structure. It uses different ends for the insertion and deletion of elements. It works on the FIFO principle i.e. First In First Out. Elements are inserted at the front end and are removed from the rear end. The queue can be thought of as a queue at a ticket window. It works on a first come first serve basis.

    Applications

    • Queues in Operating Systems are used to store the interrupts.
    • The queue is used to process synchronization in OS.
    • Queues are also used in CPU job scheduling and disk job scheduling.
    • It is used by an application program to store the incoming data.
    • Round-robin scheduling is a CPU scheduling algorithm in Operating System where each process is assigned a time slot in a cyclic pattern. This technique is implemented using queues. The circular queue is used to implement the round-robin algorithm.

    Trees

    The tree is a non-linear data structure. It is used to organize data objects based on keys or in terms of hierarchical relationships.

    Applications

    • Trees are used in several search applications where data is continuously entered and deleted such as the maps, sets, etc. of many language libraries.
    • The disk's file system is maintained as a tree by the operating system. Files and Folders act as a tree node and they are stored hierarchically. The tree structure is used as it easily accommodates the creation and deletion of folders and files i.e. nodes.
    • Trees can be used for quick traversals and searching of directory structures in the system by the OS.

    Trees are varied in their types and varieties; all together have multiple applications in different fields.

    Graphs

    Graphs are non-linear data structures that store a finite set of ordered pairs, called edges and arcs, of certain entities called vertices. Graphs are of two types, directed and undirected. It is a very useful data structure in operations like allocation, scheduling, resource networking, database design, etc. All these are the functions of the operating system.

    Applications

    • Graphs are used in CPU job scheduling. Jobs are assumed to be vertices of the Graph and edges between two jobs that are related to each other.
    • Likewise, the simultaneous execution of jobs by the set of processors is executed with the help of graphs.
    • The problem of complex timetable scheduling can be dealt with efficiently with graphs. It is presumed that at any one period, each professor can teach at most one subject and that each subject can be taught by a maximum of one professor. Similarly, at the moment, only one task can be accomplished by one processor.
    • The optimal Graph Coloring algorithm is used to figure out the remaining jobs to be completed in the graph.

    Conclusion

    Operating Systems are the backbone of the computing world, and their importance in modern life cannot be overemphasised. They have revolutionised the way we interact with computers, and they have enabled us to perform complex tasks with ease. Data Structures, on the other hand, are a crucial component of Operating Systems that help to organise, store and retrieve data effectively.

    The article has explored some commonly used data structures, such as Arrays, LinkedLists, Stacks, Queues, and Trees, and their applications in Operating Systems. These data structures are essential in job scheduling, dynamic memory allocation, synchronisation, and many other tasks. Using appropriate data structures, Operating Systems can efficiently handle vast amounts of data, improving performance and reducing resource usage.

    Therefore, it is essential to understand these data structures well to appreciate the complexity of Operating Systems and how they function.

    Frequently Asked Questions

    1. What is the role of data structures in operating systems?

    The role of data structures in operating systems is that they are used for efficient storage and retrieval of data. They help the operating system perform tasks such as scheduling jobs, managing memory, storing instructions, etc.

    2. What are some commonly used data structures in operating systems?

    Some commonly used data structures in operating systems are arrays, linked lists, stacks, queues, trees, and graphs. Each of these data structures has its own unique properties and applications in the context of operating systems.

    3. How do data structures impact the performance of an operating system?

    Data structures impact the performance of an operating system significantly, as well-designed data structures can help improve the system's efficiency, reduce memory usage, and improve the speed of various operations.

    4. Can data structures be used to enhance the security of an operating system?

    Yes, data structures be used to enhance the security of an operating system; they can be used as part of security mechanisms such as access control lists, file permissions, and encryption algorithms.

    Niyati Thakkar is a very good writer and an expert at writing about programming languages like Python and Data Structure in a technical way. Niyati has a background in Computer Science, so she has a deep understanding of these complicated topics.
    IF YOU LIKE IT, THEN SHARE IT
    Advertisement

    RELATED POSTS