Changed layout for more manageable volumes

1 files changed, 0 insertions, 1706 deletions

diff --git a/2.5.lyx b/2.5.lyx
deleted file mode 100644
index 11320d9..0000000
--- a/2.5.lyx
+++ /dev/null
@@ -1,1706 +0,0 @@
-#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