This particular case of fine-grained locking is manageable with a \textit{hand-over-hand} approach, which would
surely work, but some latency problems could occur.
In such a structure the next element is accessible only from the preceiding, thus in order to remove a specific element
all the preceiding ones must be selected first. In principle, each thread locks the current and the preceiding object advancing in the linked list.
In case of two thread concurrency trying to remove close elements, the first thread would wait for the second to advance
each step causing a non-negligible latency. When more then two threads are involved, a large queue of locked object is generated preventing updates that wouldn't cause any problem.
Secondly, for a list of size $N$, the removal operation takes a $\Theta(N)$ time and seen that the operation is read-only
until it finds the required element, then it would progressively lock any object in its path even if not really needed.
Finally, the probability that two threads could conflict is $P_{conf} =\left(\frac{1}{N}\right)^2$,
meaning that for large $N$ it's very improbable, then much waiting latency is in most of times generated for non-conflicting cases.
LL/SC and HLE share basically the same principle: protect a critical section which is submitted to coherence traffic.
The difference stands on the implementation: while LL/SC uses a single register $X$ to store the lock state,
HLE uses the LSQ instead.
In LL/SC, if the register $X$ hits and it's $0$, then execute the critical section.
In HLE protocol, the speculative addresses are kept in the LSQ and if
the access corresponds to a cache hit, then execute the critical memory operations and retire.
\end{homeworkSection}
\begin{homeworkSection}{(3)}
A lock elision needs to rollback in presence of coherence traffic and modification of the lock register, in other words, when another core has access to the lock register \texttt{LCK} and trying to load it results in a cache miss.
If the missed load of \texttt{LCK} returns 0, then speculation can safely continue, otherwise elision fails.
% TODO NON SICURO
The other case of failure is related to the ROB size: if ROB is unable to contain the whole critical section, then
\texttt{ST LCK}, which should be the last enclosing operation, wouldn't be present.
\end{homeworkSection}
\begin{homeworkSection}{(4)}
The structure of a transactional memory is thought to allow independent writing without risk of conflicts in a local
portion of memory and then, only after, interact with other threads committing transactions.
\paragraph{Atomicity:}
In case of all transactions have been committed correctly, all writes are performed in a single time.
Otherwise, if a commit is aborted, then nothing happens. Each commit is supposed to be independent and
can be aborted in any moment, thus all effective writes are managed by a superior process guaranteeing this property.
\paragraph{Isolation:}
This characteristic is equivalent to locality, in the sense that a core is able to modify its portion
and the written memory is not visible to other cores until it's committed.
\paragraph{Serializability:}
Strictly related to atomicity, each emitted transaction is globally visible as an element of a queue or of a stack,