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 --- 2.5.lyx | 1706 --------------------------------------------------------------- 1 file changed, 1706 deletions(-) delete mode 100644 2.5.lyx (limited to '2.5.lyx') 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 - - - - - - - -\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}