diff options
Diffstat (limited to 'vol1/2.5.lyx')
| -rw-r--r-- | vol1/2.5.lyx | 1706 |
1 files changed, 1706 insertions, 0 deletions
diff --git a/vol1/2.5.lyx b/vol1/2.5.lyx new file mode 100644 index 0000000..11320d9 --- /dev/null +++ b/vol1/2.5.lyx @@ -0,0 +1,1706 @@ +#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 |