[Konkurens] Improved Pipeline3 and benchmark for wait-notify (vs polling)

[Menczer Andor]

Hi Everyone,

I uploaded two new files to SVN. One is a new program that might be useful
to help students understand the need for wait-notify. The other one is an
improved version of a 4 year old lab task.

*Alarm.java*

It's a simple benchmark comparing busy waiting (nonstop polling), polling
with an interval and wait-notify. There's an "arsonist" thread that waits a
little in the beginning and then flips the 'isBurning' boolean. The main
thread is waiting for this event in various ways. The time between the
arsonist flipping the bit and the main thread noticing the change is
printed to the screen.

There's also a decoy thread that just sends a notify(), but without
flipping the flag. This is there to demonstrate the code would be unsafe
without a while loop guarding the wait() call.

Students can use "top" or "task manager" to check cpu utilisation during
execution. Essentially the lesson to be learned here is that there is no
"bad" and "good" way to implement a wait mechanism. There are pros and cons
to each solution. While wait-notify might seem to be superior to interval
polling, this requires inter-thread communications, while a simple polling
mechanism is more autonomous and does not rely on other threads and their
signalling behaviour.

svn: plc.inf.elte.hu/konkurens/repos/BSc/labs/misc/Alarm

*Pipeline3v2.java*

The original Pipeline3 is imo the best lab task for blocking queues and
pipelines. Unfortunately the original skeleton and solution are both flawed
in design.

The point of a pipeline is that data can continuously flow through, as if
it was an actual hose between a water source (eg outdoor tap) and a water
drain (eg swimming pool). The hose only buffers a small fraction of all the
water. The water is not only continuously flowing from the first queue to
the last queue, but the pipeline also takes water from the source
continuously and drains into the sink continuously. Therefore putting all
numbers into the first queue is *bad design*. Letting all the numbers
accumulate in the last queue is also *bad design*. The program is supposed
to work even with buffer sizes as small as a single number.

To remedy this problem, filling the first queue with 3, 5, 7,9 , etc.
should be running on a seperate thread and in parallel to all other
callables. Same goes for the output. Instead of draining the last queue in
a single operation, it should be a while loop that is continuously running
on its own thread.

Max integer is a valid input and should not be used as a special value.
Instead we could, for example, use the number "1".

The program should work even if no valid numbers reach the last few stages
(they are all filtered in the first half of the pipeline).

The original skeleton and solution incorrectly calls the non-filtered
numbers reaching the end of the pipeline "remainingPrimes". This is
incorrect. If the prime factorization of a non-prime integer does not
contain a small enough prime, then the number will survive the pipeline and
reach the last queue. If we have n stages, then we will only find the first
n primes (starting with 3), so if a non-prime has prime factors all larger
then the n-th prime (starting with 3), then the number will *not* get
filtered. The array holding the surviving numbers should be called
"remainingNumbers", and not "remainingPrimes".

Not really a problem, but using streams, multiple lambda expressions and
functions as arguments only to create a list of blocking queues feels like
getting rid of a mouse infestation with a hydrogen bomb. Technically it
works, but I think we should teach students that writing the simplest code
possible, unless there is a clear reason not to, is preferred. Simple code
is more likely to work the first time, easier to debug and extend in the
future. In other words, increasing code complexity just to show off our
java skills is a bad thing. To put it plainly:

   - Solving complicated problems with simple code → good
   - Solving simple problems with complicated code → bad

As I have already stated, despite its quirks, Pipeline3 is still my
favourite lab task. But that doesn't mean we shouldn't improve things as
time goes on. I'm pretty sure my version is also far from the best, so feel
free to make improved versions or create a better lab task from scratch as
a replacement.

Thanks for reading all this,
Andor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://plc.inf.elte.hu/pipermail/konkurens/attachments/20251120/c4675eb7/attachment.htm>