2.1.5 - Concurrent thinking and dependencies
Some work can overlap, while other work must wait for data or shared resources. You will identify independence, plan a schedule under stated assumptions, and judge the benefits and costs of concurrent processing in a concrete program.
Identify which tasks can overlap safely
Concurrent processing allows tasks to make progress during overlapping time periods. On multiple processing resources, tasks may execute in parallel, at the same instant. A single core can instead interleave tasks; concurrency alone does not guarantee simultaneous execution or a shorter total computation time.
To think concurrently, decompose the problem and inspect what each task reads and writes. A dependency means a task requires another task's completed result or an established condition. Tasks are independent for a proposed overlap when neither requires the other's unfinished result and their resource/data use can coexist safely.
An image-report program first loads an image (L). It then calculates a histogram (H) and makes a thumbnail (T), each reading the same unchanged loaded image. Finally it assembles the report (R), which needs both outputs. H and T can overlap after L. Neither can start before the image exists, and R must wait for both. Reading the same immutable data is not by itself a conflict; unsynchronised writes to the same changing data may be.
| Task | Required completed tasks |
|---|---|
| L: load image | None |
| H: histogram | L |
| T: thumbnail | L |
| R: assemble report | H and T |
The dependency relationships are L before H, L before T, H before R and T before R. “The tasks have different names” is not evidence of independence. If thumbnail generation modified the source image in place, histogram results could depend on when those modifications occurred; the design would need a safe copy or ordering rule.
Calculate a schedule from the dependencies
A concurrent schedule must respect both dependencies and available resources. A task cannot start simply because a processor is free if its required input is not yet ready.
Suppose L takes 2 seconds, H takes 6, T takes 4 and R takes 1. Assume two equally capable workers are available, tasks cannot be split or interrupted, and there is no overhead or resource contention. A serial schedule takes seconds. A possible concurrent schedule is:
| Task | Start | Finish |
|---|---|---|
| L | 0 | 2 |
| H | 2 | 8 |
| T | 2 | 6 |
| R | 8 | 9 |
R starts at 8, when the slower prerequisite H completes, not at 6 when only T is ready. Total elapsed time is seconds, a saving of 4 seconds. Total computational work remains 13 worker-seconds. One worker is idle between 6 and 8, but it cannot assemble R yet.
The critical dependency path is the longest required chain here: L–H–R takes 9 seconds. Under these durations, making T even faster does not shorten the report time unless H or another limiting part changes. Additional workers also do not remove L and R's required ordering. This simple case can be solved by inspecting the two paths; it is not a claim about a general scheduling algorithm.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account