From ed7cb4560c81c944cbc3347c966a49fbabd4c990 Mon Sep 17 00:00:00 2001
From: Juan Marín Noguera <juan@mnpi.eu>
Date: Mon, 6 Jan 2025 22:29:34 +0100
Subject: Finish TAOCP Volume 1 (Third Edition)

MMIX fascicle not included.
---
 2.5.lyx | 1608 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 1596 insertions(+), 12 deletions(-)

(limited to '2.5.lyx')

diff --git a/2.5.lyx b/2.5.lyx
index bfd6063..11320d9 100644
--- a/2.5.lyx
+++ b/2.5.lyx
@@ -91,31 +91,1615 @@
 
 \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 5,
- 6,
- 7,
- 12,
- 15,
- 17,
- 18,
- 19,
- 20,
- 22,
+TODO 22,
  23,
  25,
  26,
- 36 (3pp.,
- 2:53)
+ 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
-- 
cgit v1.2.3