|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 223 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 223
192
MEMORY MANAGEMENT
CHAP. 3
Memory Management with Linked Lists
Another way of keeping track of memory is to maintain a linked list of allo-
cated and free memory segments, where a segment either contains a process or is
an empty hole between two processes. The memory of Fig. 3-6(a) is represented in
Fig. 3-6(c) as a linked list of segments. Each entry in the list specifies a hole (H) or
process (P), the address at which it starts, the length, and a pointer to the next item.
In this example, the segment list is kept sorted by address. Sorting this way has
the advantage that when a process terminates or is swapped out, updating the list is
straightforward. A terminating process normally has two neighbors (except when
it is at the very top or bottom of memory).
These may be either processes or holes,
leading to the four combinations shown in Fig. 3-7. In Fig. 3-7(a) updating the list
requires replacing a P by an H.
In Fig. 3-7(b) and Fig. 3-7(c), two entries are coa-
lesced into one, and the list becomes one entry shorter.
In Fig. 3-7(d), three entries
are merged and two items are removed from the list.
Since the process table slot for the terminating process will normally point to
the list entry for the process itself, it may be more convenient to have the list as a
double-linked list, rather than the single-linked list of Fig. 3-6(c). This structure
makes it easier to find the previous entry and to see if a merge is possible.
becomes
becomes
becomes
becomes
(a)
A
X
B
(b)
A
X
(c)
X
B
(d)
X
Before X terminates
A
B
A
B
After X terminates
Figure 3-7.
Four neighbor combinations for the terminating process,
X
.
When the processes and holes are kept on a list sorted by address, several algo-
rithms can be used to allocate memory for a created process (or an existing process
being swapped in from disk).
We assume that the memory manager knows how
much memory to allocate. The simplest algorithm is
first fit
.
The memory man-
ager scans along the list of segments until it finds a hole that is big enough. The
hole is then broken up into two pieces, one for the process and one for the unused
memory, except in the statistically unlikely case of an exact fit. First fit is a fast al-
gorithm because it searches as little as possible.
A minor variation of first fit is
next fit
.
It works the same way as first fit, ex-
cept that it keeps track of where it is whenever it finds a suitable hole. The next
time it is called to find a hole, it starts searching the list from the place where it left
off last time, instead of always at the beginning, as first fit does. Simulations by
Bays (1977) show that next fit gives slightly worse performance than first fit.
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
