Data structures are used as part of storing information in kernel
The operating system must keep a lot of information about the current state of the system. As things happen within the system these data structures must be changed to reflect the current reality. For example, a new process might be spawned when a user logged into the system. The kernel must create a data structure representing the new process. The scheduler can then use it if it decides to schedule that process to run when it is its turn.
Mostly these data structures exist in physical memory and are accessible only by the kernel and its subsystems. Data structures contain data and pointers; addresses of other data structures or the addresses of routines. Taken all together, the data structures used by the Linux kernel can look very confusing. Every data structure has a purpose and although some are used by several kernel subsystems, they are simpler than at first seen.
Data structures are also used in designing file systems Many file systems use some sort of bit vector (usually referred to as a bitmap) to track where certain free blocks are, since they have excellent performance for querying whether a specific block of disk is in use and (for disks that aren’t overwhelmingly full) support reasonably fast lookups of free blocks.
Many older file systems (ext and ext2) stored directory structures using simple linked lists. Apparently this was actually fast enough for most applications, though some types of applications that used lots of large directories suffered noticeable performance hits.
The XFS file system was famous for using B+-trees for just about everything, including directory structures and its journaling system. From what I remember from my undergrad OS course, the philosophy was that since it took so long to write, debug, and performance tune the implementation of the B+-tree, it made sense to use it as much as possible.
Other file systems (ext3 and ext4) use a variant of the B-tree called the HTree that I’m not very familiar with. Apparently it uses some sort of hashing scheme to keep the branching factor high so that very few disk accesses are used.
Stacks
Stack is an abstract data type with a bounded (predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack, the only element that can be removed is the element that was at the top of the stack, just like a pile of objects.
Basic features of Stack
Stack is an ordered list of similar data type.
Stack is a LIFO structure. (Last in First out).
push() function is used to insert new elements into the Stack and pop() is used to delete an element from the stack. Both insertion and deletion are allowed at only one end of Stack called Top.
Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.
Applications of Stack
The simplest application of a stack is to reverse a word. You push a given word to stack – letter by letter – and then pop letters from the stack.
There are other uses also like : Parsing, Expression Conversion(Infix to Postfix, Postfix to Prefix etc) and many more.
Analysis of Stacks
Below mentioned are the time complexities for various operations that can be performed on the Stack data structure.
· Push Operation : O(1)
· Pop Operation : O(1)
· Top Operation : O(1)
· Search Operation : O(n)
Implementation of Stack
Stack can be easily implemented using an Array or a Linked List. Arrays are quick, but are limited in size and Linked List requires overhead to allocate, link, unlink, and deallocate, but is not limited in size. Here we will implement Stack using array.
C++ code:
Class Stack
{
int top;
public:
int a[10]; //Maximum size of Stack
Stack()
{
top = -1;
}
};
void Stack::push(int x)
{
if( top >= 10)
{
cout << “Stack Overflow”;
}
else
{
a[++top] = x;
cout << “Element Inserted”;
}
}
int Stack::pop()
{
if(top < 0)
{
cout << “Stack Underflow”;
return 0;
}
else
{
int d = a[top–];
return d;
}
}
void Stack::isEmpty()
{
if(top < 0)
{
cout << “Stack is empty”;
}
else
{
cout << “Stack is not empty”;
}
}
Queue
Queue is also an abstract data type or a linear data structure, in which the first element is inserted from one end called REAR(also called tail), and the deletion of exisiting element takes place from the other end called as FRONT(also called head). This makes queue as FIFO data structure, which means that element inserted first will also be removed first.
The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.
Basic features of Queue
- Like Stack, Queue is also an ordered list of elements of similar data types.
- Queue is a FIFO( First in First Out ) structure.
- Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.
- peek( ) function is oftenly used to return the value of first element without dequeuing it.
Applications of Queue
Queue, as the name suggests is used whenever we need to have any group of objects in an order in which the first one coming in, also gets out first while the others wait for there turn, like in the following scenarios :
- Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
- In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service representative is free.
- Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive, First come first served.
Analysis of Queue
· Enqueue : O(1)
· Dequeue : O(1)
· Size : O(1)
Implementation of Queue
Queue can be implemented using an Array, Stack or Linked List. The easiest way of implementing a queue is by using an Array. Initially the head(FRONT) and the tail(REAR) of the queue points at the first index of the array (starting the index of array from 0). As we add elements to the queue, the tail keeps on moving ahead, always pointing to the position where the next element will be inserted, while the head remains at the first index.
When we remove element from Queue, we can follow two possible approaches (mentioned [A] and [B] in above diagram). In [A] approach, we remove the element at head position, and then one by one move all the other elements on position forward. In approach [B] we remove the element from head position and then move head to the next position.
In approach [A] there is an overhead of shifting the elements one position forward every time we remove the first element. In approach [B] there is no such overhead, but whener we move head one position ahead, after removal of first element, the size on Queue is reduced by one space each time.
C++ code:
#define SIZE 100
class Queue
{
int a[100];
int rear; //same as tail
int front; //same as head
public:
Queue()
{
rear = front = -1;
}
void enqueue(int x); //declaring enqueue, dequeue and display functions
int dequeue();
void display();
}
void Queue :: enqueue(int x)
{
if( rear = SIZE-1)
{
cout << “Queue is full”;
}
else
{
a[++rear] = x;
}
}
int queue :: dequeue()
{
return a[++front]; //following approach [B], explained above
}
void queue :: display()
{
int i;
for( i = front; i <= rear; i++)
{
cout << a[i];
}
}
Which one is better :
It depends on the task that is to be performed.
Stack works on the principle of Last In First Out (LIFO). It is a recursive data structure. The simplest application of a stack is to reverse a word. You push a given word to stack – letter by letter and then pop letters from the stack. Another application is an “undo” mechanism in text editors. This operation is accomplished by keeping all text changes in a stack.
Queue is a linear collection of objects. Unlike stack, in queue, we remove the object that is least recently added. It works on the principle of First In First Out (FIFO).
The applications of both these implementations of the data structures are different.
