Module - 01
Multiprocessor System Architectures
Multiprocessor system architectures are a class of computing systems where multiple processors operate under a
unified control, typically sharing memory and interconnecting resources. These systems enhance computational
power, fault tolerance, and support concurrent execution of tasks. This section elaborates on the architectural
models, design strategies, and their significance in modern computing systems.
1. Introduction
• Traditional systems enhanced performance via faster single processors.
• With limits of hardware speed, multiprocessor systems emerged to achieve high throughput by
executing tasks in parallel.
• Multiprocessor systems use multiple CPUs sharing memory and managed by a single OS.
• End users perceive the system as a powerful unified machine.
2. Motivations for Multiprocessor Architectures
• Enhanced Performance:
o Increased system throughput (tasks/unit time).
o Allows parallel execution of subtasks within one task.
• Fault Tolerance:
o System continues functioning with graceful degradation even when a processor fails.
3. Basic Multiprocessor Architectures (Flynn’s Classification)
• Based on MIMD (Multiple Instruction Multiple Data): processors execute different instructions on
different data sets.
• Two major types:
o Tightly Coupled Systems: Shared global memory accessible to all processors.
o Loosely Coupled Systems: Each processor has its own memory; communication via message
passing.
o
4. Memory
Access
Models
• Based on how memory is accessed by processors, multiprocessor architectures are further classified as:
a) UMA (Uniform Memory Access)
• Equal access time to memory for all processors.
• Centralized shared memory with optional private caches.
• Example: Encore Multimax, VAX 8800.
b) NUMA (Non-Uniform Memory Access)
• Memory is divided and distributed among processors.
• Processors share address space but access latency varies.
• Example: CMU Cm*, BBN Butterfly.
c) NORMA (No Remote Memory Access)
• Physically distributed memory with no shared address space.
• Processors must communicate via messages.
• Example: Intel Hypercube.
5. Interconnection Networks
Interconnection networks are crucial for processor-memory communication. Three major types:
a) Bus-Based Architecture
• Single shared bus for all processor-memory connections.
• Low cost and simple design.
• Scalability limited due to bus contention.
• Example: Encore Multimax.
b) Crossbar Switch
• Grid of switches allowing multiple simultaneous connections.
• High throughput; each processor can access a different memory module concurrently.
• Cost grows quadratically (n×n switches).
• Example: Alliant FX/8.
c) Multistage Interconnection Network (MIN)
• Compromise between bus and crossbar.
• Uses several switching stages (e.g., Omega network).
• Allows multiple paths and lower cost compared to crossbar.
• Example: BBN Butterfly Machine.
6. Caching in Multiprocessor Systems
• Local caches in processors reduce access time to frequently used data.
• Reduces bus traffic and memory contention.
• Cache Coherence Problem:
o Occurs when multiple caches store the same memory block and one modifies it.
o Solutions:
▪ Write-Update: All cached copies updated.
▪ Write-Invalidate: Copies in other caches are invalidated when one is written.
7. Hypercube Architectures
• Hypercube (n-cube):
2ⁿ processors connected in an
n-dimensional cube.
• Each node connects to
n neighbors; distance grows
logarithmically.
• Highly scalable and efficient for large parallel systems.
• Mostly used in loosely coupled systems.
• Examples: Intel iPSC/2, CM-2, Ncube/10.
Structures of Multiprocessor Operating Systems
Multiprocessor operating systems are designed to support concurrent execution of tasks using multiple
processors, ensuring resource management, fault tolerance, and high performance. Based on control structure
and kernel organization, these systems are classified into three primary structures:
1. Introduction
• A multiprocessor system consists of multiple processors working under a single OS.
• All processors share physical memory but may have different levels of autonomy.
• Multiprocessor OS structures define how processors interact with the kernel and system resources.
2. Classification of OS Structures
There are three major structures for multiprocessor operating systems:
A. Separate Supervisor Configuration
• Each processor has its own private copy of:
o Kernel (or Supervisor)
o OS data structures
o I/O devices
o File system
• Common data (for interprocessor communication) is protected using synchronization mechanisms
(e.g., semaphores).
• Characteristics:
o Processors are loosely coupled and operate independently.
o Difficult to parallelize a single task across multiple processors.
o Not resource-efficient due to code duplication.
o Good fault tolerance: fails gracefully as processors are isolated.
• Example Use Case: Embedded systems or real-time environments with independent processors.
B. Master-Slave Configuration
• One processor (the master) executes the OS and schedules jobs.
• Other processors (slaves) only execute user-level tasks.
• Characteristics:
o Centralized control – the master is the decision-maker.
o Simpler design and implementation.
o Supports parallel execution by breaking tasks into subtasks.
o Master handles all system-level operations (e.g., scheduling, I/O).
• Limitations:
o Master becomes a bottleneck.
o If the master fails, entire system fails.
• Examples: Cyber 170, DEC-10.
C. Symmetric Configuration (SMP – Symmetric Multiprocessing)
• All processors are equal and autonomous.
• A single copy of the kernel is shared and can be executed by any processor.
• Access to shared kernel structures is synchronized using critical sections or locks.
• A variation called the floating master method allows the OS to be executed by any processor as
needed.
• Advantages:
o Most efficient and flexible.
o Best performance and resource utilization.
o Supports parallel execution of tasks.
o Graceful degradation in case of failure.
• Disadvantages:
o Complex to implement due to synchronization of shared kernel structures.
• Example: Hydra on [Link].
Operating System Design Issues
Designing an operating system for multiprocessor systems is more complex than for uniprocessors because
it must manage multiple CPUs, coordinate concurrent processes, and ensure efficient and fault-tolerant
operations. Below are the key design issues:
1. Threads
• Traditional processes are too heavy for fine-grained parallelism.
• Threads or lightweight processes are used instead.
• They allow multiple units of execution within the same process memory space.
• Threads improve performance by reducing context-switch overhead and enable concurrent execution
of subtasks across processors.
2. Process Synchronization
• In multiprocessor systems, disabling interrupts is not sufficient for synchronization.
• Need sophisticated synchronization mechanisms using shared variables and locks (e.g., semaphores).
• Improper synchronization can lead to race conditions and data inconsistency.
3. Processor Scheduling
• Scheduler must effectively allocate tasks across processors to maximize CPU utilization.
• Tasks with dependencies should be scheduled to avoid idle time and locking.
• Affinity-based scheduling and smart schedulers improve cache usage and avoid resource contention.
4. Memory Management
• Each processor must maintain its own map table for virtual memory.
• Shared memory access requires consistency enforcement across map tables.
• Page replacement and protection mechanisms become complex and performance-sensitive.
5. Reliability and Fault Tolerance
• Systems must degrade gracefully when hardware fails.
• Requires support for reconfiguration, error detection, and recovery mechanisms.
• Systems like Sequoia use hardware/software redundancy for fault tolerance.
6. Other Design Issues
• Protection: Prevents unauthorized access to shared resources.
• Interprocess Communication (IPC): Needs efficient support for communication between processes
running on different processors, possibly with shared memory or message-passing models.
Process Synchronization in Multiprocessor Systems
Process synchronization in multiprocessor systems ensures coordinated access to shared resources. It is
a critical component of operating systems, especially in environments where multiple processors
execute concurrently. Without proper synchronization, race conditions, data inconsistency, and
deadlocks may arise.
1. Introduction
• In multiprocessors, shared memory and parallelism demand careful coordination.
• Mutual exclusion ensures only one process accesses critical sections at a time.
• Traditional uniprocessor synchronization techniques (like disabling interrupts) are insufficient due to
physical concurrency.
• Solutions must minimize CPU wastage, memory contention, and interconnection network traffic.
2. Key Issues in Process Synchronization
• Busy-waiting wastes CPU cycles and increases interconnect traffic.
• Solutions must:
o Ensure atomic access to critical sections.
o Be efficient under heavy processor contention.
o Avoid bottlenecks and provide scalability.
3. Hardware Primitives for Synchronization
a. Test-and-Set Instruction
• Reads and sets a memory location atomically.
• Used to implement binary semaphores.
The test-and-set instruction atomically reads and modifies the contents of a memory location in one
memory cycle. It is defined as follows (variable m is a memory location):
• function Test-and-Set(var m: boolean): boolean;
begin
Test-and-Set:=m;
m:=true
end;
• The test-and-set instruction returns the current value of variable m and sets it to true. This instruction
can be used to implement P and V operations on a binary semaphore, S, in the following way (S is
implemented as a memory location):
• P(S): while Test-and-Set(S') do nothing;
• V(S): S:= false;
• Initially, S is set to false. When a P(5') operation is executed for the first time, Test-and-Set(S') returns a
false value (and sets S to true) and the “while” loop of the P(S) operation terminates. All subsequent
executions of PCS') keep looping because S is true until a V(S) operation is executed.
b. Swap Instruction
• Atomically swaps a local and shared variable.
• Implements semaphores using busy-waiting.
• procedure swapfvar x, y: boolean);
var temp: boolean;
begin
temp:= x; x:= y; y:-temp
end;
• P and V operations can be implemented using the swap instruction in the following way (p is a variable
private to the processor and S is a memory location):
• P(S): p=true;
• repeat swap(S, p) until p=false;
• V(S): S:= false;
c. Fetch-and-Add (Ultracomputer)
• Atomically adds a constant to memory and returns the previous value.
• Eliminates contention by combining requests in the network.
• Used for implementing general semaphores without repeated memory access:
• Function Fetch-and-Add(m: integer; c: integer);
var temp: integer;
begin
temp:= m\ m:= m + c; return (temp)
end;
d. Compare-and-Swap
• Used in IBM 370 and others for optimistic locking.
• Verifies that the memory content is unchanged before updating.
• If memory content matches an expected value, update proceeds.
4. Specialized Hardware: SLIC Chip
• Used in Sequent Balance/21000.
• Each processor has a SLIC chip with local copies of lock bits (gates).
• Reduces memory traffic by avoiding shared memory.
• lock-gate and unlock-gate instructions handle P and V operations:
P(S): while (lock-gate(S) = failed) do nothing;
V(S): unlock-gate(S);
Still involves busy-waiting at local level.
5. Methods for Implementing Process Wait
5.1 Busy Waiting (Spinlock)
• Constantly checks lock variable.
• Wastes CPU cycles, increases interconnect traffic.
5.2 Sleep-Lock
• A process failing to acquire lock gets suspended and reawakened via interprocessor interrupt.
• Reduces network traffic but still wastes CPU cycles during reactivation.
5.3 Queueing
• Waiting processes are placed in a global queue.
• Reduces CPU waste, but adds overhead for queue management and synchronization.
6. Scheduling Considerations
• Avoid preempting a task inside a critical section – other tasks spinning will waste resources.
• Reschedule to the same processor (cache reuse).
• Reduce context switching overhead for better performance.
Processor Scheduling and Allocation in Multiprocessor Operating
Systems
Efficient processor scheduling in multiprocessor operating systems is crucial for maximizing resource
utilization and minimizing execution time. Since multiple tasks may execute concurrently across
different processors, sophisticated scheduling strategies are needed to address performance bottlenecks,
load balancing, and synchronization issues.
1. Introduction
• A parallel program may consist of multiple cooperating tasks.
• The goal of processor scheduling is to assign ready tasks to processors to maximize overall system
performance.
• Tasks may belong to one or multiple applications, and may share data or synchronize via shared
variables or message passing.
2. Key Issues in Processor Scheduling
a. Preemption in Critical Sections
• If a task is preempted inside a spinlock, other tasks spinning for the same lock waste CPU cycles.
• Though critical sections are small, waiting time may still be significant.
b. Cache Corruption
• Switching between tasks from different applications leads to high cache miss rates, reducing
performance.
c. Context Switching Overhead
• Includes saving/restoring registers, changing address space, and flushing caches.
• Pure overhead — doesn't advance actual computation.
3. Scheduling Techniques
a. Co-Scheduling (Medusa OS)
• All runnable tasks of an application are scheduled simultaneously.
• Entire application is preempted and resumed together.
• Prevents spinning delays but can aggravate cache misses.
• Suitable for systems without caches (e.g., Cm* multiprocessor).
b. Smart Scheduling
• Avoids preempting tasks inside critical sections.
• Avoids rescheduling waiting tasks until the corresponding lock is released.
• Reduces spinning overhead but doesn't solve cache or context-switch overheads.
c. NYU Ultracomputer Scheduling
• Supports hybrid strategies:
o Individual task scheduling.
o Group (co-scheduling-like) scheduling.
o Non-preemptive group scheduling.
• Flexible and powerful for various application types.
• Includes mechanisms to prevent lock-holder preemption.
d. Affinity-Based Scheduling
• Tasks are rescheduled on the same processor to utilize cache locality.
• Reduces cache misses and bus traffic.
• But causes load imbalance — busy processors might have queues while others are idle.
• Hybrid schemes with threshold-based migration help balance the load.
e. Mach Operating System Scheduling【28:2†Module-1 [Link]**
• Two-level priority-based scheduling:
o Local queues (per processor) and global queues (shared).
• Idle processors first pick from local queues.
• Threads can have user-specified hints to affect scheduling:
o Discouragement hints to delay or suppress scheduling.
o Improve scheduling for synchronization-heavy apps.
Memory Management in Multiprocessor Operating Systems
17.7.1 Design Issues in Multiprocessor Memory Management
Memory management in multiprocessor systems presents unique challenges due to the need for
parallelism, sharing, and hardware independence. The Mach Operating System addresses these design
issues through a carefully modular and scalable approach.
Key Design Issues:
1. Machine Independence
• The memory manager must run on various processor architectures.
• Design is split into:
o Machine-independent part (core OS functions).
o Machine-dependent part (hardware interactions via pmap module).
2. Data Sharing
• Parallel programs and cooperating tasks must share memory efficiently.
• The system should support:
o Inter-process communication (IPC) via shared memory.
o Inheritance of memory regions between parent-child tasks.
3. Memory Protection
• Memory must be protected at the page level:
o Current and maximum protection levels.
o Permissions: read, write, and execute.
4. Efficiency and Performance
• Address translation, fault handling, and page replacement must be fast.
• Must avoid contention and overhead from locks and synchronization.
• The system must handle lazy allocation, copy-on-write, and demand paging effectively.
17.7.2 The Mach Kernel
The Mach kernel is a modern operating system kernel designed to support multiprocessor
environments, parallelism, and modularity. It provides advanced memory management using
virtual memory objects, enabling sharing, protection, and portability.
Key Features of the Mach Kernel:
1. Modular Design
• The Mach kernel separates machine-independent and machine-dependent code.
• Machine-independent code handles:
o Virtual memory
o Threads
o Tasks
o IPC (Interprocess Communication)
• Machine-dependent code is limited to modules like pmap for portability.
2. Task-Based Model
• Each task is a container for resources (threads, memory).
• Tasks are assigned a paged virtual address space, which can be sparse and demand-allocated.
3. Memory Objects
• Mach uses memory objects as logical units of memory.
• Memory regions in a task’s address space are backed by memory objects.
• These objects may represent physical memory, files, or devices.
4. Portability
• The kernel's architecture supports execution on diverse hardware.
• The pmap module is the only part that interacts directly with hardware-level memory management.
5. Parallel and Shared Access
• The kernel supports multiple tasks and threads accessing shared memory.
• Protection and inheritance features allow for controlled, efficient sharing of memory across tasks.
Task Address Space
In the Mach operating system, each task is assigned a virtual address space that is paged, protected,
and sparse. This allows efficient memory use, sharing, and isolation in multiprocessor environments.
Key Features:
1. Paged Virtual Memory
• Memory is divided into fixed-size pages.
• Pages are allocated on demand using a lazy allocation strategy.
• Supports sparse usage – memory is only committed when actually used.
2. Regions and Memory Objects
• The address space is split into regions, each mapped to a memory object.
• Memory objects can represent:
o Physical memory
o Files
o Shared memory
• Allows easy implementation of copy-on-write and shared memory.
3. Protection and Inheritance
• Each region has current and maximum protection levels.
• Tasks can inherit regions when forked, supporting parallelism and shared data access.
4. Machine Independence
• Virtual-to-physical mapping is handled by the pmap module, making the system portable across
hardware platforms.
Memory Protection and Machine Independence
In multiprocessor systems, memory protection ensures safe access to shared data, while machine
independence allows the OS to run on various hardware platforms. The Mach Operating System
addresses both through its modular and hardware-abstracted design.
1. Memory Protection
• Per-Page Protection: Each page in a task's address space has:
o Current protection: Active access rights (e.g., read/write).
o Maximum protection: The upper bound of future permissions.
• Access Rights:
o Read
o Write
o Execute
These are mutually exclusive and strictly enforced.
• Benefit: Prevents accidental or malicious access between tasks, ensuring system security in shared-
memory environments.
2. Machine Independence
• Achieved by separating:
o Machine-independent code (handles general VM operations)
o Machine-dependent code (interacts with hardware)
• pmap Module:
o Encapsulates hardware-specific operations like page table management and address
translation.
o Allows the rest of the memory system to remain unchanged across architectures.
• Benefit: Mach can run on multiple platforms (e.g., VAX, 68030, SPARC) without rewriting the entire
OS.
Efficiency Considerations and Copy-on-Write Operation
In multiprocessor systems, memory operations must be efficient to support parallelism, and Copy-on-
Write (COW) is a key strategy to optimize memory usage without sacrificing performance.
1. Efficiency Considerations
• Lazy Allocation: Physical memory is not allocated until a page is accessed, reducing unused memory.
• Parallel Fault Handling: Page faults can be handled concurrently across processors, improving
responsiveness.
• Concurrency with Locks:
o Map Locks, Object Locks, Page Locks prevent data corruption during simultaneous access.
• Avoiding Duplication: Shared memory and inheritance reduce the need to copy large data between
tasks.
• Goal: Minimize overhead while supporting scalable, concurrent access.
2. Copy-on-Write (COW) Operation
• COW allows multiple tasks to share a memory page as long as it’s read-only.
• When a task attempts to modify the page:
o A private copy is created (copy-on-write).
o Only the modified task uses the new page; others continue using the original.
Benefits:
• Saves memory by avoiding unnecessary copying.
• Boosts performance during process creation (e.g., fork() system call).
• Works with shadow objects, which track modified pages and maintain consistency.
Implementation: Data Structures and Algorithms
Efficient implementation of memory management in a multiprocessor OS like Mach depends on
carefully designed data structures and algorithms that support concurrency, sharing, and
performance.
1. Core Data Structures
a) Virtual Address Map
• Each task has a map describing its virtual address space.
• Maps contain regions, which point to memory objects.
b) Memory Object
• Represents the backing storage for a region.
• Used for sharing data between tasks.
• May be linked into shadow object chains for Copy-on-Write.
c) Shadow Object
• Tracks differences from the original memory object.
• Used in copy-on-write operations to avoid duplicating unchanged data.
d) Physical Page Table
• Maps physical frames to virtual addresses.
• Updated dynamically using page faults and pmap operations.
2. Algorithms Used
a) Copy-on-Write (COW)
• When a task writes to a shared page:
o A new physical page is allocated.
o Content is copied.
o Mapping is updated via the page table.
b) Page Fault Handling
• Fault triggers lookup in virtual map.
• If not present in memory:
o Page is fetched or allocated.
o Mappings updated via pmap module.
• Optimized for concurrent fault resolution.
c) Locking Mechanisms
• Used to protect shared structures:
o Map locks for virtual address maps.
o Object locks for memory object access.
o Page locks for in-use physical pages.
• Lock acquisition follows a fixed order to avoid deadlocks.
Sharing of Memory Objects
In the Mach Operating System, memory sharing is achieved through memory objects, which are
abstract representations of data that can be mapped into the address spaces of multiple tasks. This
model enables efficient inter-process communication (IPC) and parallel execution in multiprocessor
systems.
Key Concepts:
1. Memory Objects
• Represent a contiguous set of virtual pages.
• Backed by physical memory, files, or devices.
• Multiple tasks can map the same memory object into their address space, enabling data sharing.
2. Benefits of Sharing
• Avoids data duplication between cooperating tasks.
• Allows zero-copy IPC, improving performance.
• Facilitates synchronization and parallel processing.
3. Inheritance
• When a task is forked, its memory regions can be:
o Copied
o Shared
o Skipped (no inheritance)
• Sharing is especially beneficial for parallel applications needing common data structures.
4. Implementation Support
• Shared memory objects are managed through:
o Virtual memory maps per task.
o Shadow objects (used if copy-on-write is involved).
o Locks to ensure concurrency control.