| The Department of Computer Science & Engineering |
CSE 111: Great Ideas in Computer Science |
In computer science, concurrency is the idea of having multiple processors (or cores of processors) working on a single problem simultaneously. Ideally this gives us a speedup proportional to the number of processors. Consider a factory which builds cars. Each person is at their station doing some portion of the work. If we throw more people at the problem, we have to adjust the assembly line so that each person has a smaller job, or we have to add entirely new assembly lines. Either way though, we get a speedup pretty much proportional to the number of people working. Unfortunately this doesn't always work out as planned - some problems aren't as easily parallelized.
Issues in concurrency fall generally into two categories: safety and liveness. When we talk about safety we mean that the concurrent processes aren't destructive to each other. Consider driving - a naturally concurrent process since you're trying to share a single road with many people. A traffic accident is destructive - bad things happened. Therefore it's a safety problem. A traffic jam on the other hand is not destructive - nothing bad happens, just nothing good happens either. That's what we call a liveness problem (source).
The Dining Philosophers Problem:
The dining philosophers problem involves five philosophers sitting around a table, with a fork placed between each pair. They can only do two things - either think or eat. They do not do these two things at the same time. To eat, a philosopher requires two forks. When each philosopher goes to eat, they pick up the fork to their left. Now no philosopher has two forks, so no one can eat.
This is a liveness problem. The same way as a traffic jam is safe but not live (nothing good is happening).
Some ways to solve liveness issues:
Safety issues:
Solving safety issues:
In many computer programming languages there is a concept of locks. A lock is a mechanism where by only one process can access some piece of data at one time. This reduces the opportunity for parallelism (one process is waiting for another to finish), but ensures the interactions will be safe.
The idea is that for something like a paper being edited, it makes no sense for anyone other than the editor to read or write to the file. Reading it is counter productive since it's unfinished, and might be full of incomplete thoughts. Writing to it makes no sense as we discussed above. Part of the challenge is to lock as small a piece of data as possible. Perhaps your friend is working on sections 3-5 of the paper, and you have sections 1-2, well maybe you can each hold locks for those specific sections. The more fine-grained your locking is, the more efficient you can be. It's also possible in some situations (if you're very careful) to achieve reasonable parallelism without locks.
Your task:
Consider the following scenario: You live in a house with three other people. You all have to get ready in the morning to leave at the same time. Two of you are males, and two of you are females. You all shower every day in the morning, and your house contains only one bathroom. You have a rule where everyone gets up at the same time in the morning. How do you parallelize your morning tasks so you all get to sleep as late as possible?
You'll have many things to take into account here. Here are just some examples (you should have more!):
The easiest way to write your solution may be time lines for each person which show what is happening simultaneously. Don't go with your first instincts on this, spend some time really contemplating how you might save even one minute of time. You may want to ask one or more members of the opposite gender what their average time is for each morning task (or even what their morning tasks are!) if your group does not contain mebers of both genders.
You may work in groups of two (2) or three (3) humans. You should turn in your solution to this problem by the start of class Monday, July 18.