IB COMPUTER SCIENCE | A1.3.5 Multitasking and Resource Allocation (HL)

Lesson objective

Explain how the OS manages multitasking and resource allocation, including scheduling, resource contention, synchronisation and deadlock. Higher level only.

Learn

A1.3.5 | MULTITASKING AND RESOURCE ALLOCATION (HL ONLY)

01 | HL: SEVERAL TASKS, FINITE RESOURCES

Higher level only. Imagine a laptop exporting video while you edit a report, download a file and play music. All these tasks need resources, but the computer has a limited number of processor cores, a limited amount of RAM and shared storage and devices.

The OS manages multitasking so that multiple tasks can make progress, and resource allocation so that resources are assigned and used under controlled rules. Without coordination, one task could monopolise execution, consume available memory or interfere with another task’s data.

The main challenges in this part of the specification are task scheduling, resource contention and deadlock. This lesson links them: choosing which task runs is not enough if the task cannot obtain the resource it needs.

An explanation should connect the mechanism to the benefit or problem. For example, blocking a task waiting for I/O allows another ready task to use the core, therefore reducing wasted execution opportunities.

02 | CONCURRENCY IS NOT ALWAYS PARALLELISM

Concurrency means tasks make progress over overlapping periods. On one CPU core, the OS can interleave their execution, so several applications appear active even though only one instruction stream executes on that core at a time in our simplified model.

Parallelism means work actually executes at the same time on different execution resources. Multiple cores can run different tasks simultaneously, while scheduling is still needed when there is more runnable work than available cores.

Multitasking can therefore exist on a single-core machine. Conversely, adding cores does not eliminate competition for memory, storage bandwidth or locks. Two tasks on different cores can still need the same exclusive resource.

A task’s progress also includes waiting for devices. A storage operation can proceed while the CPU executes another task, helping overlap computation and I/O.

03 | PROCESSES, THREADS AND EXECUTION STATE

A process is a running program instance with associated resources and an address space. A thread is a path of execution within a process. A process can have several threads that share its memory and other resources.

Each thread needs its own execution state, including register values and an execution position. When the OS switches execution, the necessary state is saved and the next task’s state is restored so that work can resume correctly.

Sharing memory can make communication between threads efficient, but it also means one thread can alter data another uses. Separate processes usually have protected address spaces and use controlled communication mechanisms when they need to exchange data.

Real systems commonly schedule threads. The teaching models below use one thread per process, so “task A” can be read as the runnable work belonging to process A.

04 | SCHEDULING SHARES EXECUTION OPPORTUNITIES

The scheduler chooses runnable work for processor cores. It may use time slicing, priorities, queues and other policies to balance responsiveness, throughput, fairness and overhead. The previous lesson compared these choices.

With preemptive multitasking, a task can lose its CPU turn before its work finishes. A timer event or newly ready higher-priority work can cause a scheduling decision. The task’s saved context lets it continue later rather than restart.

A context switch has a cost. Switching too often consumes time saving and restoring state and may disturb useful cached data. Switching too infrequently can delay other tasks’ responses.

The OS does not create additional useful CPU capacity merely by switching rapidly. It distributes available execution opportunities, so an overloaded system may still respond slowly.

05 | READY, RUNNING AND BLOCKED: WHY STATE MATTERS

A ready task could execute if selected. A running task is currently using a core. A blocked task cannot proceed until an event or resource becomes available, such as completion of a file read or release of a lock.

If A requests a read and blocks, continuing to select A does not make the data arrive sooner. The OS can instead run ready task B, therefore using the core while the device works.

When the I/O completion is reported, A can become ready again. Ready does not mean it immediately runs: the scheduler must still choose it. That distinction explains why “the event completed” and “the application responded” can occur at different times.

An exhausted time slice normally returns runnable work to the ready state; it does not itself mean the task is blocked. State describes whether a task can proceed, not simply whether it is currently visible in a window.

06 | FOLLOW THREE TASKS ON ONE CORE

Step through this conceptual sequence. A reads data, B needs CPU time and C performs a short calculation. Each stage is an event, not an equal-duration time slot. The example illustrates state changes rather than implementing a particular scheduling algorithm.

Task states in a one-core example
TaskCurrent stateReason

07 | ALLOCATE MORE THAN CPU TIME

Resource allocation includes managing working memory, storage and file access, device requests, network facilities and synchronisation objects. Different resources need different rules: RAM capacity is not allocated in exactly the same way as a printer queue.

The OS tracks allocation and availability, applies permissions and limits, queues requests where necessary and reclaims resources when appropriate. Memory protection reduces the chance that one ordinary process overwrites another’s address space.

For example, a large video editor and a virtual machine may compete for RAM. The OS can manage their memory mappings and enforce limits, but excessive demand can cause allocation failure or expensive paging. More virtual addresses do not imply unlimited physical memory.

When a process exits, the OS can reclaim many of its resources. Application-level work may still need clean-up or recovery: closing a process does not magically undo every partially written file or external action.

08 | CONTENTION: TWO TASKS WANT THE SAME THING

Resource contention occurs when tasks compete for a limited resource. Several processes may request storage bandwidth; two threads may need to update the same data structure; several jobs may wait for one printer.

Contention does not automatically mean deadlock. If a printer finishes one queued job and serves the next, the waiting jobs are delayed but can still make progress.

The OS and supporting software manage competition through scheduling, queues, quotas, permissions and synchronisation mechanisms. These approaches can improve fairness and consistency, but also introduce waiting and management overhead.

A resource can be shareable in one sense yet still have limited capacity. Several processes can read different files concurrently, but the storage device has finite throughput. Exclusive locks are a different kind of constraint: only one holder may enter the protected operation at a time.

ResourceExample contentionPossible management
CPU coresMore runnable threads than coresScheduling and priorities
RAMWorking-memory demand exceeds available capacityAllocation control, mappings, limits and reclamation
Storage deviceMany simultaneous I/O requestsQueues and I/O scheduling
Shared dataTwo threads update the same valueAppropriate synchronisation
PrinterSeveral pending print jobsSpooling and queued access

09 | PROTECT SHARED DATA WITH SYNCHRONISATION

Suppose a shared counter starts at 10. Thread A reads 10 and plans to write 11. Before A writes, thread B also reads 10 and plans to write 11. If both then write 11, one increment is lost: the correct result of two increments would be 12.

This is a race condition: the outcome depends on the timing or ordering of unsynchronised operations on shared state. It can occur through interleaving on one core as well as through parallel execution.

A critical section is code accessing shared state that needs appropriate coordination. A mutex is a mutual-exclusion mechanism: one task holds it while performing the protected operation; another must wait to acquire it.

The OS provides synchronisation facilities, but application developers must use them correctly. Not every uncontended lock operation requires a kernel call; implementations can combine user-space operations with OS support for waiting.

Locks can prevent an unsafe update, but holding one too long delays other tasks. Acquiring several locks inconsistently can introduce deadlock. More locking is not automatically a better design.

10 | DEADLOCK: WAITING THAT CANNOT RESOLVE ITSELF

Imagine two tasks each needing exclusive access to locks R1 and R2. Each lock has one instance. A acquires R1; B acquires R2. A then waits for R2 while keeping R1. B waits for R1 while keeping R2.

Neither task can reach the code that releases its current lock because each is waiting for the other’s lock. This is deadlock: a set of tasks cannot proceed because their dependencies cannot be satisfied without outside intervention.

Giving A more CPU turns does not release R2. Increasing B’s priority does not release R1. The problem is the resource dependency, so a different CPU schedule alone cannot fix this state.

Other unrelated tasks may still run. A deadlock involving A and B does not necessarily mean every process, every core or the entire OS has stopped.

ABR1R2held byheld byrequestsrequestsResource → task: held by · Task → resource: requests
One instance of each lock. The arrows show ownership and waiting, not data transfer.

11 | FOUR CONDITIONS EXPLAIN THE RISK

For this resource deadlock model, four necessary conditions are present. Learning them helps explain the mechanism and shows where a prevention rule can intervene.

ConditionMeaningIn our example
Mutual exclusionAt least one resource cannot be shared simultaneouslyOnly one task can hold each lock
Hold and waitA task holds a resource while waiting for anotherA keeps R1 while requesting R2
No resource preemptionThe held resource is not forcibly taken away as an ordinary allocation stepThe locks are released through appropriate program actions
Circular waitA cycle of tasks waits for resources held by the nextA waits for B; B waits for A

Resource preemption is different from CPU preemption. The OS may stop A’s CPU turn without safely taking away a lock protecting a partly updated data structure.

With multiple instances of a resource, a cycle in a general allocation graph does not by itself always prove deadlock. Our drawing uses single-instance locks, so the two-way dependency is sufficient here.

12 | CREATE A DEADLOCK, THEN PREVENT IT

Choose opposite lock order to see the deadlock develop. Then restart with a consistent order: both tasks must acquire R1 before R2. B may still wait, but it does not hold R2 while preventing A from finishing.

The recovery button demonstrates cancelling B only after the deadlock exists. This model can safely discard B’s work and release its locks. Real recovery must consider partial updates, external effects and what resources can actually be reclaimed.

Exclusive lock ownership
ResourceHolder
Task progress and outstanding requests
TaskStateWaiting for

13 | PREVENTION, AVOIDANCE, DETECTION AND RECOVERY

Prevention imposes rules that break at least one necessary deadlock condition. A consistent total order for acquiring locks prevents circular wait when every participant follows the rule. Requiring resources together can remove hold-and-wait, but can reduce utilisation and make requests less flexible.

Avoidance examines whether a request can be granted while retaining a safe way for tasks to finish, under a model of resource availability and possible future needs. A request may be delayed even if the resource is currently free. An unsafe state is a risk, not necessarily a deadlock already in progress.

Detection and recovery permit the possibility of deadlock, look for the relevant dependency pattern and then act. Recovery might cancel a task, roll back work or reclaim resources where this is safe. These actions have costs and may lose progress.

The OS does not automatically detect and repair every application-level lock cycle. Its visibility and policy vary, and developers may need consistent locking rules, timeouts, monitoring and application recovery. A timeout identifies excessive waiting; it is not proof of deadlock by itself.

14 | DEADLOCK, STARVATION AND ORDINARY WAITING

These situations may all look like “the task is not progressing”, but their causes differ. Explaining the cause matters because a suitable remedy for one may not solve another.

SituationCauseUseful response
Ordinary contentionAnother task temporarily holds the needed resource and can release itQueue or wait until access is available
StarvationA task is repeatedly passed over while others progressFairness rules, aging or allocation changes
DeadlockTasks in a dependency cycle cannot proceed without interventionPrevent the cycle or detect and recover safely

Aging can help a low-priority ready task obtain CPU time, but does not automatically resolve two blocked tasks each holding the other’s needed lock. Adding a core also does not remove that lock dependency.

A related issue is priority inversion: a high-priority task waits for a lock held by a lower-priority task, which may itself be delayed by unrelated work. Some systems use priority inheritance to help the lock holder finish. That is a specialised coordination measure, not a general cure for every deadlock.

15 | BALANCE PERFORMANCE, FAIRNESS AND PROTECTION

The OS must balance several objectives. A responsive application needs timely execution, background work still needs progress, and memory or device allocation must respect protection and capacity constraints.

Quotas and limits can stop one task consuming all of a resource, but a badly chosen limit can also prevent useful work. More frequent preemption may improve responsiveness while increasing overhead. Exclusive access can preserve consistency while reducing concurrency.

These tradeoffs explain why the OS needs information about runnable tasks, blocked requests, current allocation and relevant policies. It does not simply give the most visible application every resource.

Applications also contribute to the result. Efficient resource use, short critical sections, consistent acquisition order and correct release of resources help the OS-supported mechanisms work effectively.

16 | EXPLAIN A COMPLETE SCENARIO

A media application exports a video while an editor waits for a file read and a music player needs periodic processing. The scheduler can run ready work while the editor is blocked. When the read completes, the editor becomes ready and can later be selected.

Memory management supplies and protects working memory. Device queues coordinate file access. Shared structures use appropriate synchronisation. Because all these demands have limits, contention can create delays even if the CPU has several cores.

If two export threads acquire two required locks in opposite orders and each waits while holding one, they can deadlock. More CPU time cannot resolve the ownership cycle; consistent lock ordering could have prevented it.

Notice the linked explanation: identify the OS mechanism, state the resource problem and explain the consequence. That is more precise than saying only “the OS multitasks efficiently”.

17 | EXPLAIN WITH CAUSE AND CONSEQUENCE

For explain, make the relationship clear. Use connectives such as because, therefore and resulting in to link a mechanism to its effect.

For example: “A task waiting for storage is blocked, so it cannot make useful CPU progress. The OS can schedule another ready task, therefore overlapping CPU work with device activity.”

For contention: “Two threads need the same exclusive lock, so one must wait. This prevents simultaneous unsafe access but can delay progress. If both hold different locks while requesting each other’s, a circular dependency results in deadlock.”

Avoid claiming that multitasking requires multiple cores, that a blocked task is always deadlocked, or that CPU preemption releases every resource. Explain how scheduling, allocation and synchronisation work together, and where their limits lie.

Further reading: Processes, threads and execution context · Resource dependencies and deadlocks

MATCH THE MULTITASKING TERM TO ITS MEANING

Terminology

Terminology

Multitasking

Managing progress of multiple tasks over overlapping periods.

Concurrency

Overlapping progress of tasks, possibly through interleaving.

Parallelism

Actual simultaneous execution on separate execution resources.

Process

A running program instance with associated resources and an address space.

Thread

A path of execution within a process.

Context switch

Saving one task’s execution state and restoring another’s.

Preemption

Taking running work off a core before its current burst finishes.

Scheduler

A mechanism choosing runnable work for CPU execution.

Ready

Able to execute if selected.

Running

Currently executing on a processor core.

Blocked

Waiting for an event or resource before proceeding.

Resource allocation

Assigning and managing access to limited system resources.

Resource contention

Competition for a limited resource.

Memory protection

Controls restricting access to memory belonging to other processes or the system.

Quota

A limit on permitted resource consumption.

Synchronisation

Coordination of concurrent operations to maintain required ordering or consistency.

Race condition

An outcome depending on problematic timing of unsynchronised operations.

Critical section

Code accessing shared state that needs appropriate coordination.

Mutex

A mechanism providing mutual exclusion for protected work.

Mutual exclusion

Only one task may use a particular exclusive resource at a time.

Hold and wait

Holding a resource while waiting to acquire another.

Circular wait

A cycle in which tasks wait for resources held by the next task.

Deadlock

A dependency situation preventing a set of tasks from proceeding without intervention.

Starvation

A task being repeatedly denied service while others progress.

Deadlock prevention

Rules eliminating at least one necessary deadlock condition.

Deadlock avoidance

Granting requests only when a resource model retains a safe completion possibility.

Deadlock detection

Identifying a deadlock under the system’s dependency model.

Recovery

Action such as safe cancellation or rollback to escape a deadlock.

Lock ordering

A consistent order for acquiring resources to prevent circular wait.

Priority inversion

Higher-priority work waiting for a resource held by lower-priority work.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which statements about multitasking are correct?
2. Why save execution state during a switch?
3. What happens when a task blocks on a storage read?
4. Which are examples of resource contention?
5. Why can a shared increment lose an update?
6. Which describe the two-lock deadlock?
7. Which are necessary conditions in the stated resource-deadlock model?
8. Why does consistent lock ordering help?
9. Which recovery statements are accurate?
10. Which distinguish deadlock and starvation?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Explain how multitasking works on one core.

2. Explain how multiple cores change multitasking without removing allocation problems.

3. Explain why ready and blocked tasks need different treatment.

4. Explain resource allocation using a video editor and a virtual machine.

5. Explain a lost update on a shared counter.

6. Explain how a mutex helps and what cost it introduces.

7. Explain how opposite lock ordering causes deadlock.

8. Explain why CPU preemption does not necessarily solve resource deadlock.

9. Explain why consistent acquisition order prevents the demonstrated deadlock.

10. Explain the difference between prevention and detection with recovery.

11. Explain why slow progress does not prove deadlock.

12. Explain the shared responsibilities of an OS and applications.

EXPLAIN IT | A SHARED MEDIA SERVER

A server has several runnable export tasks, an editor waiting for storage, limited RAM and two exclusive locks used by background threads. Explain how scheduling, state transitions and resource allocation support progress. Then explain how opposite lock ordering could deadlock two threads, why extra CPU time would not solve it, and how consistent ordering could prevent the cycle. Use because and therefore to link mechanisms to outcomes.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

    Selections are kept while this page is open.

    Workbook

    Workbook

    COMING SOON

    The workbook for A1.3.5 Multitasking and Resource Allocation (HL) is coming soon. Complete the matching task and written questions in your exercise book.