Your process description seems to suggest that P1 needs data read by P3 (c1), P2 needs data read by P3 (c2), and P3 needs data read by P1 and P2 (a2 and b1).
So, is this what needs to happen (where * can occur anytime after 2):
- P1 <- read a1
- P3 <- read c1
- P3 <- read c2
- P2 <- read b1 and b2
*. P1 <- read a2
Or do P1, P2, and P3 use a cache of the last value read in the other process?
If the latter, you just need one mutual exclusion semaphore to control access to the device. If the former, you can have a fourth process that handles reading all the data and synchronize on when a valid set is available for all the use and when the data set has been read by all parties.
The fourth process doesn't have to know ahead of time what the data to be read is, it can simply implement a message queue where P1, P2, and P3 send it the parameters for data to be read. It then incrementes a counting semaphore each time it completes reads from each process. After sending their read message, everyone waits until the "data ready" semaphore reaches 3, then knows a valid set of data is available. After doing a read, they in turn increment a "data read" semaphore and wait for it to reach 3. When it does, they then wait on the "data ready" semaphore to go to 0 (the fourth process handles this after everyone has signaled their read, setting the "data ready" semaphore back to 0 then the "read data" semaphore back to 0. and the whole process repeats itself. Note, you'd never have a case where a process could miss the transition back to zero (deadlock) since each process needs to signal that their read is complete before the wait for "data ready" to go to zero by the time the third process gets around to doing it's read.
So, bottom line, you should be able to implement this with either 1 semaphore or 2 depending on what your requirements are for a concurrent set of data.
EDIT - Reviewing this, the "data ready" semaphore doesn't need to be a counting one since the thread with sole ownership of the input device can simply keep an internal count and just signal once when a complete data set is ready.
After a little browsing, I created my own solution a few months back but failed to post it here in the interest of anybody that would like to do the same. Therefore, I will quickly describe the method before showing the code. It's in kotlin, but if you're familiar with Java and/or AS3 you should be able to understand the syntax.
The Method
- Scan the entire image and store each color in a table.
- Determine which color shows up most often- this is the background color
- Start at the top left and scan each line.
- If a pixel does not match the background color, then it is a sprite.
- Use a backtracking algorithm to "fill out" the entire sprite.
- Create a rectangle out of this plot.
- Store it and cut the sprite out of the image.
- Repeat 4-7 until finished.
The Code
The source is available on github, and here is the code w/o documentation or imports.
fun unpack(spriteSheet: Path): List<Image> {
Preconditions.checkArgument(Files.exists(spriteSheet),
"The file ${spriteSheet.getFileName()} does not exist")
logger.debug("Loading sprite sheet.")
// TODO: Convert to png so we have an alpha layer to work with
val spriteSheetImage = readImage(spriteSheet).toBufferedImage()
logger.debug("Determining most probable background color.")
val backgroundColor = determineProbableBackgroundColor(spriteSheetImage)
logger.debug("The most probable background color is $backgroundColor")
return findSprites(spriteSheetImage, backgroundColor) map(::copySubImage.bindFirst(spriteSheetImage))
}
private fun findSprites(image: BufferedImage,
backgroundColor: Color): List<Rectangle> {
val workingImage = copy(image)
val spriteRectangles = ArrayList<Rectangle>()
for (pixel in workingImage) {
val (point, color) = pixel
if (color != backgroundColor) {
logger.debug("Found a sprite starting at (${point.x}, ${point.y})")
val spritePlot = findContiguous(workingImage, point) { it != backgroundColor }
val spriteRectangle = Rectangle(spritePlot, image)
logger.debug("The identified sprite has an area of ${spriteRectangle.width}x${spriteRectangle.height}")
spriteRectangles.add(spriteRectangle)
eraseSprite(workingImage, backgroundColor, spritePlot)
}
}
logger.info("Found ${spriteRectangles.size()} sprites.")
return spriteRectangles
}
private fun findContiguous(image: BufferedImage, point: Point, predicate: (Color) -> Boolean): List<Point> {
val unvisited = LinkedList<Point>()
val visited = HashSet<Point>()
unvisited.addAll(neighbors(point, image) filter { predicate(Color(image.getRGB(it.x, it.y))) })
while (unvisited.isNotEmpty()) {
val currentPoint = unvisited.pop()
val currentColor = Color(image.getRGB(currentPoint.x, currentPoint.y))
if (predicate(currentColor)) {
unvisited.addAll(neighbors(currentPoint, image) filter {
!visited.contains(it) && !unvisited.contains(it) &&
predicate(Color(image.getRGB(it.x, it.y)))
})
visited.add(currentPoint)
}
}
return visited.toList()
}
private fun neighbors(point: Point, image: Image): List<Point> {
val points = ArrayList<Point>()
if (point.x > 0)
points.add(Point(point.x - 1, point.y))
if (point.x < image.getWidth(null) - 1)
points.add(Point(point.x + 1, point.y))
if (point.y > 0)
points.add(Point(point.x, point.y - 1))
if (point.y < image.getHeight(null) - 1)
points.add(Point(point.x, point.y + 1))
return points
}
However, the code is not yet complete- packing and creating the metafile is missing- and has been languishing in my Github since March, but I'll hopefully complete it one day.
Best Answer
Yes it's a deadlock, diagram the wait chain of processes (1 -> 2 indicates P1 waiting on P2 to release a resource):
1 -> 3 -> 4 -> 2 -> 1
Ran back into 1 in the wait chain and the cycle is complete; that is 1 is waiting on resources that are waiting on resources that are waiting on 1.
If following 1 like this didn't run back into itself then it would be accurate to say 1 is not in a deadlock (for instance if it was 1->3->4->2). However if one were not in a deadlock that does not prove or indicate none of the others are in dead locks. To verify none of the resources are in a deadlock you would need to graph the same chain with any nodes that weren't in the critical path for 1 (if any in the critical path were in a deadlock then 1 would be, so you know all members of it's dependency chain are not in deadlocks). Since 5 isn't in the critical path you would have to next follow 5's path if 1 wasn't in a deadlock (incidentally 5 is also in a deadlock because it links into the same cycle 1 is in, therefore all listed resources are deadlocked in that cycle)
Another point regarding this particular problem is that all resources available (the set of R1-R5) are already acquired. In such a scenario it is impossible for any process to acquire another resource if no processes are willing to first let go of a resource. A cycle is inevitable in such a scenario. This fact that you should release resources before requesting more is I think supposed to be the lesson of the 73.4 philosophers problem (don't quote me on that)