Followers

Recent

Theme images by Storman. Powered by Blogger.

Recent in Sports

Home Ads

Comments

Ads

Random Posts

Search This Blog

Popular

Pages

Tuesday, 23 February 2021

Dynamic Memory Management in Data Structures

- No comments


Dynamic Memory Management in Data Structures

Memory management

 

The responsibility of an operating system is not constrained in process management but the OS should efficiently manage its primary memory. In the operating system this responsibility is carried out by memory manager which is a part of an operating system. Since for each process to run, there must be a certain amount of primary memory, the memory manager's performance is crucial to the entire system's performance. The memory manager allocates space in a primary memory for processes and the same loads and stores the contents in the primary memory. The memory manager also assists the programmer. The memory manager's basic tasks are controlling the primary memory partition and minimizing memory access time.


In the case of system multiple processes are running simultaneously. The real challenge is that we need to manage the memory effectively. Memory multiplexing is possible in primary memory. So the memory manager can allocate each process some primary memory for its own use. However, as new processes are generated and old processes are finished, the memory manager can control which processes operate on which memory locations, and also decide how to assign and override available memory. Although different techniques are used to assign space for competing memory procedures, best fit, worst fit and first fit are the three most common.

 

First fit

 

There may be several gaps in the memory, so from the first hole it finds which is large enough to occupy the process, the operating system assigns memory, starting from the beginning of the primary storage, to reduce the time it takes to evaluate the available space to satisfy the request. The first free partition or hole wide enough to fulfil the process is allocated in the first fit strategy. After locating the first appropriate free partition, it terminates.


For example if a process needs 5KB of space. The memory manager include a list of 4KB, 20KB, 15KB, 10KB and 6KB. Here in this mechanism, memory manager will allocate the first free memory 20KB is allotted for this process


Advantage: It is the fastest algorithm among the different memory management techniques. Because its searching condition is very easy.


Disadvantage: If it is too tiny, the remaining unused memory regions available after allocation become garbage. Therefore, the need for greater memory requirements cannot be fulfilled.

 

Best fit allocation :

 

An object can be positioned by the allocator in the smallest amount of unallocated memory. To satisfy the needs of the application process, the best approach is to assign as little free partition as possible. The whole list of free partitions is first searched by this algorithm and the hole is considered small enough. It then tries to find a gap which approximates the necessary actual process size.

The process needs 10 KB of memory and currently the memory manager includes a list of 9 KB, 17 KB, 20 KB, 11 KB and 12 KB unallocated volume blocks. The best fit strategy allocates 10 KB to the 11 KB volume process.


Advantage: Memory use is better than the first fit because it looks first for the smallest free partition available.


Inconveniences: It is slow and the memory may be filled by small useless holes.

 

Worst fit:


A process is placed into the largest packet of unassigned memory by the memory manager. The premise is that, relative to the best fit, this space produces the largest space after the allotment, where the remaining space can be used for another process. It is the reverse of the best fit. In this approach memory manager checks the whole available memory partitions and finds the largest free space and allocates the memory for that process.


For example if a process needs 10KB of space. The available spaces are 20KB, 15KB, 5KB, 10KB and 30KB. In this approach the memory manager will assign 30KB partition to that process.


Advantages : Reduces the production capacity for tiny holes.


Disadvantage : If a procedure that needs additional memory comes to a later level, since the greatest hole is already split and filled, it cannot be accepted.

 

Dynamic memory allocations

 

The dynamic memory allocation principle in the c language makes it possible for the C developer to allocate memory at running time. The 4 functions of the stdlib.h header file allow dynamic memory allocation in the c language. In C language we can execute a program in which we cannot know the sequential size of the declared variable until the run time. The process is termed as dynamic memory allocation.


Manual allocation and freeing up of memory according to the programming needs is dynamic memory allocation. Dynamic memory is handled and references are provided to show the newly allocated memory space in the field called the heap. Here we can construct and delete consecutive elements at the execution time without any interruption. This is done with the help of Automatic Memory Manager layer and C dynamic memory allocation stack.


<stdlib.h> is the library which is responsible for Dynamic Memory Management. Now we are discussing about some library functions which can be used in Dynamic Memory allocation.

 

malloc()

 

The function C malloc() stands for memory allocation. It is a function that is used dynamically to assign a memory space. It preserves the prescribed size of the memory space and returns a null pointer pointing to the address of the memory. The returned pointer is typically of the void type. This allocates the memory of requested size and returns the pointer to the first byte of allocated space.

 

Syntax of malloc()

 

ptr = (cast_type *) malloc (byte_size);


ptr is the name of the pointer of cast type. Here the function returns a pointer to the allocated memory of byte_size.

Consider the below code:

ptr = (int *) malloc (50)

When this code is executed without any error, 75 bytes of memory will be allocated. The index of the address type int of the first byte of the allotted space is assigned to ptr.

 

calloc()

 

To assign a given amount of memory and then initialize it to zero, the calloc() function in C is used. The function returns this memory location with a void pointer, which can then be cast to the desired form. Two parameters that collectively determine the amount of memory to be allocated are used for the function. This allocates the space for elements of an array. Initializes the elements to zero and returns a pointer to the memory.


Syntax of calloc() function

 

ptr = (type *) calloc (n, size);


When this statement is executed, n memory blocks of same size is allocated. Once the memory block is allocated all the bytes are allocated to zero. The pointer which is pointing at the first byte of the allocated memory is returned. If there is any interruption such as scarcity of memory, then we get a null pointer.

 

The major differences between malloc() and calloc() functions

 

In general, the calloc() function is more suitable and effective than the malloc() function. Calloc() will allocate several volumes at once when both functions are used to allocate memory space. You don't need to ask each time for a block of memory. The Malloc() function generates a single memory cell of the user's defined size. For a variable, the Calloc() function may assign various memory fragments. The Malloc function includes the value of garbage. The memory block assigned by the calloc function is always zero-initialized. Calloc is slower than malloc. calloc is more secure than malloc.

 

realloc()

 

It is used to modify the size of previously allocated memory space.. Realloc() is a C library feature for attaching more storage space to memory blocks that are already allocated. The aim of realloc in C is to extend current memory blocks while keeping the original information as it is. The function realloc() helps to minimize malloc or calloc functions' size of already allocated memory. Realloc stands for memory allocation.

 

Syntax of realloc()

 

ptr = realloc (ptr,nsize);


The above statement assigns new memory space with a certain amount of variable nsize. After running the function, the pointer returns to the first byte of the memory module. The new size may be larger or smaller than the previous memory. We cannot be sure whether the newly allocated block will point to the same location as the previous memory block. This function copies all previous data to the new region. This ensures that the data is secure.

 

free() 

 

Frees or empties the previously allocated memory space. The free() function is used to de-allocate the storage assigned by the malloc(), calloc(), etc functions and return it to the heap function so that it can be used for other applications. The free () function argument is the pointer to the memory to be released.

 

Syntax of free() function

 

void free(void *pntr)


Here pntr is the address which is pointing to the previously allocated memory block by malloc(), calloc() or realloc(). When this code was executed the memory pointed by the pntr is deallocated. If the value of pntr is a null value then no action will occur.

Monday, 15 February 2021

Data Structures and their Applications

- No comments

There are many definitions available for data structures, some of them are given below.


Data structure is an art of organizing data in such a way that it can be easily and quickly accessed, queried or updated later. Organisation of data into the system in a specific way so that it can be manipulated efficiently is called a data structure. The data is the most important entity in computing, and we can systematize theses data using data structures, the value of data structure is well clear. Each data must be stored in a certain format because each scenario is different that we encounter. We have a few data structures that satisfy our needs and allow us to store data in discrete format.


Below given is the list of data structures that we use frequently


1. Arrays

2. Stacks

3. Queues

4. Linked Lists

5. Trees

6. Graphs

7. Tries

8. Hash Tables

 

1. Arrays


An array is an effortless and commonly used data structure. The data structures stack and queue are derived from these arrays. These are simplest data structures, store data of identical type. This means that each entity inside the array (array elements) has a common nature.


A static array has a fixed length of space to store the elements. If the length of the array is ‘n’ then the elements can be indexable from range[0, n-1]. Indexable is nothing but each slot/position/index of the array can be specified by a number called index key (usually based on zero). This enables any array element to have arbitrary access. Fixed arrays are presented in the form of successive memory components.


The data can be stored in an array in a tabular format. For example, if we want to store contacts on our phone, the software puts all our contacts in an array.

Mainly the array can be divided into two


1. One dimensional array

2. Multi dimensional array


Fundamental operations performed in an array are


1. Insert — Inserts an element at a given index value

2. Get — Returns the element at a given index

3. Delete — Deletes an element at a given index

4. Size — Gets the total number of elements in an array

5. Traverse — Read or print all the array elements in the order


Daily life applications of the arrays are :


1. In a leader-board game structure the score of each player can be stored in an array and organize them in descending order to clearly decide each player's rank in the game.

2. Simply the question paper is an array of a number of questions, each of will store the mark for each question.

3. The matrix technology used in image processing used 2D arrays.

4. Array can be used in speech processing, in which each speech signal is an array.


2. Linked list


Another significant linear data structure is linked list which might look identical to arrays at first but differ in many aspects such as different memory allocation, basic structure and the method of doing basic operations such as insert an element, deletion of element etc.


A linked list varies from an array in the order of the elements in the list, which is not determined by the continuous allocation of memory. Instead, due to its nature, the elements of the linked list can be sporadically stored in memory.


A linked list can be considered as a chain of nodes. These nodes have two parts, first part contains the value/information/data and the second node contain the pointer to the succeeding node in the chain i.e. the address of the succeeding node. The term head pointer used here to donate the pointer to the first element of the linked list. It’s value become null or nothing when list is empty.


Each element in the linked list have two parts:


1. The Data

2. The pointer


The data is what we have attached to that element/node, while the pointer is a reference to the next node in the list with a memory address.

A linked list is a succession of data structure in which the elements or nodes are connected through links.


Different types of linked list are :


1. Singly Linked List (Unidirectional)

2. Doubly Linked List (Bi-directional)

3. Circular Linked List.

 

Singly linked list


Singly-linked list is a collection of nodes connected together in a specific way. Each node contains a data field and an address field. Data field contains the information and the address field contain reference to the very next node.


Structure of the node in a singly linked list is

The singly linked-list may contain many nodes. If the address  of a node is NULL, then it indicate the end of the linked list.


Advantages


• Both forward and backward traversing are possible.

• Insertion and deletion options are more efficient in many cases.


Disadvantages


• It require extra space to store the previous node address.

• As the operations increases the complexity also increases.

 

Doubly Linked List


A Double Linked List includes an additional memory to store the previous node's address, along with the next node's address and the data as in the case of singly linked list. So, we store the address of the next node as well as the previous nodes here.


Layout of doubly linked list:


Here the address of previous node in the first node is NULL and address of next node in the last node is NULL.


Circular linked list


A circular linked list is a single or double linked list in which no NULL values are present. The Circular Linked List can be adapted here by using the Singly or Doubly Linked List. In the case of a singly linked list, the next address field of the last node contains the address of the first node and in case of a doubly-linked list, the next address field of last node contains the address of the first node and previous field of the first node contains the address of the last node.


Advantages of a Circular linked list


• If we want to access the data in a circle or loop manner circular list are required.

• Can traverse to previous node very easily, which is not allowed in a singly linked list.


Disadvantages


• If we didn't go through it carefully, we might end up in an infinite loop because we don't have any NULL value here to avoid the traversal.

• Compared to a single linked list and a dual linked list, operations in a circular linked list are complex.

 

Basic operations performed in a linked list


1. Traverse :: Pass through all the nodes one after another

2. Insertion :: Add a node in the specified position

        • InsertAtEnd : : Insert an element at the end of the linked list

        • InsertAtHead :: Insert a node at the start of the list

3. Delete :: Deletes an element from the list

4. Search :: Gives an element from the list as per our condition

5. isEmpty :: Checks whether the list is empty or not. Returns true if it is empty.

6. Updating :: Updates the values in a node

7. Sorting :: Arranges the elements in the list in a specified order

8. Merging :: Integrate two linked list into one

 

Applications of linked list


• We can access web pages using the previous and next URL links that are linked via the linked list.

• A circular linked list will be used to keep track of turns in a multi-player game.

• Images are interconnected with one another. So, to view the previous and next images using the previous and next buttons, an image viewer software uses a linked list.

• The music players often move between music using the same technique.

 

3. Stack

 

The concept: you store in the memory the previous states of your work (which are limited to a certain number) in such an order that the last one first appears. This can not be accomplished easily by using arrays is done by stack.

 

Stack is a linear data structure which works on the principle that Last In First Out (LIFO) order. A heap of books put in a vertical order may be a real-life instance of Stack. You would need to remove all the books put on top of it in order to get the book that is somewhere in the centre. Consider an example of plates in the canteen stacked over one another. The plate at the top is the first to be removed, i.e. the plate that was put at the bottommost position remains for the longest period of time in the stack.

In stack terms, the insertion process is called PUSH and the operation of removal is called POP. The function push() is used to insert new elements into the stack, and the function pop() is used to delete elements from the stack. Only one end of the stack, called Top, allows both insertion and deletion. When it is entirely full, the stack is said to be in the overflow state and if it is completely empty, it is said to be in the underflow state.


Operations performed in a stack


1. Push :: Insert an element into the stack

2. Pop :: Removes an element and returns the value from the stack

3. isEmpty :: Checks whether the stack is vacant or not

4. Top :: Gives the top value of the stack without removing it from the stack

 

Applications of stack

 

1. Parsing

2. Expression conversion (Infix to Postfix and vice versa.)

3. The undo operation

4. Call logs and message logs

5. Virtual machines

6. History in a web browser

 

4. Queue


Queue, similar to Stack, is another linear data structure that sequentially stores the item. The only major difference between Stack and Queue is that Queue implements the FIFO method, which is short for First in First Out, instead of using the LIFO method.

Any queue of customers for a resource where the customer who came first is served first is a good example of a queue. A single-lane one-way path, where the vehicle enters first, exits first, may be a real-world example of the queue. The distinction between stacks and queues is in removing. In a stack, the most recently added item is removed; in a queue, the least recently added item is removed.

 

Basic operations performed in a queue are:


1. enqueue() :: Add an item into the queue

2. dequeue() :: Removes an item from the queue

3. peek() :: Returns the element in the front of the queue without deleting it

4. isfull() :: Checks if the queue is full

5. isempty() :: Inspect whether the given queue is empty or not

 

Applications of queue


• The respond of a server while responding to a request

• Handling congestion in networking

• Sending of data packets in communication

• Job scheduling in operating system

Monday, 8 February 2021

Introduction to Programming Methodologies

- No comments

Introduction to Programming Methodologies


There are enormous and complicated plans are developed to solve real problems such as banking system, student enrolment, and processing of exam results etc. The way of approach and analysing software development and controlling that development to solve such problems are termed as programming methodology.


Software developers, now a day's use different types of programming methodologies