\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{}\\ \\ 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}