\part{DATA BASES}
\chapter[ Memory Management]{Memory Management}
\index{memory management|(}\nevindex{Balogh, Ádám}\nevindex{Iványi, Antal Miklós}
The main task of computers is to execute programs (even usually several programs running
simultaneously). These programs and their data must be in the
main memory of the computer during the execution.
Since the main memory is usually too small to store all these data and programs, modern computer systems
have a secondary storage too for the provisional storage of the data and programs.
In this chapter the basic algorithms of memory management will be covered.
In Section \ref{sec:part} static and dynamic partitioning, while
in Section \ref{sec:paging} the most popular paging methods will be discussed.
In Section \ref{sec:anomaly} the most famous anomaly of the history of operating systems---
the stunning features of FIFO page changing algorithm, interleaved memory and processing
algorithms with lists---will be analysed.
Finally in Section \ref{sec:filepacking} the discussion of the optimal and approximation algorithms
for the optimisation problem in which there are files with given size to be stored on the least
number of disks can be found.
\section{Partitioning}\label{sec:part}
A simple way of sharing the memory between programs is to divide the whole address space into slices,
and assign such a slice to every process. These slices are called \ki{partitions.}\inddef{partition}
The solution does not require any special hardware support, the only thing needed is that programs should be
ready to be loaded to different memory addresses, i.e., they should be \ki{relocatable.}\inddef{relocatable programs}
This must be required since it cannot be guaranteed that a program always gets into the same partition,
because the total size of the executable programs is usually much more than the size of the whole memory.
Furthermore, we cannot determine which programs can run simultaneously and which not,
for processes are generally independent of each other, and in many cases their owners are different users.
Therefore, it is also possible that the same program is executed by different users at the same time,
and different instances work with different data, which can therefore not be stored in the same part of the memory.
Relocation can be easily performed if the linker does not work with absolute but with relative memory addresses,
which means it does not use exact addresses in the memory but a base address and an offset.
This method is called \ki{base addressing,}\inddef{base addressing} where the initial address is stored
in the so called base register. Most processors know this addressing method, therefore, the program will not be slower
than in the case using absolute addresses. By using base addressing it can also be avoided that---due to an error
or the intentional behaviour of a user---the program reads or modifies the data of other programs
stored at lower addresses of the memory. If the solution is extended by another register, the so called
limit register which stores the biggest allowed offset, i.e. the size of the partition,
then it can be assured that the program cannot access other programs stored at higher memory addresses either.
Partitioning was often used in mainframe computer operating systems before. Most of the modern operating systems, however, use virtual memory management which requires special hardware support.
Partitioning as a memory sharing method is not only applicable in operating systems.
When writing a program in a language close to machine code, it can happen that
different data structures with variable size---which are created and cancelled dynamically---have
to be placed into a continuous memory space. These data structures are similar to processes,
with the exception that security problems like addressing outside their own area
do not have to be dealt with. Therefore, most of the algorithms listed below
with some minor modifications can be useful for application development as well.
Basically, there are two ways of dividing the address space into partitions. One of them divides
the initially empty memory area into slices, the number and size of which is predetermined at the beginning,
and try to place the processes and other data structures continuously into them, or remove them from
the partitions if they are not needed any more. These are called fixed partitions, since both their place
and size have been fixed previously, when starting the operating system or the application.
The other method is to allocate slices from the free parts of the memory to the newly created
processes and data structures continuously, and to deallocate the slices again when those end.
This solution is called dynamic partitioning, since partitions are created and destroyed dynamically.
Both methods have got advantages as well as disadvantages, and their implementations require totally
different algorithms. These will be discussed in the following.
\subsection{Fixed partitions}
Using \ki{fixed partitions}\inddef{fixed partitions}\index{partition!fixed} the division
of the address space is fixed at the beginning, and cannot be changed later while the system is up.
In the case of operating systems the operator defines the partition table which is activated at next reboot.
Before execution of the first application, the address space is already partitioned. In the case of
applications partitioning has to be done before creation of the first data structure in the designated
memory space. After that data structures of different sizes can be placed into these partitions.
In the following we examine only the case of operating systems, while we leave to the Reader
the rewriting of the problem and the algorithms according to given applications, since these can
differ significantly depending on the kind of the applications.
The partitioning of the address space must be done after examination of the sizes
and number of possible processes running on the system. Obviously, there is a maximum size,
and programs exceeding it cannot be executed. The size of the largest partition corresponds to this maximum size.
To reach the optimal partitioning, often statistic surveys have to be carried out,
and the sizes of the partitions have to be modified according to these statistics before restarting the system next time.
We do not discuss the implementation of this solution now.
Since there are a constant number (\var{m}) of partitions, their data can be stored in one or
more arrays with constant lengths. We do not deal with the particular place of the partitions
on this level of abstraction either; we suppose that they are stored in a constant array as well.
When placing a process in a partition, we store the index of that partition in the process header
instead of its starting address. However, concrete implementation can differ from this method, of course.
The sizes of the partitions are stored in array $\var{size}[1 \twodots m]$. Our processes are numbered
from $1$ to \var{n}. The array $\var{part}[1 \twodots m]$ keeps track of the processes executed in the individual
partitions, while its inverse, array $\var{place}[1 \twodots n]$ stores the places where individual
processes are executed. A process is either running, or waiting for a partition. This information is stored
in Boolean array $\var{waiting}[1 \twodots n]$: if process number $i$ is waiting, then
$\var{waiting}[i] = \textsc{true}$, else $\var{waiting}[i] = \textsc{false}$. The space requirements
of the processes are different. Array $\var{spacereq}[1 \twodots n]$ stores the minimum sizes of
partitions required to execute the individual processes.
Having partitions of different sizes and processes with different space requirements,
we obviously would not like small processes to be placed into large partitions, while smaller
partitions are empty, in which larger processes do not fit. Therefore, our goal is to assign each partition
to a process fitting into it in a way that there is no larger process that would fit into it as well.
This is ensured by the following algorithm:
\begin{alg}{Largest-Fit(\var{place},\var{spacereq},\var{size},\var{part},\var{waiting})}\inddef{\textsc{Largest-Fit}}
1 \' \key{for} \= $\var{j} \leftarrow 1$ \key{to} $\var{m}$\\
2 \' \> \key{do} \= \key{if} \= $\var{part}[\var{j}]=0$\\
3 \' \> \> \> \key{then} \= \textsc{Load-Largest(\var{place},\var{spacereq},\var{size},\var{j},\var{part},\var{waiting})}
\end{alg}
Finding the largest process the whose space requirement is not larger than a particular size is a simple conditional
maximum search. If we cannot find any processes meeting the requirements, we must leave the the partition empty.
\begin{alg}{Load-Largest(\var{place},\var{spacereq},\var{size},\var{p},\var{part},\var{waiting})}\inddef{\textsc{Load-Largest}}
1 \' $\var{max} \leftarrow 0$\\
2 \' $\var{ind} \leftarrow 0$
\algnewpage
3 \' \key{for} \= $\var{i} \leftarrow 1$ \key{to} $\var{n}$\\
4 \' \> \key{do} \= \key{if} \= $\var{waiting}[\var{i}]$ and $\var{spacereq}[\var{i}] \leq\var{size}[\var{p}]$
and $\var{spacereq}[\var{i}]>\var{max}$\\
5 \' \> \> \> \key{then} \= $\var{ind} \leftarrow \var{i}$\\
6 \' \> \> \> \> $\var{max} \leftarrow \var{spacereq}[\var{i}]$ \\
7 \' \key{if} \= $\var{ind}>0$\\
8 \' \> \key{then} \= $\var{part}[\var{p}] \leftarrow \var{ind}$\\
9 \' \> \> $\var{place}[\var{ind}] \leftarrow \var{p}$\\
10 \' \> \> $\var{waiting}[\var{ind}] \leftarrow \textsc{false}$
\end{alg}
The basic criteria of the correctness of all the algorithms loading the processes into the partitions is that they should not load a process into a partition which does not fit. This requirement is fulfilled by the above algorithm, since it can be derived from the conditional maximum search theorem exactly with the mentioned condition.
Another essential criterion is that it should not load more than one processes into the same partition, and also should not load one single process into more partitions simultaneously. The first case can be excluded, because we call the \textsc{Load-Largest} algorithm only for the partitions for which $\var{part}[j]=0$ and if we load a process into partition number $p$, then we give $\var{part}[p]$ the index of the loaded process as a value, which is a positive integer. The second case can be proved similarly: the condition of the conditional maximum search excludes the processes for which
$\var{waiting}[i]=\textsc{false}$, and if the process number $ind$ is loaded into one of the partitions, then the value of $\var{waiting}[ind]$ is set to \textsc{false}.
However, the fact that the algorithm does not load a process into a partition where it does not fit, does not load more then one processes into the same partition, or one single process into more partitions simultaneously is insufficient. These requirements are fulfilled even by an empty algorithm. Therefore, we have to require something more: namely that it should not leave a partition empty, if there is a process that would fit into it. To ensure this, we need an invariant, which holds during the whole loop, and at the end of the loop it implies our new requirement. Let this invariant be the following: after examination of $j$ partitions, there is no positive $k \le j$,
for which $\var{part}[k]=0$, and for which there is a positive $i \le n,$ such as $\var{waiting}[i] = \textsc{true}$, and
$\var{spacereq}[i] \le \var{size}[k]$.
\begin{description}
\item[Initialisation: ] At the beginning of the algorithm we have examined $j=0$ partitions, so there is not any positive $k \le j$.
\item[Maintenance: ] If the invariant holds for $j$ at the beginning of the loop, first we have to check whether it holds for the same $j$ at the end of the loop as well. It is obvious, since the first $j$ partitions are not modified when examining the $(j + 1)$-th one, and for the processes they contain $\var{waiting}[i]=\textsc{false}$, which does not satisfy the condition of the conditional maximum search in the \textsc{Load-Largest} algorithm. The invariant holds for the $(j + 1)$-th partition at the end of the loop as well, because if there is a process which fulfills the condition, the conditional maximum search certainly finds it, since the condition of our conditional maximum search corresponds to the requirement of our invariant set on each partition.
\item[Termination: ] Since the loop traverses a fixed interval by one, it will certainly stop. Since the loop body is executed exactly as many times as the number of the partitions, after the end of the loop there is no positive $k \le m$,
for which $\var{part}[k]=0$,, and for which there is a positive $i \le n$, such that $\var{waiting}[i] = \textsc{true}$ and
$\var{spacereq}[i] \le \var{size}[k]$, which means that we did not fail to fill any partitions that could be assigned to a process fitting into it.
\end{description}
The loop in rows 1--3 of the \textsc{Largest-Fit} algorithm is always executed in its entirety, so the loop body is executed $\Theta(m)$ times. The loop body performs a conditional maximum search on the empty partitions -- or on partitions for which $\var{part}[j] = 0$. Since the condition in row 4 of the \textsc{Load-Largest} algorithm has to be evaluated for each $j$, the conditional maximum search runs in $\Theta(n)$. Although the loading algorithm will not be called for partitions for which $\var{part}[j] > 0$, as far as running time is concerned, in the worst case even all the partitions might be empty, therefore the time complexity of our algorithm is $\Theta(mn)$.
Unfortunately, the fact that the algorithm fills all the empty partitions with waiting processes fitting into them whenever possible is not always sufficient. A very usual requirement is that the execution of every process should be started within a determined time limit. The above algorithm does not ensure it, even if there is an upper limit for the execution time of the processes. The problem is that whenever the algorithm is executed, there might always be new processes that prevent the ones waiting for long from execution. This is shown in the following example.
\begin{pelda}
Suppose that we have two partitions with sizes of 5 kB and 10 kB. We also have two processes with space requirements of 8 kB and 9 kB. The execution time of both processes is 2 seconds. But at the end of the first second a new process appears with space requirement of 9 kB and execution time of 2 seconds again, and the same happens in every 2 seconds, i. e., in the third, fifth, etc. second. If we have a look at our algorithm, we can see that it always has to choose between two processes, and the one with space requirement of 9 kB will always be the winner. The other one with 8 kB will never get into the memory, although there is no other partition into which it would fit.
\end{pelda}
To be able to fulfill this new requirement mentioned above, we have to slightly modify our algorithm:
the long waiting processes must be preferred over all the other processes,
even if their space requirement is smaller than that of the others.
Our new algorithm will process all the partitions, just like the previous one.
\begin{alg}{Largest-or-Long-Waiting-Fit(\var{place},\var{spacereq},\var{threshold},\var{size},\var{part},\var{waiting})}\inddef{\textsc{Largest-or-Long-Waiting-Fit}}
1 \' \key{for} \= $\var{j} \leftarrow 1$ \key{to} $\var{m}$\\
2 \' \> \key{do} \= \key{if} \= $\var{part}[\var{j}]=0$\\
3 \' \> \> \>\key{then} \= \textsc{Load-Largest-or-Long-Waiting(} \= \textsc{\var{place},\var{spacereq},\var{threshold},}\\
\> \> \> \> \> \textsc{\var{size},\var{j},\var{part},\var{waiting})}
\end{alg}
However, this time we keep track on the waiting time of each process. Since the algorithm is only executed when one or more partitions become free, we cannot examine the concrete time, but the number of cases where the process would have fit into a partition but we have chosen another process to fill it. To implement this, the conditional maximum search algorithm has to be modified: operations have to be performed also on items that meet the requirement (they are waiting for memory and they would fit), but they are not the largest ones among those. This operation is a simple increment of the value of a counter. We assume that the value of the counter is 0 when the process starts. The condition of the search has to be modified as well: if the value of the counter of a process is too high, (i. e., higher than a certain $\var{threshold}$), and it is higher than the value of the counter of the process with the largest space requirement found so far, then we replace it with this new process. The pseudo code of the algorithm is the following:
\begin{alg}{Load-Largest-or-Long-Waiting(\var{place},\var{spacereq},\var{threshold},\var{size},\var{p},\var{part},\var{waiting})}\inddef{\textsc{Load-Largest-or-Long-Waiting}}
1 \' $\var{max} \leftarrow 0$\\
2 \' $\var{ind} \leftarrow 0$\\
3 \' \key{for} \= $\var{i} \leftarrow 1$ \key{to} $\var{n}$\\
4 \' \> \key{do} \= \key{if} \= $\var{waiting}[\var{i}]$ and $\var{spacereq}[\var{i}] \leq \var{size}[\var{p}]$\\
5 \' \> \> \> \key{then} \= \key{if} \= ($\var{points}[\var{i}]>\var{threshold}$ and
$\var{points}[\var{i}] >\var{points}[\var{ind}]$) or\\
\> \> \> \> \> $\var{spacereq}[\var{i}]>\var{max}$\\
6 \' \> \> \> \> \> \key{then} \= $\var{points}[\var{ind}] \leftarrow \var{points}[\var{ind}]+1$\\
7 \' \> \> \> \> \> \> $\var{ind} \leftarrow \var{i}$\\
8 \' \> \> \> \> \> \> $\var{max} \leftarrow \var{spacereq}[\var{i}]$\\
9 \' \> \> \> \> \> \key{else} \> $\var{points}[\var{i}] \leftarrow \var{points}[\var{i}]+1$\\
10 \' \key{if} \= $\var{ind}>0$\\
11 \' \> \key{then} \= $\var{part}[\var{p}] \leftarrow \var{ind}$\\
12 \' \> \> $\var{place}[\var{ind}] \leftarrow \var{p}$\\
13 \' \> \> $\var{waiting}[\var{ind}] \leftarrow \textsc{false}$
\end{alg}
The fact that the algorithm does not place multiple processes into the same partition can be proved the same way as for the previous algorithm, since the outer loop and the condition of the branch has not been changed. To prove the other two criteria (namely that a process will be placed neither into more then one partitions, nor into a partition into which it does not fit), we have to see that the condition of the conditional maximum search algorithm has been modified in a way that this property stays. It is easy to see that the condition has been split into two parts, so the first part corresponds exactly to our requirement, and if it is not satisfied, the algorithm certainly does not place the process into the partition. The property that there are no partitions left empty also stays, since the condition for choosing a process has not been restricted, but extended. Therefore, if the previous algorithm found all the processes that met the requirements, the new one finds them as well. Only the order of the processes fulfilling the criteria has been altered. The time complexity of the loops has not changed either, just like the condition, according to which the inner loop has to be executed. So the time complexity of the algorithm is the same as in the original case.
We have to examine whether the algorithm satisfies the condition that a process can wait for memory only for a given time, if we suppose that there is some $p$ upper limit for the execution time of the processes (otherwise the problem is insoluble, since all the partitions might be taken by an infinite loop). Furthermore, let us suppose that the system is not overloaded, i. e., we can find a $q$ upper estimation for the number of the waiting processes in every instant of time. Knowing both limits it is easy to see that in the worst case to get assigned to a given partition a process has to wait for the processes with higher counters than its own one (at most $q$ many), and at most $\var{threshold}$ many processes larger than itself. Therefore, it is indeed possible to give an upper limit for the maximum waiting time for memory in the worst case: it is $(q + \var{threshold}) p$.
\begin{pelda}
In our previous example the process with space requirement of 8 kB has to wait for $\var{threshold} + 1 = k$ other processes, all of which lasts for 2 seconds, i. e., the process with space requirement of 8 kB has to wait exactly for 2k seconds to get into the partition with size of 10 kB.
\end{pelda}
In our algorithms so far the absolute space requirement of the processes served as the basis of their priorities. However this method is not fair: if there is a partition, into which two processes would fit, and neither of them fits into a smaller partition, then the difference in their size does not matter, since sooner or later also the smaller one has to be placed into the same, or into another, but not smaller partition. Therefore, instead of the absolute space requirement, the size of the smallest partition into which the given process fits should be taken into consideration when determining the priorities. Furthermore, if the partitions are increasingly ordered according to their sizes, then the index of the smallest partition in this ordered list is the priority of the process. It is called the rank of the process. The following algorithm calculates the ranks of all the processes.
\begin{algN}{Calculate-Rank(\var{spacereq},\var{size},\var{rank})}\inddef{\textsc{Calculate-Rank}}
1 \' $\var{order} \leftarrow \textsc{Sort(\var{size})}$\\
2 \' \key{for} \= $\var{i} \leftarrow 1$ \key{to} $\var{n}$\\
3 \' \> \key{do} \= $\var{u} \leftarrow 1$\\
4 \' \> \> $\var{v} \leftarrow \var{m}$\\
5 \' \> \> $\var{rank}[\var{i}] \leftarrow \lfloor (u+v)/2 \rfloor$\\
6 \' \> \> \key{while} \= $\var{order}[\var{rank}[\var{i}]]<\var{spacereq}[\var{i}]$ or
$\var{order}[\var{rank}[\var{i}]+1]>\var{spacereq}[\var{i}]$ \\
7 \' \> \> \> \key{do} \= \key{if} \= $\var{order}[\var{rank}[\var{i}]]<\var{spacereq}[\var{i}]$\\
8 \' \> \> \> \> \> \key{then} \= $\var{u} \leftarrow \var{rank}[i]+1$\\
9 \' \> \> \> \> \> \key{else} \= $\var{v} \leftarrow \var{rank}[i]-1$\\
10 \' \> \> \> $\var{rank}[\var{i}] \leftarrow \lfloor (u+v)/2 \rfloor$
\end{algN}
It is easy to see that this algorithm first orders the partitions increasingly according to their sizes, and then calculates the rank for each process. However, this has to be done only at the beginning, or when a new process comes. In the latter case the inner loop has to be executed only for the new processes. Ordering of the partitions does not have to be performed again, since the partitions do not change. The only thing that must be calculated is the smallest partition the process fits into. This can be solved by a logarithmic search, an algorithm whose correctness is proved. The time complexity of the rank calculation is easy to determine: the ordering of the partition takes $\Theta(m\log_2 m)$ steps, while the logarithmic search $\Theta(\log_2 m)$, which has to be executed for $n$ processes. Therefore the total number of steps is $\Theta((n+m)\log_2 m)$.
After calculating the ranks we have to do the same as before, but for ranks instead of space requirements.
\begin{alg}{Long-Waiting-or-Not-Fit-Smaller(\var{place},\var{spacereq},\var{threshold},\var{size},\var{part},\var{waiting})}\inddef{\textsc{Long-Waiting-or-Not-Fit-Smaller}}
1 \' \key{for} \= $\var{j} \leftarrow 1$ \key{to} $\var{m}$\\
2 \' \> \key{do} \= \key{if} \= $\var{part}[\var{j}]=0$\\
3 \' \> \> \>\key{then} \= \textsc{Load-Long-Waiting-or-Not-Smaller(} \=\textsc{\var{place},\var{spacereq},}\\
\> \> \> \> \>\textsc{\var{threshold},\var{size},\var{j},}\\
\> \> \> \> \>\textsc{\var{part},\var{waiting})}
\end{alg}
In the loading algorithm, the only difference is that the conditional maximum search has to be executed not on array $\var{size}$, but on array $\var{rank}$:
\begin{algN}{Load-Long-Waiting-or-Not-Smaller(\var{place},\var{spacereq},\var{threshold},\var{size},\var{p},\var{part},\var{waiting})}\inddef{\textsc{Load-Long-Waiting-or-Not-Smaller}}
1 \' $\var{mx} \leftarrow 0$\\
2 \' $\var{ind} \leftarrow 0$\\
3 \' \key{for} \= $\var{i} \leftarrow 1$ \key{to} $\var{n}$\\
4 \' \> \key{do} \= \key{if} \= $\var{waiting}[\var{i}]$ and $\var{spacereq}[\var{i}]\leq\var{size}[\var{p}]$\\
5 \' \> \> \> \key{then} \= \key{if} \= ($\var{points}[\var{i}]>\var{threshold}$ and
$\var{points}[\var{i}]>\var{points}[\var{ind}]$) or\\
\> \> \> \> \> $\var{rank}[\var{i}]>\var{max}$\\
6 \' \> \> \> \> \> \key{then} \= $\var{points}[\var{ind}] \leftarrow \var{points}[\var{ind}]+1$\\
7 \' \> \> \> \> \> \> $\var{ind} \leftarrow \var{i}$\\
8 \' \> \> \> \> \> \> $\var{max} \leftarrow \var{rank}[\var{i}]$\\
9 \' \> \> \> \> \> \key{else} \> $\var{points}[\var{i}] \leftarrow \var{points}[\var{i}]+1$\\
10 \' \key{if} \= $\var{ind}>0$\\
11 \' \> \key{then} \= $\var{part}[\var{p}] \leftarrow \var{ind}$\\
12 \' \> \> $\var{place}[\var{ind}] \leftarrow \var{p}$\\
13 \' \> \> $\var{waiting}[\var{ind}] \leftarrow \textsc{false}$
\end{algN}
\vspace{-2mm}
The correctness of the algorithm follows from the previous version of the algorithm and the algorithm calculating the rank. The time complexity is the same as that of the previous versions.
\vspace{-2mm}
\begin{pelda}
Having a look at the previous example it can be seen that both the processes with space requirement of 8 kB and 9 kB can fit only into the partition with size of 10 kB, and cannot fit into the 5 kB one. Therefore their ranks will be the same (it will be two), so they will be loaded into the memory in the order of their arrival, which means that the 8 kB one will be among the first two.
\end{pelda}
\vspace{-4mm}
\subsection{Dynamic partitions}
\ki{Dynamic partitioning}\inddef{dynamic partitions}\index{partition!dynamic} works in a totally different way from the fixed one. Using this method we do not search for the suitable processes for every empty partition, \linebreak
\newpage
\noindent but search for suitable memory space for every waiting process, and there we create partitions dynamically. This section is restricted to the terminology of operating systems as well, but of course, the algorithms can be rewritten to solve problems connected at the application level as well.
If all the processes would finish at the same time, there would not be any problems, since the empty memory space could be filled up from the bottom to the top continuously. Unfortunately, however, the situation is more complicated in the practice, as processes can differ significantly from each other, so their execution time is not the same either. Therefore, the allocated memory area will not always be contiguous, but there might be free partitions between the busy ones. Since copying within the memory is an extremely expensive operation, in practice it is not effective to collect the reserved partitions into the bottom of the memory. Collecting the partitions often cannot even be carried out due to the complicated relative addressing methods often used. Therefore, the free area on which the new processes have to be placed is not contiguous. It is obvious, that every new process must be assigned to the beginning of a free partition, but the question is, which of the many free partitions is the most suitable.
Partitions are the simplest to store in a linked list. Naturally, many other, maybe more efficient data structures could be found, but this is sufficient for the presentation of the algorithms listed below. The address of the first element of linked list $P$ is stored in $\var{head}[P]$. The beginning of the partition at address $p$ is stored in $\var{beginning}[p]$, its size in $\var{size}[p]$, and the process assigned to it is stored in variable $\var{part}[p]$. If the identifier of a process is $0$, then it is an empty one, otherwise it is a allocated. In the linked list the address of the next partition is $\var{next}[p]$.
To create a partition of appropriate size dynamically, first we have to divide a free partition, which is at least as big as needed into two parts. This is done by the next algorithm.
\begin{alg}{Split-Partition(\var{border},\var{beginning},\var{next},\var{size},\var{p},\var{q})}\inddef{\textsc{Split-Partition}}
1 \' $\var{beginning}[\var{q}] \leftarrow \var{beginning}[\var{p}] + \var{border}$\\
2 \' $\var{size}[\var{q}] \leftarrow \var{size}[\var{p}] - \var{border}$\\
3 \' $\var{size}[\var{p}] \leftarrow \var{border}$\\
4 \' $\var{next}[\var{q}] \leftarrow \var{next}[\var{p}]$\\
5 \' $\var{next}[\var{q}] \leftarrow \var{q}$
\end{alg}
In contrast to the algorithms connected to the method of fixed partitions, where processes were chosen to partitions, here we use a reverse approach. Here we inspect the list of the processes, and try to find to each waiting process a free partition into which it fits. If we found one, we cut the required part off from the beginning of the partition, and allocate it to the process by storing its beginning address in the process header. If there is no such free partition, then the process remains in the waiting list.
\newpage
\begin{alg}{Place(\var{P},\var{head},\var{next},\var{last},\var{beginning},\var{size},\var{part},\var{spacereq},\var{place})}\inddef{\textsc{Place}}
1 \' \key{for} \= $\var{i} \leftarrow 1$ \key{to} $\var{n}$\\
2 \' \> \key{do} \= \key{if} \= $\var{waiting}[\var{i}] = \textsc{true}$\\
3 \' \> \> \> \key{then} \= \textsc{$\star$-Fit}(\= \var{P},\var{head},\var{next},\var{last},\var{beginning},\var{size},\var{part},\var{spacereq},\var{place},\\
\> \> \> \> \> \var{waiting}, \var{i})
\end{alg}
The $\star$ in the pseudo code is to be replaced by one of the words \textsc{First},
\textsc{Next}, \textsc{Best}, \textsc{Limited-Best}, \textsc{Worst} or \textsc{Limited-Worst}.
There are several possibilities for choosing the suitable free partition.
The more simple idea is to go through the list of the partitions from the beginning
until we find the first free partition into which it fits. This can easily be solved using linear searching.
\begin{alg}{First-Fit(\var{P},\var{head},\var{next},\var{last},\var{beginning},\var{size},\var{part},\var{spacereq},\var{place},\var{waiting},\var{f})}\inddef{\textsc{First-Fit}}
1 \' $\var{p} \leftarrow \var{head}[\var{P}]$\\
2 \' \key{while} \= $\var{waiting}[\var{f}] = \textsc{true}$ and $\var{p} \neq \textsc{nil}$\\
3 \' \> \key{do} \= \key{if} \= $\var{part}[\var{p}]=0$ and $\var{size}[\var{p}] \ge \var{spacereq}[\var{f}]$\\
4 \' \> \> \> \key{then} \= \textsc{Split-Partition(\var{p},\var{q},\var{spacereq}[\var{f}])}\\
5 \' \> \> \> \> $\var{part}[\var{p}] \leftarrow \var{f}$\\
6 \' \> \> \> \> $\var{place}[\var{f}] \leftarrow \var{p}$\\
7 \' \> \> \> \> $\var{waiting}[\var{f}] \leftarrow \textsc{false}$\\
8 \' \> \> $\var{p} \leftarrow \var{next}[\var{p}]$
\end{alg}
To prove the correctness of the algorithm several facts have to be examined. First, we should not load a process into a partition into which it does not fit. This is guaranteed by the linear search theorem, since this criteria is part of the property predicate.
Similarly to the fixed partitioning, the most essential criteria of correctness is that one single process should not be placed into multiple partitions simultaneously, and at most one processes may be placed into one partition. The proof of this criteria is word by word the same as the one stated at fixed partitions. The only difference is that instead of the conditional maximum search the linear search must be used.
Of course, these conditions are not sufficient in this case either, since they are fulfilled by even the empty algorithm. We also need prove that the algorithm finds a place for every process that fits into any of the partitions. For this we need an invariant again: after examining $j$ processes, there is no positive $k \le j$, for which $\var{waiting}[k]$, and for which there is a $p$ partition, such that $\var{part}[p]=0$, and $\var{size}[p] \ge \var{spacereq}[k]$.
\begin{description}
\item[Initialisation: ] At the beginning of the algorithm we have examined $j=0$ many partitions, so there is no positive $k \le j$.
\item[Maintenance: ] If the invariant holds for $j$ at the beginning of the loop, first we have to check whether it holds for the same $j$ at the end of the loop as well. It is obvious, since the first $j$ processes are not modified when examining the $(j + 1)$-th one, and for the partitions containing them $\var{part}[p]>0$, which does not satisfy the predicate of the linear search in the \textsc{First-Fit} algorithm. The invariant statement holds for the $(j + 1)$-th process at the end of the loop as well, since if there is a free memory slice which fulfills the condition, the linear search certainly finds it, because the condition of our linear search corresponds to the requirement of our invariant set on each partition.
\item[Termination: ] Since the loop traverses a fixed interval by one, it certainly stops. Since the loop body is executed exactly as many times as the number of the processes, after the loop has finished, it holds that there is no positive $k \le j$, for which $\var{waiting}[k]$, and for which there is a $p$ partition, such that $\var{part}[p]=0$, and $\var{size}[p] \ge \var{spacereq}[i]$, which means that we did not keep any processes fitting into any of the partitions waiting.
\end{description}
Again, the time complexity of the algorithm can be calculated easily. We examine all the $n$ processes in any case. If, for instance, all the processes are waiting, and the partitions are all reserved, the algorithm runs in $\Theta(nm)$.
However, when calculating the time complexity, we failed to take some important points of view into consideration. One of them is that $m$ is not constant, but executing the algorithm again and again it probably increases, since the processes are independent of each other, start and end in different instances of time, and their sizes can differ considerably. Therefore, we split a partition into two more often than we merge two neighbouring ones. This phenomenon is called \ki{fragmentation the memory.}\index{fragmentation the memory} Hence, the number of steps in the worst case is growing continuously when running the algorithm several times. Furthermore, linear search divides always the first partition with appropriate size into two, so after a while there will be a lot of small partitions at the beginning of the memory area, unusable for most processes. Therefore the average execution time will grow as well. A solution for the latter problem is to not always start searching at the beginning of the list of the partitions, but from the second half of the partition split last time. When reaching the end of the list, we can continue at the beginning until finding the first suitable partition, or reaching the starting partition again. This means we traverse the list of the partitions cyclically.
\begin{algN}{Next-Fit(\var{P},\var{head},\var{next},\var{last},\var{beginning},\var{size},\var{part},\var{spacereq},\var{place},\var{waiting},\var{f})}\inddef{\textsc{Next-Fit}}
1 \' \key{if} \= $\var{last}[\var{P}] \neq \textsc{nil}$\\
2 \' \> \key{then} \= $\var{p} \leftarrow \var{next}[\var{last}[\var{P}]]$\\
3 \' \> \key{else} \> $\var{p} \leftarrow \var{head}[\var{P}]$\\
4 \' \key{while} \= $\var{waiting}[\var{f}]$ and $\var{p} \neq \var{last}[\var{P}]$\\
5 \' \> \key{do} \= \key{if} \= $\var{p}=\textsc{nil}$\\
6 \' \> \> \> \key{then} \= $\var{p} \leftarrow \var{head}[\var{P}]$\\
7 \' \> \> \key{if} \= $\var{part}[\var{p}]=0$ and $\var{size}[\var{p}]\ge \var{spacereq}[\var{f}]$\\
8 \' \> \> \> \key{then} \= \textsc{Split-Partition(\var{p},\var{q},\var{spacereq}[\var{f}])}\\
9 \' \> \> \> \> $\var{part}[\var{p}] \leftarrow \var{f}$\\
10 \' \> \> \> \> $\var{place}[\var{f}] \leftarrow \var{p}$\\
11 \' \> \> \> \> $\var{waiting}[\var{f}] \leftarrow \textsc{false}$\\
12 \' \> \> \> \> $\var{last}[\var{P}] \leftarrow \var{p}$\\
13 \' \> \> $\var{p} \leftarrow \var{next}[\var{p}]$
\end{algN}
The proof of the correctness of the algorithm is basically the same as that of the \textsc{First-Fit}, as well as its time complexity. Practically, there is a linear search in the inner loop again, only the interval is always rotated in the end. However, this algorithm traverses the list of the free areas evenly, so does not fragment the beginning of the list. As a consequence, the average execution time is expected to be smaller than that of the \textsc{First-Fit}.
If the only thing to be examined about each partition is whether a process fits into it, then it can easily happen that we cut off large partitions for small processes, so that there would not be partitions with appropriate sizes for the later arriving larger processes. Splitting unnecessarily large partitions can be avoided by assigning each process to the smallest possible partition into which it fits.
\begin{algN}{Best-Fit(\var{P},\var{head},\var{next},\var{last},\var{beginning},\var{size},\var{part},\var{spacereq},\var{place},\var{waiting},\var{f})}\inddef{\textsc{Best-Fit}}
1 \' $\var{min} \leftarrow \infty$\\
2 \' $\var{ind} \leftarrow \textsc{nil}$\\
3 \' $\var{p} \leftarrow \var{head}[\var{P}]$\\
4 \' \key{while} \= $\var{p} \neq \textsc{nil}$\\
5 \' \> \key{do} \= \key{if} \= $\var{part}[\var{p}]=0$ and
$\var{size}[\var{p}]\ge \var{spacereq}[\var{f}]$ and $\var{size}[\var{p}]<\var{min}$\\
6 \' \> \> \> \key{then} \= $\var{ind} \leftarrow \var{p}$\\
7 \' \> \> \> \> $\var{min} \leftarrow \var{size}[\var{p}]$\\
8 \' \> \> $\var{p} \leftarrow \var{next}[\var{p}]$\\
9 \' \key{if} \= $\var{ind} \neq \textsc{nil}$\\
10 \' \> \key{then} \= \textsc{Split-Partition(\var{ind},\var{q},\var{spacereq}[\var{f}])}\\
11 \' \> \> $\var{part}[\var{ind}] \leftarrow \var{f}$\\
12 \' \> \> $\var{place}[\var{f}] \leftarrow \var{ind}$\\
13 \' \> \> $\var{waiting}[\var{f}] \leftarrow \textsc{false}$
\end{algN}
All the criteria of the correctness of the algorithm can be proved in the same way as previously.
The only difference from the \textsc{First-Fit} is that conditional minimum search
is applied instead of linear search. It is also obvious that this algorithm will not split a partition larger than minimally required.
However, it is not always efficient to place each process into the smallest space
into which it fits. It is because the remaining part of the partition is often too small,
unsuitable for most of the processes. It is disadvantageous for two reasons.
On the one hand, these partitions are still on the list of free partitions,
so they are examined again and again whenever searching for a place for a process.
On the other hand, many small partitions together compose a large area that is useless,
since it is not contiguous. Therefore, we have to somehow avoid the creation of too small free
partitions. The meaning of too small can be determined by either a constant or a
function of the space requirement of the process to be placed.
(For example, the free area should be twice as large as the space required for the process.)
Since this limit is based on the whole partition and not only its remaining part,
we will always consider it as a function depending on the process. Of course,
if there is no partition to fulfill this extra condition, then we should place
the process into the largest partition. So we get the following algorithm.
\begin{algN}{Limited-Best-Fit(\var{P},\var{head},\var{next},\var{last},\var{beginning},\var{size},\var{part},\var{spacereq},\var{place},\var{waiting},\var{f})}\inddef{\textsc{Limited-Best-Fit}}
1 \' $\var{min} \leftarrow \infty$\\
2 \' $\var{ind} \leftarrow \textsc{nil}$\\
3 \' $\var{p} \leftarrow \var{head}[\var{P}]$\\
4 \' \key{while} \= $p\neq \textsc{nil}$ \\
5 \' \> \key{do} \= \key{if} \= $\var{part}[\var{p}]=0$ \= and $\var{size}[\var{p}] \ge \var{spacereq}[\var{f}]$ and\\
\> \> \> \> (\=($\var{size}[\var{p}]<\var{min}$ and $\var{size}[\var{p}]\ge \textsc{Limit}(\var{f})$) \\
\> \> \> \> or $\var{ind}=\textsc{nil}$ or ($\var{min}<\textsc{Limit}(\var{f})$ and $\var{size}[\var{p}]>\var{min}$))\\
6 \' \> \> \> \key{then} \= $\var{ind} \leftarrow \var{p}$\\
7 \' \> \> \> \> $\var{min} \leftarrow \var{size}[\var{p}]$\\
8 \' \> \> $\var{p} \leftarrow \var{next}[\var{p}]$\\
9 \' \key{if} \= $\var{ind} \neq \textsc{nil}$\\
10 \' \> \key{then} \= \textsc{Split-Partition(\var{ind},\var{q},\var{spacereq}[\var{f}])}\\
11 \' \> \> $\var{part}[\var{ind}] \leftarrow \var{f}$\\
12 \' \> \> $\var{place}[\var{f}] \leftarrow \var{ind}$\\
13 \' \> \> $\var{waiting}[\var{f}] \leftarrow \textsc{false}$
\end{algN}
This algorithm is more complicated than the previous ones. To prove its correctness we have to see that the inner loop is a conditional minimum searching. The first part of the condition, i. e. that $\var{part}[p]=0$, and $\var{size}[p] \ge \var{spacereq}[f]$ means that we try to find a free partition suitable for the process. The second part is a disjunction: we replace the item found so far with the newly examined one in three cases. The first case is when $\var{size}[p] < \var{min}$, and $\var{size}[p] \ge \textsc{Limit}(\var{spacereq}[f])$, which means that the size of the examined partition is at least as large as the described minimum, but it is smaller than the the smallest one found so far. If there were no more conditions, this would be a conditional minimum search for the conditions of which we added that the size of the partition should be above a certain limit. But there are two other cases, when we replace the previously found item to the new one. One of the cases is that $\var{ind} = \textsc{nil}$, i. e., the newly examined partition is the first one which is free, and into which the process fits. This is needed because we stick to the requirement that if there is a free partition suitable for the process, then the algorithm should place the process into such a partition. Finally, according to the third condition, we replace the previously found most suitable item to the current one, if $\var{min} < \textsc{Limit}(\var{spacereq}[f])$ and $\var{size}[p] > \var{min}$, which means that the minimum found so far did not reach the described limit, and the current item is bigger than this minimum. This condition is important for two reasons. First, if the items examined so far do not fulfill the most recent condition, but the current one does, then we replace it, since in this case $\var{min} < \textsc{Limit}(\var{spacereq}[f]) \leq \var{size}[p]$, i. e., the size of the current partition is obviously larger. Second, if neither the size of partition found so far, nor that of the current one reaches the de%%@
%%@
scribed limit, but the currently examined one approaches it better from below, then $\var{min} < \var{size}[p] < \textsc{Limit}(\var{spacereq}[f])$ holds, therefore, also in this case we replace the item found so far by the current one. Hence, if there are partitions at least as large as the described limit, then the algorithm places each process into the smallest one among them, and if there is no such partition, then in the largest suitable one.
There are certain problems, where the only requirement is that the remaining free spaces should be the largest possible. It can be guaranteed if each process is placed into the largest free partition:
\vspace{-2mm}
\begin{algN}{Worst-Fit(\var{P},\var{head},\var{next},\var{last},\var{beginning},\var{size},\var{part},\var{spacereq},\var{place},\var{waiting},\var{f})}\inddef{\textsc{Worst-Fit}}
1 \' $\var{max} \leftarrow 0$\\
2 \' $\var{ind} \leftarrow \textsc{nil}$\\
3 \' $\var{p} \leftarrow \var{head}[\var{P}]$\\
4 \' \key{while} \= $\var{p} \neq \textsc{nil}$\\
5 \' \> \key{do} \= \key{if} \= $\var{part}[\var{p}]=0$ and $\var{size}[\var{p}]
\ge \var{spacereq}[\var{f}]$ and $\var{size}[\var{p}]>\var{max}$\\
6 \' \> \> \> \key{then} \= $\var{ind} \leftarrow \var{p}$\\
7 \' \> \> \> \> $\var{min} \leftarrow \var{size}[\var{p}]$\\
8 \' \> \> $\var{p} \leftarrow \var{next}[\var{p}]$\\
9 \' \key{if} \= $\var{ind} \neq \textsc{nil}$\\
10 \' \> \key{then} \= \textsc{Split-Partition(\var{ind},\var{q},\var{spacereq}[\var{f}])}\\
11 \' \> \> $\var{part}[\var{ind}] \leftarrow \var{f}$\\
12 \' \> \> $\var{place}[\var{f}] \leftarrow \var{ind}$\\
13 \' \> \> $\var{waiting}[\var{f}] \leftarrow \textsc{false}$
\end{algN}
\vspace{-2mm}
We can prove the correctness of the algorithm similarly to the \textsc{Best-Fit} algorithm; the only difference is that maximum search has to be used instead of conditional maximum search. As a consequence, it is also obvious that the sizes of the remaining free areas are maximal.
The \textsc{Worst-Fit} algorithm maximises the smallest free partition, i. e. there will be only few partitions which are too small for most of the processes. It follows from the fact that it always splits the largest partitions. However, it also often prevents large processes from getting into the memory, so they have to wait on an auxiliary storage. To avoid this we may extend our conditions with an extra an one, similarly to the \textsc{Best-Fit} algorithm. In this case, however, we give an upper limit instead of a lower one. The algorithm only tries to split partitions smaller than a certain limit. This limit also depends on the space requirement of the process. (For example the double of the space requirement.) If the algorithm can find such partitions, then it chooses the largest one to avoid creating too small partitions. If it finds only partitions exceeding this limit, then it splits the smallest one to save bigger ones for large processes.
\begin{algN}{Limited-Worst-Fit(\var{f},\var{beginning},\var{head},\var{place},\var{spacereq},\var{next},\var{size},\var{part},\var{waiting},\var{waiting})}\inddef{\textsc{Limited-Worst-Fit}}
1 \' $\var{max} \leftarrow 0$\\
2 \' $\var{ind} \leftarrow \textsc{nil}$\\
3 \' $\var{p} \leftarrow \var{head}[\var{P}]$ \\
4 \' \key{while} \= $\var{p} \neq \textsc{nil}$\\
5 \' \> \key{do} \= \key{if} \= $\var{part}[\var{p}]=0$ \= and $\var{size}[\var{p}] \ge \var{spacereq}[\var{f}]$ and\\
\> \> \> \> (\=($\var{size}[\var{p}]>\var{max}$ and
$\var{size}[\var{p}]\le \textsc{Limit(\var{f})}$) or $\var{ind}=\textsc{nil}$ or\\
\> \> \> \> ($\var{max}>\textsc{Limit(\var{f})}$ and
$\var{size}[\var{p}]<\var{max}$))\\
\algnewpageN
6 \' \> \> \> \key{then} \= $\var{ind} \leftarrow \var{p}$\\
7 \' \> \> \> \> $\var{min} \leftarrow \var{size}[\var{p}]$\\
8 \' \> \> $\var{p} \leftarrow \var{next}[\var{p}]$\\
9 \' \key{if} \= $\var{ind} \neq \textsc{nil}$\\
10 \' \> \key{then} \= \textsc{Split-Partition(\var{ind},\var{q},\var{spacereq}[\var{f}])}\\
11 \' \> \> $\var{part}[\var{ind}] \leftarrow \var{f}$\\
12 \' \> \> $\var{place}[\var{f}] \leftarrow \var{ind}$\\
13 \' \> \> $\var{waiting}[\var{f}] \leftarrow \textsc{false}$
\end{algN}
It is easy to see that this algorithm is very similar to the \textsc{Limited-Best-Fit}, only the relation signs are reversed. The difference is not significant indeed. In both algorithms the same two conditions are to be fulfilled: there should not be too small partitions, and large free partitions should not be wasted for small processes. The only difference is which condition is taken account in the first place and which in the second. The actual problem decides which one to use.
\begin{gyak}
\ujgyak
We have a system containing two fixed partitions with sizes of 100 kB, one of 200 kB and one of 400 kB. All of them are empty at the beginning. One second later five processes arrive almost simultaneously, directly after each other without significant delay. Their sizes are 80 kB, 70 kB, 50 kB, 120 kB and 180 kB respectively. The process with size of 180 kB ends in the fifth second after its arrival, but by that time another process arrives with space requirement of 280 kB. Which processes are in which partitions in the sixth second after the first arrivals, if we suppose that other processes do not end until that time, and the \textsc{Largest-Fit}\gyakindex{\textsc{Largest-Fit}} algorithm is used? What is the case if the \textsc{Largest-or-Long-Waiting-Fit}\gyakindex{\textsc{Largest-or-long-waiting-Fit}} or the \textsc{Long-Waiting-or-Not-Fit-Smaller}\gyakindex{\textsc{Long-Waiting-or-Not-Fit-Smaller}} algorithm is used with threshold value\linebreak
\noindent of 4?
\ujgyak
In a system using dynamic partitions the list of free partition consists of the following items: one with size of 20 kB, followed by one of 100 kB, one of 210 kB, one of 180 kB, one of 50 kB, one of 10 kB, one of 70 kB, one of 130 kB and one of 90 kB respectively. The last process was placed into the partition preceding the one of 180 kB. A new process with space requirement of 40 kB arrives into the system. Into which partition is it to be placed using the \textsc{First-Fit}\gyakindex{\textsc{First-Fit}}, \textsc{Next-Fit}\gyakindex{\textsc{Next-Fit}}, \textsc{Best-Fit}\gyakindex{\textsc{Best-Fit}},
\textsc{Limited-Best-Fit}\gyakindex{\textsc{Limited-Best-Fit}}, \textsc{Worst-Fit}\gyakindex{\textsc{Worst-Fit}} or the
\textsc{Limited-Worst-Fit}\gyakindex{\textsc{Limited-Worst-Fit}} algorithms?
\ujgyak
An effective implementation of the \textsc{Worst-Fit}\gyakindex{\textsc{Worst-Fit}} algorithm is when the partitions are stored in a binary heap instead of a linear linked list. What is the time complexity of the \textsc{Place}\gyakindex{\textsc{Place}} algorithm perform in this case?
\end{gyak}
\section{Page replacement algorithms}\index{page replacement algorithms|(}\label{sec:paging}
As already mentioned, the memory of the modern computer systems consists of several levels.
These levels usually are organised into a seemingly single-level memory, called \ki{virtual memory.}
Users do not have to know this structure with several levels in detail:
operating systems manage these levels.\index{virtual memory}
The most popular methods to control this virtual memory are paging and segmentation.
Paging divides both memory levels into fixed-sized units,
called \ki{frames.}\inddef{frame} In this case programs are also divided into parts of the same size as frams have:
these parts of the programs (and data) are called \ki{pages.}\inddef{page} Segmentation uses parts of a program
with changing size---these parts are called \ki{segments.}\inddef{segment}
For the simplicity let us suppose that the memory consists
of only two levels: the smaller one with shorter access time is
called \ki{main memory}\inddef{main memory}
(or \ki{memory} for short),\inddef{memory} and the larger one with larger access time
is called \ki{backing memory.}\inddef{backing memory}
At the beginning, the main memory is empty, and there is only one program consisting of $n$
parts in the backing memory. Suppose that during the run of the program there are
instructions to be executed, and the execution of each instruction there requires an access
to a certain page of the program.
After processing the reference string, the following problems have to be solved.
\begin{enumerate}
\item
Where should we place the segment of the program responsible for executing the next
instruction in the main memory (if it is not there)?
\item
When should we place the segments of the program in the main memory?
\item
How should we deallocate space for the segments of the program to be placed into the main memory?
\end{enumerate}
It is the placing algorithms that give the answer to the first question:
as far as paging is concerned, the answer is simply anywhere---since the page frames
of the main memory are of the same size and access time.
During segmentation there are program segments and free memory areas, called holes alternating
in the main memory--and it is the segment placing algorithms that gives the answer to the first question.
To the second question the answer is given by the transferring algorithms: in working systems the
answer is on demand in most of the cases, which means that a new segment of the program starts
to be loaded from the backing memory when it turns out that this certain segment is needed.
Another solution would be preloading, but according to the experiences it involves a lot of
unnecessary work, so it has not become wide-spread.
It is the replacement algorithms that give the answer to the third question:
as far as paging is concerned, these are the page replacement algorithms,
which we present in this section. Segment replacement algorithms used by segmentation
apply basically the ideas of page replacement algorithms---completed them according
to the different sizes of the segments.
Let us suppose that the size of the physical memory is $m$ page frames,
while that of the backing memory is $n$ page frames. Naturally the inequality $1 \leq m \leq n$
holds for the parameters. In practice, $n$ is usually many times bigger than $m$.
At the beginning the main memory is empty, and there is only one program
in the backing memory. Suppose that during the run of the program there are $p$ instructions
to be executed, and to execute the $t$-th instruction $(1 \leq t \leq p)$ the page $r_t$ is necessary,
and the result of the execution of the instruction also can be stored in the same page,
i. e., we are modelling the execution of the program by \ki{reference string}\inddef{reference string}
$R = \langle r_1, r_2, \ldots, r_p \rangle$.
In the following we examine only the case of demand paging, to be more precise,
only the page replacement algorithms within it.
If it is important to differentiate reading from writing,
we will use \ki{writing array}\inddef{writing array}
$W = \langle w_1, w_2, \ldots, w_p \rangle$ besides array $R$.
Entry $w_t$ of array $W$ is \textsc{true} if we are writing onto page $r_t$, otherwise $w_1 = \textsc{false}$.
Demand paging algorithms fall into two groups; there are \ki{static} and \ki{dynamic}
algorithms.\inddef{static page replacement algorithms}\inddef{dynamic page replacement
algorithms}\index{page replacement algorithm!static}\index{page replacement algorithm!dynamic}
At the beginning of the running of the program both types fill the page frames
of the physical memory with pages, but after that static algorithms keep exactly $m$
page frames reserved until the end of the running,
while dynamic algorithms allocate at most $m$ page frames.
\subsection{Static page replacement}
The input data of static page replacement algorithms are: the size of the main memory
measured in number of the page frames $(m)$, the size of the program measured in number of of
pages $(n)$, the running time of the program measured in number of instructions $(p)$
and the reference string $(R)$; while their output is the
\ki{number of the page faults.}\inddef{number of page faults} (\var{pagefault})
Static algorithms are based on managing the \ki{page table.}\inddef{page table} The page table is a matrix
with size of $n \times 2$, the $i$-th $(i \in [0 \twodots n - 1])$ row of which refers to the $i$-th page.
The first entry of the row is a logical variable \ki{(present/absent bit),}\inddef{present/absent bit}
the value of which keeps track of whether the page is in the main memory in that certain instant
of time: if the $i$-th page is in the main memory, then
$\var{pagetable}[i, 1] = \textsc{true}$ and $\var{pagetable}[i, 2] = j$, where $j \in [0\twodots m - 1]$
shows us that the page is in the j-th page frame of the main memory.
If the $i$-th page is not in the main memory, then $\var{pagetable}[i, 1] = \textsc{false}$
and $\var{pagetable}[i, 2]$ is non-defined. Work variable \var{busy} contains the number
of the busy page frames\index{busy page frame}\\index{frame!free}\index{frame!busy} of the main memory.
If the size of the pages is $z$, then the physical address $f$ can be calculated
from virtual address $v$ so that $j = \lfloor v/z \rfloor$ gives us the
\ki{index of the virtual page frame}\inddef{index of the virtual page frame},
and $v - z\lfloor v/z \rfloor$ gives us offset $s$ referring to virtual address $v$.
If the $j$-th page is in the main memory in the given instant of time---which is indicated
by $\var{pagetable}[i, 1] = \textsc{true}$---, then $f = s + z \cdot \var{pagetable}[i, 2]$.
If, however, the $i$-th page is not in the main memory, then a page fault occurs.
In this case we choose one of the page frames of the main memory using the page
replacement algorithm, load the $j$-th page into it, refresh the $j$-th row of the page table
and then calculate $f$.
The operation of the demand paging algorithms can be described by a Mealy automaton
having an initial status. This automaton can be given as $(Q,q_0,X,Y,\delta,\lambda)$,
where $Q$ is the set of the control states, $q_o \in Q$ is the initial control state,
$X$ is the input alphabet, $Y$ is the output alphabet, $\delta : Q \times X \rightarrow Q$
is the state transition function and $\lambda : Q \times X \rightarrow Y$ is the output function.
We do not discuss the formalisation of how the automaton stop.
Sequence $R_p = \langle r_1, r_2, \ldots, r_p \rangle$
(or $R_p = \langle r_1, r_2, \ldots, r_{\infty} \rangle$) is called
\ki{reference string.}\inddef{reference string}
The description of the algorithms can be simplified introducing memory states
$S_t \ (t = 1, 2, \ldots)$: this state is the set of the pages stored in the main memory
of the automat after processing the $t$-th input sign.
In the case of static demand paging algorithms $S_0 =\emptyset$.
If the new memory status differs from the old one (which means that a new page
had to be swapped in), then a page fault has occurred.
Consequently, both a swapping of a page into an empty frame
and page replacement are called page fault.
In case of page replacement algorithms---according to Denning's proposition---instead of $\lambda$ and $\delta$
we use the state transition function $g_P: Q \times M \times X \rightarrow Q \times Y$.
Since for the page replacement algorithms $X = \{0, 1, \ldots, n - 1\}$ and $Y = X \cup \emptyset,$
holds, these two items can be omitted from the definition, so page replacement algorithm
$P$ can be described by the triple $(Q,q_0,g_P)$.
Our first example is one of the simplest page replacement algorithms,
the FIFO (\textbf{F}irst \textbf{I}n \textbf{F}irst
\textbf{O}ut),\index{First In First Out}\index{FIFO|see{First In First Out}}
which replaces the pages in the order of their loading in.
Its definition is the following: $q_0 = \langle \rangle$ and
\begin{eqnarray}\inddef{FIFO}
g_{\textsc{FIFO}}(S,q,x) =
\begin{cases}
(S,q,\epsilon), & \mathrm{if} \ x \in S \koz , \\
(S \cup \{x \}, q', \epsilon), & \mathrm{ if} \ x \notin S, \ |S| = k < m \koz , \\
(S \setminus \{y_1 \} \cup \{x \}, q", y_1), & \mathrm{ if} \ x \notin S \ \mathrm{and} \ |S| = k = m \koz ,
\end{cases}
\end{eqnarray}
where $q = \langle y_1, y_2, \ldots , y_k \rangle, \ q' = \langle y_1, y_2, \ldots, y_k, x \rangle $ and
$q'' = \langle y_2, y_3, \ldots, y_m,$ $x \rangle .$
Running of the programs is carried out by the following $\ast$-\textsc{Run} algorithm.
In this section the $\ast$ in the name of the algorithms has to be replaced
by the name of the page replacement algorithm to be applied (FIFO, LRU OPT, LFU or NRU).
In the pseudocodes it is supposed that the called procedures know the values of the variable
used in the calling procedure, and the calling procedure accesses to the new values.
\begin{alg}{$\ast$-Run$(m,n,p,R,\var{faultnumber},\var{pagetable})$}\inddef{star-Run@\textsc{*-Run}}
1 \' $\var{faultnumber} \leftarrow 0$ \\
2 \' $\var{busy} \leftarrow 0$ \\
3 \' \key{for} \= $i \leftarrow 0$ \key{to} $n - 1$ \` $\rhd$ Preparing the \var{pagetable}. \\
4 \' \> \key{do} $\var{pagetable}[i,1] \leftarrow \textsc{false}$ \\
5 \' \textsc{*-Prepare$(\var{pagetable})$} \\
6 \' \key{for} \= $i \leftarrow 1$ \key{to} $p$ \` $\rhd$ Run of the program.\\
7 \' \> \key{do} \textsc{*-Executes}$(\var{pagetable},i)$ \\
8 \' \key{return} $\var{faultnumber}$
\end{alg}
The following implementation of the algorithm keeps track of the order of loading
in the pages by queue $Q$. The preparing algorithm has to create the empty queue,
i. e., to execute the instruction $Q \leftarrow \emptyset$.
In the following pseudocode \var{swap-out}\index{swap-out@\textit{swap-out}} is the index of the
page to be replaced, and \var{swap-in}\index{swap-in@\textit{swap-in}} is the index of
the page of the main memory into which the new page is going to be swapped in.
\newpage
\begin{algN}{FIFO-Executes$(\var{pagetable},t),$}\inddef{\textsc{FIFO-Executes}}
1 \' \key{if} \= $\var{pagetable}[r_t,1] = \textsc{true}$ \` $\rhd$ The next page is in. \\
2 \' \> \key{then} \textsc{nil} \\
3 \' \key{if} \= $\var{pagetable}[r_t,1] = \textsc{false}$ \` $\rhd$ The next page is out. \\
4 \' \> \key{then} \= $\var{pagefault} \leftarrow \var{pagefault} + 1$ \\
5 \' \> \> \key{if} \= $\var{busy} < m$ \` $\rhd$ Main memory is not full. \\
6 \' \> \> \> \key{then} \= \textsc{Inqueue}$(Q,r_t)$ \\
7 \' \> \> \> \> $\var{swap-in} \leftarrow \var{busy}$ \\
8 \' \> \> \> \> $\var{busy} \leftarrow \var{busy} + 1$ \\
9 \' \> \> \key{if} \= $\var{busy} = m$ \` $\rhd$ Main memory is full. \\
10 \' \> \> \> \key{then} \= $\var{replaces} \leftarrow \textsc{Enqueue}(Q)$ \\
11 \' \> \> \> \> $\var{pagetable}[\var{swap-out},1] \leftarrow \textsc{false}$ \\
12 \' \> \> \> \> $\var{swap-in} \leftarrow \var{pagetable}[\var{swap-out},2]$ \\
13 \' \> \> \textsc{Write}$(\var{swap-in},\var{swap-out})$ \\
14 \' \> \> \textsc{Read}$(r_t,\var{load})$ \` $\rhd$ Reading.\\
15 \' \> \> $\var{pagetable}[r_t,1] \leftarrow \textsc{true}$ \` $\rhd$ Updating of the data.\\
16 \' \> \> $\var{pagetable}[r_t,2] \leftarrow \var{loads}$
\end{algN}
Procedure writing writes the page chosen to be swapped out into the backing memory:
its first parameter answers the question where from (from which page frame of the memory)
and its second parameter answers where to (to which page frame of the backing memory).
Procedure \textsc{Reading} reads the page needed to execute the next instruction from
the backing memory into the appropriate page frame of the physical memory:
its first parameter is where from (from which page frame of the backing memory)
and its second parameter is where to (to which page frame of the memory).
When giving the parameters of both the procedures we use the fact that the page frames
are of the same size, therefore, the initial address of the $j$-th page
frame is $j$-times the page size $z$ in both memories.
Most of the page replacement algorithms do not need to know the other entries
of reference string $R$ to process reference $r_t$, so when calculating space requirement
we do not have to take the space requirement of the series into consideration.
An exception for this is algorithm OPT for example.
The space requirement of the FIFO-RUN algorithm is determined
by the size of the page frame - this space requirement is $O(m)$.
The running time of the FIFO-RUN algorithm is de-termined by the loop.
Since the procedure called in rows 6 and 7 performs only a constant number
of steps (provided that queue-handling operations can be performed in $O(1)$,
the run-ning time of the FIFO-RUN algorithm is $O(p)$.
Note that some of the pages do not change while being in the memory,
so if we assign a modified bit to the pages in the memory, then we can spare
the writing in row 12 in some of the cases.
Our next example is one of the most popular page replacement algorithms,
the LRU (\textbf{L}east \textbf{R}ecently \textbf{U}sed),\index{LRU|see{Least Recently Used}}
which replaces the page used least recently. Its definition is the following: $q_0 = ()$ and
\vspace{-4mm}
\begin{eqnarray}\inddef{LRU}
g_{\textsc{LRU}}(S,q,x) =
\begin{cases} (S,q''',\epsilon), & \mathrm{if} \ x \in S \koz , \\
(S \cup \{x \}, q', \epsilon), & \mathrm{ if} \ x \notin S, \ |S|= k < m \koz , \\
(S \setminus \{y_1 \} \cup \{x \}, q", y_1), & \mathrm{ if} \ x \notin S \ \mathrm{and} \ |S| = k = m \koz ,
\end{cases}
\end{eqnarray}
where $q = \langle y_1, y_2, \ldots , y_k \rangle , \ q' = \langle y_1, y_2, \ldots, y_k, x \rangle,$
$q'' = \langle y_2, y_3, \ldots, y_m,$$x \rangle$ and if $x = y_k,$ then
$q''' = \langle y_1, y_2, \ldots, y_{k-1},\ldots,y_{k+1} \ldots y_m, y_k \rangle$.
The next implementation of LRU does not need any preparations.
We keep a record of the time of the last usage of the certain pages in array
$\var{last-call}[0..n - 1]$, and when there is a replacement needed, the least recently used page
can be found with linear search.
\begin{algN}{LRU-Executes$(\var{pagetable},t)$}\inddef{\textsc{LRU-Executes}}
1 \' \key{if} \= $\var{pagetable}[r_t,1] = \textsc{true}$ \` $\rhd$ The next page is in. \\
2 \' \> \key{then} $\var{last-ref}[r_t] \leftarrow t$ \\
3 \' \key{if} \= $\var{pagetable}[r_t,1] = \textsc{false}$ \` $\rhd$ The next page is not in. \\
4 \' \> \key{then} \= $\var{pagefault} \leftarrow \var{pagefault} + 1$ \\
5 \' \> \> \key{if} \= $\var{busy} < m$ \` $\rhd$ The physical memory is not full. \\
6 \' \> \> \> \key{then} \= $\var{swap-in} \leftarrow \var{busy}$ \\
7 \' \> \> \> \> $\var{busy} \leftarrow \var{busy} + 1$ \\
8 \' \> \> \key{if} \= $\var{busy} = m$ \` $\rhd$ The physical memory is full. \\
9 \' \> \> \> \key{then} \= $\var{swap-out} \leftarrow r_{t-1}$ \\
10 \' \> \> \> \> \key{for} \= $i \leftarrow 0$ \key{to} $n - 1$ \\
11 \' \> \> \> \> \> \key{do} \key{if} \= $\var{pagetable}[i,1] = \textsc{true}$
and \\
\' \> \> \> \> \> \> $\var{last-ref}[i] < \var{last-ref}[\var{swap-out}]$ \\
12 \' \> \> \> \> \> \> \key{then} $\var{swap-out} \leftarrow \var{last-ref}[i]$ \\
13 \' \> \> \> \> $\var{pagetable}[\var{swap-out},1] \leftarrow \textsc{false}$ \\
14 \' \> \> \> \> $\var{swap-in} \leftarrow \var{pagetable}[\var{swap-out},2]$ \\
15 \' \> \> \> \> \textsc{Write}$(\var{swap-in},\var{swap-out})$ \\
16 \' \> \> \textsc{Read}$(r_t,\var{swap-in})$ \` $\rhd$ Reading. \\
17 \' \> \> $\var{pagetable}[r_t,1] \leftarrow \textsc{true}$ \` $\rhd$ Updating. \\
18 \' \> \> $\var{pagetable}[r_t,2] \leftarrow \var{swap-in}$ \\
19 \' \> \> $\var{last-ref}[r_t] \leftarrow t$
\end{algN}
If we consider the values of both n and p as variables, then due to the linear search in rows 10--11,
the running time of the LRU-RUN algorithm is $O(np)$.
The following algorithm is optimal in the sense that with the given conditions
(fixed $m$ and $n$) it causes a minimal number of page faults.
This algorithm chooses the page from the ones in the memory, which is going to be used at the latest
(if there are several page that are not needed any more, then we choose the one at the lowest
memory address from them) to be replaced.
This algorithm does not need any preparations either.
\begin{algN}{OPT-Executes$(t,\var{pagetable},R)$}\inddef{\textsc{OPT-Executes}}
1 \' \key{if} \= $\var{pagetable}[r_t,1] = \textsc{true}$ \` $\rhd$ The next page is in. \\
2 \' \> \key{then} \textsc{nil} \\
3 \' \key{if} \= $\var{pagetable}[r_t,1] = \textsc{false}$ \` $\rhd$ The next page is not in. \\
4 \' \> \key{then} \= $\var{pagefault} \leftarrow \var{pagefault} + 1$
\algnewpageN
5 \' \> \> \key{if} \= $\var{busy} < m$ \` $\rhd$ The main memory is not full. \\
6 \' \> \> \> \key{then} \= $\var{swap-in} \leftarrow{busy}$ \\
7 \' \> \> \> \> $\var{busy} \leftarrow \var{busy} + 1$ \\
8 \' \> \> \key{if} \= $\var{busy} = m$ \` $\rhd$ The main memory is full. \\
9 \' \> \> \> \key{then} \= \textsc{OPT-Swap-Out}$(t,R)$ \\
10 \' \> \> \> \> $\var{pagetable}[\var{swap-out},1] \leftarrow \textsc{false}$ \\
11 \' \> \> \> \> $\var{swap-in} \leftarrow \var{pagetable}[\var{swap-out},2]$ \\
12 \' \> \> \> \> \textsc{Write}$(\var{swap-in},\var{swap-out})$ \\
13 \' \> \> \textsc{Read}$(r_t,\var{swap-in})$ \` $\rhd$ Reading. \\
14 \' \> \> $\var{pagetable}[r_t,1] \leftarrow \textsc{true}$ \` $\rhd$ Updating. \\
15 \' \> \> $\var{pagetable}[r_t,2] \leftarrow \var{swap-in}$
\end{algN}
Procedure \textsc{OPT-Swap-Out} determines the index of the page to be replaced.
\begin{alg}{OPT-Swap-Out$(t,R)$}\inddef{\textsc{OPT-Swap-Out}}
1 \' $\var{guarded} \leftarrow 0$ \` $\rhd$ Preparation.\index{\textit{guarded}}\\
2 \' \key{for} \= $j \leftarrow 0$ \key{to} $m - 1$ \\
3 \' \> \key{do} $\var{frame}[j] \leftarrow \textsc{false}$ \\
4 \' $s \leftarrow t + 1$ \` $\rhd$ Determining the protection of the page frames.\\
5 \' \key{while} \= $s \leq p$ \= and $\var{pagetable}[r_s,1] = \textsc{true}$ and
$\var{frame}[\var{pagetable}[r_s,2]] = \textsc{false}$ and \\
\> \> $\var{guarded} < m -1$ \\
6 \' \> \key{do} \= $\var{guarded} \leftarrow \var{guarded} + 1$ \\
7 \' \> \> $\var{frame}[r_s] \leftarrow \textsc{true}$ \\
8 \' \> \> $s \leftarrow s + 1$ \\
9 \' $\var{swap-out} \leftarrow m - 1$ \` $\rhd$ Finding the frame containing the page to be replaced.\\
10 \' $j \leftarrow 0$ \\
11 \' \key{while} \= $\var{frame}[j] = \textsc{true}$ \\
12 \' \> \key{do} $j \leftarrow j + 1$ \\
13 \' $\var{swap-out} \leftarrow j$ \\
14 \' \key{return} $\var{swap-out}$
\end{alg}
Information about pages in the main memory is stored in $\var{frame}[0\twodots m - 1]$:
$\var{frame}[j] = \textsc{true}$
means that the page stored in the $j$-th frame is protected from being replaced due to its
going to be used soon. Variable protected keeps track of how many protected
pages we know about. If we either find $m - 1$ protected pages or reach the end of $R$,
then we will choose the unprotected page at the lowest memory address for the page
to be replaced.
Since the OPT algorithm needs to know the entire array $R$, its space requirement is $O(p)$.
Since in rows 5--8 of the \textsc{OPT-Swap-Out} algorithm at most the remaining part of $R$ has
to be looked through, the running time of the \textsc{OPT-Swap-Out} algorithm is $O(p^2)$.
The following LFU (Least Frequently Used) algorithm chooses
the least frequently used page to be replaced. So that the page replacement would be
obvious we suppose that in the case of equal frequencies we replace
the page at the lowest address of the physical memory.
We keep a record of how many times each page has been referenced since
it was loaded into the physical memory with the help of array frequency[1..n - 1].
This algorithm does not need any preparations either.
\begin{algN}{LFU-Executes$(\var{pagetable},t)$}\inddef{\textsc{LFU-Executes}}
1 \' \key{if} \= $\var{pagetable}[r_t,1] = \textsc{true}$ \` $\rhd$ The next page is in. \\
2 \' \> \key{then} \var{frequency}$[r_t] \leftarrow \var{frequency}[r_t] + 1$ \\
3 \' \key{if} \= $\var{pagetable}[r_t,1] = \textsc{false}$ \` $\rhd$ The next page is not in. \\
4 \' \> \key{then} \= $\var{pagefault} \leftarrow \var{pagefault} + 1$ \\
5 \' \> \> \key{if} \= $\var{busy} < m$ \` $\rhd$ The main memory is not full. \\
6 \' \> \> \> \key{then} \= $\var{swap-in} \leftarrow \var{busy}$ \\
7 \' \> \> \> \> $\var{busy} \leftarrow \var{busy} + 1$ \\
8 \' \> \> \key{if} \= $\var{busy} = m$ \` $\rhd$ The physical memory is full. \\
9 \' \> \> \> \key{then} \= $\var{swap-out} \leftarrow r_{t-1}$ \\
10 \' \> \> \> \> \key{for} \= $i \leftarrow n - 1$ \key{downto} $0$ \\
11 \' \> \> \> \> \> \key{do} \key{if} \= $\var{pagetable}[i,1] = \textsc{true}$
and \\
\' \> \> \> \> \> \> $\var{frequency}[i] \leq \var{frequency}[\var{swap-out}]$ \\
12 \' \> \> \> \> \> \> \key{then} $\var{swap-out} \leftarrow \var{last-ref}[i]$ \\
13 \' \> \> \> \> $\var{pagetable}[\var{swap-out},1] \leftarrow \textsc{false}$ \\
14 \' \> \> \> \> $\var{swap-in} \leftarrow \var{pagetable}[\var{swap-out},2]$ \\
15 \' \> \> \> \> \textsc{Kiír}$(\var{swap-in},\var{swap-out})$ \\
16 \' \> \> \textsc{Read}$(r_t,\var{pagetable}[\var{swap-out},2])$ \` $\rhd$ Reading. \\
17 \' \> \> $\var{pagetable}[r_t,1] \leftarrow \textsc{true}$ \` $\rhd$ Updating. \\
18 \' \> \> $\var{pagetable}[r_t,2] \leftarrow \var{swap-in}$ \\
19 \' \> \> $\var{frequency}[r_t] \leftarrow 1$
\end{algN}
Since the loop body in rows 11--13 of the \textsc{LFU-Executes} algorithm
has to be executed at most $n$-times, the running time of the algorithm is $O(np)$.
There are certain operating systems in which there are two status bits
belonging to the pages in the physical memory. The referenced bit is set to \textsc{true}
whenever a page is refer-enced (either for reading or writing),
while the dirty bit is set to \textsc{true} whenever modifying (i.e. writing) a page.
When starting the program both of the status bits of each page is set to \textsc{false}.
At stated intervals (e. g. after every $k$-th instruction) the operating system sets
the referenced bit of the pages which has not been referenced since the last setting to \textsc{false}.
Pages fall into four classes according to the values of their two status bits:
class 0 contains the pages not referenced and not modified,
class 1 the not referenced but modified, class 2 the referenced, but not modified,
and finally, class 3 the referenced and modified ones.
The NRU (\textbf{N}ot \textbf{R}ecently \textbf{U}sed)\inddef{NRU}
algorithm chooses a page to be replaced from the nonempty class
with the smallest index. So that the algorithm would be deterministic,
we suppose that the NRU algorithm stores the elements of each class in a row.
The preparation of this algorithm means to fill arrays referenced and dirty
containing the indicator bits with \textsc{false} values,
to zero the value of variable performed showing the number of the operations
performed since the last zeroing and to create four empty queues.
\begin{alg}{NRU-Prepares$(n)$}\inddef{\textsc{NRU-Prepares}}
1 \' \key{for} \= $i \leftarrow 0$ \key{to} $n - 1$ \\
2 \' \> \key{do} \= $\var{referenced}[j] \leftarrow \textsc{false}$ \\
3 \' \> \> $dirty[j] \leftarrow \textsc{false}$ \\
4 \' $Q_0 \leftarrow \emptyset$ \\
5 \' $Q_1 \leftarrow \emptyset$ \\
6 \' $Q_2 \leftarrow \emptyset$ \\
7 \' $Q_3 \leftarrow \emptyset$
\end{alg}
\begin{algN}{NRU-Executes$(\var{referenced},\var{dirty},k,R,W)$}\inddef{\textsc{NRU-Executes}}
1 \' \key{if} \= $\var{pagetable}[r_t,1] = \textsc{true}$ \` $\rhd$ The next page is in. \\
2 \' \> \key{then} \= \key{if} \= $W[r_t] = \textsc{true}$ \\
3 \' \> \> \> \key{then} $\var{dirty}[r_t] \leftarrow \textsc{true}$ \\
4 \' \key{if} \= $\var{pagetable}[r_t,1] = \textsc{false}$ \` $\rhd$ The next page is not in. \\
5 \' \> \key{then} \= $\var{pagefault} \leftarrow \var{pagefault} + 1$ \\
6 \' \> \> \key{if} \= $\var{busy} < m$ \` $\rhd$ The main memory is not full. \\
7 \' \> \> \> \key{then} \= $\var{swap-in} \leftarrow \var{busy}$ \\
8 \' \> \> \> \> $\var{busy} \leftarrow \var{busy} + 1$ \\
9 \' \> \> \> \> $\var{referenced}[r_t] \leftarrow \textsc{true}$ \\
10 \' \> \> \> \> \key{if} \= $W[r_t] = \textsc{true}$ \\
11 \' \> \> \> \> \> \key{then} $dirty[r_t] \leftarrow \textsc{true}$ \\
12 \' \> \> \key{if} \= $\var{busy} = m$ \` $\rhd$ The main memory is full. \\
13 \' \> \> \> \key{then} \= \textsc{NRU-Swap-Out}$(t,\var{swap-out})$ \\
14 \' \> \> \> \> $\var{pagetable}[\var{swap-out},1] \leftarrow \textsc{false}$ \\
15 \' \> \> \> \> $\var{swap-in} \leftarrow \var{pagetable}[\var{swap-out},2]$ \\
16 \' \> \> \> \> \key{if} \= $\var{dirty}[\var{sap-out}] = \textsc{true}$ \\
17 \' \> \> \> \> \> \key{then} \textsc{Write}$(\var{swap-in},\var{swap-out})$ \\
18 \' \> \> \textsc{Read}$(r_t,\var{pagetable}[\var{swap-in},2])$ \` $\rhd$ Reading. \\
19 \' \> \> $\var{pagetable}[r_t,1] \leftarrow \textsc{true}$ \` $\rhd$ Updating. \\
20 \' \> \> $\var{pagetable}[r_t,2] \leftarrow \var{swap-in}$ \\
21 \' \key{if} \= $t/k = \lfloor t/k \rfloor $ \\
22 \' \> \key{then} \= \key{for} \= $i \leftarrow 0$ \key{to} $n - 1$ \\
23 \' \> \> \> \key{do} \= \key{if} \= $\var{referenced}[i] = \textsc{false}$ \\
24 \' \> \> \> \> \> \key{then} $\var{dirty}[i] \leftarrow \textsc{false}$
\end{algN}
\vspace{-2mm}
Choosing the page to be replaced is based on dividing the pages in the physical memory
into four queues $(Q_1, Q_2, Q_3, Q_4)$.
\vspace{-2mm}
\begin{algN}{NRU-Swap-Out(\var{time})}\inddef{\textsc{NRU-Swap-Out}}
1 \' \key{for} \= $\var{i} \leftarrow 0$ \key{to} $n - 1$ \` $\rhd$ Classifying the pages. \\
2 \' \> \key{do} \= \key{if} \= $\var{referenced}[i] = \textsc{false}$ \\
3 \' \> \> \> \key{then} \= \key{if} \= $\var{dirty}[\var{i}] = \textsc{false}$ \\
4 \' \> \> \> \> \> \key{then} \= \textsc{Enqueue(\var{Q$_1$},\var{i})}\\
5 \' \> \> \> \> \> \key{else} \= \textsc{Enqueue(\var{Q$_2$},\var{i})}
\algnewpageN
6 \' \> \> \> \key{else} \> \key{if} \= $\var{dirty}[\var{i}] = \textsc{false}$\\
7 \' \> \> \> \> \> \key{then} \= \textsc{Enqueue(\var{Q$_3$},\var{i})}\\
8 \' \> \> \> \> \> \key{else} \= \textsc{Enqueue(\var{Q$_4$},\var{i})}\\
9 \' \key{if} \= $\var{Q$_1$}\neq \emptyset$ \` $\rhd$ Choosing the page to be replaced. \\
10 \' \> \key{then} \= $\var{swap-out} \leftarrow \textsc{Dequeue}(\var{Q$_1$})$\\
11 \' \> \key{else} \= \key{if} \= $\var{Q$_2$}\ne\emptyset$\\
12 \' \> \> \> \key{then} \= $\var{swap-out} \leftarrow \textsc{Dequeue}(\var{Q}_2)$\\
13 \' \> \> \> \key{else} \= \key{if} \= $\var{Q}_3 \neq \emptyset$\\
14 \' \> \> \> \> \> \key{then} \= $\var{swap-out} \leftarrow
\textsc{Dequeue}(\var{Q$_3$})$\\
15 \' \> \> \> \> \> \key{else} \= $\var{swap-out} \leftarrow
\textsc{Dequeue}(\var{Q$_4$})$\\
16 \' \key{return} $\var{swap-out}$
\end{algN}
The space requirement of the RUN-NRU algorithm is $O(m)$ and its running time is $O(np)$.
The \textsc{Second-Chance} algorithm is a modification of FIFO. Its main point is that if the referenced
bit of the page to be replaced is \textsc{false} according to FIFO, then we swap it out.
If, however, its referenced bit is \textsc{true}, then we set it to \textsc{false} and put the page from the
beginning of the queue to the end of the queue. This is repeated until a page
is found at the be-ginning of the queue, the referenced bit of which is \textsc{false}.
A more efficient implementation of this idea is the \textsc{Clock}\index{\textsc{Clock}} algorithm
which stores the in-dices of the $m$ pages
in a circular list, and uses a hand to point to the next page to be replaced.
The essence of the LIFO (\textbf{L}ast \textbf{I}n \textbf{F}irst \textbf{O}ut) algorithm is that after filling
in the physical memory according to the requirements we always replace the last arrived page,
i. e., after the initial period there are $m - 1$
pages constantly in the memory---and all the replacements
are performed in the page frame with the highest address.
\subsection{Dynamic paging}
It is typical of most of the computers that there are multiple programs running
simultane-ously on them. If there is paged virtual memory on these computers,
it can be managed both locally and globally. In the former case each program's demand is dealt
with one by one, while in the latter case a program's demand can be satisfied
even at other programs' expenses. Static page replacement algorithms using local management
have been discussed in the last section. Now we present two dynamic algorithms.
The WS (\textsc{Working-Set})\index{\textsc{Working-Set}} algorithm is based on the experience that
when a program is run-ning, in relatively short time there are only few of its pages needed.
These pages form the working set belonging to the given time interval.
This working set can be defined for example as the set of the pages needed for the last $h$
instructions. The operation of the algorithm can be illustrated as pushing a
"window" with length of $h$ along reference array $R$, and keeping the pages
seen through this window in the memory.
\begin{algN}{WS$(\var{pagetable},t,h)$}\inddef{\textsc{WS}}\index{WS|see{Working Set}}
1 \' \key{if} \= $\var{pagetable}[r_t,1] = \textsc{false}$ \` $\rhd$ The next page is not in. \\
2 \' \> \key{then} \= \textsc{WS-swap-out}$(t)$ \\
3 \' \> \> \textsc{Write}$(\var{pagetable}[\var{swap-out},2],\var{swap-out})$ \\
4 \' \> \> $\var{pagetable}[r_t,1] \leftarrow \textsc{true}$ \\
5 \' \> \> $\var{pagetable}[r_t,2] \leftarrow \var{swap-out}$ \\
6 \' \key{if} \= $t > h$ \` $\rhd$ Does $r_{t - h}$ in the memory? \\
7 \' \> \key{then} \= $j \leftarrow h - 1$ \\
8 \' \> \> \key{while} \= $r_j \neq r_{t - h}$ and $j < t$ \\
9 \' \> \> \> \key{do} \= $j \leftarrow j + 1$ \\
10 \' \> \> \key{if} \= $j > t$ \\
11 \' \> \> \> \key{then} $\var{pagetable}[r_{t - h},1] \leftarrow \textsc{false}$
\end{algN}
When discussing the WS algorithm, to make it as simple as possible, we suppose that $h \leq n,$,
therefore, storing the pages seen through the window in the memory is possible even
if all the $h$ references are different (in practice, $h$ is usually significantly bigger
than $n$ due to the many repetitions in the reference string).
The \textsc{WS-Swap-Oout} algorithm can be a static page replacement algorithm,
for instance, which chooses the page to be replaced from all the pages in the memory---i. e., globally.
If, for example, the FIFO algorithm with running time $\Theta(p)$ is used
for this purpose, then the running time of the WS algorithm will be $\Theta(hp)$,
since in the worst case it has to examine the pages in the window belonging
to every single instruction.
The PFF (\textbf{P}age \textbf{F}requency \textbf{F}ault)\index{Page Frequency Fault}
algorithm uses a parameter as well.
This algorithm keeps record of the number of the instructions executed
since the last page fault. If this number is smaller when the next page fault occurs
than a previously determined value of parameter $d$, then the program will get
a new page frame to be able to load the page causing page fault.
If, however, the number of instructions executed without any page faults reaches value $d$,
then first all the page frames containing pages that have not been used
since the last page fault will be taken away from the program,
and after that it will be given a page frame for storing the page causing page fault.
\begin{algN}{PFF$(\var{pagetable},t,d)$}\inddef{\textsc{PFF}}\index{PFF|see{Page Frequency Fault}}
1 \' $\var{counter} \leftarrow 0$ \` $\rhd$ Preparation. \\
2 \' \key{for} \= $i \leftarrow 1$ \key{to} $n$ \\
3 \' \> \key{do} \= $\var{pagetable}[i,1] \leftarrow \textsc{false}$ \\
4 \' \> \> $\var{referenced}[i] \leftarrow \textsc{false}$ \\
5 \' \key{for} \= $j \leftarrow 1$ \key{to} $p$ \` $\rhd$ Running. \\
6 \' \> \key{do} \= \key{if} \= $\var{pagetable}[r_t,1] = \textsc{true}$ \\
7 \' \> \> \> \key{then} \= $\var{counter} \leftarrow \var{counter} + 1$ \\\index{\textit{counter}}
8 \' \> \> \> \key{else} \> \textsc{PFF-Swap-In}$(t,d,\var{swap-out})$ \\
9 \' \> \> \> \> \textsc{Write}$(\var{pagetable}[\var{swap-out},2],\var{swap-out})$ \\
10 \' \> \> \> \> $\var{pagetable}[r_t,1] \leftarrow \textsc{true}$
\algnewpage
11 \' \> \> \key{for} \= $i \leftarrow$ \key{to} $n$ \\
12 \' \> \> \> \key{do} \key{if} \= $\var{referenced}[i] = \textsc{false}$ \\
13 \' \> \> \> \> \key{then} \= $\var{pagetable}[i,1] \leftarrow \textsc{false}$ \\
14 \' \> \> \> \> \> $\var{referenced}[i] \leftarrow \textsc{false}$
\end{algN}
\begin{gyak}
\ujgyak
Consider the following reference string: $R = \langle 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2,$ $3,
7, 6, 3, 2, 1, 2, 3, 6 \rangle$. How many page faults will occur when using FIFO, LRU or
OPT algorithm on a computer with main memory containing $k$ $(1 \leq k \leq 8)$ page frames?
\ujgyak
Implement the FIFO algorithm using a pointer---instead of queue $Q$---pointing to the
page frame of the main memory, which is the next one to load a page.
\ujgyak
What would be the advantages and disadvantages of the page replacement algorithms'
using an $m \times 2$ page map---besides the page table---the $j$-th row of which
indicating whether the $j$-th row of the physical memory is reserved, and also reflecting its content?
\ujgyak
Write and analyse the pseudo code pseudocode of \textsc{Second-Chance,
Clock}\gyakindex{\textsc{Second-Chance}}\gyakindex{\textsc{Clock}} and \textsc{LIFO}\gyakindex{LIFO} algorithms.
\ujgyak
Is it possible to decrease the running time of the NFU\gyakindex{NFU} algorithm (as far as its order
of magnitude is concerned) if the pages are not classed only after each page faults,
but the queues are maintained continuously?
\ujgyak
Another version, NFU', of the NRU\gyakindex{NRU} algorithm is also known, which uses four sets
for classing the pages, and it chooses the page to be replaced from the nonempty set
with the smallest index by chance. Write the pseudo code of operations
\textsc{In-Set} and \textsc{From-Set} needed for this algorithm, and calculate the space requirement
and running time of the NFU' algorithm.
\hardgyak
Extend the definition of the page replacement automat so that it would stop after processing
the last entry of the finite reference sequence. \textit{Hint.} Complete the set
of incoming signs with an 'end of the sequence' sign.
\end{gyak}
\section{Anomalies}\label{sec:anomaly}
When the first page replacement algorithms were tested in the IBM Watson Research
Institute at the beginning of the 1960's, it caused a great surprise that in certain cases
increasing the size of the memory leads to an increase in running time of the programs.
In computer systems the phenomenon, when using more recourses leads to worse results is called anomaly.
Let us give three concrete examples. The first one is in connection with the FIFO page
replacement algorithm, the second one with the \textsc{List-Scheduling}\index{\textsc{List-Scheduling}}
algorithm used for processor scheduling, and the third one with parallel program
execution in computers with interleaved memories.
Note that in two examples out of the three ones a very rare phenomenon can be observed,
namely that the degree of the anomaly can be any large.
\subsection{Page replacement}
Let $m$, $M$, $n$ and $p$ be positive integers $(1 \leq m \leq n < \infty)$,
$k$ a non-negative integer, $A = \{a_1, \ a_2, \ldots, a_n \}$ a finite alphabet. $A^k$ is the set
of the words over $A$ with length $k$, and $A^*$ the words over $A$ with finite length.
Let $m$ be the number of page frames in the main memory of a small, and $M$ a big computer.
The FIFO algorithm has already been defined in the previous section. Since in this subsection
only the FIFO page replacement algorithm is discussed, the sign of the page replacement
algorithm can be omitted from the notations.
Let us denote the number of the page faults by $f_P(R,m)$. The event, when
$M > m$ and $f_P(R,M) > f_P(R,m)$ is called \ki{anomaly.}\inddef{anomaly}
In this case the quotient $f_P(R,M) / f_P(R,m)$ is the degree of the anomaly.
The efficiency of algorithm $P$ is measured by paging speed $E_P(R,m)$ which is defined as
\begin{equation}
E_P(R,m) = \frac{f_P(R, m)}{p} \koz ,
\end{equation}
for a finite reference string $R = \langle r_1, r_2, \ldots \rangle$, while for an infinite
reference string $R = \langle r_1, r_2, \ldots \rangle$ by
\begin{eqnarray}
E_P(R, m) = \liminf_{k \rightarrow \infty} \frac{f_P(R_k, m)}{k} \koz .
\end{eqnarray}
Let $1 \leq m < n$ and let $C = (1,2, \ldots, n)^*$ be an infinite, circular reference sequence.
In this case $E_{\textsc{FIFO}}(C, m) = 1$.
If we process the reference string $R = \langle 1,2,3,4,1,2,5,1,2,3,4,5 \rangle$,
then we will get 9 page faults in the case of $m = 3$,
and 10 ones in the case of $m = 4$, therefore, $f_{\textsc{FIFO}}(R,m) = 10/9$.
Bélády,\nevindex{Bélády, László A.} Nelson\nevindex{Nelson, R. A.}\nevindex{Shedler, G. S.}
and Shedler has given the following necessary and sufficient
condition for the existing of the anomaly.
\begin{tetel} There exists a reference sequence R for which the \textsc{FIFO} page replacement
algorithm causes an anomaly if, and only if $m < M < 2m - 1$.
\end{tetel}
The following has been proved as far as the degree of the anomaly is concerned.
\begin{tetel} If $m < M < 2m - 1$, then for every $\epsilon > 0$ there exists
a reference sequence $R = \langle r_1, r_2, \ldots, r_p \rangle$ for which
\begin{equation}
\frac{f(R,M)}{f(R,m)} > 2 - \epsilon \koz .
\end{equation}
\end{tetel}
Bélády, Nelson and Shedler had the following conjecture.
\begin{sejtes} For every reference sequence R and memory sizes $M > m \geq 1$
\begin{equation}
\frac{f_{\textsc{FIFO}}(R,M)}{f_{\textsc{FIFO}}(R,m)} \leq 2 \koz .
\end{equation}
\end{sejtes}
This conjecture can be refuted e. g. by the following example.
Let $m = 5, \ M = 6, \ n = 7, \ k \geq 1$, and $R = UV^k$, where $V = (1, 2, 3, 4, 5, 6, 7)^3$ and
$U = \langle 1, 2,$ $3, 4, 5, 6, 7, 1, 2, 4, 5, 6, 7, 3, 1, 2, 4, 5, 7, 3,
6, 2, 1, 4, 7, 3, 6, 2, 5, 7, 3, 6, 2, 5 \rangle$.
If execution sequence U is executed using a physical memory with $m = 5$ page frames,
then there will be 29 page faults, and the processing results in controlling status
(7,3,6,2,5). After that every execution of reference sequence $V$ causes 7 new page
faults and results in the same controlling status.
If the reference string $U$ is executed using a main memory with $M = 6$ page frames,
then we get control state $\langle 2, 3, 4, 5, 6, 7 \rangle$ and 14 page faults.
After that every execution of reference sequence $V$ causes 21 new page faults and
results in the same control state.
Choosing $k = 7$ the degree of the anomaly will be
$(14 + 7 \times 21)/(29 + 7 \times 7) = 161/78 > 2$.
As we increment the value of $k$, the degree of the anomaly will go to three.
Even more than that is true: according to the
following theorem by Péter Fornai\nevindex{Fornai, Péter} and
Antal Iványi\nevindex{Iványi, Antal Miklós} the degree of the anomaly can be any arbitrarily large.
\begin{tetel} For any large number L it is possible to give parameters
m, M and R so that the following holds:
\begin{equation}
\frac{f(R,M)}{f(R,m)} > L \koz .
\end{equation}
\end{tetel}
\subsection{Scheduling with lists}
Suppose that we would like to execute $n$ \ki{tasks}\inddef{task} on $p$ processors.
By the execution the priority order of the programs has to be taken into consideration.
The processors operate according to First Fit, and the execution is carried out according to a given list $L$.
E. G. Coffman jr. wrote in 1976 that decreasing the number of processors,
decreasing \ki{execution time}\inddef{execution time} $t_i$ of the tasks,
reducing the precedence restrictions, and altering the list can each cause an anomaly.
Let the \ki{vector of the execution times}\inddef{vector of the execution times}
of the tasks denoted by \textbf{t},\
the precedence relation by <, the list by $L$, and execution time of all the tasks
with a common list on $p$ equivalent processors by $C(p,L,<,\mathbf{t})$.
The degree of the anomaly is measured by the ratio of the execution time $C'$ at the new parameters
and execution time $C$ at the original parameters.
First let us show four examples for the different types of the anomaly.
\begin{pelda} Consider the following task system $\tau_1$ and its scheduling $S_1$ received using
list $L=(T_1, \ T_2, \ \dots, \ T_9)$ on $m = 3$ equivalent processors.
In this case $C_\mathrm{max} (S_1)=12$ (see Figure \ref{abra:anom1}),
which can be easily proved to be the optimal value.
\begin{figure}[!t]
\begin{center}
\resizebox{6.5cm}{!}{
\epsfbox{figs/anom1_psfrag.eps}
}
\end{center}
\vspace{2mm}
\begin{center}
\parbox[5ex]{2em}{$S_1:$\vspace{2.5ex}}
\small
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$
\vspace{3ex}
\end{tabular}
\begin{tabular}{!{0} l !{1} l !{2} l !{3} l !{4} l !{5} l !{6} l !{7} l !{8} l !{9} l !{10} l !{11} l !{12}}
\hline
\mc{3}{|c|}{$\m T_1$}&\mc{9}{c|}{$\m T_9$} \\ \hline
\mc{2}{|c|}{$\m T_2$}&\mc{2}{c|}{$\m T_4$}&\mc{4}{c|}{$\m T_5$}&\mc{4}{c|}{$\m T_7$} \\ \hline
\mc{2}{|c|}{$\m T_3$}&\grn2-&\mc{4}{c|}{$\m T_6$}&\mc{4}{c|}{$\m T_8$} \\ \hline
&&&&&&&&&&&
\end{tabular}
\caption{\label{abra:anom1} Task system $\tau_1$, and its optimal schedule.}
\end{center}
\end{figure}
\end{pelda}
\begin{pelda} Schedule the previous task system $\tau_1$ for $m = 3$ equivalent processors with
list $L'= \langle \m T_1,\m T_2,\m T_4,\m T_5,\m T_6,\m T_3,\m T_9,\m T_7,\m T_8 \rangle$.
In this case for the resulting scheduling $S_2$ we get $C_{max}(S_2)=14$ (see Figure \ref{abra:S2utemezes}).
\end{pelda}
\begin{figure}[!t]
\small
\begin{center}
\parbox[5ex]{2em}{$S_2:$\vspace{2.5ex}}
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$
\vspace{3ex}
\end{tabular}
\begin{tabular}{!{0} l !{1} l !{2} l !{3} l !{4} l !{5} l !{6} l !{7} l !{8} l
!{9} l !{10} l !{11} l !{13} l !{12} l !{14}}
\hline
\mc{3}{|c|}{$\m T_1$}&\mc{2}{c|}{$\m T_3$}&\mc{9}{c|}{$\m T_9$} \\ \hline
\mc{2}{|c|}{$\m T_2$}&\mc{4}{c|}{$\m T_5$}&\mc{4}{c|}{$\m T_7$}&\grn4- \\\hline
\mc{2}{|c|}{$\m T_4$}&\mc{4}{c|}{$\m T_6$}&\mc{4}{c|}{$\m T_8$}&\grn4- \\\hline
&&&&&&&&&&&&&
\end{tabular}
\normalsize
\caption{\label{abra:S2utemezes} Scheduling of the task system $\tau_1$
at list $L'$.}
\end{center}
\end{figure}
\begin{pelda} Schedule the task system $\tau_1$ with list $L$ for $m'=4$ processors.
It results in $C_{max}(S_3)=15$ (see Figure \ref{abra:S3utemezes}).
\end{pelda}
\begin{figure}[!t]
\small
\begin{center}
\parbox[5ex]{2em}{$S_3:$\vspace{3ex}}
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$ \\
$P_4$
\vspace{3ex}
\end{tabular}
\begin{tabular}{!{0} l !{1} l !{2} l !{3} l !{4} l !{5} l !{6} l !{7} l !{8} l
!{9} l !{10} l !{11} l !{13} l !{12} l !{14} l !{15}}
\hline
\mc{3}{|c|}{$\m T_1$}&\mc{4}{c|}{$\m T_8$}&\grn8- \\ \hline
\mc{2}{|c|}{$\m T_2$}&\mc{4}{c|}{$\m T_5$}&\mc{9}{c|}{$\m T_9$} \\\hline
\mc{2}{|c|}{$\m T_3$}&\mc{4}{c|}{$\m T_6$}&\grn9- \\\hline
\mc{2}{|c|}{$\m T_4$}&\mc{4}{c|}{$\m T_7$}&\grn9- \\\hline
&&&&&&&&&&&&&&
\end{tabular}
\normalsize
\caption{\label{abra:S3utemezes} Scheduling of the task system $\tau_1$
using list $L$ on $m'=4$ processors.}
\end{center}
\end{figure}
\begin{pelda} Decrement the executing times by one in $\tau_1$. Schedule the resulting task
system $\tau_2$ with list $L$ for $m = 3$ processors. The result is: $C_{max}(S_4)=13$
(see Figure \ref{abra:S4utemezes}).
\end{pelda}
\begin{figure}[!t]
\small
\begin{center}
\parbox[5ex]{2em}{$S_4:$\vspace{2.5ex}}
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$
\vspace{3ex}
\end{tabular}
\begin{tabular}{!{0} l !{1} l !{2} l !{3} l !{4} l !{5} l !{6} l !{7} l !{8} l !{9} l !{10} l !{11} l !{12} l !{13}}
\hline
\mc{2}{|c|}{$\m T_1$}&\mc{3}{c|}{$\m T_5$}&\mc{3}{c|}{$\m T_8$}&\grn5- \\\hline
\mc{1}{|c|}{$\m T_2$}&\mc{1}{c|}{$\m T_4$}&\mc{3}{c|}{$\m T_6$}&\mc{8}{c|}{$\m T_9$} \\ \hline
\mc{1}{|c|}{$\m T_3$}&\gr-&\mc{3}{c|}{$\m T_7$}&\grn8- \\ \hline
&&&&&&&&&&&&
\end{tabular}
\normalsize
\caption{\label{abra:S4utemezes} Scheduling of $\tau_2$ with list $L$ on
$m=3$ processors.}
\end{center}
\end{figure}
\begin{pelda} Reduce the precedence restrictions: omit edges $(T_4, \ T_5)$ and $(T_4, \ T_6)$ from the graph.
The result of scheduling $S_5$ of the resulting task system $\tau_3$ can be seen
in Figure \ref{abra:S5utemezes}: $C_{\mathrm{max}}(S_5)=16$.
\end{pelda}
\begin{figure}[!t]
\small
\begin{center}
\parbox[5ex]{2em}{$S_5:$\vspace{2.5ex}}
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$
\vspace{3ex}
\end{tabular}
\begin{tabular}{!{0} l !{1} l !{2} l !{3} l !{4} l !{5} l !{6} l !{7} l !{8} l !{9} l !{10} l !{11} l !{12} l !{13} l !{14} l !{15} l !{16}}
\hline
\mc{3}{|c|}{$\m T_1$}&\mc{4}{c|}{$\m T_6$}&\mc{9}{c|}{$\m T_9$} \\\hline
\mc{2}{|c|}{$\m T_2$}&\mc{2}{c|}{$\m T_4$}&\mc{4}{c|}{$\m T_7$}&\grn8- \\\hline
\mc{2}{|c|}{$\m T_3$}&\mc{4}{c|}{$\m T_5$}&\mc{4}{c|}{$\m T_8$}&\grn6- \\\hline
&&&&&&&&&&&&&&&
\end{tabular}
\normalsize
\caption{\label{abra:S5utemezes} Scheduling task system $\tau_3$ on $m=3$ processors.}
\end{center}
\end{figure}
The following example shows that the increase of maximal finishing time in the worst case
can be caused not only by a wrong choice of the list.
\begin{pelda} Let task system $\tau$ and its optimal scheduling $S_\textsc{OPT}$ be as showed
by Figure \ref{abra:anom2}. In this case $C_{max}(S_\textsc{OPT})=19$.
\end{pelda}
\begin{figure}[!th]
\begin{center}
\begin{tabular}{l}
\resizebox{4.2cm}{!}{
\epsfbox{figs/anom2_psfrag.eps}
}
\end{tabular}
\vspace{2mm}
\small
\begin{center}
\parbox[5ex]{2em}{$S_{OPT}:$\vspace{2.5ex}}
\begin{tabular}{l}
$P_1$ \\
$P_2$
\vspace{3ex}
\end{tabular}
\hspace{-3ex}
\setlength{\tabcolsep}{2pt}
\begin{tabular}{!{0} l !{1} l !{2} l !{3} l !{4} l !{5} l !{6} l !{7} l !{8} l
!{9} l !{10} l !{11} l !{12} l !{13} l !{14} l !{15} l !{16} l !{17} l !{18}
l !{19}}
\hline
\mc{4}{|c|}{$\m T_1$}&\mc{5}{c|}{$\m T_4$}&\mc{10}{c|}{$\m T_6$} \\\hline
\mc{2}{|c|}{$\m T_2$}&\mc{2}{c|}{$\m T_3$}&\mc{5}{c|}{$\m T_5$}&\mc{10}{c|}{$\m T_7$} \\\hline
&&&&&&&&&&&&&&&&&&
\end{tabular}
\end{center}
\normalsize
\caption{\label{abra:anom2} Task system $\tau$ and its optimal scheduling $S_\m{OPT}$
on two processors.}
\end{center}
\end{figure}
We can easily prove that if the executing times are decremented by one,
then in the resulting task system $\tau'$ we cannot reach a better result
than $C_{max}(S_6)=20$ with any lists (see Figure \ref{abra:anom3}).
\begin{figure}[!t]
\begin{center}
\parbox[5ex]{2em}{$S_6:$\vspace{2.5ex}}
\hspace{-2ex}
\begin{tabular}{l}
$P_1$ \\
$P_2$
\vspace{3ex}
\end{tabular}
\hspace{-3ex}
\small
\setlength{\tabcolsep}{3pt}
\begin{tabular}{!{0} l !{1} l !{2} l !{3} l !{4} l !{5} l !{6} l !{7} l !{8} l
!{9} l !{10} l !{11} l !{12} l !{13} l !{14} l !{15} l !{16} l !{17} l !{18}
l !{19} l !{20}}
\hline
\mc{3}{|c|}{$\m T_1$}&\mc{4}{c|}{$\m T_4$}&\mc{4}{c|}{$\m T_5$}&\mc{9}{c|}{$\m T_7$} \\\hline
\mc{1}{|c|}{$\m T_2$}&\mc{1}{c|}{$\m T_3$}&\mc{9}{c|}{$\m T_6$}&\grn9- \\\hline
&&&&&&&&&&&&&&&&&&&
\end{tabular}
\normalsize
\caption{\label{abra:anom3} Optimal list scheduling of task system $\tau'$.}
\end{center}
\end{figure}
After these examples we give a relative limit reflecting the effects of the scheduling
parameters. Suppose that for given task systems $\tau$ and $\tau'$ we have $\T'=\T$,
$<'\,\subseteq\,<$, $\t'\le\t$.
Task system $\tau$ is scheduled with the help of list $L$, and $\tau'$ with $L'$---
the former on $m$, while the latter on $m'$ equivalent processors.
For the resulting schedulings $S$ and $S'$ let $C(S)=C$ and $C(S')=C'$.
\begin{tetel}[scheduling limit]. With the above conditions
\begin{equation}
\frac{C'}{C} \le 1+\frac{m-1}{m'} \koz .\label{eq:utkorlat}
\end{equation}
\end{tetel}
\begin{biz} Consider scheduling diagram $D'$ for the parameters with apostrophes
(for $S'$). Let the definition of two subsets---$A$ and $B$---of the interval $[0,C')$
be the following: $A = \{ t \in [0,C') |$ all the processors are busy in time $t \}$,
$B = [0,C')\setminus A$. Note that both sets are unions of disjoint, half-open
(closed from the left and open from the right) intervals.
Let $T_{j_1}$ be a task the execution of which ends in $C'$ instant of time according to
D1 (i. e., $f_{j_1} = C'$). In this case there are two possibilities:
Starting point $s_{j_1}$ of task $T_{j_1}$ is either an inner point of $B$, or not.
\begin{enumerate}
\item
If $s_{j_1}$ is an inner point of $B$, then according to the definition of $B$ there
is a processor for which with $\varepsilon>0$ it holds that it does not work
in the interval $[s_{j_1}-\varepsilon, s_{j_1})$.
This can only occur if there is a task $T_{j_2}$ for which
$\m T_{j_2}<'\m T_{j_1}$ and $f_{j_2}=s_{j_1}$ (case a).
\item
If $s_{j_1}$ is not an inner point of $B$, then either $s_{j_1}=0$ (case b), or $s_{j_1}>0$.
If $B$ has got a smaller element than $s_{j_1}$ (case c), then let
$x_1=\sup\{x\mid x0$, then it follows from the construction of $A$ and $B$
that there is a processor for which a task $\m T_{j_2}$ can be found the execution of which
is still in progress in this time interval, and for which $\m T_{j_2}<'\m T_{j_1}$.
\end{enumerate}
Summarising the two cases we can say that either there is a task $\m T_{j_2}<'\m T_{j_1}$
for which in the case of $y\in[f_{j_2}, s_{j_1})$ holds $y\in A$ (case a or c),
or for every number $x c \geq 1$.
Let the sequences be deterministic.
Since for every bite-size $B_t \ (t = 1,2,\ldots)$ of $G_b$ holds $b \leq B_t \leq bn$,
the same bounds are right for every average value $(\sum B_i)_{i=1}^t)/t$ and for every
expected value $E((\sum_{i=1}^t B_i)/t)$, too. From this it follows, that the limits $S_b$ and
$S_c$ defined in (\ref{def:speed-limit}) also must lie between these bounds, that is
\begin{equation}
b \leq S_b \leq bn, \ \ \ g \leq S_c \leq cn \koz .
\end{equation}
Choosing the maximal value of $S_b$ and the minimal value of $S_c$ and vice versa
we get the following trivial upper and lower bounds for the speed ratio $S_b/S_c$:
\begin{equation}
\frac{b}{cn} \leq \frac{S_b}{S_c} \leq \frac{bn}{c} \koz . \label{eq:gomboc}
\end{equation}
Now we show that in many cases these trivial bounds cannot be improved (and so
the dumpling eating speed of a small giant can
be any times bigger than that of a big giant).
\begin{tetel} If $r \geq 1, \ n \geq 3, \ b > c \geq 1$,
then there exist dumpling sequences, for which
\begin{equation}
\frac{S_b}{S_c} = \frac{b}{cn} \koz ,
\end{equation}
further
\begin{equation}
\frac{S_b}{S_c} = \frac{bn}{c} \koz .
\end{equation}
\end{tetel}
\begin{biz} To see the sharpness of the lower limit in the inequality
(\ref{eq:gomboc}) giving the natural limits let consider the following sequences:
\begin{equation}
\begin{array}{l}
1^{b}2^{2b+1}1^* \\
1^{b+1}(2 3 \ldots n)^* \koz .
\end{array}
\end{equation}
Giant $G_b$ eats these sequences in the following manner:
\begin{equation}
\begin{array}{lllll}
\| 1^{b}2^{b} & \| 2^b & \| 21^b & \| 1^b & \| ^* \\
\| -- & \| 1^b & \| -- & \| -- & \| .
\end{array}
\end{equation}
Here $B_1 = 2b$, $B_2 = 2b$, $B_3 = b + 1$, $B_t = b$ (for $t = 4, 5, \ldots$.
For the given sequences we have
\begin{equation}
S_b = \lim _{t \rightarrow \infty}\frac{2b + 1 + tb}{t} = b.
\end{equation}
$G_c$ eats these sequences as follows:
\begin{equation}
\begin{array}{llllllll}
\| 1^c & \| ^{\alpha} \ 1^{c_1}2^{c} & \| 2^c & \| ^{\beta} \ 2^c & \| 2^c & \| ^{\gamma} \ 2^{c_4} 1^c & \| 1^c & \| ^* \\
\| -- & \| 1^{c_2} & \| 1^c & \| 1^{c_3} & \| --& \| (23\ldots)^{c_3} & \| (23\ldots)^c & \|.
\end{array}
\end{equation}
Here
$$ \alpha = \left \lceil \frac{b - c}{c} \right \rceil ; \ c_1 = b - \alpha c; \ c_2 = c - c_1 \koz ;$$
$$ \beta = \left \lceil \frac{b + 1 - c_2 - c}{c} \right \rceil ; \ c_3 = b + 1 - c_2 - \beta c \koz ;$$
$$ \gamma = \left \lceil \frac{2b + 1 -c(\beta + 2)}{c} \right \rceil; \ c_4 = 2b + 1 - c(\beta + \gamma + 2) \koz ;$$
$$c_5 = c - c_4.$$
In this case we get (in a similar way, as we have got $S_b$)
\begin{equation}
S_c = cn
\end{equation}
and therefore
\begin{equation}
\frac{S_b}{S_c} = \frac{b}{cn} \koz .
\end{equation}
In order to derive the exact upper bound, we consider the following sequence:
\begin{equation}
\begin{array}{l}
1 2^{2b + 1} 1^* \\
1^{b - 1} 3^{2b} 1^b (2 3 \ldots n)^* \koz .
\end{array}
\end{equation}
$G_b$ eats these sequences as follows:
\begin{equation}
\begin{array}{lllll}
\| 12^b & \| 2^b & \| 21^b & \| 1^b & \| ^* \\
\| 1^{b-1}3^b & \| 3^b1^b & \| (23\ldots)^{b-1} & \| (23\ldots n)^b & \| \koz .
\end{array}
\end{equation}
From here we get
\begin{equation}
S_b = \lim_{t \rightarrow \infty} \frac{3b+3b+n(b-1)+2+(t-3)bn}{t} = bn \koz .
\end{equation}
$G_c$'c eating is characterised by
\begin{equation}
\begin{array}{lllllllll}
\| 12^c & \| 2^c & \| ^\alpha 2^c & \| 2^c & \| ^\beta \ 2^{c_3}1^c & \| 1^c & \| 1^c & \| 1^c & \| ^* \\
\| 1^{c_1} & \| 1^c & \| 1^{c_2}3^c & \| 3^c & \| 3^c & \| 3^c & \| 3^{c_4} & \| -- & \| \koz ,
\end{array}
\end{equation}
where
$$c_1 = c - 1; \ \alpha = \left \lceil \frac{b-c-c_1}{c} \right \rceil ; \ c_2 = b-1-c_1-\alpha c \koz ;$$
$$\beta =\left \lceil \frac{2b+1-c(\alpha+\beta)}{c}\right \rceil ;
\gamma = \left \lceil \frac{2b-c(\beta + 2)}{c}\right \rceil \ \koz ;$$
$$c_4 = 2b - c(\beta + \gamma + 2) c_3 = 2b + 1 - c(\alpha+\beta+2) \koz .$$
Since $B_t = c$ for $t = \alpha + \beta + \gamma + 5, \ t = \alpha + \beta + \gamma + 6, \ldots,$
therefore $S_c = c,$ and so $S_b/S_c = bn/c.$
\end{biz}
$$ \alpha = \left \lceil \frac{b - c}{c} \right \rceil ; \ c_1 = b - \alpha c; \ c_2 = c - c_1 \koz ;$$
$$ \beta = \left \lceil \frac{b + 1 - c_2 - c}{c} \right \rceil ; \ c_3 = b + 1 - c_2 - \beta c \koz ;$$
$$ \gamma = \left \lceil \frac{2b + 1 -c(\beta + 2)}{c} \right \rceil; \ c_4 = 2b + 1 - c(\beta + \gamma + 2) \koz ;$$
$$c_5 = c - c_4.$$
\subsection{Avoiding the anomaly}
We usually try to avoid anomalies.
For example at page replacing the sufficient condition of avoiding it is
that the replacing algorithm should have the stack property: if the same reference string
is run on computers with memory sizes of $m$ and $m + 1$, then after every reference
it holds that the bigger memory contains all the pages that the smaller does.
At the examined scheduling problem it is enough not to require the scheduling algorithm's using a list.
\begin{gyak}
\ujgyak
Give parameters $m, M, n, p$ and $R$ so that the FIFO algorithm would cause
at least three more page faults with a main memory of size $M$ than with that of size $m$.
\ujgyak
Give such parameters that using scheduling with list when increasing the number
of processors the maximal stopping time increases at least to half as much again.
\ujgyak
Give parameters with which the dumpling eating speed of
a small giant is twice as big as that of a big giant.
\end{gyak}
\section{Optimal file packing}\label{sec:filepacking}
In this section we will discuss a memory managing problem in which files with given sizes
have to be placed onto discs with given sizes. The aim is to minimise the number of the discs used.
The problem is the same as the bin-packing problem that can be found among the problems
in Section \textit{Approximation algorithms} in the book titled \textit{Introduction to Algorithms}.
Also scheduling theory uses this model in connection with minimising the number of processors.
There is the number $n$ of the files given, and array vector $\textbf{t} = (t_1, t_2, \ldots, t_n)$
containing the sizes of the files to be stored, for the elements of which
$0 < t_i \leq 1$ holds $(i = 1, 2, \ldots, n)$. The files have to be placed
onto the discs taking into consideration that they cannot be divided and the capacity of the discs is a unit.
\subsection{Approximation algorithms}
The given problem is NP-complete. Therefore, different approaching algorithms are used in practice.
The input data of these algorithms are: the number $n$ of files, a vector $\textbf{t} = \langle t_1,
t_2, \ldots, t_n\rangle$ with the sizes of the files to be placed.
And the output data are the number of discs needed (discnumber) and the level array
$h = (h_1, h_2, \ldots, h_n)$ of discs.
\subsubsection{Linear Fit (LF)}\index{Linear Fit}
According to \textbf{L}inear \textbf{F}it file
$F_i$ is placed to disc $D_i$. The pseudocode of LF is the following.
\begin{alg}{LF$(n,\mathbf{t})$}\inddef{\textsc{LF}}\index{LF|see{Linear Fit}}
1 \' \key{for} \= $i \leftarrow 1$ \key{to} $n$ \\
2 \' \> \key{do} $h[i] \leftarrow t[i]$ \\
3 \' $\var{number-of-discs} \leftarrow n$ \\
4 \' \key{return} $\var{number-of-discs}$
\end{alg}
Both the running time and the place requirement of this algorithm are $O(n)$.
If, however, reading the sizes and printing the levels are carried out in the loop in rows
2--3, then the space requirement can be decreased to $O(1)$.
\subsubsection{Next Fit (NF)}\index{Next Fit}
\textbf{N}ext \textbf{F}it packs the files onto the disc next in line as long as possible.
Its pseudocode is the following.
\begin{alg}{NF$(n,\mathbf{t})$}\inddef{\textsc{NF}}\index{NF|see{Next Fit}}
1 \' $h[1] \leftarrow t[1]$ \\
2 \' $\textit{number-of-discs} \leftarrow 1$ \\
3 \' \key{for} \= $i \leftarrow 2$ \key{to} $n$ \\
4 \' \> \key{do} \key{if} \= $h[\textit{number-of-discs}] + t[i] \leq 1$ \= \\
5 \' \> \> \key{then} \= $h[\textit{number-of-discs}] \leftarrow h[\textit{number-of-discs}] + t[i]$ \\
6 \' \> \> \key{else} \> $\textit{number-of-discs} \leftarrow \textit{number-of-discs} + 1$ \\
7 \' \> \> \> $h[\textit{number-of-discs}] \leftarrow t[i]$ \\
8 \' \key{return} $\var{number-of-discs}$
\end{alg}
Both the running time and the place requirement of this algorithm are $O(n)$.
If, however, reading the sizes and taking the levels out are carried out in the loop in rows 3--6,
then the space requirement can be decreased to $O(1)$, but the running time is still $O(n)$.
\subsubsection{First Fit (FF)}\index{First Fit}\index{FF|see{First Fit}}
\textbf{F}irst \textbf{F}it packs each files onto the first disc onto which it fits.
\begin{algN}{FF$(n,\mathbf{t})$}\inddef{\textsc{FF}}
1 \' $\var{number-of-discs} \ \leftarrow 1$ \\
2 \' \key{for} \= $i \leftarrow 1$ \key{to} $n$ \\
3 \' \> \key{do} $h[i] \leftarrow 0$ \\
3 \' \key{for} \= $i \leftarrow 1$ \key{to} $n$ \\
4 \' \> \key{do} \= $k \leftarrow 1$ \\
5 \' \> \> \key{while} \= $t[i] + h[k] > 1$ \\
6 \' \> \> \> \key{do} \= $k \leftarrow k + 1$ \\
7 \' \> \> $h[k] \leftarrow h[k] + t[i]$ \\
8 \' \> \> \key{if} \= $k > \var{number-of-discs}$ \\
9 \' \> \> \> \key{then} $\var{number-of-discs} \leftarrow \var{number-of-discs} + 1$ \\
10 \' \key{return} $\var{number-of-discs}$
\end{algN}
The space requirement of this algorithm is $O(n)$, while its time requirement is $O(n^2)$.
If, for example, every file size is 1, then the running time of the algorithm is $\Theta(n^2)$.
\subsubsection{Best Fit (BF)}\index{Best Fit}\index{BF|see{Best Fit}}
\textbf{B}est \textbf{F}it places each file onto the first disc on which the remaining capacity is the smallest.
\begin{algN}{BF$(n,\mathbf{t})$}\inddef{\textsc{BF}}
1 \' $\var{number-of-discs} \leftarrow 1$ \\
2 \' \key{for} \= $i \leftarrow 1$ \key{to} $n$ \\
3 \' \> \key{do} $h[i] \leftarrow 0$ \\
4 \' \key{for} \= $i \leftarrow 1$ \key{to} $n$ \\
5 \' \> \key{do} \= $\var{free} \leftarrow 1.0$\index{\textit{free}} \\
6 \' \> \> $\var{ind} \leftarrow 0$\index{\textit{ind}} \\
7 \' \> \> \key{for} \= $k \leftarrow 1$ \key{to} $\var{number-of-discs}$ \\
8 \' \> \> \> \key{do} \> \key{if} \= $h[k] + t[i] \leq 1$
and $1 - h[k] - t[i] < \var{free}$ \\
9 \' \> \> \> \> \key{then} \= $\var{ind} \leftarrow k$ \\
10 \' \> \> \> \> \> $\var{szabad} \leftarrow 1-h[k]-t[i]$ \\
11 \' \> \key{if} \= $\var{ind} > 0$ \= \\
12 \' \> \> \key{then} \= $h[\var{ind}] \leftarrow h[\var{ind}] + t[i]$ \\
13 \' \> \> \key{else} \> $\var{number-of-discs} \leftarrow \var{number-of-discs} + 1$ \\
14 \' \> \> \> $h[\var{number-of-discs}] \leftarrow t[i]$ \\
15 \' \key{return} $\var{number-of-discs}$
\end{algN}
The space requirement of this algorithm is $O(n)$, while its time requirement is $O(n2)$.
\subsubsection{Pairwise Fit (PF)}\index{Pairwise Fit}\index{PF|see{Pairwise Fit}}
Pairwise Fit creates a pair of the first and the last element of the array of sizes,
and places the two files onto either one or two discs---according to the sum of the two sizes.
In the pseudocode there are two auxiliary variables: bind is the index of the first element
of the current pair, and eind is the index of the second element of the current pair.
\begin{algN}{PF$(n,\mathbf{t})$}\inddef{\textsc{PF}}
1 \' $\var{number-of-discs} \leftarrow 0$ \\
2 \' $\var{beg-ind} \leftarrow 1$\index{\textit{beg-ind}} \\
3 \' $\var{end-ind} \leftarrow n$\index{\textit{end-ind}} \\
4 \' \key{while} \= $\var{end-ind} \geq \var{beg-ind}$ \\
5 \' \> \key{do} \= \key{if} \= $\var{end-ind} - \var{beg-ind} \geq 1$ \\
6 \' \> \> \> \key{then} \= \key{if} \= $t[\var{beg-ind}] + t[\var{end-ind}] > 1$ \= \\
7 \' \> \> \> \> \> \key{then} \= $\var{number-of-discs} \leftarrow \var{number-of-discs} + 2$ \\
8 \' \> \> \> \> \> \> $h[\var{number-of-discs} - 1] \leftarrow t[\var{bind}]$ \\
9 \' \> \> \> \> \> \> $h[\var{number-of-discs}] \leftarrow t[\var{eind}]$ \\
10 \' \> \> \> \> \> \key{else} \= $\var{number-of-discs} \leftarrow \var{number-of-discs} + 1$ \\
11 \' \> \> \> \> $h[\var{number-of-discs}] \leftarrow t[\var{beg-ind}] + t[\var{eind}]$ \\
12 \' \> \> \key{if} \= $\var{end-ind} = \var{beg-ind}$ \= \\
13 \' \> \> \> \key{then} \= $\var{number-of-discs} \leftarrow \var{number-of-discs} + 1$ \\
14 \' \> \> \> \> $h[\var{number-of-discs}] \leftarrow t[\var{end-ind}]$ \\
15 \' \> \> $\var{beg-ind} \leftarrow \var{beg-ind} + 1$ \\
16 \' \> \> $\var{end-ind} \leftarrow \var{end-ind} - 1$ \\
17 \' \key{return} $\var{number-of-discs}$
\end{algN}
The space requirement of this algorithm is $O(n)$, while its time requirement is $O(n^2)$.
If, however, reading the sizes and taking the levels of the discs out are carried out online,
then the space requirement will only be $O(1)$.
\subsubsection{Next Fit Decreasing (NFD)}\index{NFD}\index{NFD|see{Next Fit Decreasing}}
The following five algorithms consist of two parts: first they put the tasks
into decreasing order according to their executing time, and then they schedule the ordered tasks.
\textbf{N}ext \textbf{F}it \textbf{D}ecreasing operates according to NF after ordering.
Therefore, both its space and time requirement are made up of that of the applied ordering algorithm and NF.
\subsubsection{First Fit Decreasing (FFD)}\index{FFD}\index{FFD|see{First Fit decreasing}}
First Fit Decreasing operates according to First Fit (FF) after ordering,
therefore its space requirement is $O(n)$ and its time requirement is $O(n^2)$.
\subsubsection{Best Fit Decreasing (BFD)}\index{Best Fit Decreasing}\index{BFD|see{Best Fit Decreasing}}
\textbf{B}est \textbf{F}it \textbf{D}ecreasing operates according to Best Fit (BF) after ordering,
therefore its space requirement is $O(n)$ and its time requirement is $O(n2)$.
\subsubsection{Pairwise Fit Decreasing (PFD)}\index{Pairwise Fit Decreasing}\index{PFD|see{pairwise Fit Decreasing}}
\textbf{P}airwise \textbf{F}it \textbf{D}ecreasing creates pairs of the first and the last tasks
one after another, and schedules them possibly onto the same processor
(if the sum of their executing time is not bigger than one). If it is not possible,
then it schedules the given pair onto two processors.
\subsubsection{Quick Fit Decreasing (QFD)}\index{Quick Fit Decreasing}\index{QFD|see{Quick Fit Decreasing}}
\textbf{Q}uick \textbf{F}it \textbf{D}ecreasing places the first file after ordering onto the next empty disc,
and then adds the biggest possible files (found from the end of the ordered array of sizes)
to this file as long as possible.
The auxiliary variables used in the pseudocode are: bind is the index of the first file
to be examined, and eind is the index of the last file to be examined.
\begin{algN}{QFD$(n,\mathbf{s})$}\inddef{\textsc{QFD}}
1 \' $\var{beg-ind} \leftarrow 1$ \\
2 \' $\var{end-ind} \leftarrow n$ \\
4 \' $\var{number-of-discs} \leftarrow 0$ \\
5 \' \key{while} \= $\var{end-ind} \geq \var{beg-ind}$ \\
6 \' \> \key{do} \= $\var{number-of-discs} \leftarrow \var{number-of-discs} + 1$ \\
7 \' \> \> $h[\var{number-of-discs}] \leftarrow s[\var{bind}]$ \\
8 \' \> \> $\var{beg-ind} \leftarrow \var{beg-ind} + 1$ \\
9 \' \> \> \key{while} \= $\var{end-ind} \geq \var{beg-ind}$ and $h[\var{number-of-discs}] + s[\var{eind}] \leq 1$ \\
10 \' \> \> \> \key{do} \= $\var{ind} \leftarrow \var{end-ind}$ \\
11 \' \> \> \> \> \key{while} \= $\var{ind} > \var{beg-ind}$ and $h[\var{number-of-discs}] + s[\var{ind} - 1] \leq 1$ \\
12 \' \> \> \> \> \> \key{do} $\var{ind} \leftarrow \var{ind} - 1$ \\
13 \' $h[\var{number-of-discs}] \leftarrow h[\var{number-of-discs}] + s[\var{ind}]$ \\
14 \' \key{if} \= $\var{end-ind} > \var{ind}$ \\
15 \' \> \key{then} \= \key{for} \= $i \leftarrow \var{ind}$ \key{to} $\var{end-ind} - 1$ \\
16 \' \> \> \> \key{do} $s[i] \leftarrow s[i + 1]$ \\
17 \' $\var{end-ind} \leftarrow \var{end-ind} - 1$ \\
18 \' \key{return} $\var{number-of-discs}$
\end{algN}
The space requirement of this program is $O(n)$, and its running time in worst case is
$\Theta(n_2)$, but in practice---in case of executing times of uniform distribution---it
is $(n \lg n)$.
\subsection{Optimal algorithms}
\subsubsection{Simple Power (SP)}\index{Simple Power}\index{SP|see{Simple Power}}
This algorithm places each file---independently of each other---on each of the $n$ discs,
so it produces $n^n$ placing, from which it chooses an optimal one.
Since this algorithm produces all the different packing (supposing that two placing are
the same if they allocate the same files to all of the discs), it certainly finds one of the optimal placing.
\subsubsection{Factorial Algorithm (FACT)}\index{Factorial}\index{FACT|see{Factorial}}
This algorithm produces the permutations of all the files (the number of which is $n!$),
and then it places the resulted lists using NF.
The algorithm being optimal can be proved as follows. Consider any file system and
its optimal packing is $S_{\textsc{OPT}}(t)$. Produce a permutation $P$ of the files based
on $S_{\textsc{OPT}}(t)$ so that we list the files placed onto $P_1, P_2, \ldots, P_{\textsc{OPT}}(t)$
respectively. If permutation $P$ is placed by NF algorithm, then we get either
$S_{\textsc{OPT}}$ or another optimal placing (certain tasks
might be placed onto processors with smaller indices).
\subsubsection{Quick Power (QP)}\index{Quick Power}\index{QP|see{Quick Power}}
This algorithm tries to decrease the time requirement of
SP by placing 'large' files (the size of which is bigger than 0.5) on separate discs,
and tries to place only the others (the 'small' ones) onto all the $n$ discs.
Therefore, it produces only $n^K$ placing instead of $n^n$,
where $K$ is the number of small files.
\subsubsection{Economic Power (EP)}\index{Economic Power}\index{EP|see{Economic Power}}
This algorithm also takes into consideration that two small files always fit onto a
disc---besides the fact that two large ones do not fit. Therefore, denoting the
number of large files by $N$ and that of the small ones by $K$ it needs at most
$N + (K + 1) / 2$ discs. So first we schedule the large discs to separate discs,
and then the small ones to each of the discs of the number mentioned above.
If, for instance, $N = K = n / 2$, then according to this we only have to produce $(0.75n)^{0.5n}$.
\subsection{Shortening of lists (SL)}\index{Shortening of lists}\index{SL|see{Shortening of lists}}
With certain conditions it holds that list $\textbf{t}$ can be split into lists
$\textbf{t}_1$ and $\textbf{t}_2$ so that $\textsc{OPT}(\textbf{t}_1) +
\textsc{OPT}(\textbf{t}_2) \leq \textsc{OPT}(\textbf{t})$ (in these cases the formula
holds with equality). Its advantage is that usually shorter lists can be packed
optimally in a shorter time than the original list.
For example, let us assume that $t_i + t_j = 1$. Let $\textbf{t}_1 = (t_i,t_j)$ and
$\textbf{t}_2 = \textbf{t} \setminus \textbf{t}_1$. In this case
$\textsc{OPT}(\mathbf{t}_1) = 1$ and $\textsc{OPT}(\mathbf{t}_2) = \textsc{OPT}(\mathbf{t}) - 1.$
To prove this, consider the two discs onto which the elements of list $\textbf{t}_1$ have been packed
by an optimal algorithm. Since next to them there can be files whose sum is at most $1 - t_1$
and $1 - t_2$, their executing time can sum up to at most $2 - (t_1 + t_2)$, i.e., 1.
Examining the lists on both ends at the same time we can sort out the pairs of files
the sum of whose running time is 1 in $O(n)$. After that we order the list \textbf{t}.
Let the ordered list be \textbf{s}. If, for example $s_1 + s_n < 1$,
then the first file will be packed onto a different disc by every placing,
so $\mathbf{t}_1 = (t_1,t_j)$ and $\mathbf{t}_2 = \mathbf{t} \setminus \mathbf{t}_1$
is a good choice. If for the ordered list $s_1 + s_n < 1$ and $s_1 + s_{n - 1} + s_n > 1$ hold,
then let $s_j$ be the largest element of the list that can be added to $s_1$ without exceeding one.
In this case with choices $\mathbf{t}_1 = (t_1,t_j)$ and $\mathbf{t}_2 = \mathbf{t} \setminus \mathbf{t}_1$
list $\mathbf{t_2}$ is two elements shorter than list \textbf{t}.
With the help of the last two operations lists can often be shortened
considerably (in favourable case they can be shortened to such an extent that
we can easily get the optimal number of processors for both lists).
Naturally, the list remained after shortening has to be processed---for example
with one of the previous algorithms.
\subsection{Upper and lower estimations (ULE)}\index{upper and lower estimations}\index{ULE|see{upper and lower estimations}}
Algorithms based on upper and lower estimations operate as follows.
Using one of the approaching algorithms they produce an upper estimation A$(\textbf{t})$ of
OPT(\textbf{t}), and then they give a lower estimation for the value of
OPT(\textbf{t} as well. For this---among others---the properties of packing are suitable,
according to which two large files cannot be placed onto the same disc,
and the sum of the size cannot be more than 1 on any of the discs.
Therefore, both the number of the large files and the sum of the size of the files,
and so also their maximum MAX(\textbf{t}) is suitable as a lower estimation. If
A(\textbf{t} = MAX(\textbf{t}), then algorithm A produced an optimal scheduling.
Otherwise it can be continued with one of the time-consuming optimum searching algorithms.
\subsection{Pairwise comparison of the algorithms}
If there are several algorithms known for a scheduling (or other) problem,
then a simple way of comparing the algorithms is to examine whether the values
of the parameters involved can be given so that the chosen output value is more
favourable in the case of one algorithm than in the case of the other one.
In the case of the above discussed placing algorithm the number of processors discs
allocated to size array \textbf{t} by algorithm A and B is denoted by A(\textbf{t}
and B(\textbf{t}, and we examine whether there are arrays \textbf{t}$_1$ and \textbf{t}$_2$
for which A(\textbf{t}$_1)$ < B(\textbf{t}$_1$) and A(\textbf{t}$_2$) > B(\textbf{t}$_2$) hold.
We answer this question in the case of the above defined ten approaching algorithms and for the optimal one.
It follows from the definition of the optimal algorithms that for each \textbf{t}
and each algorithm A holds OPT$(\textbf{t} \leq \textsc{A}(\textbf{t})$.
In the following the elements of the arrays in the examples will be twentieth.
Consider the following seven lists:
\\
$\mathbf{t_1} = (12/20, 6/20, 8/20, 14/20),$
$\mathbf{t_2} = (8/20, 6/20, 6/20, 8/20, 6/20, 6/20),$
$\mathbf{t_3} = (15/20, 8/20, 8/20, 3/20, 2/20, 2/20, 2/20)$,
$\mathbf{t_4} = (14/20, 8/20, 7/20, 3/20, 2/20, 2/20, 2/20, 2/20),$
$\mathbf{t_5} = (10/20, 8/20, 10/20, 6/20, 6/20),$
$\mathbf{t_6} = (12/20, 12/20, 8/20, 8/20),$
$\mathbf{t_7} = (8/20, 8/20, 12/20, 12/20).$ \\
The packing results of these lists are summarised in Figure \ref{fig:lemezszam}.
\begin{figure}[!t]
\small
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
& LF & NF & FF & BF & PF & NFD & FFD & BFD & PFD & QFD & OPT \\ \hline
$\mathbf{t}_1$ & 4 & 3 & 3 & 3 & 3 & 3 & 2 & 2 & 2 & 2 & 2 \\ \hline
$\mathbf{t}_2$ & 6 & 2 & 2 & 2 & 3 & 3 & 3 & 3 & 3 & 3 & 2 \\ \hline
$\mathbf{t}_3$ & 7 & 3 & 2 & 3 & 4 & 3 & 2 & 3 & 4 & 2 & 2 \\ \hline
$\mathbf{t}_4$ & 8 & 3 & 3 & 2 & 4 & 3 & 3 & 2 & 4 & 3 & 2 \\ \hline
$\mathbf{t}_5$ & 5 & 3 & 3 & 3 & 3 & 2 & 2 & 2 & 3 & 2 & 2 \\ \hline
$\mathbf{t}_6$ & 4 & 3 & 2 & 2 & 2 & 3 & 2 & 2 & 2 & 2 & 2 \\ \hline
$\mathbf{t}_7$ & 4 & 3 & 3 & 3 & 2 & 3 & 2 & 2 & 2 & 2 & 2 \\ \hline
\end{tabular}
\caption{Summary of the numbers of discs.\label{fig:lemezszam}}
\end{center}
\end{figure}
As shown in Figure \ref{fig:lemezszam}, LF needs four discs for the first list,
while the others need fewer than that. In addition, the row of list
\textbf{t}$_1$ shows that FFD, BFD, PFD, QFD and OPT need fewer discs than NF, FF, BF, PF and NFD.
Of course, there are no lists for which any of the algorithms would use fewer discs than OPT.
It is also obvious that there are no lists for which LF would use fewer discs
than any of the other ten algorithms.
These facts are shown in Figure \ref{fig:parok}. In the figure symbols X in the main diagonal
indicate that the algorithms are not compared to themselves. Dashes in the first column indicate
that for the algorithm belonging to the given row there is no list
which would be processed using more disc by this algorithm than by the algorithm
belonging to the given column, i.e., LF.
Dashes in the last column show that there is no list for which the optimal algorithm
would use more discs than any of the examined algorithms.
Finally, 1's indicate that for list \textbf{t}$_1$ the algorithm belonging
to the row of the given cell in the figure needs more discs than the algorithm
belonging to the column of the given cell.
\begin{figure}[!t]
\small
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|} \hline
& LF & NF & FF & BF & PF & NFD & FFD & BFD & PFD & QFD & OPT \\ \hline
LF & X & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline
NF & -- & X & & & & & 1 & 1 & 1 & 1 & 1 \\ \hline
FF & -- & & X & & & & 1 & 1 & 1 & 1 & 1 \\ \hline
BF & -- & & & X & & & 1 & 1 & 1 & 1 & 1 \\ \hline
PF & -- & & & & X & & 1 & 1 & 1 & 1 & 1 \\ \hline
NFD & -- & & & & & X & 1 & 1 & 1 & 1 & 1 \\ \hline
FFD & -- & & & & & & X & & & & \\ \hline
BFD & -- & & & & & & & X & & & \\ \hline
PFD & -- & & & & & & & & X & & \\ \hline
QFD & -- & & & & & & & & & X & \\ \hline
OPT & -- & -- & -- & -- & -- & -- & -- &-- & -- & -- & X \\ \hline
\end{tabular}
\caption{Pairwise comparison of algorithms.\label{fig:parok}}
\end{center}
\end{figure}
If we keep analysing the numbers of discs in Figure \ref{fig:parok},
we can make up this figure to Figure \ref{fig:tobbpar}.
\begin{figure}[!t]
\small
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|} \hline
& LF & NF & FF & BF & PF & NFD & FFD & BFD & PFD & QFD & OPT \\ \hline
LF & X & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline
NF & -- & X & 3 & 4 & 7 & 5 & 1 & 1 & 1 & 1 & 1 \\ \hline
FF & -- & -- & X & 4 & 7 & 5 & 1 & 1 & 1 & 1 & 1 \\ \hline
BF & -- & -- & 3 & X & 8 & 5 & 1 & 1 & 1 & 1 & 1 \\ \hline
PF & -- & 2 & 2 & 2 & X & 3 & 1 & 1 & 1 & 1 & 1 \\ \hline
NFD & -- & 2 & 2 & 2 & 6 & X & 1 & 1 & 1 & 1 & 1 \\ \hline
FFD & -- & 2 & 2 & 2 & & -- & X & 4 & & -- & 2\\ \hline
BFD & -- & 2 & 2 & 2 & & -- & 3 & X & & 3 & 2\\ \hline
PFD & -- & 2 & 2 & 2 & 3 & 3 & 3 & 3 & X & 3 & 2 \\ \hline
QFD & -- & 2 & 2 & 2 & & -- & -- & 4 & & X & 2\\ \hline
OPT & -- & -- & -- & -- &-- & -- & -- & -- & -- & -- & X \\ \hline
\end{tabular}
\caption{Results of the pairwise comparison of algorithms.\label{fig:tobbpar}}
\end{center}
\end{figure}
Since the first row and the first column of the table is filled, we do not deal more with
algorithm LF.
For list \textbf{t}$_2$ NF, FF, BF and OPT use two discs, while the other 6 algorithms use three ones.
Therefore we write 2's in the points of intersection of the columns of the 'winners'
and the rows of the 'losers' (but we do not rewrite the 1's given in the points of intersection
of PF and OPT, and NFD and OPT, so we write 2's in $4 \times 6 - 2 = 22$ cells.
Since both the row and the column of OPT have been filled in, it is not dealt with any more in this section.
The third list is disadvantageous for PF and PFD, therefore we write 3's in the empty
cells in their rows. This list shows an example also for the fact that NF can be worse
than FF, BF can be worse than FF, and BFD than FFD and QFD.
The fourth list can be processed only by BF and BFD optimally, i.e., using two discs.
Therefore we can write 4's in the empty cells in the columns of these two algorithms.
For the fifth list NFD, FFD, BFD and QFD use only two, while NF, FF, BF, PF and PDF
use three discs. So we can fill the suitable cells with 5's.
The 'losers' of list \textbf{t}$_6$ are NF and NFD---therefore, we write 6's in the empty cells in their rows.
PF performs better when processing list \textbf{t}$_7$ than FF.
The following theorem helps us filling in the rest of the cells.
\begin{tetel} If $\mathbf{t} \in D$, then
$$\textsc{FF}(\mathbf{t}) \leq \textsc{NF}(\mathbf{t}) \koz . $$
\end{tetel}
\begin{biz} We perform an induction according to the length of the list.
Let \textbf{t} = $\langle t_1, t_2, \ldots, t_n \rangle$ and
\textbf{t}$_i = \langle t_1, t_2, \ldots, t_i \rangle \ (i = 1, 2, \ldots, n)$.
Let NF$(\mathbf{t}_i) =$ N$_i$ and FF$(\mathbf{t}_i) =$ F$_i$,
and let $n_i$ be the level of the last disc according to NF, which means the sum
of the lengths of the files placed onto the non empty disc with the higher index,
when NF has just processed $\mathbf{t}_i$. Similarly, let $f_i$ be the level
of the last disc according to FF. We are going to prove the following invariant
property for each $i$: either $F_i < N_i$, or $F_i = N_i$ and $f_i \leq n_i$.
If $i = 1$, then $F_1 = N_1$ and $f_1 = n_1 = t_1$, i.e., the second part
of the invariant property holds. Suppose that the property holds for the value
$1 \leq i < n$. If the first part of the invariant property holds before
packing $t_{i + 1}$, then either inequality $F_i < N_i$ stays true,
or the numbers of discs are equal, and $f_i < n_i$ holds.
If the numbers of discs were equal before packing of $t_{i + 1}$, then after placing it
either the number of discs of FF is smaller, or the numbers of discs are equal
and the level of the last disc of FF is at most as big as that of NF.
\end{biz}
A similar statement can be proved for the pairs of algorithms NF-BF, NFD-FFD and NFD-BFD.
Using an induction we could prove that FFD and QFD need the same number of discs for every list.
The previous statements are summarised in Figure 11.20.
\subsection{The error of approximate algorithms}
The relative efficiency of two algorithms (A and B) is often described by the ratio
of the values of the chosen efficiency measures, this time the relative number of
processors $\textsc{A}(\mathbf{t})/\textsc{B}(\mathbf{t})$. Several different
characteristics can be defined using this ratio. These can be divided into two groups:
in the first group there are the quantities describing the worst case,
while in the other group there are those describing the usual case.
Only the worst case is going to be discussed here (the discussion of the usual case
is generally much more difficult).
Let $D_n$ denote the real list of $n$ elements and $D$ the set of all the real lists, i.e.,
$$ D = \displaystyle{\cup}_{i=1}^{\infty} D_i \koz . $$
Let $\mathcal{A}_{\var{nd}}$ be the set of algorithms, determining the number of discs, that is
of algorithms, connecting a nonnegative real number to each list $\mathbf{t} \in D$,
so implementing the mapping $D \rightarrow \R^+_0$).
Let $\mathcal{A}_{\var{opt}}$ be the set of the optimal algorithms, that is of
algorithms ordering the optimal number
of discs to each list, and OPT an element of this set (i.e., an algorithm
that gives the number of discs sufficient and necessary to place the files
belonging to the list for each list $\mathbf{t} \in D$).
Let $\mathcal{A}_{\var{app}}$ be the set of the approximation algorithms, that is of
algorithms $\textsc{A} \in \mathcal{A}_{\var{nd}}$
for which $\textsc{A}(\mathbf{t}) \geq \textsc{OPT}(\mathbf{t})$ for each list $\mathbf{t} \in D$,
and there is a list $\mathbf{t} \in D$, for which $\textsc{A}(\mathbf{t})
> \textsc{OPT}(\mathbf{t}).$.
Let $A_{est}$ be the set of estimation algorithms, that is of
algorithms $\textsc{E} \in \mathcal{A}_{\var{lsz}}$
for which $\textsc{E}(\mathbf{t}) \leq \textsc{OPT}(\mathbf{t})$ for each list $\mathbf{t} \in D$,
and there is a list $\mathbf{t} \in D$, for which $\textsc{E}(\mathbf{t}) < \textsc{OPT}(\mathbf{t}).$.
Let $F_n$ denote the set of real lists for which $\textsc{OPT}(\mathbf{t}) = n,$,
i.e., $F_n = \{\mathbf{t} | \mathbf{t} \in D$ and $\textsc{OPT}(\mathbf{t}) = n \} \ (n = 1, 2, \ldots ).$.
In the following we discuss only algorithms contained in $\mathcal{A}_{nd}$.
We define $(\textrm{A, \ B} \in \mathcal{A}) \ R_{\textsc{A,B,}n}$ error function,
$R_{\textsc{A,B}}$ error (absolute error) and $R_{A,\infty}$ asymptotic error of algorithms A and B
$(\textrm{A, \ B} \in \mathcal{A})$ as follows:
$$R_{\textrm{A,B,}n} = \sup _{t \in F_n} \frac{\textsc{A}(\mathbf{t})}{\textsc{B}(\mathbf{t})} \koz ,$$
$$R_{\textrm{A,B}} = \sup _{t \in D} \frac{\textsc{A}(\mathbf{t})}{\textsc{B}(\mathbf{t})} \koz ,$$
$$R_{\textrm{A,B,}\infty} = \limsup _{n \rightarrow \infty} R_{A,B,n} \koz .$$
These quantities are interesting especially if $\textsc{B} \in \mathcal{A}_\var{opt}$.
In this case, to be as simple as possible, we omit B from the denotations,
and speak about the error function, error and asymptotic error of algorithms $\textsc{A} \in \mathcal{A},$
and $\textsc{E} \in \mathcal{A}$.
The characteristic values of NF file placing algorithm are known.
\begin{tetel} If $\mathbf{t} \in F_n$, then\label{th:NF}
\begin{equation}
n = \textsc{OPT}(\mathbf{t}) \leq \textsc{NF}(\mathbf{t}) \leq
2\textsc{OPT}(\mathbf{t})-1=2n-1 \koz .\label{eq:NFkorlatok}
\end{equation}
Furthermore, if $k \in \Z,$, then there are lists $\textbf{u}_k$ and $\textbf{v}_k$ for which
\begin{equation}
k = \textsc{OPT}(\mathbf{u}_k) = \textsc{NF}(\mathbf{u}_k)
\end{equation}
and
\begin{equation}
k = \textsc{OPT}(\mathbf{v}_k) \ \var{and} \ \textsc{NF}(\mathbf{v}_k) = 2k - 1 \koz .
\end{equation}
\end{tetel}
From this statement follows the error function, absolute error and asymptotic error of NF placing algorithm.
\begin{kov}If $n \in \Z,$ then
\begin{equation}
R_{\textsc{NF},n} = 2 - \frac{1}{n} \koz ,
\end{equation}
and
\begin{equation}
R_{\textsc{NF}} = R_{\textsc{NF},\infty} = 2 \koz .
\end{equation}
\end{kov}
The following statement refers to the worst case of the FF and BF file packing algorithms.
\begin{tetel} If $\mathbf{t} \in F_n$, then
\begin{equation}
\textsc{OPT}(\mathbf{t}) \leq \textsc{FF}(\mathbf{t}), \ \textsc{BF}(\mathbf{t}) \leq 1.7\textsc{OPT}(\mathbf{t}) + 2 \koz .\label{eq:FFkorlatok}
\end{equation}
Furthermore, if $k \in \Z,$, then there are lists $u_k$ and $v_k$ for which
\begin{equation}
k = \textsc{OPT}(\mathbf{u}_k) = \textsc{FF}(\mathbf{u}_k) = \textsc{BF}(\mathbf{u}_k)
\end{equation}
and
\begin{equation}
k = \textsc{OPT}(\mathbf{v}_k) \ \var{and} \ \textsc{FF}(\mathbf{v}_k) =
\textsc{BF}(\mathbf{v}_k) = \lfloor 1.7k \rfloor \koz .
\end{equation}
\end{tetel}
For the algorithm FF holds the following stronger upper bound too.
\begin{tetel} If $\mathbf{t} \in F_n,$ then\label{th:FF1}
\begin{equation}
\textsc{OPT}(\mathbf{t}) \leq \textsc{FF}(\mathbf{t}) < 1.7\textsc{OPT}(\mathbf{t}) + 1 \koz .\label{eq:FFkorlatok}
\end{equation}
\end{tetel}
From this statement follows the asymptotic error of FF and BF, and the good estimation of their error function.
\begin{kov} If $n \in \Z,$ then
\begin{equation}
\frac{\lfloor 1.7n \rfloor}{n} \leq R_{\textsc{FF},n} \leq \frac{\lceil 1.7n \rceil}{n}
\label{memeq:FFegyhet}
\end{equation}
and
\begin{equation}
\frac{\lfloor 1.7n \rfloor}{n} \leq R_{\textsc{BF},n} \leq \frac{\lfloor 1.7n + 2 \rfloor}{n}
\label{memeq:BFegyhet}
\end{equation}
further
\begin{equation}
R_{\textsc{FF},\infty} = R_{\textsc{BF},\infty} = 1.7 \koz .
\end{equation}
\end{kov}
If n is divisible by 10, then the upper and lower limits in inequality (\ref{memeq:FFegyhet})
are equal, thus in this case 1.7 = R$_{\textsc{FF},n} = R_{\textsc{BF},n}$.
\begin{gyak}
\ujgyak Prove that the absolute error of the FF and BF algorithms is at least 1.7 by an example.
\ujgyak
Implement the basic idea of the FF and BF algorithms so that the running time would be $O(n \lg n)$.
\ujgyak
Complete Figure 11.20.
\end{gyak}
\begin{fld}
\ujfld{Smooth process selection for an empty partition}{
Modify the \textsc{Long-Waiting-or-Not-Fit-Smaller} algorithm in a way that instead of giving
priority to processes with \var{points} above the \var{threshold},
selects the process with the highest $\var{rank}+\var{points}$
among the processes fitting into the partition. Prove the correctness of the algorithm
and give an upper bound for the waiting time of a process.}
\ujfld{Partition search algorithms with restricted scope}{
Modify the \textsc{Best-Fit}, \textsc{Limited-Best-Fit}, \textsc{Worst-Fit},
\textsc{Limited-Worst-Fit} algorithms to only search for their optimal partitions among
the next \var{m} suitable one following the last split partition, where \var{m}
is a fixed positive number. Which algorithms do we get in the $\var{m}=1$
and $\var{m}=\infty$ cases. Simulate both the original and the new algorithms,
and compare their performance regarding execution time, average number
of waiting processes and memory fragmentation.}
\ujfld{Avoiding page replacement anomaly}{
Class the discussed page replacement algorithms based on whether they ensure
to avoid the anomaly or not.}
\ujfld{Optimal page replacement algorithm}{
Prove that for each demanding page replacement algorithm $A$, memory size $m$ and
reference string $R$ holds
$$f_A(m,R) \leq f_{\textsc{OPT}}(m,R) \koz .$$}
\ujfld{Anomaly}{
Plan (and implement) an algorithm with which it can occur that a given
problem takes longer to solve on $q > p$ processors than on $p > 1$ ones.}
\ujfld{Error of file placing algorithms}{
Give upper and lower limits for the error of the BF, BFD, FF and FFD algorithms.
}
\end{fld}
\begin{fejmegj}
The basic algorithms for dynamic and fixed partitioning and page replacement are discussed
according to textbooks by Silberschatz,
Galvin and Gagne\nevindex{Gagne, Greg} \cite{SGG00},
\nevindex{Silberschatz, Avi}\nevindex{Galvin, Peter Baer} and
Tanenbaum\nevindex{Tanenbaum, Andrew S.} and Woodhull\nevindex{Woodhull, Albert S.} \cite{TaW97}.
Defining page replacement algorithms by a Mealy-automat is based
on the summarising article by Denning\nevindex{Denning, Peter J.} \cite{Denning}, and textbooks by
Ferenc Gécseg\nevindex{Gécseg, Ferenc} and István Peák\nevindex{Peák, István (1938--1989)}
\cite{GecsegPeak}, Hopcroft,\nevindex{Hopcroft, John E.} Motwani\nevindex{Motwani, Rajeev}
and Ullman\nevindex{Ullman, Jeffrey David} \cite{HopcroftMoUl01}.
Optimizing the MIN algorithm was proved by Mihnovskiy and Shor in 1965 \cite{MihSho65},
after that by Mattson, Gecsei, Slutz and Traiger in 1970 \cite{Mattson70}.
\nevindex{Mattson, R. L.}\nevindex{Gecsei, Jan}\nevindex{Slutz, D. R.}\nevindex{Traiger, I. L.}
\nevindex{Mihnovskiy, S. D.}\nevindex{Shor, N. Z.}
The anomaly experienced in practice when using FIFO page replacement algorithm
was first described by László Bélády\nevindex{Bélády, László A.} \cite{Belady69} in 1966,
after that he proved in a constructive way that the degree of the anomaly
can approach two arbitrarily closely in his study
he wrote together with Shedler.\nevindex{Shedler, G. S.} The conjecture that it cannot actually reach
two can be found in the same article (written in 1969).
Péter Formai\nevindex{Fornai, Péter} and Antal Iványi\nevindex{Iványi, Antal Miklós} \cite{FornaiIv02} showed that
the ratio of the numbers of page replacements needed on a big and on a smaller computer
can be arbitrarily large in 2002.
Examples for scheduling anomalies can be found in the books
by Coffman\nevindex{Coffman, Ed G., Jr.} \cite{Coffman76}, Iványi and
Smelyanskiy \cite{IvanyiSz85} and Roosta \cite{Roosta2100},
and in the article by Lai and Sahni \cite{LaS1984}.
\nevindex{Iványi, Antal Miklós}\nevindex{Szmeljánszkij,
Ruszlán}\nevindex{Roosta, Sayed H.}\nevindex{Fornai, Péter}\nevindex{Coffman,
Ed G., Jr.}\nevindex{Sahni, Sartaj}\nevindex{Lai, Ten Hwang}
Analysis of the interleaved memory derives from the article \cite{IvanyiGiants}.
The bound $\textsc{NF}(\textbf{t}) \leq 2\textsc{OPT}(\textbf{t}) + 2$
can be found in D. S. Johnson's PhD dissertation \cite{JohnsonPhD}, the precise
Theorem \ref{th:NF}. comes from \cite{Ivanyi84}.\nevindex{Iványi, Antal Miklós}
The upper limit for FF and BF is a result by Johnson, Demers,
Ullman, Garey and Graham \cite{JohnsonDU}, while the proof of the accuracy of the limit is
that by \cite{Ivanyi84,IvanyiBin}. The source of the upper limit for FFD and BFD is \cite{JohnsonDU},
and that of the limit for NFD is \cite{Baker}. The proof of the NP-completeness
of the file packing problem---leading it back to the problem of partial sum---can be found
in the chapter on approximation algorithms in
\textit{Introduction to Algorithms} \cite{CormenLe2009}.\nevindex{Cormen, Thomas
H.}\nevindex{Leiserson, Charles E.}\nevindex{Rivest, Ronald Lewis}
\end{fejmegj}\index{memory management|)}