Skip to main content

Engineering Computer Science EBK DATA STRUCTURES AND ALGORITHMS IN C

Program Plan: 1.The below mentioned variables are used: Three constant variables MEMALLOC, FREE_LIST_SIZE and minBlkSize are declared for various purposes. Another variable of int type kk is used for the loop. 2. The below mentioned functions are used in the program that are declared within the class. Blockallocation()function to allocate the blocks of the memory. allocateRequestedMemory()to allocate requested memory block. deallocateMemory()to return a block to the memory. Program description: To implement the given memory allocation method. Program: #include <iostream> #include <cstdlib> using namespace std; /* Declare the memory size, free list and minimum block size.*/ #define MEMALLOC 1024 #define FREE_LIST_SIZE 16 #define minBlkSize 1 // Forward declaration void deallocateMemory(void *retBlk); // Union Declaration union blockHeader { // Header of the block. struct { // Pointer to the next block on the free list. union blockHeader *nxtBlk; // Block size. unsigned int blkSze; } blk; }; // Rename the block header. typedef union blockHeader BLOCKHEADER; // Defining empty block list. static BLOCKHEADER base[FREE_LIST_SIZE]; // Array of pointers to the free lists. static BLOCKHEADER * avail[FREE_LIST_SIZE]; // Function to initialize the avail list. void Init_AvailList() { // Declare varaiables. int kk; // Use loop to initialize the linked list for(kk = 0; kk < FREE_LIST_SIZE; kk++) { // Set the location avail[kk] = &base[kk]; // Initialize the next block avail[kk]->blk.nxtBlk = NULL; // Initialize the block size avail[kk]->blk.blkSze = 0; } // Last cell in the free list. avail[FREE_LIST_SIZE-1]->blk.nxtBlk = &base[FREE_LIST_SIZE-1]; } // Function to allocate memory from system. static BLOCKHEADER* BlockAllocation(BLOCKHEADER * myFreelst, unsigned int reqUnits, unsigned int blks) { // Declare variables char * prevPgmBrk; int kk; unsigned int nBytes = reqUnits*blks; // Create temporary block BLOCKHEADER *newBlk; // Get the previous allocated memory prevPgmBrk = new char[(nBytes * sizeof(BLOCKHEADER))]; // Check free space is available. If not, return. if (prevPgmBrk == (char *) -1) // Memory is full. So return. return NULL; // Loop allocate memory to the free lists for(kk = 0; kk < blks; kk++) { // Create new block newBlk = (BLOCKHEADER *) (prevPgmBrk + sizeof(BLOCKHEADER)*reqUnits*kk); // Set size newBlk->blk.blkSze = reqUnits; // Coalesce the block with the existing block deallocateMemory((void*)(newBlk+1)); } // Return the list return myFreelst; } /* Function to allocate the requested size block in memory using quick-fit. */ void *allocateRequestedMemory(size_t reqSize) { // Declare variables BLOCKHEADER *curPntr, *prePntr; unsigned int rndBytes; int kk, allowedBytes; BLOCKHEADER * matBlk; /* Check the requested block size. If block size is 0, then return NULL. */ if (reqSize == 0) { // Block size is 0. so return null. return NULL; } // Roundoff the requested block size reqSize. rndBytes = (reqSize+sizeof(BLOCKHEADER)-1)/sizeof(BLOCKHEADER) + 1; /* Check avail is initialised. If not then initialize it.*/ if (avail[0] == NULL) { // Call method to initialize the avail list. Init_AvailList(); } // Start searching the list with minimum of 1 bytes. allowedBytes = minBlkSize; // Loop to find the matching free list. for(kk = 0; kk < FREE_LIST_SIZE-1; kk++, allowedBytes *= 2) { /* Check if available list size is matching with the requested size. If not then goto the next free list.*/ if (allowedBytes < rndBytes) // Goto the loop start. continue; // Check no block is matching. If so, return. if (avail[kk] == NULL || avail[kk]->blk.blkSze == 0) // Allocate the blocks and check. if (BlockAllocation(avail[kk], allowedBytes, 1) == NULL) /* No Matching free block is available. so return*/ return NULL; // Remove the first free slot. matBlk = avail[kk]; /* Make avail[i] to point to the next free block in the list. */ avail[kk] = avail[kk]->blk.nxtBlk; // Return the matching block. return (void*)(matBlk+1); } /* Since matching block is not found. so use first-fit method on the final free list.*/ /* Make pointer to point to the first block in the last free list.*/ prePntr = avail[FREE_LIST_SIZE-1]; // Initialize the current block. curPntr = prePntr->blk.nxtBlk; /* Infinite loop to search through the entire last list. */ for (;;) { // Check available size is large enough. if (curPntr->blk.blkSze >= rndBytes) { // Check available size is matching. if (curPntr->blk.blkSze == rndBytes) { /*Remove the matching block from the free list. */ prePntr->blk.nxtBlk = curPntr-> blk.nxtBlk; } /* Otherwise, available size is larger than requested size. so split the block. */ else { /* Remove the requested units from the block.*/ curPntr->blk.blkSze -= rndBytes; /* Create a new block at the end of this current block. */ curPntr += curPntr->blk.blkSze; curPntr->blk.blkSze = rndBytes; } // Return the allocated block. return (void *)(curPntr+1); } /* Check visited all the blocks in the last free list. If so, then retun. */ if (curPntr == avail[FREE_LIST_SIZE-1]) { // Check memory is full. if (curPntr == NULL) /* Memory is full. We couldnt allocate requested block size. */ return NULL; } /* Otherwise, Move to the next block in the last free list. */ prePntr = curPntr; curPntr = curPntr->blk.nxtBlk; } } // Function to add the returned block to the memory. void deallocateMemory(void *retBlk) { // Declare variables. int kk, allowedBytes; BLOCKHEADER *retHeader; BLOCKHEADER *pp; // Check retBlk is null. If so then return. if (retBlk == NULL) //Return statement. return; // Make pointer to point to the block header. retHeader = (BLOCKHEADER *)retBlk - 1; allowedBytes = minBlkSize; /* Loop to find the free list matching with the returned block size */ for(kk = 0; kk < FREE_LIST_SIZE-1; kk++, allowedBytes *= 2) { /* Check if available list size is matching with the returned size. If not then goto the next free list.*/ if (allowedBytes < retHeader->blk.blkSze) // Move to the next free list. continue; /* If the returned block fits, then add it to the list end. */ retHeader->blk.nxtBlk = avail[kk]; avail[kk] = retHeader; //Return statement. return; } // Loop to find the matching block to coalese. for(pp = avail[FREE_LIST_SIZE-1]; ;pp = pp-> blk.nxtBlk) { /* Check returned block is in between free blocks.*/ if (pp <= retHeader && pp->blk.nxtBlk >= retHeader) break; // Check the block. if (pp >= pp->blk.nxtBlk) { // Check returned block is at the start. if (retHeader > pp) // If so, then come out of the loop. break; // Check returned block is at the end. if (retHeader < pp->blk.nxtBlk) // If so, then come out of the loop. break; } } /* Check Coalescing the returned block with pp.nxtBlk is possible. If so, coalesce retured block with pp.nxtBlk.*/ if (retHeader + retHeader->blk.blkSze == pp-> blk.nxtBlk) { // Reset the block size. retHeader->blk.blkSze += pp->blk.nxtBlk-> blk.blkSze; // set the next block. retHeader->blk.nxtBlk = pp->blk.nxtBlk-> blk.nxtBlk; } //If coalescing is not possible. else { // Just connect the blocks. retHeader->blk.nxtBlk = pp->blk.nxtBlk; } /* Check Coalescing the returned block with pp is possible. If so, coalesce retured block with pp.*/ if (pp + pp->blk.blkSze == retHeader) { // Reset the block size. pp->blk.blkSze += retHeader->blk.blkSze; // Set the next block. pp->blk.nxtBlk = retHeader->blk.nxtBlk; } //If coalescing is not possible. else { // Just connect the blocks. pp->blk.nxtBlk = retHeader; } } // main() method. int main() { // Seeding the random generator. srand(time(NULL)); cout<<"Quick fit implementation :"<<endl;< p="" style="box-sizing: border-box;"></endl;<> // Initialize the list. Init_AvailList(); // Declare variables. void *tempBlk; int nBytes=0; // Display the avail. cout<<"List of blocks"<<endl;< p="" style="box-sizing: border-box;"></endl;<> // Loop to print the avail info. for(int kk = 0; kk< FREE_LIST_SIZE; kk++) { cout<<<"\t"<blk.nxtBlk <<"\t"<blk.blkSze <<endl;< p="" style="box-sizing: border-box;"></endl;<> } // Randomly generate the block size to allocate. nBytes=rand()%1024; /* Call method to allocate the requested block in memory */ tempBlk=allocateRequestedMemory(nBytes); /* Check memory for the requested block size is allocated. */ if(tempBlk!=NULL) cout<<"Memory Allocated for block size"<<nbytes<<endl;< p="" style="box-sizing: border-box;"></nbytes<<endl;<> // Otherwise memory is not allocated. else cout<<"Memory is not allocated"<<endl;< p="" style="box-sizing: border-box;"></endl;<> // Delete the allocated memory. deallocateMemory(tempBlk); cout<<"Memory deallocated"<<endl;< p="" style="box-sizing: border-box;"></endl;<> // Pause the console window. system("pause"); return 0; } Output: Quick fit implementation : List of blocks 000A9178 00000000 0 000A9180 00000000 0 000A9188 00000000 0 000A9190 00000000 0 000A9198 00000000 0 000A91A0 00000000 0 000A91A8 00000000 0 000A91B0 00000000 0 000A91B8 00000000 0 000A91C0 00000000 0 000A91C8 00000000 0 000A91D0 00000000 0 000A91D8 00000000 0 000A91E0 00000000 0 000A91E8 00000000 0 000A91F0 000A91F0 0 Memory Allocated for 849 Memory deallocated Explanation: In the code provided above, an implementation to implement the given memory allocation method is given which is called a sthe quick-fit method. This approach employs an array of n + 1 cells, each cell I pointing to a linked list of blocks of size I for an experimentally discovered number n of the most often requested block sizes. The last cell (n + 1) refers to a block of sizes that aren't used as often. It might alternatively be a pointer to a linked list, but due to the possibility of a high number of such blocks, another organisation, such as a binary search tree, is preferred.

Program Plan: 1.The below mentioned variables are used: Three constant variables MEMALLOC, FREE_LIST_SIZE and minBlkSize are declared for various purposes. Another variable of int type kk is used for the loop. 2. The below mentioned functions are used in the program that are declared within the class. Blockallocation()function to allocate the blocks of the memory. allocateRequestedMemory()to allocate requested memory block. deallocateMemory()to return a block to the memory. Program description: To implement the given memory allocation method. Program: #include <iostream> #include <cstdlib> using namespace std; /* Declare the memory size, free list and minimum block size./ #define MEMALLOC 1024 #define FREE_LIST_SIZE 16 #define minBlkSize 1 // Forward declaration void deallocateMemory(void retBlk); // Union Declaration union blockHeader { // Header of the block. struct { // Pointer to the next block on the free list. union blockHeader nxtBlk; // Block size. unsigned int blkSze; } blk; }; // Rename the block header. typedef union blockHeader BLOCKHEADER; // Defining empty block list. static BLOCKHEADER base[FREE_LIST_SIZE]; // Array of pointers to the free lists. static BLOCKHEADER avail[FREE_LIST_SIZE]; // Function to initialize the avail list. void Init_AvailList() { // Declare varaiables. int kk; // Use loop to initialize the linked list for(kk = 0; kk < FREE_LIST_SIZE; kk++) { // Set the location avail[kk] = &base[kk]; // Initialize the next block avail[kk]->blk.nxtBlk = NULL; // Initialize the block size avail[kk]->blk.blkSze = 0; } // Last cell in the free list. avail[FREE_LIST_SIZE-1]->blk.nxtBlk = &base[FREE_LIST_SIZE-1]; } // Function to allocate memory from system. static BLOCKHEADER* BlockAllocation(BLOCKHEADER * myFreelst, unsigned int reqUnits, unsigned int blks) { // Declare variables char * prevPgmBrk; int kk; unsigned int nBytes = reqUnitsblks; // Create temporary block BLOCKHEADER newBlk; // Get the previous allocated memory prevPgmBrk = new char[(nBytes * sizeof(BLOCKHEADER))]; // Check free space is available. If not, return. if (prevPgmBrk == (char ) -1) // Memory is full. So return. return NULL; // Loop allocate memory to the free lists for(kk = 0; kk < blks; kk++) { // Create new block newBlk = (BLOCKHEADER ) (prevPgmBrk + sizeof(BLOCKHEADER)reqUnitskk); // Set size newBlk->blk.blkSze = reqUnits; // Coalesce the block with the existing block deallocateMemory((void)(newBlk+1)); } // Return the list return myFreelst; } / Function to allocate the requested size block in memory using quick-fit. / void allocateRequestedMemory(size_t reqSize) { // Declare variables BLOCKHEADER curPntr, prePntr; unsigned int rndBytes; int kk, allowedBytes; BLOCKHEADER * matBlk; /* Check the requested block size. If block size is 0, then return NULL. / if (reqSize == 0) { // Block size is 0. so return null. return NULL; } // Roundoff the requested block size reqSize. rndBytes = (reqSize+sizeof(BLOCKHEADER)-1)/sizeof(BLOCKHEADER) + 1; / Check avail is initialised. If not then initialize it./ if (avail[0] == NULL) { // Call method to initialize the avail list. Init_AvailList(); } // Start searching the list with minimum of 1 bytes. allowedBytes = minBlkSize; // Loop to find the matching free list. for(kk = 0; kk < FREE_LIST_SIZE-1; kk++, allowedBytes = 2) { /* Check if available list size is matching with the requested size. If not then goto the next free list./ if (allowedBytes < rndBytes) // Goto the loop start. continue; // Check no block is matching. If so, return. if (avail[kk] == NULL || avail[kk]->blk.blkSze == 0) // Allocate the blocks and check. if (BlockAllocation(avail[kk], allowedBytes, 1) == NULL) / No Matching free block is available. so return/ return NULL; // Remove the first free slot. matBlk = avail[kk]; / Make avail[i] to point to the next free block in the list. / avail[kk] = avail[kk]->blk.nxtBlk; // Return the matching block. return (void)(matBlk+1); } /* Since matching block is not found. so use first-fit method on the final free list./ / Make pointer to point to the first block in the last free list./ prePntr = avail[FREE_LIST_SIZE-1]; // Initialize the current block. curPntr = prePntr->blk.nxtBlk; / Infinite loop to search through the entire last list. / for (;;) { // Check available size is large enough. if (curPntr->blk.blkSze >= rndBytes) { // Check available size is matching. if (curPntr->blk.blkSze == rndBytes) { /Remove the matching block from the free list. / prePntr->blk.nxtBlk = curPntr-> blk.nxtBlk; } / Otherwise, available size is larger than requested size. so split the block. / else { / Remove the requested units from the block./ curPntr->blk.blkSze -= rndBytes; / Create a new block at the end of this current block. / curPntr += curPntr->blk.blkSze; curPntr->blk.blkSze = rndBytes; } // Return the allocated block. return (void )(curPntr+1); } /* Check visited all the blocks in the last free list. If so, then retun. / if (curPntr == avail[FREE_LIST_SIZE-1]) { // Check memory is full. if (curPntr == NULL) / Memory is full. We couldnt allocate requested block size. / return NULL; } / Otherwise, Move to the next block in the last free list. / prePntr = curPntr; curPntr = curPntr->blk.nxtBlk; } } // Function to add the returned block to the memory. void deallocateMemory(void retBlk) { // Declare variables. int kk, allowedBytes; BLOCKHEADER retHeader; BLOCKHEADER pp; // Check retBlk is null. If so then return. if (retBlk == NULL) //Return statement. return; // Make pointer to point to the block header. retHeader = (BLOCKHEADER )retBlk - 1; allowedBytes = minBlkSize; / Loop to find the free list matching with the returned block size / for(kk = 0; kk < FREE_LIST_SIZE-1; kk++, allowedBytes = 2) { /* Check if available list size is matching with the returned size. If not then goto the next free list./ if (allowedBytes < retHeader->blk.blkSze) // Move to the next free list. continue; / If the returned block fits, then add it to the list end. / retHeader->blk.nxtBlk = avail[kk]; avail[kk] = retHeader; //Return statement. return; } // Loop to find the matching block to coalese. for(pp = avail[FREE_LIST_SIZE-1]; ;pp = pp-> blk.nxtBlk) { / Check returned block is in between free blocks./ if (pp <= retHeader && pp->blk.nxtBlk >= retHeader) break; // Check the block. if (pp >= pp->blk.nxtBlk) { // Check returned block is at the start. if (retHeader > pp) // If so, then come out of the loop. break; // Check returned block is at the end. if (retHeader < pp->blk.nxtBlk) // If so, then come out of the loop. break; } } / Check Coalescing the returned block with pp.nxtBlk is possible. If so, coalesce retured block with pp.nxtBlk./ if (retHeader + retHeader->blk.blkSze == pp-> blk.nxtBlk) { // Reset the block size. retHeader->blk.blkSze += pp->blk.nxtBlk-> blk.blkSze; // set the next block. retHeader->blk.nxtBlk = pp->blk.nxtBlk-> blk.nxtBlk; } //If coalescing is not possible. else { // Just connect the blocks. retHeader->blk.nxtBlk = pp->blk.nxtBlk; } / Check Coalescing the returned block with pp is possible. If so, coalesce retured block with pp./ if (pp + pp->blk.blkSze == retHeader) { // Reset the block size. pp->blk.blkSze += retHeader->blk.blkSze; // Set the next block. pp->blk.nxtBlk = retHeader->blk.nxtBlk; } //If coalescing is not possible. else { // Just connect the blocks. pp->blk.nxtBlk = retHeader; } } // main() method. int main() { // Seeding the random generator. srand(time(NULL)); cout<<"Quick fit implementation :"<<endl;< p="" style="box-sizing: border-box;"></endl;<> // Initialize the list. Init_AvailList(); // Declare variables. void tempBlk; int nBytes=0; // Display the avail. cout<<"List of blocks"<<endl;< p="" style="box-sizing: border-box;"></endl;<> // Loop to print the avail info. for(int kk = 0; kk< FREE_LIST_SIZE; kk++) { cout<<<"\t"<blk.nxtBlk <<"\t"<blk.blkSze <<endl;< p="" style="box-sizing: border-box;"></endl;<> } // Randomly generate the block size to allocate. nBytes=rand()%1024; /* Call method to allocate the requested block in memory / tempBlk=allocateRequestedMemory(nBytes); / Check memory for the requested block size is allocated. */ if(tempBlk!=NULL) cout<<"Memory Allocated for block size"<<nbytes<<endl;< p="" style="box-sizing: border-box;"></nbytes<<endl;<> // Otherwise memory is not allocated. else cout<<"Memory is not allocated"<<endl;< p="" style="box-sizing: border-box;"></endl;<> // Delete the allocated memory. deallocateMemory(tempBlk); cout<<"Memory deallocated"<<endl;< p="" style="box-sizing: border-box;"></endl;<> // Pause the console window. system("pause"); return 0; } Output: Quick fit implementation : List of blocks 000A9178 00000000 0 000A9180 00000000 0 000A9188 00000000 0 000A9190 00000000 0 000A9198 00000000 0 000A91A0 00000000 0 000A91A8 00000000 0 000A91B0 00000000 0 000A91B8 00000000 0 000A91C0 00000000 0 000A91C8 00000000 0 000A91D0 00000000 0 000A91D8 00000000 0 000A91E0 00000000 0 000A91E8 00000000 0 000A91F0 000A91F0 0 Memory Allocated for 849 Memory deallocated Explanation: In the code provided above, an implementation to implement the given memory allocation method is given which is called a sthe quick-fit method. This approach employs an array of n + 1 cells, each cell I pointing to a linked list of blocks of size I for an experimentally discovered number n of the most often requested block sizes. The last cell (n + 1) refers to a block of sizes that aren't used as often. It might alternatively be a pointer to a linked list, but due to the possibility of a high number of such blocks, another organisation, such as a binary search tree, is preferred.

Solution Summary: The author describes the functions used in the program to implement the given memory allocation method.

EBK DATA STRUCTURES AND ALGORITHMS IN C

EBK DATA STRUCTURES AND ALGORITHMS IN C

4th Edition

ISBN: 9781285415017

Author: DROZDEK

Publisher: YUZU

See similar textbooks

Videos

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

Blurred answer

Chapter 12, Problem 11E

Chapter 13, Problem 1E

Students have asked these similar questions

Implement an interleave function which combines two integer arrays into a new dynamic array. The term interleave means to alternatively insert the values of two arrays into a single array. For example, given these two arrays as input: Array A: 95 92 27 98 76 Array B: 40 96 This function will return the following dynamic array: 95 40 92 96 27 98 76 The algorithm should work with arrays of same or different size. All array indexing must be done using pointer arithmetic. int* interleave (int *a, int *b int s1, int s2) {

Given an unsorted array Arr of size N of positive integers. One number 'A' from set {1, 2, ...N} is missing and one number 'B' occurs twice in the array. Find these two numbers A and B. int Arr[6] = {5,4,5,2,6,1}

Select the for-loop which iterates through all even index values of an array.A. for(int idx = 0; idx < length; idx++)B. for(int idx = 0; idx < length; idx%2)C. for(int idx = 0; idx < length; idx+2)D. for(int idx = 0; idx < length; idx=idx+2)

Chapter 12 Solutions

EBK DATA STRUCTURES AND ALGORITHMS IN C

Ch. 12 - Prob. 6E Ch. 12 - Prob. 7E Ch. 12 - Prob. 9E Ch. 12 - Prob. 10E Ch. 12 - Prob. 1PA

Knowledge Booster

Background pattern image

Computer Science

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

SEE MORE QUESTIONS

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning

Text book image

C++ Programming: From Problem Analysis to Program...

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

SEE MORE TEXTBOOKS

Definition of Array; Author: Neso Academy;https://www.youtube.com/watch?v=55l-aZ7_F24;License: Standard Youtube License