Dynamic Memory Management in Data Structures

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.

Data Structures and their Applications

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

Introduction to Programming Methodologies

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

Digital Communication Viva Questions

 

Digital Communication Lab Viva Questions with Answers

 

1.  List down the major advantages and disadvantages of analog communication techniques?

The major advantages of analog communication are:

(a) For audio and video transmission, analog signals are mostly suited

(b) It can be ported easily

(c) They can be processed easily

(d) Bandwidth usage is less than digital signals

(e) For analog signals, the need of new graphics board is not necessary.

(f) Analog signals can present more refined information because of its higher density

Electrical Measurements Lab Viva Questions and Answers

 

Electrical Measurements and Instrumentation Lab Viva Questions and Answers

 

1. What you know about the Cathode ray oscilloscope (CRO)?

Basically the Cathode ray oscilloscope (CRO) is considered as the 'eye' of an electronics engineer. An electronics engineer can see all the signals and waveforms with the help of CRO. Initially it was known as Oscillograph.  The use of CRO is for the measurement and analysis of waveforms, for display and other phenomenon in electrical and electronic circuit. CRO has 4 sections namely display, vertical controllers, horizontal controllers and triggers. Probes are used for input and output measurements in CRO. the waveform is plotted in CRO by plotting amplitude 'A' on x axis and time 't' on y-axis. The main applications of CRO are: Radio, TV Receivers, etc.

 

Applications of Lasers in Scientific Field

Applications of Lasers in Communication, Space, Surgery, Military...

The ingenious principle of laser was first worked out in 1958 by Charles Townes of Columbia University. He made use of this principle a few years earlier in 1953 to invent a very similar device- maser where microwaves are used instead of light waves. Hence laser is an optical maser. The first successful laser using a large synthetic ruby crystal was built by Teodore H Maimann in 1960. With the discovery of laser man's control of light has been and will continue to extend to an unpredictably large and diverse number of applications in scientific field.

(i) Communication :

Since light from the laser is coherent it can theoretically carry messages in the same manner as comparatively low frequency carriers. The frequency of the laser is so high that each message or band of frequencies is a very small percentage of the carrier frequency. Hence a large number of messages can be sent. It can accommodate millions of television channels.

(ii) Space exploration :

Rockets and satellites can be efficiently controlled by laser beam.

(iii) Measurement of large distances

Distance between earth and other planets can be accurately measured by laser beam because it is highly collimated.

(iv) Welding

The laser can be used effectively for spot welding. It possible to weld a joint even after the joint has been sealed inside glass envelope.

(v) Hole drilling

A sharply focused laser beam can be used to cut holes in diamond and other hard materials,

(vi) Surgery

(a) Tooth drilling : The beam destroys by vaporization the dark decayed spot.

(b) Eye - Surgery : Eye - tumors can be removed and detached retina of human eye can be welded by low power laser beam. The Lasik surgery is nowadays used in treating the defects of eye by correcting the shape of the cornea of the eye using laser beam to get sharp image of an object exactly on the retina of the eye.

(c) Cancer treatment : Laser beam can remove some cancerous cell instantly, accurately, and without pain or bleeding.

(vii) Thermonuclear fusion

Laser can he used to trigger a thermonuclear fusion.

(viii) Military applications

The laser beam can be used to destroy an attacking missile in space. Moreover it can be used as 'death-ray gun' to destroy enemies.

(ix) Photography

Laser beam can be used to produce three dimensional images without the use of lenses. This process is called Holography.

(x) Science

(i) Chemical reactions can be accelerated by exposing it to the laser beam.

(ii) Laser can he used to study Raman effect.

Doppler Effect in Light | Redshift and Blueshift

Doppler Effect in Light

We are already familiar with the Doppler effect in sound i.e., the apparent change in frequency of sound due to the relative motion between the source and the listener in a medium. It is named so, because of Doppler who was the first to have stated a theory in the case of sound waves in the year, 1842. He pointed out the relevance of the phenomenon in the case of light.

If the source of light (source of em waves) of frequency f is stationary and the observer moves towards the source with a velocity v (v << c, the velocity of light), the apparent frequency of light as observed by the observer,

f‘ = f(1 + v/c)

The above equation is also valid in the case when the source moves towards the stationary observer. If the source moves away from the stationary observer or the observer moves away from a stationary source,

f‘ = f(1 - v/c)

Doppler effect in sound is asymmetric whereas the Doppler effect in light is symmetric. It means that the apparent frequency of sound when the source is approaching a listener at rest and the apparent frequency when the listener is approaching the source at rest are different. But, for light, the source approaching the observer and observer approaching the source exhibit exactly the same Doppler change in the frequency.

Doppler effect is a convenient tool to estimate the speed and direction of motion of stars, planets etc. in our universe relative to us. In general, if the wavelengths of light received from these objects shift towards the red end of the spectrum, these objects are moving away from the earth. This is known as Redshift. If the wavelengths of spectral lines emitted by these objects shift towards the violet end of the spectrum, these objects are moving towards the earth. In the case of stars, the red shift is observed. This shows that stars are moving away from the earth. By finding the shift, the velocity of these heavenly bodies can be estimated. When waves are received from a source which is moving in the direction of the observer, then there would be an apparent decrease in the wavelength. This is referred to as Blueshift.

The Doppler effect finds application to estimate the speed of aeroplane and automobiles, track artificial satellites, estimate the velocity and rotation of the sun etc.