path: root/vol1/2.5.lyx

#LyX 2.4 created this file. For more info see https://www.lyx.org/
\lyxformat 620
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\begin_preamble
\input defs
\end_preamble
\use_default_options true
\maintain_unincluded_children no
\language english
\language_package default
\inputencoding utf8
\fontencoding auto
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_roman_osf false
\font_sans_osf false
\font_typewriter_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\float_placement class
\float_alignment class
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_formatted_ref 0
\use_minted 0
\use_lineno 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tablestyle default
\tracking_changes false
\output_changes false
\change_bars false
\postpone_fragile_content false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\docbook_table_output 0
\docbook_mathml_prefix 1
\end_header

\begin_body

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc5[18]
\end_layout

\end_inset

Suppose it is known that 
\family typewriter
N
\family default
 is always 100 or more in Algorithm A.
 Would it be a good idea to set 
\begin_inset Formula $c=100$
\end_inset

 in the modified step 
\begin_inset Formula $\text{A4}'$
\end_inset

?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

No,
 because while we cannot use that storage 
\emph on
right now
\emph default
,
 it might be worth it after the next allocated block gets freed.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc6[23]
\end_layout

\end_inset

(
\emph on
Next fit.
\emph default
) After Algorithm A has been used repeatedly,
 there will be a strong tendency for blocks of small 
\family typewriter
SIZE
\family default
 to remain at the front of the 
\family typewriter
AVAIL
\family default
 list,
 so that it will often be necessary to search quite far into the list before finding a block of length 
\family typewriter
N
\family default
 or more.
 For example,
 notice how the size of the blocks essentially increases in Fig.
 42,
 for both reserved and free blocks,
 from the beginning of memory to the end.
 (The 
\family typewriter
AVAIL
\family default
 list used while Fig.
 42 was being prepared was kept sorted by the order of location,
 as required by Algorithm B.) Can you suggest a way to modify Algorithm A so that
\end_layout

\begin_layout Enumerate
short blocks won't need to accumulate in a particular area,
 and
\end_layout

\begin_layout Enumerate
the 
\family typewriter
AVAIL
\family default
 list may still be kept in order of increasing memory locations,
 for purposes of algorithms like Algorithm B?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Yes,
 we could arrange the free space as a circular list and start each search where the previous one left off.
 In more precise terms,
 in A1 we would change 
\begin_inset Formula $\mathtt{Q}\gets\mathtt{LOC(AVAIL)}$
\end_inset

 to 
\begin_inset Formula $\mathtt{Q}\gets\mathtt{AVAIL}$
\end_inset

,
 in A4 we would add 
\begin_inset Formula $\mathtt{AVAIL}\gets\mathtt{Q}$
\end_inset

,
 and the test in A2 would be 
\begin_inset Formula $\mathtt{Q}=\mathtt{AVAIL}$
\end_inset

 rather than 
\begin_inset Formula $\mathtt{P}=\Lambda$
\end_inset

 and it would be skipped in the first iteration.
 Other algorithms that deal with memory management might need to be modified as well to avoid invalidating 
\family typewriter
AVAIL
\family default
.
 For example,
 algorithm B would have to deal with this when freeing the block just before it.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc7[10]
\end_layout

\end_inset

The example (1) shows that first-fit can sometimes be definitely superior to best-fit.
 Give a similar example that shows a case where best-fit is superior to first-fit.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="3">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\emph on
memory
\begin_inset Newline newline
\end_inset

request
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\emph on
available areas,
\begin_inset Newline newline
\end_inset

first-fit
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\emph on
available areas,
\begin_inset Newline newline
\end_inset

best-fit
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
—

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1300,
 1200
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1300,
 1200
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1100
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
200,
 1200
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1300,
 100
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
250
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
200,
 950
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1050,
 100
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1000
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
stuck
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
50,
 100
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc12[20]
\end_layout

\end_inset

Modify Algorithm A so that it follows the boundary-tag conventions (7)–(9),
 uses the modified step A4' described in the text,
 and also incorporates the improvement of exercise 6.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset


\series bold
Algorithm A'
\series default
 (
\emph on
Next-fit method with boundary-tag conventions
\emph default
).
 Let the heap be stored as in (7)–(9),
 
\begin_inset Formula $c$
\end_inset

 be as in step A4' in the text,
 and let 
\family typewriter
PTR
\family default
 be a variable whose value persists among runs of this algorithm and which starts with the value 
\family typewriter
AVAIL
\family default
.
 (We could just get rid of the list head in 
\family typewriter
LOC(AVAIL)
\family default
 and use this 
\family typewriter
Q
\family default
 instead of 
\family typewriter
AVAIL
\family default
,
 but let's follow convention (9).) For this algorithm 
\begin_inset Formula $\mathtt{N}$
\end_inset

 is two more than the number of words we want to allocate.
\end_layout

\begin_layout Enumerate
\begin_inset Argument item:1
status open

\begin_layout Plain Layout

\series bold
A1.
\end_layout

\end_inset

[Initialize.] Set 
\begin_inset Formula $\mathtt{P}\gets\mathtt{PTR}$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Argument item:1
status open

\begin_layout Plain Layout

\series bold
A2.
\end_layout

\end_inset


\begin_inset CommandInset label
LatexCommand label
name "enu:e2512b"

\end_inset

[Is 
\family typewriter
SIZE
\family default
 enough?] If 
\begin_inset Formula $\mathtt{SIZE(P)}\geq\mathtt{N}$
\end_inset

,
 go to 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:e2512d"
plural "false"
caps "false"
noprefix "false"
nolink "false"

\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Argument item:1
status open

\begin_layout Plain Layout

\series bold
A3.
\end_layout

\end_inset

[End of list?] Set 
\begin_inset Formula $\mathtt{P}\gets\mathtt{LINK(P)}$
\end_inset

.
 If 
\begin_inset Formula $\mathtt{P}=\mathtt{PTR}$
\end_inset

,
 the algorithm terminates unsuccessfully;
 there is no room for a block of 
\family typewriter
N
\family default
 consecutive blocks.
 Otherwise go back to 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:e2512b"
plural "false"
caps "false"
noprefix "false"
nolink "false"

\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Argument item:1
status open

\begin_layout Plain Layout

\series bold
A4.
\end_layout

\end_inset


\begin_inset CommandInset label
LatexCommand label
name "enu:e2512d"

\end_inset

[Reserve 
\family typewriter
N
\family default
.] Set 
\begin_inset Formula $\mathtt{K}\gets\mathtt{SIZE(P)}-\mathtt{N}$
\end_inset

,
 but if 
\begin_inset Formula $\mathtt{K}<c$
\end_inset

,
 set 
\begin_inset Formula $\mathtt{K}\gets0$
\end_inset

.
 Then,
 set 
\begin_inset Formula $\mathtt{L}\gets\mathtt{P}+\mathtt{K}$
\end_inset

 and 
\begin_inset Formula $\mathtt{TAG(L)}\gets\mathtt{TAG(P+SIZE(P)}-1\mathtt{)}\gets\text{``\ensuremath{+}''}$
\end_inset

.
 Finally,
 if 
\begin_inset Formula $\mathtt{K}=0$
\end_inset

,
 set 
\begin_inset Formula $\mathtt{LINK(LINK(P}+1\mathtt{))}\gets\mathtt{LINK(P)}$
\end_inset

 and 
\begin_inset Formula $\mathtt{LINK(LINK(P)}+1\mathtt{)}=\mathtt{LINK(P}+1\mathtt{)}$
\end_inset

;
 otherwise set 
\begin_inset Formula $\mathtt{SIZE(L)}\gets\mathtt{N}$
\end_inset

,
 
\begin_inset Formula $\mathtt{SIZE(P)}\gets\mathtt{SIZE(L}-1\mathtt{)}\gets\mathtt{K}$
\end_inset

,
 and 
\begin_inset Formula $\mathtt{TAG(L}-1\mathtt{)}\gets\text{``\ensuremath{-}''}$
\end_inset

.
 The result is an allocation of size 
\begin_inset Formula $\mathtt{SIZE(L)}-2\geq\mathtt{N}-2$
\end_inset

 that spans from 
\begin_inset Formula $\mathtt{L}+1$
\end_inset

 to 
\begin_inset Formula $\mathtt{L}+\mathtt{SIZE(L)}-1$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc15[24]
\end_layout

\end_inset

Show how to speed up Algorithm C at the expense of a slightly longer program,
 by not changing any more links than absolutely necessary in each of four cases depending on whether 
\begin_inset Formula $\mathtt{TAG(P0}-1\mathtt{)}$
\end_inset

,
 
\begin_inset Formula $\mathtt{TAG(P0}+\mathtt{SIZE(P0))}$
\end_inset

 are plus or minus.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer
\end_layout

\end_inset


\end_layout

\begin_layout Enumerate
[Initialize.] Set 
\begin_inset Formula $\mathtt{S}\gets\mathtt{SIZE(P0)}$
\end_inset

 and 
\begin_inset Formula $\mathtt{PU}\gets\mathtt{P0}+\mathtt{S}$
\end_inset

.
\end_layout

\begin_layout Enumerate
[Check lower bound.] If 
\begin_inset Formula $\mathtt{TAG(P0}-1\mathtt{)}=\text{``\ensuremath{+}''}$
\end_inset

,
 go to step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:e2515e"
plural "false"
caps "false"
noprefix "false"
nolink "false"

\end_inset

.
\end_layout

\begin_layout Enumerate
[Move to lower area.] Set 
\begin_inset Formula $\mathtt{S}\gets\mathtt{S}+\mathtt{SIZE(P0}-1\mathtt{)}$
\end_inset

 and 
\begin_inset Formula $\mathtt{P0}\gets\mathtt{P0}-\mathtt{SIZE(P0}-1\mathtt{)}$
\end_inset

.
\end_layout

\begin_layout Enumerate
[Remove upper area.] If 
\begin_inset Formula $\mathtt{TAG(PU)}=\text{``\ensuremath{-}''}$
\end_inset

,
 set 
\begin_inset Formula $\mathtt{P1}\gets\mathtt{LINK(PU)}$
\end_inset

,
 
\begin_inset Formula $\mathtt{P2}\gets\mathtt{LINK(PU}+1\mathtt{)}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK(P1}+1\mathtt{)}\gets\mathtt{P2}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK(P2}\mathtt{)}\gets\mathtt{P1}$
\end_inset

,
 and 
\begin_inset Formula $\mathtt{S}\gets\mathtt{S}+\mathtt{SIZE(PU)}$
\end_inset

.
 Go to step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:e2515g"
plural "false"
caps "false"
noprefix "false"
nolink "false"

\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:e2515e"

\end_inset

[Allocate.] If 
\begin_inset Formula $\mathtt{TAG(PU)}=\text{``\ensuremath{+}''}$
\end_inset

,
 set 
\begin_inset Formula $\mathtt{LINK(P0)}\gets\mathtt{AVAIL}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK(P0}+1\mathtt{)}\gets\mathtt{LOC(AVAIL)}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK(AVAIL}+1\mathtt{)}\gets\mathtt{P0}$
\end_inset

,
 and 
\begin_inset Formula $\mathtt{AVAIL}\gets\mathtt{P0}$
\end_inset

.
\end_layout

\begin_layout Enumerate
[Merge upper area.] Otherwise let 
\begin_inset Formula $\mathtt{P1}\gets\mathtt{LINK(P0)}\gets\mathtt{LINK(PU)}$
\end_inset

,
 
\begin_inset Formula $\mathtt{P2}\gets\mathtt{LINK(P0}+1\mathtt{)}\gets\mathtt{LINK(PU}+1\mathtt{)}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK(P1}+1\mathtt{)}\gets\mathtt{LINK(P2)}\gets\mathtt{P0}$
\end_inset

,
 and 
\begin_inset Formula $\mathtt{S}\gets\mathtt{SIZE(P0)}+\mathtt{SIZE(PU)}$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:e2515g"

\end_inset

[Update size.] Set 
\begin_inset Formula $\mathtt{TAG(P0)}\gets\mathtt{TAG(P0}+\mathtt{S}-1\mathtt{)}\gets\text{``\ensuremath{-}''}$
\end_inset

 and 
\begin_inset Formula $\mathtt{SIZE(P0)}\gets\mathtt{SIZE(P0}+\mathtt{S}-1\mathtt{)}\gets\mathtt{S}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc17[10]
\end_layout

\end_inset

What should the contents of 
\begin_inset Formula $\mathtt{LOC(AVAIL)}$
\end_inset

 and 
\begin_inset Formula $\mathtt{LOC(AVAIL)}+1$
\end_inset

 be in (9) when there are no available blocks present?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

They should both point to 
\begin_inset Formula $\mathtt{LOC(AVAIL)}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc18[20]
\end_layout

\end_inset

Figures 42 and 43 were obtained using the same data,
 and essentially the same algorithms (Algorithms A and B),
 except that Fig.
 43 was prepared by modifying Algorithm A to choose best-fit instead of first-fit.
 Why did this cause Fig.
 42 to have a large available area in the 
\emph on
higher
\emph default
 locations of memory,
 while in Fig.
 43 there is a large available area in the 
\emph on
lower
\emph default
 locations?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Both algorithms allocate at the end of the block of free memory that they choose,
 and in the beginning,
 both will allocate from higher to lower locations,
 leaving a large area at the end.
 
\end_layout

\begin_layout Standard
However,
 as soon as some of the areas allocated are freed,
 the best fit method will tend to use those newly freed areas from the higher locations since they will tend to be smaller,
 whereas the first fit method will prefer to allocate in the large lower area.
 
\end_layout

\begin_layout Standard
Eventually the first-fit method fills up the large area and starts allocating at other areas in the lower part,
 leaving the higher locations mostly free as the first chunks are freed,
 whereas the best fit method continues to avoid filling up this large area.
\end_layout

\begin_layout Standard
Note that this works because most allocations have a limited lifetime;
 in other algorithms it might be the case that some of the first allocations are never freed until the end of the algorithm while many other chunks appear and disappear quickly.
 In this case,
 the first fit method would still show some allocations in the higher locations,
 although more sparse than those in lower locations.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc19[24]
\end_layout

\end_inset

Suppose that blocks of memory have the form of (7),
 but without the 
\family typewriter
TAG
\family default
 or 
\family typewriter
SIZE
\family default
 fields required in the last word of the block.
 Suppose further that the following simple algorithm is being used to make a reserved block free again:
 
\begin_inset Formula $\mathtt{Q}\gets\mathtt{AVAIL}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK(P0)}\gets\mathtt{Q}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK(P0}+1\mathtt{)}\gets\mathtt{LOC(AVAIL)}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK(Q}+1\mathtt{)}\gets\mathtt{P0}$
\end_inset

,
 
\begin_inset Formula $\mathtt{AVAIL}\gets\mathtt{P0}$
\end_inset

,
 
\begin_inset Formula $\mathtt{TAG(P0)}\gets\text{``\ensuremath{-}''}$
\end_inset

.
 (This algorithm does nothing about collapsing adjacent areas together.)
\end_layout

\begin_layout Standard
Design a reservation algorithm,
 similar to Algorithm A,
 that does the necessary collapsing of adjacent free blocks while searching the 
\family typewriter
AVAIL
\family default
 list,
 and at the same time avoids any unnecessary fragmentation of memory as in (2),
 (3),
 and (4).
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

The following algorithm reserves a block of size 
\begin_inset Formula $\mathtt{N}\geq2$
\end_inset

 in the first available area while collapsing adjacent free blocks to find such area.
 In order to avoid unnecessary fragmentation,
 it allocates in the beginning of the block that is found rather than in the end.
\end_layout

\begin_layout Enumerate
[Initialize.] Set 
\begin_inset Formula $\mathtt{P}\gets\mathtt{AVAIL}$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:e2519b"

\end_inset

[Collapse free blocks.] Let 
\begin_inset Formula $\mathtt{PU}\gets\mathtt{P}+\mathtt{SIZE(P)}$
\end_inset

.
 If 
\begin_inset Formula $\mathtt{TAG(PU)}=\text{``\ensuremath{-}''}$
\end_inset

,
 then set 
\begin_inset Formula $\mathtt{P1}\gets\mathtt{LINK(PU)}$
\end_inset

,
 
\begin_inset Formula $\mathtt{P2}\gets\mathtt{LINK(PU}+1\mathtt{)}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK(P1}+1\mathtt{)}\gets\mathtt{P2}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK(P2)}\gets\mathtt{P1}$
\end_inset

,
 
\begin_inset Formula $\mathtt{SIZE(P)}\gets\mathtt{SIZE(P)}+\mathtt{SIZE(PU)}$
\end_inset

,
 and repeat this step.
\end_layout

\begin_layout Enumerate
[Do we have enough space?] If 
\begin_inset Formula $\mathtt{SIZE(P)}<\mathtt{N}$
\end_inset

,
 go to step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:e2519e"
plural "false"
caps "false"
noprefix "false"
nolink "false"

\end_inset

.
\end_layout

\begin_layout Enumerate
[Advance.] Set 
\begin_inset Formula $\mathtt{P}\gets\mathtt{LINK(P)}$
\end_inset

.
 If 
\begin_inset Formula $\mathtt{P}=\mathtt{LOC(AVAIL)}$
\end_inset

,
 terminate unsuccessfully;
 otherwise go to step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:e2519b"
plural "false"
caps "false"
noprefix "false"
nolink "false"

\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:e2519e"

\end_inset

[Reserve block.] Set 
\begin_inset Formula $\mathtt{P1}\gets\mathtt{LINK(P)}$
\end_inset

,
 
\begin_inset Formula $\mathtt{P2}\gets\mathtt{LINK(P}+1\mathtt{)}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK(P1}+1\mathtt{)}\gets\mathtt{P2}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK(P2)}\gets\mathtt{P1}$
\end_inset

,
 and 
\begin_inset Formula $\mathtt{TAG(P)}\gets\text{``}+''$
\end_inset

.
 
\begin_inset Formula $\mathtt{PF}\gets\mathtt{P+N}$
\end_inset

,
\end_layout

\begin_layout Enumerate
[Reclaim extra space.] Let 
\begin_inset Formula $\mathtt{K}\gets\mathtt{SIZE(P)}-\mathtt{N}$
\end_inset

 and 
\begin_inset Formula $\mathtt{PU}\gets\mathtt{P}+\mathtt{SIZE(P)}$
\end_inset

.
 If 
\begin_inset Formula $\mathtt{K}=0$
\end_inset

,
 or 
\begin_inset Formula $\mathtt{K}=1$
\end_inset

 and 
\begin_inset Formula $\mathtt{TAG(P1)}=\text{``\ensuremath{+}''}$
\end_inset

,
 then terminate the algorithm.
 Otherwise,
 set 
\begin_inset Formula $\mathtt{P1}\gets\mathtt{AVAIL}$
\end_inset

 and 
\begin_inset Formula $\mathtt{P2}\gets\mathtt{LOC(AVAIL)}$
\end_inset

 if 
\begin_inset Formula $\mathtt{TAG(PU)}=\text{``\ensuremath{+}''}$
\end_inset

,
 
\begin_inset Formula $\mathtt{P1}\gets\mathtt{LINK(PU)}$
\end_inset

 and 
\begin_inset Formula $\mathtt{P2}\gets\mathtt{LINK(PU}+1\mathtt{)}$
\end_inset

 otherwise.
 Finally set 
\begin_inset Formula $\mathtt{LINK(P1}+1\mathtt{)}\gets\mathtt{LINK(P2)}\gets\mathtt{PF}\gets\mathtt{P}+\mathtt{N}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK(PF)}\gets\mathtt{P1}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK(PF}+1\mathtt{)}\gets\mathtt{P2}$
\end_inset

,
 
\begin_inset Formula $\mathtt{SIZE(PF)}\gets\mathtt{K}$
\end_inset

,
 
\begin_inset Formula $\mathtt{TAG(PF)}\gets\text{``\ensuremath{-}''}$
\end_inset

,
 and 
\begin_inset Formula $\mathtt{SIZE(P)}\gets\mathtt{N}$
\end_inset

.
 The resulting block is at position 
\begin_inset Formula $\mathtt{P}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc20[00]
\end_layout

\end_inset

Why is it desirable to have the 
\begin_inset Formula $\mathtt{AVAIL[}k\mathtt{]}$
\end_inset

 lists in the buddy system doubly linked instead of simply having straight linear lists?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

To be able to remove arbitrary elements from the lists efficiently in step S2 of the liberation algorithm.
\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
TODO 22,
 23,
 25,
 26,
 36
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc22[21]
\end_layout

\end_inset

The text repeatedly states that the buddy system allows only blocks of size 
\begin_inset Formula $2^{k}$
\end_inset

 to be used,
 and exercise 21 shows this can lead to a substantial increase in the storage required.
 But if an 11-word block is needed in connection with the buddy system,
 why couldn't we find a 16-word block and divide it into an 11-word piece together with two free blocks of sizes 4 and 1?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

We could indeed modify the algorithms to work like this,
 although they would get quite complicated and slower (more blocks would have to be marked as reserved for the liberation algorithm to work).
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc23[05]
\end_layout

\end_inset

What is the binary address of the buddy of the block of size 4 whose binary address is 011011110000?
 What would it be if the block were of size 15 instead of 4?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

011011110100 and 011011100000,
 respectively.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc25[22]
\end_layout

\end_inset

Criticize the following idea:
 
\begin_inset Quotes eld
\end_inset

Dynamic storage allocation using the buddy system will never reserve a block of size 
\begin_inset Formula $2^{m}$
\end_inset

 in practical situations (since this would fill the whole memory),
 and,
 in general,
 there is a maximum size 
\begin_inset Formula $2^{n}$
\end_inset

 for which no blocks of greater size will ever be reserved.
 Therefore it is a waste of time to start with such large blocks available,
 and to combine buddies in Algorithm S when the combined block has a size larger than 
\begin_inset Formula $2^{n}$
\end_inset

.
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

While this is correct when we actually know the program and the size of the allocations it can make is bounded for any valid input,
 there are many situations where this is not the case,
 for example when we are writing a library or when the size of some allocation depends on the input;
 then the program would spuriously fail for inputs that it could otherwise have processed at least in a some computer.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc26[21]
\end_layout

\end_inset

Explain how the buddy system could be used for dynamic storage allocation in memory locations 0 through 
\begin_inset Formula $\mathtt{M}-1$
\end_inset

 even when 
\family typewriter
M
\family default
 does not have the form 
\begin_inset Formula $2^{m}$
\end_inset

 as required in the text.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

If 
\begin_inset Formula $m$
\end_inset

 is an integer such that 
\begin_inset Formula $2^{m}\leq\mathtt{M}<2^{m+1}$
\end_inset

,
 the memory could be split into pieces of size 
\begin_inset Formula $2^{k}$
\end_inset

,
 
\begin_inset Formula $0\leq k\leq m$
\end_inset

,
 no more than one piece of the same size.
 For example,
 for locations 0 to 3999,
 we would initially have one free area at 0 of size 2048,
 another one at 2048 of size 1024,
 another one at 3072 of size 512,
 another one at 3584 of size 256,
 another one at 3840 of size 128,
 and another one at 3968 of size 32.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc36[20]
\end_layout

\end_inset

A certain lunch counter in Hollywood,
 California,
 contains 23 seats in a row.
 Diners enter the shop in groups of one or two,
 and a glamorous hostess shows them where to sit.
 Prove that she will always be able to seat people immediately without splitting up any pairs,
 if no customer who comes alone is assigned to any of the seats numbered 2,
 5,
 8,
 ...,
 20,
 provided that there never are more than 16 customers present at a time.
 (Pairs leave together.)
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

A single customer can always seat,
 and they can avoid the 
\begin_inset Quotes eld
\end_inset

forbidden
\begin_inset Quotes erd
\end_inset

 seats.
 Now,
 if a pair comes,
 there were at most 14 customers already there.
 If seats 22 and 23 are free,
 then we can sit the pair there.
 Otherwise there are at most 13 customers in the seats 1–21,
 so if we divide the seats in 7 groups of 3 (1–3,
 4–6,
 etc.),
 at least one of these groups has no more than one seat taken,
 and it cannot be the middle one,
 so that group has two consecutive free seats where we can seat the pair.
\end_layout

\end_body
\end_document