36 lines
2.8 KiB
TeX
36 lines
2.8 KiB
TeX
\documentclass[12pt,a4paper]{article}
|
|
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage[margin=2cm]{geometry}
|
|
|
|
\title{Howework 2 -- Programming Fundamentals 3}
|
|
\author{Claudio Maggioni}
|
|
|
|
\begin{document}
|
|
\maketitle
|
|
\tableofcontents
|
|
\section{Exercise 1}
|
|
\subsection{Question 2}
|
|
Results returned by \texttt{BinTreeSimple} are wrong since the class is not thread safe. In particular, \texttt{BinTreeSimple.insert(int)} has race conditions on the integer field occ of each node, and the fields left and right on each node. To fix this, an AtomicInteger could be used for occ and access on n.left and n.right could be synchronized.
|
|
|
|
\subsection{Question 3: Note on implementation}
|
|
I have implemented the class \texttt{BinTreeFullSync}
|
|
as a thread-safe alternative of \texttt{BinTreeSimple} where the only code modification between the two were the addition of \texttt{synchronized} keywords on already existing threads. Since I was not sure how to interpret this specific question, I have implemented \texttt{BinTreeFullSyncEdited}, a thread-safe refactoring of \texttt{BinTreeSimple} where the only synchronization mechanism is method-level \texttt{synchronized} blocks, which are used on new methods created in the subclass \texttt{Node}.
|
|
|
|
\subsection{Question 5}
|
|
\texttt{BinTreeFullSync} has the worst performance of all 3 implementations since it allows only sequential access to the tree structure. \texttt{BinTreeFullSyncEdited} is slightly faster, but \texttt{BinTreeCAS} is the fastest since the first one is a \texttt{synchronized} block imitation of the second one, which is instead based on \texttt{Atomic*} objects and can use the extra speed provided by architecture based optimization.
|
|
|
|
\section{Exercise 2}
|
|
\subsection{Question 1}
|
|
\texttt{SimpleVoteCounter} behaves incorrectly since its implementation is not thread-safe: the \texttt{Map} implementation is not thread-safe, and the \texttt{addVote(Integer)} method is also not thread safe since its operation of access, conditional computation and storage is not atomic nor synchronized.
|
|
|
|
\subsection{Question 2}
|
|
\texttt{SyncMapVoteCounter} is still not thread safe since \texttt{addVote(Integer)} is still not synchronized. This means that two threads may assess that a candidate has no vote at almost the same time and count the first vote twice.
|
|
|
|
\subsection{Question 3}
|
|
\texttt{LockVoteCounter} is thread safe since only a thread at a time can either add a vote or get the votes for a candidate. However, this type of synchronization is inefficient since concurrent accesses to the number of votes of a candidate are safe if no other thread is casting a vote.
|
|
|
|
\subsection{Question 4}
|
|
As with \texttt{SyncMapVoteCounter}, \texttt{ConcurrentVoteCounter} is not thread safe since the operation of casting a vote is not atomic nor synchronized.
|
|
\end{document}
|