text:
\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}

\usepackage[english]{babel}
\usepackage[dvinames]{xcolor}
\usepackage[compact,small]{titlesec}
\usepackage{booktabs}
\usepackage{multirow}
\usepackage{amsfonts,amsmath,amssymb}
\usepackage{marginnote}
\usepackage[top=1.8cm, bottom=1.8cm, outer=1.8cm, inner=1.8cm, heightrounded, marginparwidth=2.5cm, marginparsep=0.5cm]{geometry}
\usepackage{enumitem}
\setlist{noitemsep,parsep=2pt}
\newcommand{\highlight}[1]{\textcolor{kuleuven}{#1}}
%\usepackage{pythonhighlight}
\usepackage{cleveref}
\usepackage{graphicx}
%\usepackage{subfigure}
\usepackage{float}
\usepackage{caption}
\usepackage{subcaption}

\newcommand{\nextyear}{\advance\year by 1 \the\year\advance\year by -1}
\newcommand{\thisyear}{\the\year}
\newcommand{\deadlineGroup}{November 27, \thisyear{} at 16:00 CET}
\newcommand{\deadlineCode}{December 18, \thisyear{} at 16:00 CET}
\newcommand{\deadlineReport}{January 4, \nextyear{} at 16:00 CET}

\newcommand{\ReplaceMe}[1]{{\color{blue}#1}}
\newcommand{\RemoveMe}[1]{{\color{purple}#1}}

\setlength{\parskip}{5pt}

%opening
\title{Evolutionary Algorithms: Final report}
\author{Georgios Kouros (r0816917)}

\begin{document}
\fontfamily{ppl}
\selectfont{}

\maketitle

\section{Metadata}

\begin{itemize}
 \item \textbf{Group members during group phase:} Kostantinos Gkentsidis and Jeffrey Quicken
 \item \textbf{Time spent on group phase:} 15 hours
 \item \textbf{Time spent on final code:} 45 hours
 \item \textbf{Time spent on final report:} 12 hours
\end{itemize}

\section{Modifications since the group phase}

%\RemoveMe{\textbf{Goal:} Based on this section, we will evaluate insofar as you are able to analyse common problems arising in the design and implementation of evolutionary algorithms and your ability to effectively solve them.}

\subsection{Main improvements}

%\ReplaceMe{List the main changes that you implemented since the group phase. You do not need to explain the employed techniques in detail; for this, you should refer to the appropriate subsection of section 3 of the report.}

%\paragraph{} \ReplaceMe{Short description 1: State what modification you made (e.g., replaced top-$\lambda$ selection with $k$-tournament selection). What aspect of your evolutionary algorithm did it improve?}

\paragraph{Greedy Heuristic Initialization}: Added a heuristic initialization of candidate solutions in order to inject some good initial candidates to the random initial population and speed up the search of the optimum. For more information see Subsection \ref{ss:initialization}.

\paragraph{Local Search:} Converted the evolutionary algorithm to a memetic algorithm through the inclusion of 2-opt local search after the variation step of each iteration. This addition significantly improved convergence to really good candidate solutions. For more information see Subsection \ref{ss:local_search}.

%\paragraph{Mutation Self-Adaptivity:} Self-adaptivity was added to vary mutation rate and strength in order to improve the diversity of the population across iterations and prevent premature convergence.

\paragraph{Diversity Promotion}: Fitness sharing was added to the $(\lambda+\mu)$~elimination step to improve the diversity of the population across iterations and prevent premature convergence. For more information see Subsections \ref{ss:elimination} and \ref{ss:diversity_promotion} .

\paragraph{Greedy Mutation:} Added a new mutation operator that uses a greedy approach to adapt an individual in the optimal way. For more information see Subsection \ref{ss:mut}

\subsection{Issues resolved}
%\ReplaceMe{Recall the list of issues from the group phase. Describe how you solved these issues in the individual phase.}

%\paragraph{}\ReplaceMe{Short description 1: Describe the observation or problem from the group phase. Explain what caused this issue. How did you solve it (you can refer to the list of improvements)? Did fixing it significantly benefit your evolutionary algorithm? If you did not fix it: why not?}

\paragraph{Depleting Diversity:} In the group phase, we detected a problem with diversity, meaning that our algorithm converged prematurely to locally optimal candidate solutions, thus preventing the discovery of better solutions. This issue was fixed through the addition of diversity promotion, increased mutation strength, and varying mutation operators.

\paragraph{Premature convergence:} In the group phase, we used the $(\lambda+\mu)-elimination$ in combination with a convergence criterion of matching mean to best fitness. This resulted in a mostly exploitative behavior resulting in premature convergence. This issue was fixed by implementing methods for diversity promotion.

\paragraph{Loss of Best Candidate:} In the individual phase it was discovered that sometimes the best candidate was lost across iterations. This was easily visible as unexplained spikes in the corresponding graph across iterations. This happened due to an unwanted modification of the original population during mutation. Fixing this bug cleared this error.

\paragraph{Inefficient Crossover Operator:} The code used for the Order Crossover operator was taken from stackoverflow. In an effort to refine this code and remove needless code repetition, the operator was rewritten from scratch and ended up being more efficient, shorter and more readable.

\section{Final design of the evolutionary algorithm}

%\RemoveMe{\textbf{Goal:} Based on this section, we will evaluate insofar as you are able to design and implement an advanced, effective evolutionary algorithm for solving a model problem.}

%\ReplaceMe{In this section, you should describe all components of your final evolutionary algorithm and how they fit together.}

\subsection{Representation} \label{ss:representation}

%\ReplaceMe{How do you represent the candidate solutions? What is your motivation to choose this one? What other options did you consider? How did you implement this specifically in Python (e.g., a list, set, numpy array, etc)?}

In Davis et al ~\cite{davis}, five different representations are presented for TSP: Binary, Path, Adjacency, Ordinal, and Matrix representations. Based on a review of the different methods in the same research, it was decided in the group phase to select the \textbf{Path} / \textbf{Permutation Representation}, because of its better performance, operator variety, and explainability. The same representation was kept in the individual phase. This  Path representation was implemented as a python class called Individual that stores a list of integers representing indices of cities with respect to the given distance matrix. The route of the candidate solution is checked against errors on update and hence the use of python sets was deemed redundant.

\subsection{Initialization} \label{ss:initialization}

%\ReplaceMe{How do you initialize the population? How did you determine the number of individuals? Did you implement advanced initialization mechanisms (local search operators, heuristic solutions)? If so, describe them. Do you believe your approach maintains sufficient diversity? How do you ensure that your population enrichment scheme does not immediately take over the population? Did you implement other initialization schemes that did not make it to the final version? Why did you discard them? How did you determine the population size?}

In the group phase, a random initialization was used for the population resulting in high diversity with a high probability given a big enough population size $\lambda$. In order to achieve good results, it was decided to use a quite large population (1000-2000).

In the individual phase, the initialization step was augmented with a number of greedy heuristic candidate solutions in order to provide some direction to the search and avoid reinventing the wheel. The greedy heuristic search starts from a random city keeps following the shortest path from city to city until all cities are visited exactly once and finally ends up on the first city.

The use of really good candidate solutions entails the danger of taking over the population fairly quickly. However, this issue can be mitigated by limiting the number of heuristic candidate solutions or limiting the steps of the greedy search. Both methods were implemented and based on experiments it was decided to apply greedy search for $10\%$ of the initial population

Furthermore, the addition local search and diversity promotion, allowed the use of a population and offspring size that's two magnitudes smaller ($\lambda = 10, \mu=5$). Using a lower population and offspring size resulted in better performance with more iterations and no impact on the final results.

\subsection{Selection operators} \label{ss:selection}

%\ReplaceMe{Which selection operators did you implement? If they are not from the slides, describe them. Can you motivate why you chose this one? Are there parameters that need to be chosen? Did you use an advanced scheme to vary these parameters throughout the iterations? Did you try other selection operators not included in the final version? Why did you discard them?}
Similarly to the group phase, \textit{k-tournament selection} was picked for the individual phase as well. This selection method performed really well before and offered a nice balance between exploration and exploitation, hence it was kept in this phase as well. The only tunable parameter of this selection operator is the number $k$ of individuals that take part in a tournament.

\subsection{Mutation operators} \label{ss:mut}

%\ReplaceMe{Which mutation operators did you implement? If they are not from the slides, describe them. How do you choose among several mutation operators? Do you believe it will introduce sufficient randomness? Can that be controlled with parameters? Do you use self-adaptivity? Do you use any other advanced parameter control mechanisms (e.g., variable across iterations)? Did you try other mutation operators not included in the final version? Why did you discard them?}

In the group phase, two mutation methods were used, namely inversion mutation and swap mutation. Both mutation operators, were extended in the individual phase with a new parameter called mutation strength $\sigma_\mu$, which determines the number of successive applications of the operator on an individual.

Besides, those two mutation operators, a new greedy mutation operator was implemented in the individual phase. This operator removes four edges from a route randomly, resulting in five unconnected segments, which are greedily reconnected by finding the segment permutation with the best fitness.

Initially each mutation operator was assigned equal probability $33.333\%$ to be chosen. However, in a trial of adaptive parameter control with a reward system, it was discovered that the greedy mutation operator improved solutions more consistently and took over the operator selection, so in the end it was decided to use only the greedy mutation operator.

\subsection{Recombination operators} \label{ss:recombination}

%\ReplaceMe{Which recombination operators did you implement? If they are not from the slides, describe them. How do you choose among several recombination operators? Why did you choose these ones specifically? Explain how you believe that these operators can produce offspring that combine the best features from their parents. How does your operator behave if there is little overlap between the parents? Can your recombination be controlled with parameters; what behavior do they change? Do you use self-adaptivity? Do you use any other advanced parameter control mechanisms (e.g., variable across iterations)? Did you try other recombination operators not included in the final version? Why did you discard them? Did you consider recombination with arity strictly greater than 2?}

In the individual phase, it was decided to reuse the \textit{Order Crossover} \cite{davis} operator, since it performs really well for order-based permutation problems like TSP according to the literature eg. \cite{memetic} and based on experiments. The only change regarding this operator was the rewritting of its code to make it more efficient and readable.

The operator consists of the following steps:
\begin{enumerate}
\item Copy a segment between two randomly generated crossover points of the first parent to the first child.
\item Starting from the second crossover point on the second parent this time, start copying its genes/alleles that are not already contained on the child, until the child is full.
\item Create the second child like the first but with the reverse order of the parents.
\end{enumerate}

One advantage of this operator is that it ensures the generation of only valid offspring and thus doesn't require the need to implement a repair mechanism. Moreover, the fact that the operator preserves the order of the cities from the parents is especially beneficial to Asymetric TSP problems, since it preserves good edges more effectively.

The operator, in general, preserves a segment of the first parent on the child and then tries to fill the rest with the city order of the second parent, thus preserving useful information from both parents. At the same time, because of the combination of two random parents that may or may not have much overlap, the resulting children can be similar to the parents and explore new space, while always producing valid candidate solutions.

Two enhancements ideas were considered regarding recombination operators. First was the possibility to add more recombination operators that vary significantly to Order Crossover and then self-adaptively select the best performing one per individual. This would provide some extra variation in the solutions, while at the same time, one operator might perform better in the beginning and another at the end close to convergence. Secondly, it seemed beneficial to implement the Distance Preserving Crossover (DPX) operator \cite{dpx} which removes the edges that do not exist in both parents and then greedily reconnects the resulting segments.

\subsection{Elimination operators} \label{ss:elimination}

%\ReplaceMe{Which elimination operators did you implement? If they are not from the slides, describe them. Why did you select this one? Are there parameters that need to be chosen? Did you use an advanced scheme to vary these parameters throughout the iterations? Did you try other elimination operators not included in the final version? Why did you discard them?}

In the group phase, there was no choice but to use the $(\lambda+\mu)-elimination$ operator, which did not achieve a good balance between exploration and exploitation. This method chooses the top-$\lambda$ candidates and eliminates worse candidate solutions that could result in better results after a few generations. Instead it even promotes similar candidates that have high fitness, which often causes premature convergence.

In the individual phase, two more elimination operators were implemented, namely, \textit{fitness-sharing-based elimination} and \textit{replace-worst elimination}. Both aimed at preserving diversity.

Fitness-sharing-based elimination is basically implemented as $(\lambda+\mu)-elimination$ with a recalculated fitness of each individual based on the number of its neighbouring individuals. The idea behind fitness sharing, according to \cite{eiben}, is to prevent very similar candidate solutions from overtaking the population by increasing their cost during selection or elimination based on their number of closely resembling neighbours. The distance metric that was used to determine the similarity of two individuals is the number of uncommon edges.

Replace-worst elimination results in a more diverse population than the simple $(\lambda+\mu)-elimination$ by keeping the $\lambda-\mu$ best individuals from the original population and replacing the rest with new offspring. This requires that $\lambda > \mu$.

Out of all three, the fitness-sharing-based elimination achieved the best and most consistent results and was the most successful at preventing premature convergence.

\subsection{Local search operators} \label{ss:local_search}

%\ReplaceMe{What local search operators did you implement? Describe them. Did they cause a significant improvement in the performance of your algorithm? Why (not)? Did you consider other local search operators that did not make the cut? Why did you discard them? Are there parameters that need to be determined in your operator? Do you use an advanced scheme to determine them (e.g., adaptive or self-adaptive)?}
The absence of a local search operator in the group phase meant that the implemented evolutionary algorithm required a considerable amount of iterations and a really large population in order to find a good solution. As a result, it was deemed imperative to implement a local search operator for the individual phase. After a thorough literature review of the available methods, it was decided to proceed with k-opt local search, proposed by Croes et al \cite{k-opt}.

The local search operator was implemented for $k=2$ and $k=3$. However, the 3-opt operator proved quite inefficient especially for the larger problems and thus was abandoned in favor of 2-opt, despite it being more suitable for the asymmetric TSP. A basic 2-opt local search algorithm will try all possible swap combinations that will result in an improvement of the fitness of an individual.

Although, 2-opt increases the computational complexity of the algorithm, at the same time, it results in quicker discovery of really good solutions. For really large problems, like $tour929$, however, the operator proved extremely slow. This problem was alleviated by modifying the operator to run using \emph{numba}, which decreased the running time of the operator by two orders of magnitute (10 seconds to less than 0.1 seconds).

\subsection{Diversity promotion mechanisms} \label{ss:diversity_promotion}

%\ReplaceMe{Did you implement a diversity promotion scheme? If yes, which one? If no, why not? Describe the mechanism you implemented. In what sense does the mechanism improve the performance of your evolutionary algorithm? Are there parameters that need to be determined? Did you use an advanced scheme to determine them?}

In the individual phase, two diversity promotion mechanisms were implemented. The first one involves a varying mutation rate and strength, but it didn't manage to preserve diversity very well and was thus abandoned. The second one is fitness sharing, it is implemented in the elimination step and it's described in more detail in Subsection \ref{ss:elimination}.

The fitness sharing mechanism has two tunable parameters, the shape $\alpha$ and distance $\sigma$ that determine its sensitivity. A larger $\alpha$ value results in a higher penalty for each neighbour and $\sigma$ represents the distance between two individuals for them to be considered neighbours.

\subsection{Stopping criterion} \label{ss:stopping_criterion}

%\ReplaceMe{Which stopping criterion did you implement? Did you combine several criteria?}

In the individual phase, two convergence criteria were combined. The first one was the same that was used in the group phase. This criterion stops the algorithm when the mean fitness converges to the best fitness of the population. However, because of the diversity promotion mechanisms that was implemented, this criterion never activates. As a result a second criterion was added that simply checks if there was no improvement of the best fitness in the last $100$ iterations.

\subsection{The main loop} \label{ss:main_loop}

%\ReplaceMe{Describe the main loop of your evolutionary algorithm using a clear picture (preferred) or high-level pseudocode. In what order do you apply the various operators? Why that order? If you are using several selection, mutation, recombination, elimination, and local search operators, describe how you choose among the possibilities. Are you selecting/eliminating all individuals in parallel, or one by one? With or without replacement?}

The order of the operators that are applied to the population in each generation can be seen on Figure \ref{fig:main_loop}. It follows the classic order of evolutionary algorithms, starting with selection to produce offspring, then recombination, mutation, and finally elimination. In addition, local search is applied after mutation for each of the generated offspring with a $p_l$ probability in each generation.

\begin{figure}[H]
\centering
\includegraphics[width=0.5\textwidth]{images/genetic_algorthm_main_loop.png}
\caption{A high level flowchart of the developed evolutionary algorithm.}
\label{fig:main_loop}
\end{figure}

Selection is done with replacement, so that there is increased probability to pick really good individuals multiple times to recombine with other individuals. We basically desire good genes to be reused in the next generation.

A $(\lambda+\mu)-elimination$ operator selects the new population by combining the old population with the new offspring, sorting the combined population and keeping the $top-\lambda$ individuals. Because of the fitness sharing scheme that is used, the elimination method selects individuals sequentially and not in parallel, with replacement. After each selection the combined population plus offspring are reweighted, so as to avoid several similar solutions from surviving to the next generation.

\subsection{Parameter selection}\label{ss:parameter_selection}

%\ReplaceMe{For all of the parameters that are not automatically determined by adaptivity or self-adaptivity (as you have described above), describe how you determined them. Did you perform a hyperparameter search? How did you do this? How did you determine these parameters would be valid both for small and large problem instances?}

Because of the addition of local search and fitness sharing, the algorithm grew more computationally expensive. As a result the population size and the offspring size were significantly reduced by two orders of magnitude to allow the algorithm to run for more generations before time runs out. In particular, $\lambda$ was reduced from $2000$ to $10$ and $\mu$ was reduced from around $2000/3$ to $10$. These parameters were tuned to achieve good performance in all problems, big and small. Figure \ref{fig:lambda_search} presents the performance of the algorithm on $tour194$ for $\lambda$ values between $10$ and $100$ and $\mu$ values defined as $\mu = \lambda$. The reduction of the population $\lambda$ and offspring size $\mu$ means that the algorithm can produce more generation before time runs out.

For mutation, the idea of mass mutation from Eiben et al \cite{eiben} was applied. This mass mutation approach refers mostly to memetic algorithms, which find really good locally optimal solutions using local search operators. The goal of mass mutation is to apply mutation with a really high rate so that the algorithm can find solutions that escape from local minima. This approach is implemented with a mutation probability $p_m = 0.9$. Figure \ref{fig:pm_search} presents the best fitness for various mutation rates from 0.1 to 1.0 on $tour194$.

The number $k$ of participants in the tournament selection was chosen via hyperparameters search. The results are shown in Figure \ref{fig:k_search}, where a $k=4$ was chosen due to its nice balance between performance and computational load.

The fitness sharing parameters $\alpha$ and $\sigma$ were selected as 1 and $num\_cities / 5$ ($38$ for $tour194$) respectively, balancing performance and diversity. The shape parameter $\alpha$ is average with regard to punishment of similar candidates, while the distance $\sigma$ is selected with respect to the size of the problem. It wouldn't be prudent to select the same distance threshold for all problem sizes, since a threshold of $\sigma=5$ might be suitable for the smallest $tour29$ problem, but it would result in a very homogeneous population for the largest problem $tour929$. Figure \ref{fig:sigma_search} presents the best fitness for various $\sigma$ values in range of one tenth of the number of cities $N$ to $N$ on $tour194$.

All of the aforementioned parameters were tested with regard to whether they allowed the algorithm to run for enough generations on each problem and whether they produced good enough solutions. The full list of selected hyperparameters can be seen in Subsection \ref{ss:metadata}.

\begin{figure}[H]
\centering
\includegraphics[width=\textwidth]{results/tuning/lambda_hyperparameter_search.png}
\caption{Hyperparameter search of $\lambda$}\label{fig:lambda_search}
\end{figure}%

\begin{figure}[H]
\includegraphics[width=\textwidth]{results/tuning/mutation_rate_hyperparameter_search.png}
\caption{Hyperparameter search of mutation rate $p_m$}
\label{fig:pm_search}
\end{figure}%

\begin{figure}[H]
\includegraphics[width=\textwidth]{results/tuning/k_hyperparamter_search.png}
\caption{Hyperparameter search of $k$ in $k$-tournament selection}
\label{fig:k_search}
\end{figure}%

\begin{figure}[H]
\includegraphics[width=\textwidth]{results/tuning/fs_sigma_hyperparamter_search.png}
\caption{Hyperparameter search of fitness sharing $\sigma$ for $\sigma=num\_cities/d$, where $d \epsilon \{1,2,3,4,5,6,7,8,9,10\}$}
\label{fig:sigma_search}
\end{figure}%

%Another parameter that was added in the individual phase is the mutation strength $\sigma_m$, which was also tuned via hyperparameter search. The results are shown in Figure \ref{fig:sigma-mu}. The algorithm achieved the best results for $\sigma_m = 3$, although, it could just be a matter of luck. A more thorough hyperparameter search would repeatedly run the same experiment and then decide the best value based on the average of the results.

%\begin{figure}[H]
%    \centering
%	\includegraphics[width=\textwidth]{results/tuning/sigma_mu.png}
%    \caption{Best Fitness for various mutation strength values. Experiment was run on \textit{tour194}}
%    \label{fig:sigma-mu}
%\end{figure}

%\subsection{Other considerations}

%\ReplaceMe{Did you consider other items not listed above, such as elitism, multiobjective optimization strategies (e.g., island model, pareto front approximation), a parallel implementation, or other interesting computational optimizations (e.g. using advanced algorithms or data structures)? You can describe them here or add additional subsections as needed.}

\section{Numerical experiments} \label{s:numerical_experiments}

%\RemoveMe{\textbf{Goal:} Based on this section and our execution of your code, we will evaluate the performance (time, quality of solutions) of your implementation and your ability to interpret and explain the results on benchmark problems.}

\subsection{Metadata} \label{ss:metadata}

%\ReplaceMe{What parameters are there to choose in your evolutionary algorithm? Which fixed parameter values did you use for all experiments below? If some parameters are determined based on information from the problem instance (e.g., number of cities), also report their specific values for the problems below.

%Report the main characteristics of the computer system on which you ran your evolutionary algorithm. Include the processor or CPU (including the number of cores and clock speed), the amount of main memory, and the version of Python 3.}

The following list presents the different parameters that were chosen for the experiments presented in the following subsections.
\begin{itemize}
\item $\lambda = 10$: size of population
\item $\mu = 10$: size of offspring
\item $\lambda_h = 0.2 \times \lambda = 2$: number of heuristic solutions calculated during initialization
\item $k = 4$: number of individuals in the k-tournament selection
\item $p_c = 0.9$: recombination probability per generation
\item $p_m = 0.9$: mutation probability per generation
\item $p_l = 1.0$: local search probabiility per generation
\item $\sigma_m = 1$: mutation strength
\item $\alpha_{fs} = 1$: Fitness sharing shape
\item $\sigma_{fs} = \frac{N}{5}$: Fitness sharing distance threshold, where N is the size of the problem (eg. for $tour29$ $N=29$)
\end{itemize}

All experiments were run in a laptop with an Intel i7 processor with 4 physical cores, 8 logical cores, 8GB Ram, and a clock speed of 1.3GHz (3.9GHz turbo speed). No parallelization was used, so execution was limited to one core. Finally, all experiments were run with \textit{Python 3.8.5}.

\subsection{tour29.csv} \label{ss:tour29}

%\ReplaceMe{Run your algorithm on this benchmark problem (with the 5 minute time limit from the Reporter). Include a typical convergence graph, by plotting the mean and best objective values in function of the time (for example based on the output of the Reporter class).

%What is the best tour length you found? What is the corresponding sequence of cities?

%Interpret your results. How do you rate the performance of your algorithm (time, memory, speed of convergence, diversity of population, quality of the best solution, etc)? Is your solution close to the optimal one?

%Solve this problem 1000 times and record the results. Make a histogram of the final mean fitnessess and the final best fitnesses of the 1000 runs. Comment on this figure: is there a lot of variability in the results, what are the means and the standard deviations?}

Figure \ref{fig:tour29convergence} presents a typical convergence graph of the algorithm run on \textit{tour29}. The algorithm finds the optimal value in about 3 seconds and converges after 200 generations of no improvement in about 7 seconds. Furthermore, the mean fitness never converges fully to the best fitness because of the fitness sharing scheme that is used, which indicates good preservation of diversity across generations.

\begin{figure}
\begin{subfigure}[t]{0.5\textwidth}
    \centering
	\includegraphics[width=\textwidth]{results/4.2/tour29_convergence.png}
    \caption{Tour29}
    \label{fig:tour29convergence}
\end{subfigure}
\begin{subfigure}[t]{0.5\textwidth}
    \centering
	\includegraphics[width=\textwidth]{results/4.3/tour100_convergence.png}
    \caption{Tour100}
    \label{fig:tour100convergence}
\end{subfigure}\\
\begin{subfigure}[t]{0.5\textwidth}
    \centering
	\includegraphics[width=\textwidth]{results/4.4/tour194_convergence.png}
    \caption{Tour194}
    \label{fig:tour194convergence}
\end{subfigure}
\begin{subfigure}[t]{0.5\textwidth}
    \centering
	\includegraphics[width=\textwidth]{results/4.5/tour929_convergence.png}
    \caption{Tour929}
    \label{fig:tour929convergence}
\end{subfigure}
\caption{Typical convergence graphs on the various datasets.}
\end{figure}

The best tour that was found has a fitness - tour length of approximately $\textbf{27154.48839924464m}$. The corresponding tour sequence is the following:
\begin{center}
\textit{[6, 8, 12, 13, 15, 23, 24, 26, 19, 25, 27, 28, 22, 21, 20, 16, 17, 18, 14, 11, 10, 9, 5, 0, 1, 4, 7, 3, 2]}
\end{center}

\begin{figure}[H]
     \centering
     \includegraphics[width=\textwidth]{results/4.2/tour29_histogram.png}
     \caption{Tour29 1000 run histograms of best and mean fitness}
     \label{fig:tour29histogram}
\end{figure}

Based on Figure \ref{fig:tour29histogram}, the algorithm seems to perform really well on \textit{tour29}, consistently finding the optimal or a near optimal solution for a $1000$ runs. At the same time, the histogram of the mean fitness illustrates the fact that even at convergence the algorithm manages to preserve some diversity in the population, since mean fitness is always greater than the best fitness. The mean and std of the 1000 runs for the best and the mean fitness are shown in Table \ref{table:1000run_statistics}.

\begin{table}[H]
\centering
\begin{tabular}{ |c|c|c|c| }
\hline
Fitness & 1000-Run Average & 1000-Run Sandard Deviation\\
\hline
Best & $2154.48839924464$ & $43.44519234412967$ \\
Mean & $27497.005460551067$ & $92.03286853386737$ \\
\hline
\end{tabular}
\caption{Statistics of 1000 runs on \textit{tour29}.}
\label{table:1000run_statistics}
\end{table}

\subsection{tour100.csv} \label{ss:tour100}

%\ReplaceMe{Run your algorithm on this benchmark problem (with the 5 minute time limit from the Reporter). Include a typical convergence graph, by plotting the mean and best objective values in function of the time (for example based on the output of the Reporter class).
%
%What is the best tour length you found in each case?
%
%Interpret your results. How do you rate the performance of your algorithm (time, memory, speed of convergence, diversity of population, quality of the best solution, etc)? Is your solution close to the optimal one?}

Figure \ref{fig:tour100convergence} presents the fitness and mean fitness of a run of the algorithm on \textit{tour100}. The algorithm converged on the 346th generation taking 77 seconds and the best solution that was found comes very close to the optimal solution (red dotted line). Although, this solution was found before generation \#150, it took 200 more generations until convergence. The diversity promotion scheme performed really well as can be seen from the distance between the mean and best fitness across generations.

The best tour that was found has a fitness - tour length of approximately $\textbf{7401.970200443819m}$. The corresponding tour sequence is the following:\\

\begin{minipage}{\textwidth}
\centering
\textit{[92, 52, 60, 2, 47, 35, 25, 71, 55, 80, 16, 20, 63, 24, 97, 98, 48, 40, 44, 78, 33, 90, 85, 70, 27, 22, 77, 96, 69, 29, 1, 17, 34, 95, 76, 68, 23, 49, 18, 59, 5, 56, 57, 19, 73, 39, 32, 74, 38, 13, 8, 86, 4, 51, 54, 41, 12, 89, 61, 43, 58, 67, 42, 83, 66, 0, 50, 65, 15, 79, 64, 93, 14, 6, 88, 72, 94, 84, 36, 46, 91, 28, 10, 37, 45, 7, 62, 53, 11, 87, 30, 9, 3, 31, 82, 21, 75, 99, 26, 81]}
\end{minipage}

\subsection{tour194.csv} \label{ss:tour194}

%\ReplaceMe{Run your algorithm on this benchmark problem (with the 5 minute time limit from the Reporter). Include a typical convergence graph, by plotting the mean and best objective values in function of the time (for example based on the output of the Reporter class).
%
%What is the best tour length you found?
%
%Interpret your results. How do you rate the performance of your algorithm (time, memory, speed of convergence, diversity of population, quality of the best solution, etc)? Is your solution close to the optimal one?}

Figure \ref{fig:tour194convergence} presents the fitness and mean fitness of a run of the algorithm on \textit{tour194}. The best solution that was found lies between the greedy heuristic (yellow dotted line) and the optimal one (red dotted line). It is closer to the optimal one and a clear improvement rate can be observed across iterations. The algorithm finds the best solution at about the 320th iteration, but it doesn't converge until the timeout at around the 570th generation, since there haven't been over 200 iterations without improvement. Furthermore, the diversity promotion scheme managed to keep enough diversity which can be observed by the nonzero distance between the best and mean fitnesses.

The best tour that was found has a fitness - tour length of $\textbf{9385.50274991716m}$. The algorithm converged on the 812th generation taking 177 seconds. The corresponding tour sequence is the following:

\begin{center}
\textit{[46, 50, 60, 66, 72, 65, 67, 63, 69, 76, 83, 80, 78, 82, 87, 91, 96, 94, 95, 92, 90, 101, 102, 105, 104, 106, 107, 99, 109, 111, 114, 115, 116, 120, 119, 122, 123, 127, 132, 128, 134, 142, 147, 159, 165, 170, 169, 166, 161, 157, 158, 164, 167, 177, 179, 184, 192, 187, 190, 191, 188, 183, 180, 176, 174, 172, 173, 171, 178, 185, 182, 186, 189, 193, 181, 175, 168, 163, 162, 160, 155, 129, 126, 124, 125, 131, 133, 136, 139, 144, 148, 145, 141, 137, 138, 143, 149, 153, 156, 152, 151, 140, 146, 150, 154, 135, 130, 117, 121, 118, 108, 112, 113, 110, 103, 100, 98, 93, 88, 89, 97, 84, 85, 64, 19, 62, 35, 58, 61, 81, 70, 79, 86, 75, 74, 77, 71, 73, 68, 59, 56, 44, 36, 26, 21, 28, 27, 32, 17, 20, 23, 25, 16, 6, 10, 13, 24, 22, 12, 15, 7, 5, 0, 3, 1, 2, 4, 8, 9, 11, 14, 18, 29, 31, 30, 34, 37, 40, 47, 45, 43, 41, 49, 48, 54, 53, 51, 52, 55, 57, 42, 39, 33, 38]}
\end{center}

\subsection{tour929.csv} \label{ss:tour929}

%\ReplaceMe{Run your algorithm on this benchmark problem (with the 5 minute time limit from the Reporter). Include a typical convergence graph, by plotting the mean and best objective values in function of the time (for example based on the output of the Reporter class).
%
%What is the best tour length you found?
%
%Interpret your results. How do you rate the performance of your algorithm (time, memory, speed of convergence, diversity of population, quality of the best solution, etc)? Is your solution close to the optimal one?
%
%Did your algorithm converge before the time limit? How many iterations did you perform?}

Figure \ref{fig:tour929convergence} presents the fitness and mean fitness of a run of the algorithm on \textit{tour929}. The best solution that was found is significantly better than the greedy heuristic (yellow dotted line) and fairly close to the optimal one (red dotted line). The algorithm didn't converge before the timeout after the 228th generation. Furthermore, the diversity promotion scheme managed to keep enough diversity which can be observed by the nonzero distance between the best and mean fitnesses.

The best tour that was found has a fitness - tour length of approximately $\textbf{96953.57508056797m}$. The corresponding tour sequence is the following:
\begin{center}
\textit{[925, 927, 922, 920, 918, 913, 907, 894, 899, 916, 917, 915, 912, 910, 909, 911, 906, 904, 903, 898, 893, 890, 897, 887, 884, 863, 853, 843, 830, 804, 826, 834, 835, 854, 857, 861, 870, 881, 871, 873, 877, 878, 883, 872, 865, 864, 851, 846, 847, 859, 845, 841, 827, 832, 818, 811, 627, 628, 645, 723, 765, 783, 787, 813, 814, 812, 802, 803, 788, 792, 790, 807, 815, 805, 806, 808, 809, 797, 774, 768, 776, 770, 757, 758, 752, 748, 756, 762, 767, 760, 771, 784, 775, 786, 791, 798, 801, 799, 800, 785, 782, 789, 780, 769, 750, 749, 739, 731, 727, 712, 703, 698, 696, 688, 689, 701, 711, 718, 724, 734, 737, 728, 715, 699, 694, 684, 697, 713, 740, 753, 766, 747, 742, 702, 683, 658, 642, 668, 677, 670, 666, 674, 657, 656, 659, 669, 673, 676, 681, 693, 680, 678, 671, 652, 651, 654, 667, 655, 644, 639, 643, 650, 653, 660, 665, 695, 709, 710, 720, 733, 735, 746, 751, 755, 764, 773, 778, 781, 772, 761, 763, 716, 706, 708, 719, 736, 741, 738, 730, 717, 705, 714, 722, 732, 721, 704, 707, 700, 692, 690, 691, 682, 675, 664, 679, 672, 641, 640, 610, 528, 609, 595, 586, 580, 572, 579, 590, 603, 608, 607, 598, 589, 585, 577, 569, 568, 556, 547, 540, 557, 541, 532, 527, 518, 506, 499, 498, 480, 471, 463, 455, 448, 441, 454, 462, 492, 505, 526, 531, 536, 546, 555, 571, 576, 584, 593, 594, 602, 606, 611, 619, 620, 615, 633, 635, 634, 663, 686, 794, 777, 726, 662, 685, 743, 661, 810, 793, 725, 624, 623, 614, 622, 618, 617, 599, 581, 582, 604, 600, 605, 601, 583, 567, 566, 561, 554, 560, 553, 552, 539, 530, 524, 523, 510, 509, 522, 515, 521, 534, 543, 537, 544, 538, 535, 545, 551, 565, 564, 563, 559, 550, 508, 438, 443, 433, 426, 439, 434, 445, 444, 451, 466, 473, 467, 474, 484, 495, 496, 511, 516, 512, 502, 486, 476, 485, 475, 456, 452, 446, 457, 468, 447, 453, 477, 469, 487, 513, 488, 478, 458, 479, 490, 489, 497, 517, 525, 503, 504, 491, 461, 470, 460, 459, 440, 435, 428, 427, 418, 417, 406, 400, 401, 413, 402, 407, 420, 421, 429, 422, 430, 431, 423, 416, 408, 409, 410, 419, 399, 395, 389, 387, 376, 378, 388, 386, 382, 394, 396, 398, 405, 404, 415, 414, 403, 393, 392, 391, 384, 385, 381, 377, 355, 357, 348, 345, 346, 343, 333, 352, 375, 341, 342, 339, 344, 340, 331, 337, 363, 373, 370, 366, 367, 379, 432, 449, 450, 493, 500, 573, 587, 596, 562, 464, 397, 360, 368, 371, 380, 390, 411, 436, 442, 481, 482, 472, 501, 570, 613, 574, 592, 591, 629, 795, 729, 838, 817, 823, 844, 858, 868, 875, 852, 848, 839, 820, 646, 630, 636, 687, 616, 632, 558, 514, 437, 424, 412, 356, 361, 353, 351, 350, 329, 325, 315, 309, 303, 304, 297, 306, 293, 273, 272, 256, 265, 264, 260, 269, 271, 281, 285, 270, 314, 318, 284, 274, 313, 292, 283, 259, 253, 250, 268, 282, 327, 326, 324, 244, 305, 296, 254, 236, 92, 93, 87, 83, 84, 85, 81, 45, 48, 80, 77, 89, 200, 99, 62, 39, 41, 40, 21, 7, 1, 5, 43, 31, 24, 23, 25, 22, 11, 16, 8, 6, 0, 18, 26, 51, 67, 65, 78, 131, 132, 102, 96, 88, 72, 59, 36, 32, 27, 12, 14, 9, 2, 3, 4, 10, 17, 13, 30, 29, 19, 28, 35, 33, 20, 38, 37, 46, 44, 50, 52, 53, 55, 54, 60, 63, 66, 70, 69, 74, 68, 73, 82, 86, 95, 98, 229, 251, 261, 288, 298, 299, 302, 294, 310, 316, 320, 334, 323, 301, 300, 290, 286, 289, 278, 266, 243, 248, 245, 249, 252, 255, 257, 267, 262, 276, 263, 258, 204, 153, 237, 203, 180, 165, 161, 147, 143, 130, 109, 105, 108, 104, 120, 124, 126, 133, 145, 156, 146, 154, 159, 174, 182, 185, 187, 199, 214, 227, 233, 222, 211, 208, 206, 193, 190, 186, 176, 173, 179, 172, 181, 184, 192, 205, 202, 194, 189, 196, 207, 215, 217, 221, 225, 234, 228, 216, 226, 235, 239, 240, 242, 246, 247, 241, 238, 232, 230, 224, 223, 210, 198, 213, 201, 188, 177, 175, 169, 167, 163, 160, 148, 141, 139, 137, 144, 151, 171, 168, 162, 157, 155, 140, 128, 138, 164, 166, 183, 195, 209, 197, 212, 218, 220, 231, 219, 191, 170, 150, 106, 112, 111, 121, 107, 116, 129, 113, 103, 114, 119, 123, 136, 134, 135, 142, 149, 158, 152, 125, 127, 122, 118, 117, 115, 110, 100, 91, 58, 61, 101, 97, 90, 94, 75, 42, 47, 56, 57, 49, 15, 34, 64, 71, 76, 79, 178, 287, 308, 307, 330, 332, 338, 347, 359, 362, 354, 358, 365, 383, 520, 533, 597, 519, 507, 549, 588, 626, 575, 621, 649, 631, 625, 548, 483, 425, 372, 335, 336, 322, 321, 291, 312, 275, 277, 280, 279, 295, 311, 319, 317, 328, 349, 374, 364, 369, 465, 494, 529, 542, 578, 612, 637, 647, 648, 754, 816, 744, 638, 759, 796, 825, 833, 855, 849, 856, 866, 869, 888, 891, 892, 889, 885, 874, 880, 879, 886, 882, 876, 862, 842, 837, 836, 831, 828, 824, 779, 745, 822, 821, 819, 829, 840, 850, 860, 867, 895, 902, 896, 900, 901, 905, 908, 914, 919, 928, 926, 923, 921, 924]}
\end{center}

\section{Critical reflection} \label{s:critical_reflection}

%\RemoveMe{\textbf{Goal:} Based on this section, we will evaluate your understanding and insight into the main strengths and weaknesses of your evolutionary algorithms.}

%\ReplaceMe{Describe the main lessons learned from this project. What do you think are the main strong points of evolutionary algorithms in general? Did you apply these strengths in this project? What are the main weaknesses of evolutionary algorithms and of your implementation in particular? Do you think these can be avoided or mitigated? How? Do you believe evolutionary algorithms are appropriate for this problem? Why (not)? What surprised you and why? What did you learn from this project?}

Working on this project allowed me the opportunity me to study evolutionary algorithms and understand them in more depth, while also looking at state-of-the-art research to find clues as to how to refine my algorithm for solving the \textit{Travelling Salesman Problem (TSP)}. Evolutionary algorithms in general are really good at solving non-convex optimization problems whose solution space contains many local minima, where a popular optimization algorithm like Steepest Descent would get stuck quite easily in a suboptimal solution. TSP is such a non-convex problem and hence evolutionary algorithms are a good approach to solve it. Of course in most cases it's not guaranteed that an evolutionary algorithm will find the global optimum in finite time, but it certainly has the capability to escape local minima and find really good solutions. This is mainly thanks to the random nature of the mutation and recombination steps. On one hand we have the random combination of the useful information that already exists in the population and on the other hand we have the randomness that's inserted into new individuals, which may produce even better solutions than the previous generations.

A good evolutionary algorithm, in general, needs really careful design and needs to be specialized to a problem and use problem specific information to guide the search towards optimal solutions. For example, it's easy to design an evolutionary algorithm for solving the TSP with a lot of randomness, but to make it really efficient, it is very advantageous to seed the initial population or even other steps of the algorithm with heuristic information. This step proved to improve the efficiency of the developed algorithm and speed up the search of good candidate solutions quite considerably. Moreover, an evolutionary algorithm can become even more efficient if it's combined with local search methods like steepest descent or k-opt. Instead of waiting to find local minima after many generations of mutation and recombination it's a lot more efficient to run local search on a lot of individuals from the population and thus find many local minima, thus increasing the probability to find the global minima or at least a really good solution. The introduction of 2-opt proved instrumental in finding really good solutions without letting the algorithm run for thousands of generations.

Of course, evolutionary algorithms are not the perfect tool for solving any problem in many cases there are way better alternatives. One main disadvantage of evolutionary algorithms is that they are very computationally expensive. The developed evolutionary algorithm, in particular, is quite inefficient because of the really expensive local search operator (2-opt) that prevents the larger problems from running for a high number generations given the 5-minute time limit. This could have potentially been alleviated by parallelizing the local search on multiple offspring at the same time. Another issue with the local search operator and the greedy heuristic initialization was that the algorithm was directed towards strong local minima and couldn't escape easily. However, the benefit of those two methods far outweighed the costs.

What surprised me the most in this project was mainly how modular and customizable an evolutionary algorithm can be. There are so many different methods to choose from, yet not all of them are compatible with all problems or with each other and it's a quite complex and time-consuming task to find the right ones to combine. Furthermore, a few methods that I experimented with, such as self-adaptive mutation rate and/or strength failed to provide any measurable improvement to the algorithm, despite them being quite popular in the literature. Another thing that was quite difficult to work out was how to interpret the results. Due to the random nature of evolutionary algorithms, it was difficult for example to evaluate if a modification to the algorithm or the tuning of a parameter made any difference, which resulted in a lot of trial and error to find a good combination of parameters.

%\section{Other comments} \label2{sec_other}
%
%\ReplaceMe{In case you think there is something important to discuss that is not covered by the previous sections, you can do it here. }

\bibliographystyle{plain}
\bibliography{ref}

\end{document}

max_stars_repo_name: gkouros/gaev-mai-kuleuven

max_issues_repo_name: gkouros/tsp-genetic-algorithm

max_forks_repo_name: gkouros/tsp-genetic-algorithm


text:
\section{Definitions}

\todo

ext: tex

max_stars_repo_name: sumedhe/ucsc-thesis-template

max_issues_repo_name: sumedhe/ucsc-thesis-template

max_forks_repo_name: sumedhe/ucsc-thesis-template


text:
\section{\textbf{CoarseCuckooHashSetTest}}

\subsection{Particular Case (problem)}
The problem we try to solve is that of concurrent hashing, when we use
the hash to implement a set data structure.

\subsection{Solution}
The solution uses three techniques combined: \\

\begin{itemize}
  \item cuckoo-hashing: which consists in shifting to the right
    elements, by performing consecutive swaps on elements having a
    collision due hash function. \\
  \item double hashing where we use a couple of hash tables; the first
    one is based on a simple hash function (modulus of the element's
    hash code), and the second table is indexed with random numbers
    generated out of a sequence feed from the hash code of elements.
    \item coarse access: as the whole structure is being protected by
      mutual exclusion with a lock.
\end{itemize}
\hfill

Below the most representative function, \C{add}, along with the two
hash functions used: \\

\begin{lstlisting}[style=numbers]
  private final int hash0(Object x) {
    return x.hashCode() % size;
  }

  private final int hash1(Object x) {
    random.setSeed(x.hashCode());
    return random.nextInt(size);
  }

  public boolean add(T x) {
    lock.lock();
    try {
      if (contains(x)) {
        return false;
      }
      for (int i = 0; i < LIMIT; i++) {
        if ((x = swap(0, hash0(x), x)) == null) {
          return true;
        } else if ((x = swap(1, hash1(x), x)) == null) {
          return true;
        }
      }
      System.out.println("uh-oh");
      throw new CuckooException();
    } finally {
      lock.unlock();
    }
  }
\end{lstlisting}
\hfill

Something additional to mention about this solution, is that when
adding a new element we constraint the maximum number of swaps to
perform (while shifting the elements to the right). In this
implementation is \C{LIMIT} is 32; if after those attempts we could
not arrange all elements on its slot we raise an exception.

\subsection{Experiment Description}
The test program consists of three test cases:

\begin{itemize}
  \item \C{testSequential}: add 512 elements to the hash set
    (sequentially), perform a \C{contains} test for each one
    (sequentially) and finally remove the 512 elements
    (sequentially). \\
  \item \C{testParallelAdd}: add 512 elements to the hash set
    (in parallel with 8 threads), perform a \C{contains} test for each one
    (sequentially) and finally remove the 512 elements
    (sequentially). \\
  \item \C{testParallelRemove}: add 512 elements to the hash set
    (sequentially), perform a \C{contains} test for each one
    (sequentially) and finally remove the 512 elements
    (in parallel with 8 threads). \\
  \item \C{testParallelBoth}: adds and removes 512 elements to the
    hash set in parallel with 8 adder threads, and 8 remover threads;
    the removers complain if someone else removed its designated range
    of elements.
\end{itemize}

\subsection{Observations and Interpretations}
The tests works fine on both machines (2 and 24 cores respectively),
with the exception that the parallel test remover threads complain
when they try to delete an element which does not exist yet (which is
an expected consequence of the test). A sample output is shown below:

\begin{verbatim}
[oraadm@gdlaa008 orig]$ junit hash.CoarseCuckooHashSetTest

.sequential add, contains, and remove
.parallel both
Exception in thread "Thread-5" Exception in thread "Thread-9"
                Exception in thread "Thread-11" Exception in thread

"Thread-1" junit.framework.AssertionFailedError: DeqThread: duplicate

remove
at junit.framework.Assert.fail(Assert.java:57)
at junit.framework.TestCase.fail(TestCase.java:227)
at

...

.parallel add
.parallel remove

Time: 0.053

OK (4 tests)
\end{verbatim}
\hfill

max_stars_repo_name: rzavalet/multiprocessor

max_issues_repo_name: rzavalet/multiprocessor

max_forks_repo_name: rzavalet/multiprocessor


text:
%&latex -*- latex -*-

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Introduction}

This is the reference manual for scsh,
a {\Unix} shell that is embedded within {\Scheme}.
Scsh is a Scheme system designed for writing useful standalone Unix
programs and shell scripts---it spans a wide range of application,
from ``script'' applications usually handled with perl or sh,
to more standard systems applications usually written in C.

Scsh comes built on top of {\scm}, and has two components:
a process notation for running programs and setting up pipelines
and redirections,
and a complete syscall library for low-level access to the operating system.
This manual gives a complete description of scsh.
A general discussion of the design principles behind scsh can be found
in a companion paper, ``A Scheme Shell.''

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Copyright \& source-code license}
Scsh is open source. The complete sources come with the standard
distribution, which can be downloaded off the net.
Scsh has an ideologically hip, BSD-style license.

We note that the code is a rich source for other Scheme implementations
to mine. Not only the \emph{code}, but the \emph{APIs} are available
for implementors working on Scheme environments for systems programming.
These APIs represent years of work, and should provide a big head-start
on any related effort. (Just don't call it ``scsh,'' unless it's
\emph{exactly} compliant with the scsh interfaces.)

Take all the code you like; we'll just write more.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Obtaining scsh}
Scsh is distributed via net publication.
We place new releases at well-known network sites,
and allow them to propagate from there.
We currently release scsh to the following Internet sites:
\begin{inset}\begin{flushleft}
\ex{\urlh{ftp://ftp.scsh.net/pub/scsh}{ftp://ftp.scsh.net/pub/scsh}} \\
\ex{\urlh{http://prdownloads.sourceforge.net/scsh/}{http://prdownloads.sourceforge.net/scsh/}} \\
\end{flushleft}
\end{inset}
%
Each should have a compressed tar file of the entire scsh release,
which includes all the source code and the manual,
and a separate file containing just this manual in Postscript form,
for those who simply wish to read about the system.

However, nothing is certain for long on the Net.
Probably the best way to get a copy of scsh is to use a network
resource-discovery tool, such as archie,
to find ftp servers storing scsh tar files.
Take the set of sites storing the most recent release of scsh,
choose one close to your site, and download the tar file.

\section{Building scsh}
Scsh currently runs on a fairly large set of Unix systems, including
Linux, FreeBSD, OpenBSD, NetBSD, MacOS X, SunOS, Solaris, AIX, NeXTSTEP, Irix, and HP-UX.
We use the Gnu project's autoconfig tool to generate self-configuring
shell scripts that customise the scsh Makefile for different OS variants.
This means that if you use one of the common Unix implementations,
building scsh should require exactly the following steps:
\begin{inset}
\begin{tabular}{l@{\qquad}l}
\ex{gunzip scsh.tar.gz} &       \emph{Uncompress the release tar file.} \\
\ex{untar xfv scsh.tar} &       \emph{Unpack the source code.}          \\
\ex{cd scsh-0.6.x} &              \emph{Move to the source directory.}    \\
\ex{./configure} &              \emph{Examine host; build Makefile.}    \\
\ex{make} &                     \emph{Build system.}
\end{tabular}
\end{inset}
When you are done, you should have a virtual machine compiled in
file \ex{scshvm}, and a heap image in file \ex{scsh/scsh.image}.
Typing
\begin{code}
make install
\end{code}
will install these programs in your installation directory
(by default, \ex{/usr/local}), along with a small stub startup
binary, \ex{scsh}.

If you don't have the patience to do this, you can start up
a Scheme shell immediately after the initial make by simply
saying
\codex{./scshvm -o ./scshvm -i scsh/scsh.image}
See chapter~\ref{chapt:running} for full details on installation
locations and startup options.

It is not too difficult to port scsh to another Unix platform if your
OS is not supported by the current release.
See the release notes for more details on how to do this.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Caveats}

It is important to note what scsh is \emph{not}, as well as what it is.
Scsh, in the current release, is primarily designed for the writing of
shell scripts---programming.
It is not a very comfortable system for interactive command use:
the current release lacks job control, command-line editing, a terse,
convenient command syntax, and it does not read in an initialisation
file analogous to \ex{.login} or \ex{.profile}.
We hope to address all of these issues in future releases;
we even have designs for several of these features;
but the system as-released does not currently provide these features.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Naming conventions}
Scsh follows a general naming scheme that consistently employs a set of
abbreviations.
This is intended to make it easier to remember the names of things.
Some of the common ones are:
\begin{description}
\item [\ex{fdes}]
        Means ``file descriptor,'' a small integer used in {\Unix}
        to represent I/O channels.

\item [\ex{\ldots*}]
        A given bit of functionality sometimes comes in two related forms,
        the first being a \emph{special form} that contains a body of
        {\Scheme} code to be executed in some context,
        and the other being a \emph{procedure} that takes a procedural
        argument (a ``thunk'') to be called in the same context.
        The procedure variant is named by taking the name of the special form,
        and appending an asterisk. For example:
\begin{code}
;;; Special form:
(with-cwd "/etc"
  (for-each print-file (directory-files))
  (display "All done"))

;;; Procedure:
(with-cwd* "/etc"
  (lambda ()
    (for-each print-file (directory-files))
    (display "All done")))\end{code}

\item [\ex{\var{action}/\var{modifier}}]
    The infix ``\ex{/}'' is pronounced ``with,'' as in
    \ex{exec/env}---``exec with environment.''

\item [\ex{call/\ldots}]
        Procedures that call their argument on some computed value
        are usually named ``\ex{call/\ldots},'' \eg,
        \ex{(call/fdes \var{port} \var{proc})}, which calls \var{proc}
        on \var{port}'s file descriptor, returning whatever \var{proc}
        returns. The abbreviated name means ``call with file descriptor.''

\item [\ex{with-\ldots}]
        Procedures that call their argument, and special forms that execute
        their bodies in some special dynamic context frequently have
        names of the form \ex{with-\ldots}. For example,
        \ex{(with-env \var{env} \vari{body}1 \ldots)} and
        \ex{(with-env* \var{env} \var{thunk})}. These forms set
        the process environment body, execute their body or thunk,
        and then return after resetting the environment to its original
        state.

\item[\ex{create-}]
        Procedures that create objects in the file system (files, directories,
        temp files, fifos, \etc), begin with \ex{create-\ldots}.

\item [\ex{delete-}]
        Procedures that delete objects from the file system (files,
        directories, temp files, fifos, \etc), begin with \ex{delete-\ldots}.

\item[ \ex{\var{record}:\var{field}} ]
        Procedures that access fields of a record are usually written
        with a colon between the name of the record and the name of the
        field, as in \ex{user-info:home-dir}.

\item[\ex{\%\ldots}]
        A percent sign is used to prefix lower-level scsh primitives
        that are not commonly used.

\item[\ex{-info}]
        Data structures packaging up information about various OS
        entities frequently end in \ldots\ex{-info}. Examples:
        \ex{user-info}, \ex{file-info}, \ex{group-info}, and \ex{host-info}.

\end{description}
%
Enumerated constants from some set \var{s} are usually named
\ex{\var{s}/\vari{const}1}, \ex{\var{s}/\vari{const}2}, \ldots.
For example, the various {\Unix} signal integers have the names
\ex{signal/cont}, \ex{signal/kill}, \ex{signal/int}, \ex{signal/hup},
and so forth.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Lexical issues}
Scsh's lexical syntax is just {\RnRS} {\Scheme}, with the following
exceptions.

\subsection{Extended symbol syntax}
Scsh's symbol syntax differs from {\RnRS} {\Scheme} in the following ways:
\begin{itemize}
\item In scsh, symbol case is preserved by \ex{read} and is significant on
      symbol comparison. This means
      \codex{(run (less Readme))}
      displays the right file.

\item ``\ex{-}'' and ``\ex{+}'' are allowed to begin symbols.
      So the following are legitimate symbols:
      \codex{-O2 -geometry +Wn}

\item ``\ex{|}'' and ``\ex{.}'' are symbol constituents.
  This allows \ex{|} for the pipe symbol, and \ex{..} for the parent-directory
  symbol. (Of course, ``\ex{.}'' alone is not a symbol, but a
  dotted-pair marker.)

\item A symbol may begin with a digit.
      So the following are legitimate symbols:
\codex{9x15 80x36-3+440}
\end{itemize}

\subsection{Extended string syntax}
Scsh strings are allowed to contain the {\Ansi} C escape sequences
      such as \verb|\n| and \verb|\161|.

\subsection{Block comments and executable interpreter-triggers}
Scsh allows source files to begin with a header of the form
\codex{\#!/usr/local/bin/scsh -s}
The Unix operating system treats source files beginning with the headers
of this form specially;
they can be directly executed by the operating system
(see chapter~\ref{chapt:running} for information on how to use this feature).
The scsh interpreter ignores this special header by treating \ex{\#!} as a
comment marker similar to \ex{;}.
When the scsh reader encounters \ex{\#!}, it skips characters until it finds
the closing sequence
new\-line/{\ob}ex\-cla\-ma\-tion-{\ob}point/{\ob}sharp-{\ob}sign/{\ob}new\-line.

Although the form of the \ex{\#!} read-macro was chosen to support
interpreter-triggers for executable Unix scripts,
it is a general block-comment sequence and can be used as such
anywhere in a scsh program.

\subsection{Here-strings}
The read macro  \ex{\#<} is used to introduce ``here-strings''
in programs, similar to the \ex{<<} ``here document'' redirections
provided by sh and csh.
There are two kinds of here-string, character-delimited and line-delimited;
they are both introduced by the \ex{\#<} sequence.

\subsubsection{Character-delimited here-strings}
A \emph{character-delimited} here-string has the form
\codex{\#<\emph{x}...stuff...\emph{x}}
where \emph{x} is any single character
(except \ex{<}, see below),
which is used to delimit the string bounds.
Some examples:
\begin{inset}
\begin{tabular}{ll}
        Here-string syntax              & Ordinary string syntax \\ \hline
        \verb:#<|Hello, world.|:        & \verb:"Hello, world.":        \\
        \verb:#<!"Ouch," he said.!:     & \verb:"\"Ouch,\" he said.":
\end{tabular}
\end{inset}
%
There is no interpretation of characters within the here-string;
the characters are all copied verbatim.

\subsubsection{Line-delimited here-strings}
If the sequence begins "\ex{\#<<}" then it introduces a \emph{line-delimited}
here-string.
These are similar to the ``here documents'' of sh and csh.
Line-delimited here-strings are delimited by the rest of the text line that
follows the "\ex{\#<<}" sequence.
For example:

\begin{code}
#<<FOO
Hello, there.
This is read by Scheme as a string,
terminated by the first occurrence
of newline-F-O-O-newline or newline-F-O-O-eof.
FOO\end{code}
%
Thus,
\begin{code}
#<<foo
Hello, world.
foo\end{code}
%
is the same thing as
\codex{"Hello, world."}

Line-delimited here-strings are useful for writing down long, constant
strings---such as long, multi-line \ex{format} strings,
or arguments to Unix programs, \eg,
\begin{code}
;; Free up some disk space for my netnews files.
(run (csh -c #<<EOF
cd /urops
rm -rf *
echo All done.

EOF
))\end{code}

The advantage they have over the double-quote syntax
(\eg, \ex{"Hello, world."})
is that there is no need to backslash-quote special characters internal
to the string, such as the double-quote or backslash characters.

The detailed syntax of line-delimited here-strings is as follows.
The characters "\ex{\#<<}" begin the here-string.
The characters between the "\ex{\#<<}" and the next newline are the
\emph{delimiter line}.
All characters between the "\ex{\#<<}" and the next newline comprise the
delimiter line---including any white space.
The body of the string begins on the following line,
and is terminated by a line of text which exactly matches the
delimiter line.
This terminating line can be ended by either a newline or end-of-file.
Absolutely no interpretation is done on the input string.
Control characters, white space, quotes, backslash---everything
is copied as-is.
The newline immediately preceding the terminating delimiter line is
not included in the result string
(leave an extra blank line if you need to put a final
newline in the here-string---see the example above).
If EOF is encountered before reading the end of the here-string,
an error is signalled.

\subsection{Dot}
It is unfortunate that the single-dot token, ``\ex{.}'', is both
a fundamental {\Unix} file name and a deep, primitive syntactic token
in {\Scheme}---it means the following will not parse correctly in scsh:
\codex{(run/strings (find . -name *.c -print))}
You must instead quote the dot:
\codex{(run/strings (find "." -name *.c -print))}

When you write shell scripts that manipulate the file system,
keep in mind the special status of the dot token.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Record types and the \texttt{define-record} form}
\label{sec:defrec}
\index{define-record@\texttt{define-record}}

Scsh's interfaces occasionally provide data in structured record types;
an example is the \ex{file-info} record whose various fields describe the size,
protection, last date of modification, and other pertinent data for a
particular file.
These record types are described in this manual using the \ex{define-record}
notation, which looks like the following:
%
\begin{code}
(define-record ship
  x
  y
  (size 100))\end{code}
%
This form defines a \var{ship} record, with three fields:
its x and y coordinates, and its size.
The values of the \var{x} and \var{y} fields are specified as parameters
to the ship-building procedure, \ex{(make-ship \var{x} \var{y})},
and the \var{size} field is initialised to 100.
All told, the \ex{define-record} form above defines the following procedures:
%
\begin{center}
\begin{tabular}{|ll|}
\multicolumn{1}{l}{Procedure} & \multicolumn{1}{l}{Definition} \\
\hline
(make-ship \var{x} \var{y}) & Create a new \var{ship} record. \\
\hline
(ship:x \var{ship})     & Retrieve the \var{x} field. \\
(ship:y \var{ship})     & Retrieve the \var{y} field. \\
(ship:size \var{ship})  & Retrieve the \var{size} field. \\
\hline
(set-ship:x \var{ship} \var{new-x}) & Assign the \var{x} field. \\
(set-ship:y \var{ship} \var{new-y}) & Assign the \var{y} field. \\
(set-ship:size \var{ship} \var{new-size}) & Assign the \var{size} field. \\
\hline
(modify-ship:x \var{ship} \var{xfun}) & Modify \var{x} field with \var{xfun}. \\
(modify-ship:y \var{ship} \var{yfun}) & Modify \var{y} field with \var{yfun}. \\
(modify-ship:size \var{ship} \var{sizefun}) & Modify \var{size} field with \var{sizefun}. \\
\hline
(ship? \var{object})    & Type predicate. \\
\hline
(copy-ship \var{ship}) & Shallow-copy of the record. \\
\hline
\end{tabular}
\end{center}
%

An implementation of \ex{define-record} is available as a macro for Scheme
programmers to define their own record types;
the syntax is accessed by opening the package \ex{defrec-package}, which
exports the single syntax form \ex{define-record}.
See the source code for the \ex{defrec-package} module
for further details of the macro.

You must open this package to access the form.
Scsh does not export a record-definition package by default as there are
several from which to choose.
Besides the \ex{define-record} macro, which Shivers prefers\footnote{He wrote
it.}, you might instead wish to employ the notationally-distinct
\ex{define-record-type} macro that Jonathan Rees
prefers\footnote{He wrote it.}.
It can be found in the
\ex{define-record-types} structure.

Alternatively, you may define your own, of course.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{A word about {\Unix} standards}
``The wonderful thing about {\Unix} standards is that there are so many
to choose from.''
You may be totally bewildered about the multitude of various standards that
exist.
Rest assured that nowhere in this manual will you encounter an attempt
to spell it all out for you;
you could not read and internalise such a twisted account without
bleeding from the nose and ears.

However, you might keep in mind the following simple fact: of all the
standards, {\Posix} is the least common denominator.
So when this manual repeatedly refers to {\Posix}, the point is ``the
thing we are describing should be portable just about anywhere.''
Scsh sticks to {\Posix} when at all possible; its major departure is
symbolic links, which aren't in {\Posix} (see---it
really \emph{is} a least common denominator).

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "man"
%%% End:

max_stars_repo_name: takusuman/scsh

max_issues_repo_name: takusuman/scsh

max_forks_repo_name: takusuman/scsh


text:
\documentclass{article}

\usepackage[version=3]{mhchem} % Package for chemical equation typesetting
\usepackage{siunitx} % Provides the \SI{}{} and \si{} command for typesetting SI units
\usepackage{graphicx} % Required for the inclusion of images
\usepackage{natbib} % Required to change bibliography style to APA
\usepackage{amsmath} % Required for some math elements
\usepackage{caption}
\usepackage{subcaption}
\usepackage{listings}
\usepackage{color}

\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}

\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},
    commentstyle=\color{codegreen},
    keywordstyle=\color{codepurple},
    numberstyle=\tiny\color{codegray},
    stringstyle=\color{codepurple},
    basicstyle=\footnotesize,
    breakatwhitespace=false,
    breaklines=true,
    captionpos=b,
    keepspaces=true,
    numbers=left,
    numbersep=5pt,
    showspaces=false,
    showstringspaces=false,
    showtabs=false,
    tabsize=2
}
\lstset{style=mystyle}

\setlength\parindent{0pt} % Removes all indentation from paragraphs

\renewcommand{\labelenumi}{\alph{enumi}.} % Make numbering in the enumerate environment by letter rather than number (e.g. section 6)

\newcommand\tab[1][0.5cm]{\hspace*{#1}}

%\usepackage{times} % Uncomment to use the Times New Roman font

\renewcommand{\thesubsection}{\thesection.\alph{subsection}}

%----------------------------------------------------------------------------------------
%	DOCUMENT INFORMATION
%----------------------------------------------------------------------------------------

\title{COMP 304: Assignment 2} % Title

\author{Berkay \textsc{Barlas}} % Author name

\date{\today} % Date for the report

\begin{document}

\maketitle % Insert the title, author and date

\begin{center}
\begin{tabular}{l r}
Date Performed: & April 15, 2019 \\ % Date the experiment was performed
Instructor: & Didem Unat % Instructor/supervisor
\end{tabular}
\end{center}

% If you wish to include an abstract, uncomment the lines below
% \begin{abstract}
% Abstract text
% \end{abstract}

%----------------------------------------------------------------------------------------
%	SECTION 1
%----------------------------------------------------------------------------------------

\section{Problem 1}

\subsection{}

\begin{description}
    \item[Process Execution Gantt Chart of FCFS] \hfill

    \includegraphics[width=1\linewidth]{./fcfs.png}
    \item[Process Execution Gantt Chart of SJF] \hfill

    \includegraphics[width=1\linewidth]{./sjf.png}
    \item[Process Execution Gantt Chart of non-preemptive Priority] \hfill

    \includegraphics[width=1\linewidth]{./priority.png}
    \item[Process Execution Gantt Chart of RR] \hfill

    \includegraphics[width=1\linewidth]{./rr.png}
\end{description}

\subsection{} If the context-switch overhead is 1 ms, calculate the waiting time of each process for
each of the scheduling algorithms in part (a). Which of the schedules results in the minimal
average waiting time?

SJF(Shortest Job First) results in the minimal average waiting time.\\ \\

\begin{description}
    \item[Process Execution Gantt Chart of FCFS] \hfill
    \begin{description}
        \item[Waiting Time of P1:] 0
        \item[Waiting Time of P2:] 9
        \item[Waiting Time of P3:] 15
        \item[Waiting Time of P4:] 19
        \item[Waiting Time of P5:] 21
        \item[Average waiting time:] ( 9 + 15 + 19 + 21 ) / 5 = 12,8
    \end{description}
    \item[Process Execution Gantt Chart of SJF] \hfill
    \begin{description}
        \item[Waiting Time of P1:] 12
        \item[Waiting Time of P2:] 6
        \item[Waiting Time of P3:] 2
        \item[Waiting Time of P4:] 0
        \item[Waiting Time of P5:] 21
        \item[Average waiting time:] ( 12 + 6 + 2 + 0 + 21 ) / 5 = 8.2
    \end{description}
    \item[Process Execution Gantt Chart of non-preemptive Priority] \hfill
    \begin{description}
        \item[Waiting Time of P1:] 17
        \item[Waiting Time of P2:] 0
        \item[Waiting Time of P3:] 26
        \item[Waiting Time of P4:] 30
        \item[Waiting Time of P5:] 6
        \item[Average waiting time:] ( 17 + 0 + 26 + 30 + 6) / 5 = 15,8
    \end{description}

    \item[Process Execution Gantt Chart of RR] \hfill
    \begin{description}
        \item[Waiting Time of P1:] 16 + 5 - 8 = 13
        \item[Waiting Time of P2:] 21 + 6 - 5 = 22
        \item[Waiting Time of P3:] 10
        \item[Waiting Time of P4:] 14
        \item[Waiting Time of P5:] 27 + 8 -10 = 25
        \item[Average waiting time:] (13 + 22 + 10 + 14 + 25) / 5 = 16,8
    \end{description}

\end{description}

\subsection{Calculate average turnaround time for each of the scheduling algorithms in part (a).}
\begin{description}
    \item[Average turnaround time for FCFS] \hfill
\\( 8 + 13 + 16 + 17 + 27 ) / 5 = 16.2
    \item[Average turnaround time for SJF] \hfill
\\( 1 + 4 + 9 + 17 + 27 ) / 5 = 11.6
    \item[Average turnaround time for non-preemptive Priority] \hfill
\\( 5 + 15 + 23 + 26 + 27 ) / 5 = 19.2
    \item[Average turnaround time for RR] \hfill
\\( 20 + 21 + 11 + 12 + 27 ) / 5 = 18.2
\end{description}

\section{Problem 2}
Now assume that the context-switching overhead is equivalent to 0.5 ms. Calculate the CPU utilisation for all four scheduling algorithms in Problem 1.
\\
\begin{equation*}
    CPU utilisation  = 100 * \frac{{Total Time Spend on Processes}}{\mathrm{Total Time Spend on Execution}}
%\begin{center}\ce{}\end{center}
\end{equation*}
\begin{description}
    \item[CPU utilisation of FCFS] \hfill \\
(27 / 29 * 100) = 93,10
    \item[CPU utilisation of SJF] \hfill \\
    (27 / 29 * 100) = 93,10
    \item[CPU utilisation of non-preemptive Priority] \hfill \\
    (27 / 29 * 100) = 93,10
    \item[CPU utilisation of RR] \hfill \\
(27 / 31 * 100) = 87,09
\end{description}

\section{Problem 3}

\subsection{}
\tab There is race condition in code, thus, output is non-deterministic and depends on order of process execution.
\\The available\_connections is shared variable and it might be written by multiple threads simultaneously inside of the connect() and disconnect() methods.
\\Since write is actually consist of multiple Instructions, a race condition may occur when two or more threads access the shared data and they try to change it at the same time.
\subsection{}
We could use locks to prevent race condition.

\begin{lstlisting}[language=C]
//PROBLEM 3
#define MAX_CONNECTIONS 5000
int available_connections = MAX_CONNECTIONS;
mutex lock;

/* When a thread wishes to establish a connection with the rver,
it invokes the connect() function:*/

int connect() {
    mutex_lock(&lock);
    if (available_connections < 1) {
        mutex_unlock(&lock);
        return -1;
    } else {
        available_connections--;
    }
    mutex_unlock(&lock);
    return 0;
}

 /* When a thread wishes to drop a connection with the server,
 it invokes disconnect() */
 int disconnect() {
    mutex_lock(&lock);
    available_connections++;
    mutex_unlock(&lock);
    return 0;
 }
\end{lstlisting}

\subsection{}
\tab
\\ \tab Using atomic integer will prevent the race condition that caused by change of shared variable by multiple threads at the same time. However, replacing the integer with atomic integer is not enough. While one of the threads inside of the if statement of connect method (before returning) another thread might increase the available\_connections variable which might effect of the result of if statement. For example, connect() method could return \-1 even available\_connections is 1 (It was 0 when the statement checked but then inreased to 1 before return by another thread inside of the disconnect() method. ).
\newpage
\section{Problem 4}
\tab We could use semaphore with initial value M ,however, if a party with more than 4 numcustomers arrive we need to be sure we have enough rooms. Thus, we can use a semaphore with initial value 1 and a global variable to check available number of rooms.
\begin{lstlisting}[language=C]

    semaphore roomLock = 1;
    int roomNum = M;

    int makeReservation(int numCustomers) {
        int roomNeeded = (numCustomers + 3 ) / 4;
        // I added 3 to round upper bound.
        // When 1 || 2 || 3 || 4 customer come roomNeeded should be 1
        // When 5 customer come roomNeeded should be 2
        // int a = (2 + 3) / 4 = 1; a = 1
        wait(roomLock);

        if(roomNum >=roomNeeded ) {
            //accept
            roomNum = roomNum - roomNeeded;

        } else {
            //decline
        }
        signal(roomLock);
        return 0;
    }

    int checkout(int roomNumber) {
        wait(roomLock);
        roomNum = roomNum + roomNumber;
        signal(roomLock);
    }

\end{lstlisting}
\newpage
\section{Problem 5}
\tab I we can use 3 different semaphores with initial value 1 for each data item. Process P and S requires only one semaphore since they only share single data item with other process. However, processes Q and R share two data item therefore they need 2 semaphores.
\begin{lstlisting}[language=C]

    data d1; // shared data item, could be any data
    data d2; // shared data item, could be any data
    data d3; // shared data item, could be any data
    semaphore lock1 = 1;
    semaphore lock2 = 1;
    semaphore lock3 = 1;
/* process P runs in this function */
void *P() {
    wait(lock1);

    //makeCalculation

    signal(lock1);
}

/* process Q runs in this function */
void *Q() {
    wait(lock2);
    wait(lock1);

    //makeCalculation

    signal(lock1);
    signal(lock2);
}

/* process R runs in this function */
void *R() {
    wait(lock2);
    wait(lock3);

    //makeCalculation

    signal(lock3);
    signal(lock2);
}

/* process S runs in this function */
void *S() {
    wait(lock3);

    //makeCalculation

    signal(lock3);
}
\end{lstlisting}
\end{document}

max_stars_repo_name: berkaybarlas/Operating-Systems

max_issues_repo_name: berkaybarlas/Operating-Systems

max_forks_repo_name: berkaybarlas/Operating-Systems