Signup/Sign In

How Data Structures are used in Operating System

Posted in Programming   MAY 4, 2022

    Introduction to Operating System

    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 is running at all times on the computer.

    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, 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 a 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

    • Just like any other application or program, Operating Systems also use all sorts of data structures like arrays, linked lists, stacks, queues, trees, etc.
    • The most commonly used application of data structures in OS is a queue, it is extensively used in process scheduling.
    • Another example is trees. It is used to implement the File System.
    Published by: niyatithakkar
    Tags:Operating SystemData Structures
    IF YOU LIKE IT, THEN SHARE IT
     

    RELATED POSTS