Number the philosophers clockwise from $p_0 \ldots p_4$ such that $p_0$ is the one that tries for the right chopstick first. Number the chopsticks $c_0 \ldots c_4$ such that $c_i$ is to the left of $p_i$.

Assume the system is deadlocked. Therefore all philosophers are blocked waiting for a chopstick. Therefore philosopher $p_1$ is blocked. There are two cases to consider. Either $p_1$ is waiting for their first (left) chopstick, $c_1$, or their second (right) chopstick, $c_0$.

• Case 1: If $p_1$ is waiting for $c_1$, then $p_2$ has it. But $c_1$ is $p_2$’s right (second) chopstick, so $p_2$ is eating and the system is not deadlocked.
• Case 2: If $p_1$ is waiting for $c_0$, then $p_0$ has it. But $c_0$ is $p_1$’s left (second) chopstick, so $p_0$ is eating and the system is not deadlocked.

Thus if we assume the system is deadlocked, then it is not deadlocked. Therefore deadlock is impossible.

This problem is a really good fit for the Ada Rendezvous, as threads message each other.

with Ada.Text_IO;
use Ada.Text_IO;

procedure Concurrent_Sieve is
   Last: constant Natural := 1000;

   -- A Filter is a task corresponding to a particular value, Divisor, which
   -- when asked to check whether a value N is divisible by Divisor passes it
   -- it along if it does not.
   task type Filter (Divisor: Natural) is
      entry Check_Divisible (N: Natural);
   end Filter;

   -- This function looks unnecessary but it really is necessary. You
   -- might think that in the body of a Filter task you could just write
   -- "new Filter" but there is some stupid rule about the task type name
   -- in the task body referring to the currently executing task object
   -- of that type. #Shrug
   function New_Filter (D: Natural) return access Filter is
   begin
      return new Filter(D);
   end New_Filter;

   task body Filter is
      Test: Natural;                          -- value being tested
      Next: access Filter;                    -- pointer to next prime task
   begin
      Put (Natural'Image(Divisor));           -- Divisor is prime; write it
      loop
         select
            accept Check_Divisible (N: Natural) do
               Test := N;
            end Check_Divisible;
            if Test rem Divisor /= 0 then     -- not divisible; maybe prime
               if Next /= null then           -- if there are more divisors
                  Next.Check_Divisible(Test); -- pass it to next filter
               else                           -- otherwise
                  Next := New_Filter(Test);   -- it is prime
               end if;
            end if;
         or
            terminate;                        -- this JUST WORKS, love it
         end select;
      end loop;
   end Filter;

   First_Filter: access Filter := new Filter(2);
begin
   for I in 2 .. Last loop
      First_Filter.Check_Divisible(I);
   end loop;
end Concurrent_Sieve;

Java doesn’t really do message passing directly, so the trick is to use a shared blocking queue between each thread. I’m not sure of the best way to shut everything down correctly; this -1 is a real hack. It would have been nice to use virtual threads, but these would all need to have been joined.

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class ConcurrentSieve {
    private static final int LIMIT = 1000;

    private static class Filter implements Runnable {
        private final int divisor;
        private final BlockingQueue<Integer> queue;

        public Filter(int divisor) {
            this.divisor = divisor;
            this.queue = new LinkedBlockingQueue<>();
            Thread.ofPlatform().start(this);
        }

        public void checkIfDivisible(int n) throws InterruptedException {
            this.queue.put(n);
        }

        public void finish() throws InterruptedException {
            queue.put(-1);
        }

        @Override
        public void run() {
            System.out.println(this.divisor);
            try {
                Filter next = null;
                while (true) {
                    Integer n = queue.take();
                    if (n == -1) break;
                    if (n % divisor == 0) continue;
                    if (next == null) next = new Filter(n);
                    else next.checkIfDivisible(n);
                }
                if (next != null) next.finish();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        var firstFilter = new Filter(2);
        for (int i = 3; i < LIMIT; i++) {
            firstFilter.checkIfDivisible(i);
        }
        firstFilter.finish();
    }
}

We have to use both channels and goroutines to implement the sieve concurrently, but it’s all fairly natural in Go. Shutting down and waiting are the big things here. At least the built-in close function is present. It’s so much better than that silly -1 I used in the Java solution.

package main

import (
    "fmt"
    "sync"
)

const limit = 1000

var wg sync.WaitGroup

// Each prime number has an associated goroutine that filters out
// all multiples of that prime from the input channel.
func filter(in <-chan int) {
    defer wg.Done()

    // The first thing you read on the channel is a prime number.
    // But this may be the last one, in which case the previous
    // filter will have closed this channel, so we have to check
    // for this and terminate gracefully if so.
    prime, ok := <-in
    if !ok {
        return
    }
    fmt.Println(prime)

    // Now make a goroutine and an output channel to which we will send
    // out all the numbers that are not multiples of this one.
    out := make(chan int)
    wg.Add(1)
    go filter(out)
    for n := range in {
        if n%prime != 0 {
            out <- n
        }
    }

    // We have to close after we've sent everything out, otherwise we'd deadlock
    close(out)
}

func main() {
    // Create a channel to send candidates to the first filter
    firstChannel := make(chan int)

    // Start the first filter
    wg.Add(1)
    go filter(firstChannel)

    // Send numbers from 2 to limit to the first filter. Make sure
    // to close after sending all candidates, so all the goroutines
    // know when to finish cleanly.
    for i := 2; i < limit; i++ {
        firstChannel <- i
    }
    close(firstChannel)

    wg.Wait()
    fmt.Println("All primes printed")
}