Java, request queues
The basic idea is that, for each resource, there\'s a queue of tasks that request to use the resource.\n\n      resource1 [taskA]\n\t  resource2 [taskA, taskB]\
The basic idea is that, for each resource, there\'s a queue of tasks that request to use the resource.\n\n      resource1 [taskA]\n\t  resource2 [taskA, taskB]\n\t  resource3 [taskB]\n\nFor a new task, append it to the queue of each resource that the task requires.\n\nIf a task is at the head of every queue of its required resources, it owns all the resources; the tasks can now execute. In the example above, taskA owns resource1 and resource2, and taskA can run.\n\nWhen a running tasks is finished, remove itself from all queues. In the example above, after taskA is done, taskB becomes the head of its queues, and taskB can run.\n\nIn the example above, taskB depends on taskA. Task dependencies form a DAG. All tasks will be executed, fairly, in topological order. \n\nHowever, parallelism may not be optimal in some cases. For example, if taskC is added which requires resource3 and resource4, taskC cannot execute now, even though both resources are not used by anyone at the moment; taskC must wait for taskB. We may try reordering waiting tasks in the queues to enhance resource usage. On the other hand, we don\'t want starvation. If a task has been delayed for too long, it cannot be delayed further.\n\n```\n    class DiningPhilosophers {\n\n        final static int N = 5;\n        final Object lock = new Object();\n        final HashMap<Integer, LinkedList<Integer>> queues = new HashMap<>();\n\n        public DiningPhilosophers() {\n\n            synchronized (lock){\n                for(int i=0; i<N; i++)\n                    queues.put(i, new LinkedList<>());\n            }\n        }\n\n        boolean owns(int task, int... resources){\n            for(int resource : resources){\n                if(queues.get(resource).peekFirst()!=task)\n                    return false;\n            }\n            return true;\n        }\n\n        // call the run() method of any runnable to execute its code\n        public void wantsToEat(int philosopher,\n                               Runnable pickLeftFork,\n                               Runnable pickRightFork,\n                               Runnable eat,\n                               Runnable putLeftFork,\n                               Runnable putRightFork) throws InterruptedException {\n\n            final int task = philosopher;\n            final int[] resources = {philosopher, (philosopher+1)%N}; // i.e. forks\n\n            synchronized (lock){\n                for(int resource : resources)\n                    queues.get(resource).addLast(task);\n\n                while(!owns(task, resources))\n                    lock.wait();\n            }\n\n            {\n                pickLeftFork.run();\n                pickRightFork.run();\n                eat.run();\n                putLeftFork.run();\n                putRightFork.run();\n            }\n\n            synchronized (lock){\n                for(int resource : resources)\n                    queues.get(resource).removeFirst();\n                lock.notifyAll();\n            }\n        }\n    }```
[]