|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 224 out of 1137
Modern Operating Systems by Herbert Bos and Andrew...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Modern Operating Systems by Herbert...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Page 224
SEC. 3.2
A MEMORY ABSTRACTION: ADDRESS SPACES
193
Another well-known and widely used algorithm is
best fit
.
Best fit searches
the entire list, from beginning to end, and takes the smallest hole that is adequate.
Rather than breaking up a big hole that might be needed later, best fit tries to find a
hole that is close to the actual size needed, to best match the request and the avail-
able holes.
As an example of first fit and best fit, consider Fig. 3-6 again. If a block of
size 2 is needed, first fit will allocate the hole at 5, but best fit will allocate the hole
at 18.
Best fit is slower than first fit because it must search the entire list every time it
is called. Somewhat surprisingly, it also results in more wasted memory than first
fit or next fit because it tends to fill up memory with tiny, useless holes. First fit
generates larger holes on the average.
To get around the problem of breaking up nearly exact matches into a process
and a tiny hole, one could think about
worst fit
, that is, always take the largest
available hole, so that the new hole will be big enough to be useful. Simulation has
shown that worst fit is not a very good idea either.
All four algorithms can be speeded up by maintaining separate lists for proc-
esses and holes.
In this way, all of them devote their full energy to inspecting
holes, not processes. The inevitable price that is paid for this speedup on allocation
is the additional complexity and slowdown when deallocating memory, since a
freed segment has to be removed from the process list and inserted into the hole
list.
If distinct lists are maintained for processes and holes, the hole list may be kept
sorted on size, to make best fit faster. When best fit searches a list of holes from
smallest to largest, as soon as it finds a hole that fits, it knows that the hole is the
smallest one that will do the job, hence the best fit. No further searching is needed,
as it is with the single-list scheme.
With a hole list sorted by size, first fit and best
fit are equally fast, and next fit is pointless.
When the holes are kept on separate lists from the processes, a small optimiza-
tion is possible. Instead of having a separate set of data structures for maintaining
the hole list, as is done in Fig. 3-6(c), the information can be stored in the holes.
The first word of each hole could be the hole size, and the second word a pointer to
the following entry. The nodes of the list of Fig. 3-6(c), which require three words
and one bit (P/H), are no longer needed.
Yet another allocation algorithm is
quick fit
, which maintains separate lists for
some of the more common sizes requested. For example, it might have a table with
n
entries, in which the first entry is a pointer to the head of a list of 4-KB holes, the
second entry is a pointer to a list of 8-KB holes, the third entry a pointer to 12-KB
holes, and so on. Holes of, say, 21 KB, could be put either on the 20-KB list or on
a special list of odd-sized holes.
With quick fit, finding a hole of the required size is extremely fast, but it has
the same disadvantage as all schemes that sort by hole size, namely, when a proc-
ess terminates or is swapped out, finding its neighbors to see if a merge with them
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
Concordia_University
School:
Operating_Systems
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
