Module -1
1. Explain the basic Multiprocessor System Architectures (Tightly Coupled and Loosely
Coupled) with neat diagrams. ( repeated )
System Architectures (Multiprocessor OS Architectures)
Multiprocessor systems consist of two or more processors sharing memory and I/O resources.
Based on the way processors communicate and share memory, multiprocessor architectures are
classified into two types:
1. Tightly Coupled Systems (Shared-Memory System)
Definition
A tightly coupled multiprocessor system has a common shared memory, which all processors can
directly access.
Characteristics
1. A tightly coupled multiprocessor system has a common shared memory, which all
processors can directly access.
2. Most commercial tightly coupled systems provide a cache memory with each CPU, along
with a global shared memory.
3. Information can be shared among CPUs by placing it in the common global memory.
4. Processors communicate through shared variables, and synchronization mechanisms such as
semaphores and locks are used.
5. These systems are most efficient when task interaction is high, since shared memory allows
fast data exchange.
Use Case
Small to medium-scale systems where processes frequently share data, such as:
• Multi-core CPUs in laptops
• Servers
2. Loosely Coupled Systems (Distributed-Memory System)
Definition
A loosely coupled multiprocessor system is one in which each processor has its own private local
memory and communicates with other processors through a communication network.
Characteristics
1. In this model, each processor has its own private local memory.
2. Processors are connected by a communication network (switching scheme) to exchange
information.
3. Data and programs are shared through a message-passing scheme rather than shared
memory.
4. Communication takes place through packets, which contain:
o Address
o Data content
o Error detection codes
5. These systems are most efficient when task interaction is minimal, as message passing has
higher latency than shared memory.
Use Case
Large-scale distributed systems where processors work mostly independently, such as:
• Distributed systems
• Computer clusters
• Supercomputers
2. Explain the Structures of Multiprocessor Operating Systems. Compare different OS structures.
Structures of Multiprocessor Operating System (OS)
Multiprocessor Operating Systems are designed to manage systems with two or more processors.
Based on the organization of the operating system, multiprocessor OS structures are classified into
the following types:
1. Separate Supervisor Structure
Definition
Each processor has its own copy of the Operating System, including the kernel, memory, tables, and
I/O management.
Characteristics
• Each processor has its own copy of the Operating System (kernel, tables, memory, and I/O).
• A few shared/common data structures are used for inter-processor communication.
• Processors work independently with weak coordination.
• Each processor manages its own resources and scheduling separately.
2. Master–Slave Structure
Definition
One processor is designated as the master, while the remaining processors act as slaves.
Characteristics
• One processor is designated as the master, running the Operating System.
• Other processors act as slaves, executing only user programs or assigned tasks.
• The master controls scheduling, task assignment, and I/O management.
• OS data structures and control logic are maintained in the master's private memory.
3. Symmetric Multiprocessing (SMP) Structure
Definition
All processors are identical and share a single copy of the Operating System.
Characteristics
• All processors are identical and share a single OS copy.
• Any processor can execute kernel functions (floating master method).
• A shared memory system is used to hold Process Control Blocks (PCBs) and ready queues.
• Idle processors select the next task from the common ready queue for execution.
3 Discuss the major OS Design Issues in Multiprocessor Operating Systems.
OS Design Issues in Multiprocessor System
Multiprocessor operating systems must manage multiple processors working together. This makes
their design more complex than single-processor operating systems. The major OS design issues are
as follows:
1. Threads
Definition
Threads allow parallel execution within a process, enabling multiple tasks to run simultaneously.
Key Points
• Threads allow parallel execution within a process.
• Multiple threads can run on multiple processors simultaneously.
• Increases system throughput and responsiveness.
2. Process Synchronisation
Definition
Process synchronisation ensures that multiple processors safely access shared data without
conflicts.
Key Points
• Ensures safe access to shared data among processors.
• Achieved using semaphores, locks, and atomic operations.
• Prevents race conditions and data inconsistency.
3. Processor Scheduling
Definition
Processor scheduling determines which process or job is assigned to which processor.
Key Points
• Decides which job runs on which processor.
• Aims for fair allocation and balanced workload.
• Avoids processor idling and overloading.
4. Memory Management
Definition
Memory management efficiently manages shared and private memory among multiple processors.
Key Points
• Manages shared memory among multiple processors.
• Allocates private and shared memory efficiently.
• Keeps memory consistent across all processors.
5. Reliability and Fault Tolerance
Definition
Reliability and fault tolerance ensure the system continues to operate even if a processor fails.
Key Points
• Ensures the system works even if one processor fails.
• Other processors take over the failed processor's tasks.
• Improves system availability and dependability.
4. Explain Process Synchronization in Multiprocessor Systems using Test-and-Set and Swap
Instructions. ( repeated )
Process Synchronization
Definition
In a multiprocessor system, multiple processors may access shared data simultaneously. To ensure
correct execution and prevent data inconsistency, a process synchronization mechanism is required.
The main objective is to solve the Mutual Exclusion Problem, ensuring that only one process can
enter the critical section at a time.
1. Test-and-Set Instruction
The Test-and-Set instruction is an atomic hardware instruction used to provide synchronization
among concurrent processes.
It returns the old value of a memory location and sets it to 1 (true) as a single atomic operation.
Working
• If Lock = 0, the critical section is free, and the process enters the critical section.
• If Lock = 1, another process is already inside the critical section, so the process waits.
Lock Values
• Lock = 0 → Critical section is vacant.
• Lock = 1 → Critical section is occupied.
Algorithm
while (Test-and-Set(lock))
; // Wait
Critical Section
lock = 0; // Release Lock
Advantages
• Ensures mutual exclusion.
• Simple hardware implementation.
• Supports process synchronization.
Disadvantages
• Uses busy waiting (spin lock).
• Does not guarantee bounded waiting.
• Causes increased processor and network traffic.
2. Swap Instruction
Definition
The Swap instruction is an atomic hardware instruction that exchanges the contents of two
variables (memory locations) in a single operation. It is used to implement mutual exclusion in
multiprocessor systems.
Working
• A process swaps the value of its local variable with the shared lock variable.
• If the lock was false (0), the process enters the critical section.
• If the lock was true (1), the process keeps waiting until the lock becomes available.
Algorithm
key = true;
do
swap(key, lock);
} while (key == true);
Critical Section
lock = false;
Advantages
• Ensures mutual exclusion.
• Atomic operation prevents simultaneous access.
• Easy to implement in hardware.
Disadvantages
• Uses busy waiting.
• Increases processor and memory traffic.
• No guarantee of bounded waiting.
6. Explain Process Scheduling and Processor Allocation in Multiprocessor Systems.
Process Scheduling and Processor Allocation
Definition
In multiprocessor systems, a parallel program is divided into multiple tasks that may belong to the
same application or different applications. Processor scheduling assigns these ready tasks to
available processors so that system performance, throughput, and resource utilization are
maximized.
Issues in Processor Scheduling
1. Preemption inside Spinlock-Controlled Critical Sections
Explanation
When a task holding a lock is preempted, the lock cannot be released immediately. Other tasks
continue waiting (spinning) for the lock, wasting processor time.
Key Points
• When a task holding a lock is preempted, the lock cannot be released on time.
• Other tasks continue spinning while waiting, wasting CPU cycles.
• This leads to performance degradation and poor processor utilization.
• A solution is to avoid preemption in lock-holding tasks or apply priority inheritance.
2. Cache Corruption
Explanation
When different applications execute one after another on the same processor, cached data is
replaced, increasing cache misses.
Key Points
• Successive tasks from different applications evict each other's cache data.
• This causes frequent cache misses and forces reloads from main memory.
• As a result, execution time increases and system throughput decreases.
• Cache affinity techniques can reduce this problem by scheduling tasks on the same
processor as before.
3. Context Switching Overheads
Explanation
Switching from one process to another requires saving and restoring processor information, which
increases execution overhead.
Key Points
• Every switch requires saving registers, program counters, and processor states.
• Page tables and Translation Lookaside Buffers (TLB) must be reloaded.
• These operations add heavy execution overhead in multiprocessor environments.
• Minimizing unnecessary switches and using lightweight mechanisms improves efficiency.
Scheduling Strategies
1. Co-Scheduling (Medusa OS)
Definition
All runnable tasks of an application are scheduled simultaneously on processors.
Key Points
• All runnable tasks of an application are scheduled simultaneously on processors.
• If one task is preempted, all tasks of that application are preempted.
Advantages
• Removes lock-spinning wastage.
Limitations
• Still suffers from context switching and cache problems.
2. Smart Scheduling
Definition
Smart scheduling avoids preempting a task while it is inside a critical section.
Key Points
• Avoids preempting a task when it is in a critical section.
• Tasks that were busy-waiting are not rescheduled until the lock is released.
Advantages
• Reduces CPU wastage due to spinlocks.
Limitations
• Context-switching overhead still exists.
3. Scheduling in the NYU Ultracomputer
Definition
This scheduling technique combines the features of Co-Scheduling and Smart Scheduling.
Key Points
• Combines features of Co-Scheduling and Smart Scheduling.
• Supports multiple scheduling policies:
o Normal scheduling (per task)
o Group scheduling (all tasks scheduled/preempted together)
o Non-preemptive group scheduling (never preempt tasks in a group)
Advantages
• Flexible and adaptable to different workload patterns.
4. Affinity-Based Scheduling
Definition
A task is scheduled on the same processor where it previously executed.
Key Points
• Task is rescheduled on the same processor where it last executed.
• Reduces cache misses since working data may still reside in the processor's cache.
• Improves cache performance and reduces bus traffic.
Limitations
• Can reduce load balancing across processors.
5. Scheduling in Mach OS
Definition
Mach Operating System uses thread-based scheduling with priority queues.
Key Points
• Mach OS uses thread-based scheduling with priority queues.
• Threads are bound to processor sets.
• Uses two-level priority scheduling:
o Local queue (Higher priority)
o Global queue (Lower priority)
Advantages
• Supports fine-grained scheduling.
• Provides priority-based execution.
6. Discuss Memory Management in Multiprocessor Systems. Explain Mach OS Copy-on-Write
Mechanism. ( repated )
Memory Management in Multiprocessor Systems
Definition
Memory management in a multiprocessor system is responsible for managing shared and private
memory efficiently among multiple processors. It ensures correct memory allocation, protection,
sharing, and consistency while improving system performance.
Design Issues in Memory Management
. 1. Portability
• The OS must run on multiple architectures.
• Hence, virtual memory design should be architecture-independent.
2. Data Sharing
• Processes running on different processors often share memory for communication and
synchronization.
• Flexible shared memory support is required.
3. Protection
• Memory protection mechanisms must prevent unauthorized access to shared objects.
4. Efficiency
• Virtual memory must be fast in:
o Page lookups
o Address translation
o Page replacement
• Algorithms should exploit parallelism.
Mach Operating System
Mach OS is designed for parallel and distributed computing environments. Its Mach Kernel provides
services such as:
• Process management
• Memory management
• Inter-process communication (IPC)
• I/O services
The Mach Kernel supports the following abstractions:
• Threads
• Tasks
• Ports
• Messages
• Memory Objects
Memory Sharing in Mach OS
Mach OS allows multiple tasks to share memory efficiently using the Inheritance Mechanism.
Each page can have one of the following inheritance attributes:
1. None
• Child process does not inherit the page.
2. Copy
• Child receives a separate copy of the page.
• Changes made by one process do not affect the other.
3. Share
• Parent and child share the same physical page.
• Both access the same copy of data.
Mach OS Copy-on-Write (COW) Mechanism
Definition
Copy-on-Write (COW) is a memory management technique in Mach OS that allows multiple tasks to
share the same memory object until one of them modifies it.
Instead of creating a new copy immediately, Mach OS delays copying until a write operation occurs.
Working of Copy-on-Write
1. Initially, the parent and child tasks share the same memory object.
2. As long as both tasks only read the memory, one copy is maintained.
3. When a task attempts to write to the shared page:
o A new private page is created.
o The modified data is copied into this new page.
o The original shared page remains unchanged for the other task.
4. Mach OS uses Shadow Objects to store the modified pages.
5. Multiple shadow objects can form a shadow chain during repeated copy-on-write
operations.
Advantages of Copy-on-Write
• Saves memory by avoiding unnecessary copying.
• Faster process creation (e.g., fork()).
• Improves memory utilization.
• Reduces CPU overhead.
• Efficient for read-only shared data.
Disadvantages of Copy-on-Write
• Slight overhead during the first write operation.
• Shadow object management increases complexity.
• Performance may reduce if many pages are modified.
Advantages of Memory Management in Multiprocessor Systems
• Efficient memory sharing.
• Better processor utilization.
• Faster execution of parallel programs.
• Improved memory protection.
• High scalability and reliability.
6. Explain User-Level Threads and Kernel-Level Threads. Compare both. ( reapeated )
1. User-Level Threads (ULT)
Definition
User-Level Threads are threads that are created, managed, and scheduled entirely by the user-level
thread library. The operating system kernel is not aware of these threads.
Characteristics
• Managed by the user-level thread library.
• Kernel is not aware of the threads.
• Thread creation and switching are fast.
• Does not require kernel support.
• If one thread performs a blocking system call, the entire process blocks.
Advantages
• Fast thread creation and switching.
• Low overhead.
• Portable across operating systems.
Disadvantages
• Entire process blocks if one thread blocks.
• Cannot achieve true parallelism on multiprocessor systems.
2. Kernel-Level Threads (KLT)
Definition
Kernel-Level Threads are threads that are created, managed, and scheduled directly by the
operating system kernel.
Characteristics
• Managed by the operating system kernel.
• Kernel is aware of all threads.
• Supports true parallel execution on multiprocessor systems.
• If one thread blocks, other threads continue executing.
• Thread operations require kernel support.
Advantages
• Supports parallelism.
• Better responsiveness.
• Blocking of one thread does not affect other threads.
Disadvantages
• Thread creation and switching are slower.
• Higher overhead due to kernel involvement.