Exercise 1 The HeapManager in this chapter implements a first-fit mechanism. It uses the first block on the free list that is at least as large as the requested size. Another fairly simple mechanism is called best-fit. As you might guess, the idea is to search the free list for a sufficiently large block that is as close to the requested size as possible. If there is an exact fit on the free list, the best-fit mechanism can stop the search early. Otherwise, it has to search all the way to the end of the free list. This has the advantage that it does not break up large blocks unnecessarily. For example, if there is an exact fit somewhere on the list, the best-fit mechanism will find one, so it will not have to split a block at all. Implement a version of HeapManager with a best-fit mechanism. Start with a renamed copy of the HeapManager class, and then modify the allocate method to implement a best-fit search. (The code for HeapManager is available on the Web site for this book. It includes the coalescing version of deallocate, which is the one you should use.) After this has been tested and works, find a simple sequence of operations for which your best-fit manager succeeds while the first-fit one fails, Hint: There is a sequence that begins like this: mm = new HeapManager (new int [7]); int a mm.allocate (2); int b mm. allocate (1); inte mm. allocate (1); mm.deallocate (a); mm.deallocate (c); By extending this sequence with just two more calls to mm. allocate, you can get something that will succeed for best-fit and fail for first-fit. Although best-fit is often a better placement strategy than first-fit, there are examples for which it is worse. Find a simple sequence of operations for which the first-fit manager succeeds while your best-fit one fails. Hint: There is a sequence that begins like this: mim = new HeapManager (new int [11]); a mm. allocate (4); b = mm. allocate (1); c mm. allocate (3); mm.deallocate (a); mm.deallocate (c); By extending this sequence with just three more calls to mm. allocate, you can get
Exercise 1 The HeapManager in this chapter implements a first-fit mechanism. It uses the first block on the free list that is at least as large as the requested size. Another fairly simple mechanism is called best-fit. As you might guess, the idea is to search the free list for a sufficiently large block that is as close to the requested size as possible. If there is an exact fit on the free list, the best-fit mechanism can stop the search early. Otherwise, it has to search all the way to the end of the free list. This has the advantage that it does not break up large blocks unnecessarily. For example, if there is an exact fit somewhere on the list, the best-fit mechanism will find one, so it will not have to split a block at all. Implement a version of HeapManager with a best-fit mechanism. Start with a renamed copy of the HeapManager class, and then modify the allocate method to implement a best-fit search. (The code for HeapManager is available on the Web site for this book. It includes the coalescing version of deallocate, which is the one you should use.) After this has been tested and works, find a simple sequence of operations for which your best-fit manager succeeds while the first-fit one fails, Hint: There is a sequence that begins like this: mm = new HeapManager (new int [7]); int a mm.allocate (2); int b mm. allocate (1); inte mm. allocate (1); mm.deallocate (a); mm.deallocate (c); By extending this sequence with just two more calls to mm. allocate, you can get something that will succeed for best-fit and fail for first-fit. Although best-fit is often a better placement strategy than first-fit, there are examples for which it is worse. Find a simple sequence of operations for which the first-fit manager succeeds while your best-fit one fails. Hint: There is a sequence that begins like this: mim = new HeapManager (new int [11]); a mm. allocate (4); b = mm. allocate (1); c mm. allocate (3); mm.deallocate (a); mm.deallocate (c); By extending this sequence with just three more calls to mm. allocate, you can get
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
![Exercise 1 The HeapManager in this chapter implements a first-fit mechanism.
It uses the first block on the free list that is at least as large as the requested size.
Another fairly simple mechanism is called best-fit. As you might guess, the idea is
to search the free list for a sufficiently large block that is as close to the requested
size as possible. If there is an exact fit on the free list, the best-fit mechanism can
stop the search early. Otherwise, it has to search all the way to the end of the free
list. This has the advantage that it does not break up large blocks unnecessarily. For
example, if there is an exact fit somewhere on the list, the best-fit mechanism will
find one, so it will not have to split a block at all.
Implement a version of HeapManager with a best-fit mechanism. Start with a
renamed copy of the HeapManager class, and then modify the allocate method
to implement a best-fit search. (The code for HeapManager is available on the Web
site for this book. It includes the coalescing version of deallocate, which is the
one you should use.)
After this has been tested and works, find a simple sequence of operations for
which your best-fit manager succeeds while the first-fit one fails, Hint: There is a
sequence that begins like this:
mm = new HeapManager (new int [7]);
int a mm.allocate (2);
int b mm. allocate (1);
inte mm. allocate (1);
mm.deallocate (a);
mm.deallocate (c);
By extending this sequence with just two more calls to mm. allocate, you can get
something that will succeed for best-fit and fail for first-fit.
Although best-fit is often a better placement strategy than first-fit, there are
examples for which it is worse. Find a simple sequence of operations for which the
first-fit manager succeeds while your best-fit one fails. Hint: There is a sequence
that begins like this:
mim = new HeapManager (new int [11]);
a
mm. allocate (4);
b = mm. allocate (1);
c mm. allocate (3);
mm.deallocate (a);
mm.deallocate (c);
By extending this sequence with just three more calls to mm. allocate, you can get
something that will succeed for first-fit and fail for best-fit.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F2d356527-6a5f-491c-911a-59a116263ba7%2F551c5e3d-e53c-4393-9d5b-e21cc3215553%2Fl8ncdx_processed.png&w=3840&q=75)
Transcribed Image Text:Exercise 1 The HeapManager in this chapter implements a first-fit mechanism.
It uses the first block on the free list that is at least as large as the requested size.
Another fairly simple mechanism is called best-fit. As you might guess, the idea is
to search the free list for a sufficiently large block that is as close to the requested
size as possible. If there is an exact fit on the free list, the best-fit mechanism can
stop the search early. Otherwise, it has to search all the way to the end of the free
list. This has the advantage that it does not break up large blocks unnecessarily. For
example, if there is an exact fit somewhere on the list, the best-fit mechanism will
find one, so it will not have to split a block at all.
Implement a version of HeapManager with a best-fit mechanism. Start with a
renamed copy of the HeapManager class, and then modify the allocate method
to implement a best-fit search. (The code for HeapManager is available on the Web
site for this book. It includes the coalescing version of deallocate, which is the
one you should use.)
After this has been tested and works, find a simple sequence of operations for
which your best-fit manager succeeds while the first-fit one fails, Hint: There is a
sequence that begins like this:
mm = new HeapManager (new int [7]);
int a mm.allocate (2);
int b mm. allocate (1);
inte mm. allocate (1);
mm.deallocate (a);
mm.deallocate (c);
By extending this sequence with just two more calls to mm. allocate, you can get
something that will succeed for best-fit and fail for first-fit.
Although best-fit is often a better placement strategy than first-fit, there are
examples for which it is worse. Find a simple sequence of operations for which the
first-fit manager succeeds while your best-fit one fails. Hint: There is a sequence
that begins like this:
mim = new HeapManager (new int [11]);
a
mm. allocate (4);
b = mm. allocate (1);
c mm. allocate (3);
mm.deallocate (a);
mm.deallocate (c);
By extending this sequence with just three more calls to mm. allocate, you can get
something that will succeed for first-fit and fail for best-fit.
Transcribed Image Text:Exercise 3 Write ObjectAList, a generic version of the AList class from the
previous exercise, that works with keys and values that are objects of any class.
(You will need a new version of ANode as well: an ObjectANode that allows the
value stored in the node to be an object of any class.)
When comparing keys for equality, continue to use the equals method; that is,
test x.equals (y) instead of switching to x==y. You might ask, what if x is now
of some class that does not have an equals method? Don't worry, there is no such
class. One of the methods that all classes inherit from the root class Object is the
equals method. If x is a reference to any object and y is any reference-type vari-
able, you can always evaluate x.equals (y)-in effect, asking x to report whether
or not it is equal to y. The inherited implementation is the simplest. x.equals (y)
is more or less the same as x==y. But classes are free to override this inherited
method with a more sophisticated test. (For example, if x and y are String objects,
x.equals (y) will be true if they contain the same sequence of characters, even if
they are not the same object.)
Now write a class IntAList that implements a dictionary with int keys and
values and uses an ObjectAList to store them. Your IntAList class should have
these three methods:
public void associate (int key, int value);
public int find(int key);
public int size();
The find method should return the value associated with the given key; if that key
is not found in the list, find should return 0. Notice that the associate method
in IntAList does not need to return a value.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
Knowledge Booster
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
Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education