\documentclass[runningheads,a4paper]{llncs}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{algpseudocode}

\begin{document}

\begin{minipage}{\textwidth}
\title\textbf{Synchronisation Mechanisms Lab Assignment Technical Report}
\newline
\newline
\newline
Student: Theodora-Ioana Danciulescu, CEN 3.1
\end{minipage}

\section{Problem statement}
The statement of this problem is to implement the producer-consumer concurrency problem. The idea of the problem is that there exists a type of producer thread and a type of consumer thread. The two types of threads share the same buffer, as one of the threads has to store elements int the buffer and the others to remove elements from the buffer.
\newline One important aspect to take into consideration is that the size of the buffer is finite, so if the buffer is full no elements can be added, and if the buffer is empty, no elements can be extracted.
\newline The elements that are stored in the buffer are random English alphabet letters. Every producer and consumer threads are assigned a number of letters to produce and to consume, respectively.
\newline The quantity assigned to each thread is computed in the following way: if there are \textit{P} producers, the size of the buffer is \textit{N}. Let $N = pq + r$, where \textit{q} and \textit{r} represents the  result by dividing \textit{N} to \textit{P} and respectively the remainder of the division of \textit{N} to \textit{P}.
\newline In the same way is happening in the consumer threads case.
\newline Note: $P < N$, $C < N$.

\section{Implementation}

\subsection{Semaphores Method}

\indent The memory usage of the program in big lines consists of 2 arrays where the producer and consumer threads are stored, the queue data structure used as a buffer for the thread and various variables for sharing data between classes. The time execution for one set of 10 data inputs is

\begin{figure}[H]
  \includegraphics[width=\linewidth]{exec_time.png}
  \label{fig:execution time}
\end{figure}

The classes used:

\begin{itemize}
    \item \textbf{Main.java} - Initially computes the number of letters that each thread should produce/consume according to the formulas in the problem statement. Here is the \textit{main function} that creates the necessary objects for generating input file, created the correspondent threads and starts them, then all the threads are being waited to be finished in order to collect data report from each thread and analyze the global result.
    \item \textbf{InputGenerator.java} -  This class represents the input generator for our problem.
    \newline
    \begin{itemize}
        \item \textbf{GenerateBufferSize} - Method that is returning random integer in interval [1, 1000] that represents the size of the buffer
        \item \textbf{GenerateProducersConsumersNumber} - Method that is returning a pair of random integers in interval [1, 1000] that represent the number of producers consumers respectively. The number of producers and consumers is known from the problem statement that is lower than the size of the buffer.
        \item \textbf{GenerateInputFile} - Method that returns a .txt file containing 10 rows with 3 integers on every line representing the size of the buffer, the number of producers and the number of consumers.
    \end{itemize}
    \item \textbf{ProducerThread} -  This class represents the producer behaviour. This class extends the \textit{Thread} class. The \textit{run} method is generating the assigned number of letters to produce and calls the \textit{produce} method.
    \item \textbf{ConsumerThread} - This class represents the consumer behaviour. This class extends the \textit{Thread} class. The \textit{run} method calls the \textit{consume} method for the number of times the respective thread has be assigned to consume.
    \item \textbf{MyBuffer} - This class represents the queue that stores the items/objects for the two threads that produce and/or consume.
    \begin{itemize}
        \item A queue data structure represents the shared memory space between the threads. When a letter is produced it is added to the top of the queue and when a letter is consumed if removed from the end of the queue.
        \item Semaphore for producers with N number of permits
        \item  Semaphore for consumers, initially 0 because we need to wait for at least 1 element to be produced.
        \item \textbf{produce} - this method is a synchronized method as it is essentially to allow access to the shared memory space to only one process at a time. This method adds a letter to the buffer. It releases the consumer semaphore because after each added item a consumer can use it.
        \begin{algorithm}[H]
        \caption{produce}
        \algblock[TryCatchFinally]{try}{endtry}
        \algcblock[TryCatchFinally]{TryCatchFinally}{finally}{endtry}
        \algcblockdefx[TryCatchFinally]{TryCatchFinally}{catch}{endtry}
	    [1]{\textbf{catch} #1}
	{\textbf{end try}}
        \begin{algorithmic}[1]
        \try
            \State{acquire semaphoreProducer}
            \IF{ buffer not full }
                \State{add to buffer}
                \State{print \textit{letter was added}}
            \ENDIF
        \catch
            exception
        \finally
           \State{release semaphoreConsumer}
        \endtry
        \end{algorithmic}
        \end{algorithm}
    \end{itemize}
\end{itemize}

\subsection{Monitors Method}

\indent The memory usage of the program in big lines consists of 2 arrays where the producer and consumer threads are stored, the queue data structure used as a buffer for the thread and various variables for sharing data between classes. The time execution for one set of data input is

\begin{figure}[H]
  \includegraphics[width=\linewidth]{exec_time2.png}
  \label{fig:execution time}
\end{figure}

The classes used:

\begin{itemize}
    \item \textbf{Main.java} - Initially computes the number of letters that each thread should produce/consume according to the formulas in the problem statement. Here is the \textit{main function} that creates the necessary objects for generating input file, created the correspondent threads and starts them, then all the threads are being waited to be finished in order to collect data report from each thread and analyze the global result.
    \item \textbf{InputGenerator.java} -  This class represents the input generator for our problem.
    \newline
    \begin{itemize}
        \item \textbf{GenerateBufferSize} - Method that is returning random integer in interval [1, 1000] that represents the size of the buffer
        \item \textbf{GenerateProducersConsumersNumber} - Method that is returning a pair of random integers in interval [1, 1000] that represent the number of producers consumers respectively. The number of producers and consumers is known from the problem statement that is lower than the size of the buffer.
        \item \textbf{GenerateInputFile} - Method that returns a .txt file containing 10 rows with 3 integers on every line representing the size of the buffer, the number of producers and the number of consumers.
    \end{itemize}
    \item \textbf{ProducerThread} -  This class represents the producer behaviour. This class extends the \textit{Thread} class. The \textit{run} method is generating the assigned number of letters to produce.
    \begin{itemize}
        \item This String represents the alphabet from which we choose the random letters to produce.
        \item Reference to the queue that represents the buffer
        \item \textbf{run} - The method that generates a random letter from the alphabet string and then adds it to the buffer. It contains a synchronized block as the queue is a shared memory resource between more processes.

        \begin{algorithm}[H]
        \caption{run}
        \algblock[TryCatchFinally]{try}{endtry}
        \algcblock[TryCatchFinally]{TryCatchFinally}{finally}{endtry}
        \algcblockdefx[TryCatchFinally]{TryCatchFinally}{catch}{endtry}
	    [1]{\textbf{catch} #1}
	{\textbf{end try}}
        \begin{algorithmic}[1]
        \State{synchronized(buffer)}
        \WHILE{running}
            \State{$letter = random letter $}
        \WHILE { buffer is full }
        \try
            \State{wait}
        \catch
            exception
        \endtry
        \ENDWHILE
        \State{print letter was added}
        \State{add letter to buffer}
        \IF{produced the  assigned number of letters}
            \State{$running = false$}
        \ELSE
            \State{NotifyAll)
        \ENDIF
        \ENDWHILE
        \end{algorithmic}
        \end{algorithm}

    \end{itemize}
    \item \textbf{ConsumerThread} - This class represents the consumer behaviour. This class extends the \textit{Thread} class. The \textit{run} method calls the \textit{consume} method for the number of times the respective thread has be assigned to consume.
    \begin{itemize}
        \item Reference to the queue that represents the buffer
        \item \textbf{run} - The method that generates a random letter from the alphabet string and then adds it to the buffer. It contains a synchronized block as the queue is a shared memory resource between more processes.

        \begin{algorithm}[H]
        \caption{run}
        \algblock[TryCatchFinally]{try}{endtry}
        \algcblock[TryCatchFinally]{TryCatchFinally}{finally}{endtry}
        \algcblockdefx[TryCatchFinally]{TryCatchFinally}{catch}{endtry}
	    [1]{\textbf{catch} #1}
	{\textbf{end try}}
        \begin{algorithmic}[1]
        \State{synchronized(buffer)}
        \WHILE{running}
            \State{$letter = random letter $}
        \WHILE { buffer is empty }
        \try
            \State{wait}
        \catch
            exception
        \endtry
        \ENDWHILE
        \State{print letter was removed}
        \State{remove letter from buffer}
        \IF{consumed the  assigned number of letters}
            \State{$running = false$}
        \ELSE
            \State{NotifyAll)
        \ENDIF
        \ENDWHILE
        \end{algorithmic}
        \end{algorithm}

    \end{itemize}

\end{itemize}

\subsection{Locks Method}

\indent The memory usage of the program in big lines consists of 2 arrays where the producer and consumer threads are stored, the queue data structure used as a buffer for the thread and various variables for sharing data between classes. The time execution for one set of 10 data inputs is

\begin{figure}[H]
  \includegraphics[width=\linewidth]{exec_time3.png}
  \label{fig:execution time}
\end{figure}

The classes used:

\begin{itemize}
    \item \textbf{Main.java} - Initially computes the number of letters that each thread should produce/consume according to the formulas in the problem statement. Here is the \textit{main function} that creates the necessary objects for generating input file, created the correspondent threads and starts them, then all the threads are being waited to be finished in order to collect data report from each thread and analyze the global result.
    \item \textbf{InputGenerator.java} -  This class represents the input generator for our problem.
    \newline
    \begin{itemize}
        \item \textbf{GenerateBufferSize} - Method that is returning random integer in interval [1, 1000] that represents the size of the buffer
        \item \textbf{GenerateProducersConsumersNumber} - Method that is returning a pair of random integers in interval [1, 1000] that represent the number of producers consumers respectively. The number of producers and consumers is known from the problem statement that is lower than the size of the buffer.
        \item \textbf{GenerateInputFile} - Method that returns a .txt file containing 10 rows with 3 integers on every line representing the size of the buffer, the number of producers and the number of consumers.
    \end{itemize}
    \item \textbf{ProducerThread} -  This class represents the producer behaviour. This class extends the \textit{Thread} class. The \textit{run} method is generating the assigned number of letters to produce and calls the \textit{produce} method.
    \item \textbf{ConsumerThread} - This class represents the consumer behaviour. This class extends the \textit{Thread} class. The \textit{run} method calls the \textit{consume} method for the number of times the respective thread has be assigned to consume.
    \item \textbf{MyBuffer} - This class represents the queue that stores the items/objects for the two threads that produce and/or consume.
    \begin{itemize}
        \item A queue data structure represents the shared memory space between the threads. When a letter is produced it is added to the top of the queue and when a letter is consumed if removed from the end of the queue.
        \item  ReentrantLock - This variable represents the lock of the threads, it allows only 1 thread at a time in the critical section.
        \item  bufferNotEmpty, bufferNotFull - These variables represent the condition signa that allows the consumer to start again being sure that the buffer is not empty and respectively the condition signal that allows the producer to start again being sure that the buffer is not full.
        \item \textbf{produce} - This method adds a letter to the buffer,it takes the lock, produce, signal and then unlocks the lock.
        \begin{algorithm}[H]
        \caption{produce}
        \algblock[TryCatchFinally]{try}{endtry}
        \algcblock[TryCatchFinally]{TryCatchFinally}{finally}{endtry}
        \algcblockdefx[TryCatchFinally]{TryCatchFinally}{catch}{endtry}
	    [1]{\textbf{catch} #1}
	{\textbf{end try}}
        \begin{algorithmic}[1]
        \State{lock the lock}
        \try
            \WHILE{ buffer is full }
                \State{await 10 milliseconds condition bufferNotFull}
                \RETURN
            \ENDWHILE
            \State{add letter to buffer}
            \State{signall all bufferNotEmpty}
        \catch
            exception
        \finally
           \State{unlock the lock}
        \endtry
        \end{algorithmic}
        \end{algorithm}

        \item \textbf{consume} - This method removes the first element from the buffer.It takes the lock, checks if the buffer is empty,awaits for the buffer not to be empty and then consumes the objects unlocking the lock.
        \begin{algorithm}[H]
        \caption{consume}
        \algblock[TryCatchFinally]{try}{endtry}
        \algcblock[TryCatchFinally]{TryCatchFinally}{finally}{endtry}
        \algcblockdefx[TryCatchFinally]{TryCatchFinally}{catch}{endtry}
	    [1]{\textbf{catch} #1}
	{\textbf{end try}}
        \begin{algorithmic}[1]
        \State{lock the lock}
        \try
            \WHILE{ buffer is empty }
                \State{await 10 milliseconds condition bufferNotEmpty}
                \RETURN
            \ENDWHILE
            \State{remove letter from buffer}
            \State{signall all bufferNotFull}
        \catch
            exception
        \finally
           \State{unlock the lock}
        \endtry
        \end{algorithmic}
        \end{algorithm}
    \end{itemize}
\end{itemize}


%
%

\end{document}

\section{Experiments and results}

\subsection{Semaphores Method}