From 4f670b750af5c11e1eac16d9cd8556455f89f46a Mon Sep 17 00:00:00 2001 From: Juan Marín Noguera Date: Fri, 16 May 2025 22:18:44 +0200 Subject: Changed layout for more manageable volumes --- vol1/2.5.lyx | 1706 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1706 insertions(+) create mode 100644 vol1/2.5.lyx (limited to 'vol1/2.5.lyx') 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 + + + + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\emph on +memory +\begin_inset Newline newline +\end_inset + +request +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\emph on +available areas, +\begin_inset Newline newline +\end_inset + +first-fit +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\emph on +available areas, +\begin_inset Newline newline +\end_inset + +best-fit +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +— + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +1300, + 1200 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +1300, + 1200 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +1100 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +200, + 1200 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +1300, + 100 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +250 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +200, + 950 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +1050, + 100 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +1000 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +stuck +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +50, + 100 +\end_layout + +\end_inset + + + + +\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}