source: liacs/cvp/java/report/report.tex@ 210

\documentclass[a4paper,12pt]{article}
\usepackage{hyperref}
\usepackage{a4wide}
%\usepackage{indentfirst}
\usepackage[english]{babel}
\usepackage{graphics}
%\usepackage[pdftex]{graphicx}
\usepackage{latexsym}
\usepackage{fancyhdr}
\usepackage{fancyvrb}

\parindent=0cm

\pagestyle{fancyplain}
\newcommand{\tstamp}{\today}
\newcommand{\id}{$ $Id: report.tex 195 2007-05-30 01:04:25Z rick $ $}
\lfoot[\fancyplain{\tstamp}{\tstamp}]   {\fancyplain{\tstamp}{\tstamp}}
\cfoot[\fancyplain{\id}{\id}]           {\fancyplain{\id}{\id}}
\rfoot[\fancyplain{\thepage}{\thepage}] {\fancyplain{\thepage}{\thepage}}


\title{ Concepts of programming languages \\
\large{Assignment 1 - Java}}
\author{Rick van der Zwet\\
  \texttt{<hvdzwet@liacs.nl>}\\
  \\
  LIACS\\
  Leiden Universiteit\\
  Niels Bohrweg 1\\
  2333 CA Leiden\\
  The Netherlands}
\date{\today}
\begin{document}
\maketitle
\section{Introduction}
Analyse on Java program Write two Java programs to get some experience
implementing concurrent programs in Java. 

\section{Analyse Eyes.java}
Compiling and execution of the program is pretty staight forward
\begin{verbatim}
$ javac Eyes.class Eyes.java
\end{verbatim}
A detailed explanation of the program code is found in the Appendix -
Ogen.java \ref{file:Ogen.java}

\section{The Readers/Writer Problem}
\subsection{Problem}
\label{rwproblem}
Two kind processes -readers and writers- share a database. Writers
execute transactions than update the database; reader transactions
access the database without modifying it. The database is assumed
initially to be in a consistend state (i.e one in which relations
between data are meaningfull). Each transaction, if executed in
isolation, transforms the database from one consistent state to another.
To preclude interference between transactions, a writer process must
have exclusive access to the database. Assuming no writer is accessing
the database, any number of readers my concurrently execute
transactions.
\\
To tackle this problem we first have to indentify the main states and
summerize the conditions:
\begin{enumerate}
\item No processes is reading/writing the database \\
Both new read/write processes are allowed to start right away
\item X processes are reading the database \\
A new read process is allowed to start right away, a write process needs to
wait
\item 1 process is writing the database \\
Both new read/write processes need to wait
\end{enumerate}

\subsection{Implementation}
\label{rw-implentation}
To implement this problem we keep track how many processes are reading
the database by using an counter (called Readers), which is incremented
when an reader starts reading and decremented when done. Writing to the
datebase will be locked by a flag (called WriteLocked) stating we are
busy and released when done.
\\\\
When a reader process tries to access the database, it will check
whether the WriteLocked is set free and then increment the Writers, and
decrement the Writers when done else it will wait
\\\\
When a writer process tries to access the database, it will check wether
the WriteLocked is set free, else it will wait. If the WriteLocked is
set free and there are no Readers (e.g Readers = 0), it will lock it
WriteLocked and release when done.
\\\\
The java implemetation is found at first/Database.java~\ref{file:Database.java}

\subsection{Test Suite}
\label{rw-test-suite}
In order to test this implemtation a test program is created. In short
it will create X number of readers and writers using threads to make
them recurrent and have them all access the database
\\\\
The java implemetation is found at RWProblem.java~\ref{file:RWProblem.java}


\section{The Readers/Writer Problem enhanced}
\subsection{Problem}
Implement the Readers/Writers problem (described at~\ref{rwproblem})
giving priority to the writers: i.e. if a writer wants to enter the
database but has to wait then no reader may enter, and of course the
writer still has to wait for current readers in the database to be
finished
\\\\
The main states defined in~\ref{rwproblem} still exists, but the
state 2 is slightly changed
\begin{enumerate}
\item No processes is reading/writing the database \\
Both new read/write processes are allowed to start right away
\item X processes are reading the database \\
A new read process is allowed to start if no writer process is waiting,
a write process needs to wait
\item 1 process is writing the database \\
Both new read/write processes need to wait
\end{enumerate}

\subsection{Implementation}
As the actions are slightly changed, the implementation needs to be
changed a slight little bit as well from the implementation at~
\ref{rw-implentation}. The flag WriterWaiting will indentify wether a
Writer is waiting. A Reader which tries to access the database will now
check wheter both WriteLocked and WriterWaiting are false before reading
is done.
A Writer which try to access the database and find the database locked
by WriteLocked will now set WriterWaiting and start waiting, when a
Writer find WriteLocked to be false it will start running (setting
WriteLocked to be true) and set WriterWaiting to be false.
\\\\
Using this implementation there is only one caveat -which only occurs
when the stack grow that big that not all processes database attemps
are checked during the time of one write- . Take a look at the following
stack order: W(rite), R(ead), R, R, R, W, R, R. and assume the current state
is 1 (no-one reading/writing). Process 1 will set the WriteWaiting flag
to be false, if the write of Process completed, before the next Write is
checked (and the flag WriteWaiting is set again). The read processes are
allowed to start even there is a Write process waiting in the queue
\\\\
The java implemetation is found at second/Database.java~
\ref{file:secondDatabase.java}

\subsection{Test Suite}
Used the same test tool as defined in~\ref{rw-test-suite}

\section{Appendix}

\subsection{Ogen.java}
\label{file:Ogen.java}
\VerbatimInput{../eyes/Ogen.java}
%Newpage
\subsection{first/Database.java}
\label{file:Database.java}
\VerbatimInput{../first/Database.java}
%Newpage
\subsection{second/Database.java}
\label{file:secondDatabase.java}
\VerbatimInput{../second/Database.java}
%Newpage
\subsection{RWProblem.java}
\label{file:RWProblem.java}
\VerbatimInput{../first/RWProblem.java}
%Newpage

\end{document}