Multiprocessor Operating System in Distributed Operating System

A multiprocessor operating system manages multiple processors within a single system to enhance performance, reliability, and efficiency. By utilizing parallel processing, tasks are divided into smaller sub-tasks that are processed concurrently, significantly improving system throughput and reducing latency. These systems are scalable, allowing for the addition of more processors to boost performance. They offer increased reliability and fault tolerance, as other processors can take over if one fails. The operating system ensures balanced workload distribution and efficient resource management, coordinating processes to maintain data consistency through synchronization mechanisms. Inter-processor communication and load balancing are crucial for optimal performance. Multiprocessor systems can be symmetric, with processors sharing memory equally, or asymmetric, with a master processor allocating tasks. Despite their complexity and higher costs, they are ideal for high-demand applications like scientific simulations.

1. NADAR SARASWATHI COLLEGE ARTS AND SCIENCE distributed operating system MULTIPROCESSOR OPERATING SYSTEM Presented by , Varshini r i-m.sc(cs)

2. INDEX 17.1 - Introduction 17.2 - Structures Of Multiprocessor Operating System 17.3 - Operating System Design Issues 17.4 - Threads 17.5 - Process Synchronization

3. 17.1 INTRODUCTION Multiprocessor operating systems are similar to multiprogrammed uniprocessor systems in that they perform resource management and hide hardware complexities to provide a high-level machine abstraction to users. However, they are more complex due to the need for multiple processors to execute tasks concurrently with physical rather than virtual concurrency. To increase performance, a multiprocessor operating system must support concurrent execution of multiple tasks and effectively utilize multiple processors.

4. 17.2 STRUCTURES OF MULTIPROCESSOR OPERATING SYSTEMS Based on the control structure and organization, there are three main classes of multiprocessor operating systems: 1. Separate Supervisor Configuration : Each processor has its own copy of the kernel, supervisor, and data structures, with common data structures for inter-processor communication. This configuration minimizes coupling among processors but makes parallel task execution challenging and is inefficient due to code replication and poor fault tolerance.

5. 2. The Master-Slave Configuration : One processor (the master) controls all other processors (slaves), assigning tasks and monitoring status. Slaves execute application programs under the master's supervision, which simplifies implementation but creates a single point of failure and potential bottlenecks, limiting parallel execution efficiency. Examples include Cyber 170 and DEC-10.

6. 3. The Symmetric Configuration : All processors are autonomous and treated equally, sharing one copy of the kernel. This setup allows for more flexible and efficient parallel execution of tasks and is more resilient to processor failures. It supports better load balancing and avoids single points of failure. Examples include the Hydra system on the C.mmp .

7. 17.3 OPERATING SYSTEM DESIGN ISSUES A multiprocessor operating system must support concurrent task execution, exploit multiple processors, ensure physical concurrency, and manage execution and process coordination efficiently. Key issues include Threads Process Synchronization Processor Scheduling Memory Management Reliability and Fault Tolerance

8. 1. Threads : Effective parallel computing relies on the ability to express and control parallelism. Threads, widely used in applications, help manage concurrency but can impose significant overhead if not managed properly. 2. Process Synchronization : Ensuring processes operate in sync is crucial. Inadequate synchronization can lead to performance issues. 3. Processor Scheduling : Efficient hardware use requires scheduling that balances tasks across processors, optimizing parallelism.

9. 4. Memory Management : Shared memory complicates design. Operating systems must manage memory access and consistency to avoid conflicts. 5. Reliability and Fault Tolerance : Systems should degrade gracefully and have mechanisms to recover from failures.

10. 17.4 THREADS Traditional processes have a single address space and control thread. To enhance performance, threads can be created and managed at either the user or kernel level, each with distinct advantages and challenges. Managing state information in multiprocessor operating systems includes handling page tables, swap images, file descriptors, and I/O requests. This state information is maintained per program and per process, increasing the cost and complexity of process creation and maintenance.

11. With shared memory multiprocessor systems, it's crucial to switch processes to fully exploit concurrency. Effective parallel computing relies on managing primitives that control parallelism. For example, file servers must efficiently manage different user requests, which can be simplified by maintaining separate processes for each user. Threads or lightweight processes help handle frequent process switching efficiently. Threads separate execution notions from process definitions, allowing parts of a program to run concurrently within the same address space. Each thread has its program counter, stack, and control block, and shares most process information with other threads, reducing overhead.

12. To manage frequent process creation, maintenance, and switching, threads (or lightweight processes) are used. A thread executes a part of a program and collaborates with other threads within the same address space. Each thread has its own program counter, stack of activation records, and control block containing thread management information, like readiness and synchronization with other threads. Most process information is shared among threads, reducing the overhead and the data that needs to be saved during thread switches. Threads can operate at the user level or the kernel level, each with specific advantages, disadvantages, and performance impacts. User-level threads are managed by runtime libraries without needing kernel intervention, offering good performance but with potential inefficiencies in multiprocessor systems compared to kernel-level threads.

13. 17.4.1 USER-LEVEL THREADS Threads can be implemented at either the user level or the kernel level, each with its own set of advantages, disadvantages, and performance implications. User-level threads are managed by runtime libraries, do not require kernel intervention, and typically offer excellent performance at a lower cost compared to kernel-level threads. No modifications in the existing operating system kernel are required to support user-level threads

14. User-level threads, while advantageous, face several limitations. Their performance, excellent for certain parallel programs, may not suit applications requiring fine-grained movement. Operating within traditional processes, user-level threads execute as virtual processors but rely on physical processors controlled by the OS kernel. This leads to scheduling and synchronization issues, as the kernel might reallocate processors during time slices, causing discrepancies. Blocking system calls are problematic, as one blocked thread can block all threads in its block, potentially leading to deadlocks. Nonblocking system calls are essential for user-level threads, but many frequent calls in UNIX, like file operations, are blocking.

15. 17.4.2 KERNEL LEVEL THREADS Kernel-level threads have several disadvantages. Thread management operations incur higher overhead relative to user-level threads. Every operation involves a kernel trap, even when the processor is multiplexed between the threads in the same address space. On every thread operation, there is overhead due to copying and checking of parameters being passed to the kernel for validation. Since the kernel is the sole provider of thread managing operations, it has to provide an appropriate mechanism for any reasonable application. This generality means that every new feature needed by any application feature still have to incur overhead due to unused features provided in the kernel.

16. In summary: (1) kernel-level threads are too costly to use, and (2) user-level threads can provide excellent performance, but problems such as a lack of coordination between synchronization and scheduling, and blocking system calls, pose serious challenges to performance potential. System developers have favored user-level threads, despite their disadvantages. This is because they provide excellent performance. The cause of problems with user-level threads are related to the following facts. User-level threads are not recognized or supported by the kernel .

17. 17.4.3 FIRST CLASS THREADS The above problems have been addressed in at least two different ways: (1) by granting user-level threads a first-class status so that they can be used as traditional processes, thus leaving the details of the implementations to the user-level code, and (2) by combining the advantages of kernel events to the user-level thread scheduler. We next describe two thread mechanisms based on the above approaches.

18. 1. The kernel and the thread package share important data structures, allowing the thread package to access kernel-managed data through read-only mechanisms. This sharing occurs without requiring a system call. The kernel can also communicate with the thread package by specifying what actions are needed when kernel detects specific events like timer expirations.

19. 2. the kernel provides the thread package with software interrupts (signals, upcalls) to make scheduling decisions when necessary. For example, a user-level interrupt handler is activated to take care of scheduling decisions when a thread blocks or resumes after blocking. Timer interrupts support the thread package by allowing preemption, aiding in the proper allocation of kernel resources .

20. 3. Scheduler interfaces are provided to enable the kernel to block and unblock threads efficiently. These interfaces facilitate synchronization between the kernel and user-level threads, helping solve issues like the producer-consumer problem across different thread packages. For instance, the kernel can store the identity of the unblocking routines in the thread data structure and unblock the corresponding consumer thread as needed.

21. 17.4.4 SCHEDULER ACTIVATIONS The kernel and thread package share critical data structures, allowing read-only access to kernel-managed data by the thread package through shared memory. The kernel provides the thread package with software interrupts for scheduling decisions and managing preemption. Scheduler interfaces enable the communication between the kernel and user-level threads, allowing for blocking and unblocking of threads and synchronization. A scheme based on scheduler activations addresses user-level thread disadvantages by ensuring efficient communication between the kernel and user-level thread packages .

22. Notifying Kernel-Level Events to User-Level Threads When a user-level thread blocks in the kernel space, the kernel creates an activation for the blocked thread, freeing it for reuse. This activation mechanism enables seamless switching between kernel and user-level threads, optimizing performance and handling critical events efficiently. The approach balances the load, ensuring that user-level threads can operate with minimal overhead while still benefiting from kernel-level event handling

23. Notifying User-Level Events to the Kernel When the kernel detects that a user-level thread is stopped, it informs the user-level thread system of the event, allowing it to manage thread reactivation appropriately. This cooperation ensures that user-level threads remain responsive and that resources are efficiently utilized, preventing deadlocks and ensuring smooth operation across different scheduling contexts.

24. 17.5 PROCESS SYNCHRONIZATION Process Synchronization is a mechanism in operating systems that coordinates the execution of processes to ensure they operate without conflicts, especially when they share resources. It is crucial in environments with concurrent processes, such as multiprogramming and multiprocessing systems, where multiple processes may need to access shared data or resources (like files, memory, or printers).

25. 17.5.1 ISSUES IN PROCESS SYNCHRONIZATION: The execution of concurrent programs on multiprocessor systems often requires processors to access shared data structures, potentially causing performance bottlenecks. A mechanism is needed to ensure mutual exclusion and avoid conflicts when accessing shared data. Existing solutions for uniprocessor systems, like busy-waiting, are inefficient for multiprocessor systems due to high interconnection network traffic. Effective synchronization requires mechanisms that minimize contention and maintain high performance

26. 17.5.2 THE TEST-AND-SET INSTRUCTION: The test-and-set instruction is used to achieve mutual exclusion by reading and modifying a memory location atomically. The function is defined as function Test-and-Set(var S: boolean ): boolean ; begin Test-and-Set := S; S := true; end; It returns the current value of S and sets S to true. This instruction ensures that a critical section can be entered only by one processor at a time.

27. 17.5.3 THE SWAP INSTRUCTION: The swap instruction exchanges the contents of two variables atomically. It is defined as follows: ALGORITHM procedure Swap(var x, y: boolean ); var temp: boolean ; begin temp := x; x := y; y := temp; end;

28. Using the swap instruction, the P and V operations can be implemented to achieve synchronization. If S is the semaphore: P(S): repeat Swap(S, temp) until temp = false; V(S): S := false; this ensures mutual exclusion by allowing only one process to enter the critical section at a time.

29. 17.5.4 THE FETCH-AND-ADD INSTRUCTION: The fetch-and-add instruction atomically adds a constant to a memory location and returns the previous value. It is defined as: ALGORITHM: function Fetch-and-Add(var x: integer; increment: integer): integer; begin Fetch-and-Add := x; x := x + increment; end;

30. This instruction can be used for implementing semaphore operations and other synchronization mechanisms by ensuring atomic updates to shared variables The fetch-and-add instruction enables mutual exclusion by performing an atomic increment operation. When multiple processors attempt to modify the same memory location, the instruction ensures that only one succeeds, reducing the variable by 1. This is particularly useful for implementing P (wait) and V (signal) operations on semaphores, as it ensures consistent access control.

31. Algorithm for Fetch-and-Add (P and V Operations): P(S): while (Fetch-and-Add(S, -1) < 0) do nothing; Begin Fetch-and-add(s,1); While(s<=0)do nothing; End; This checks if the resource is available, waiting until S is greater than 0. V(S): Fetch-and-Add(S, 1); This operation increments S, signaling the release of the resource.

32. 17.5.5 SLIC CHIP OF THE SEQUENT The Sequent Balance/21000 multiprocessor system uses SLIC chips to support a low-level mutual exclusion hardware mechanism. Each processor has a local SLIC chip, reducing network traffic and improving performance by storing status locally. When a processor wants to lock a resource, it attempts to close the gate on its SLIC chip. If successful, it sends a lock status to other chips, allowing for coordinated access across the system P(S): while (lock-gate(S) =failed) do nothing; V(S):unlock-gate(S);

33. 17.5.6 IMPLEMENTATION OF PROCESS WAIT To handle process wait, systems use techniques like busy-waiting, sleep-lock, and queuing. In busy-waiting, processors repeatedly check for resource availability, which can waste CPU cycles. Sleep-lock allows suspended processes to release resources, waking up when conditions are met. Queuing involves placing waiting processes in a queue, preventing redundant checks and enhancing efficiency

34. Busy Waiting: Processors repeatedly check the shared variable status in a tight loop. While simple, this method can waste CPU cycles and network bandwidth. Sleep-Lock: This technique suspends processes when the lock is not available, allowing other processes to execute. When a process is resumed, it checks the lock again, improving efficiency compared to busy-waiting. Queuing: Processes waiting for a resource are placed in a queue. When the resource becomes available, the next process in the queue is granted access, reducing unnecessary polling and optimizing resource usage.

35. 17.5.7 THE COMPARE-AND-SWAP INSTRUCTION IBM’s 370 series implements the compare-and-swap instruction, an optimistic synchronization mechanism that compares a register and memory location before swapping values. This instruction is critical for concurrency control and managing shared data in multiprocessor systems.

36. Algorithm for Compare-and-Swap (CAS): Compare-and-Swap r1, r2, mem: integer; var temp: integer; begin temp := r1; if temp = r2 then {r2 := mem; r2 := temp;} else { goto label;} end.

37. In this algorithm: r1 and r2 are registers, and mem is a memory location. The CAS operation checks if r1 equals mem. If true, it assigns r2 to mem, indicating a successful swap. If false, it moves to the next step or retry. This atomic operation minimizes overhead and avoids the need for explicit lock mechanisms

38. The Compare-and-Swap (CAS) instruction is used in multiprocessor systems to achieve atomicity in synchronization. This operation compares a memory location with a register (R1) and, if they match, updates the memory with the value in another register (R2). If the comparison fails, the CAS operation does not change the memory location. The CAS operation is used to coordinate processes in critical sections without explicit locks, reducing contention and enabling more efficient concurrent access to shared data. .