Multi-processor systems OS

OBJECTIVE-TYPE QUESTIONS
Q1. _____ is a model of one address computer.
P-RAM
RAM
ROM
P-ROM

Ans: B

Q2. All algorithms for ___________________ can be expressed in terms of RAM model and its instruction set.

Parallel Machines
SIMD/ Vector Processing Systems
Sequential Machines
Every type of machines

Ans: C

Q3. Default behavior of P-RAM is running multiple instruction Streams on different processors. However, it possible to constraint all the processors to fetch and execute the same set of instructions? (True / False)

Ans: True.

Q4. A multi-computer system is a _____________ Whereas Multi-Processor System is a _____________

Collection of computer systems that include multiple processors, single autonomous computer that is interconnected with other systems for achieving parallelism.
Single autonomous computer that is interconnected with other systems for achieving parallelism, Collection of computer systems that include multiple processors.
Single Computer that include multiple processors, Collection of multiple interconnected autonomous computer systems.
Collection of multiple interconnected autonomous computer systems, Single Computer that include multiple processors.
Ans: D

Q5. The most suitable interconnection network for small multiprocessor systems (i.e. having upto 10 processing units) is:

Common Bus
Cross Bar Switch
Hierarchical Organization of Processors
None Of the Above
Ans: A

Q6. By organizing processors and memory modules in hierarchically, one can obtain _________ architecture.

UMA
NUMA
Symmetric
Asymmetric
Ans: B

Q7. _______________ , which is used for keeping latest updated value in cache for single processor systems, is neither necessary nor sufficient for achieving cache coherence in multi-processor systems.

Static Coherence Checking Algorithms
Dynamic Coherence Checking Algorithms
Write through fashion
Static & Dynamic Coherence Checking Algorithm and Write through mechanism
Ans: C

Q8. List possible organizations in design of operating systems for multi-processor systems:

Ans: 1. Master Slave Configuration
2. Separate Supervisor Configuration
3. Floating Supervisor Configuration

Q9. In which Message passing Model, the sender is also blocked till receiver receives and acknowledges the message?

Synchronous
Asynchronous
Both Synchronous and Asynchronous
In None of Message Passing Model sender get blocked

Ans: A

Q10. Does Message Passing Model require mechanism for mutual exclusion to access shared data? (Yes/NO)

Ans. Does not require (NO)

Q11. Multithreading is implementation of which parallel programming model?

Message Passing Model
Functional and Logical Models
Data Parallel Model
Shared Memory Model
Ans: D

Q12. Give an example (programming language) of Data parallel programming model for SIMD processors.

Ans: Fortran 90



SUBJECTIVE-TYPE QUESTIONS

Q1. Depending Upon the Sharing of resources Multiple Processor Systems can be classified into which categories? Explain each briefly. What are desirable properties of Multi-Processor Systems?
Ans: Depending Upon the Sharing of resources such as Memory, Clock, Computer bus and the way of Communication, Multi Processor Systems can be classified in following two categories:
Tightly Coupled Systems
Loosely Coupled Systems

· Tightly Coupled Systems:
The Tightly Coupled Multi Processor Systems are those in which the Processors are kept in close communication to share the processing tasks. These systems can further be divided in to two sub-categories:
1. Shared Memory Multi-Processor systems
2. Message Passing Multi-Computer Systems

Shared Memory Multi-Processor systems contain multiple processors that are connected at the system bus level. These systems allow 1000 CPU’s to communicate via a Shared Memory. Every CPU has equal access to the entire physical memory. These systems may also participate in a memory hierarchy with both local and shared memory.

Depending upon the way the Operating System used in Multiple Processors, two Organizations of Multi-Processor system are possible. These are:
Asymmetric Multiprocessor
Symmetric Multiprocessor

Asymmetric Multiprocessor: In an asymmetrical multiprocessor system, one processor, called Master, is dedicated to execute the Operating System. The remaining processors are usually identical and form a pool of computational processors. All the processors in this pool are called Slaves. The Master processor schedules the work and control the activities of the slave processors depending upon the resources available with them. Due to this arrangement of multi processors, it is also known as Master-Slave Multi Processing. In some asymmetrical multiprocessor system, the processors are assigned different roles such that they do not depend upon the master for their processing. For Example: One processor may handle all trivial requests and jobs like editing, calculating etc.


Symmetric Multi Processor: In a symmetrical multiprocessor system, all of the processors are essentially identical and perform identical functions. There is one copy of Operating System in Memory. The CPU, on which the system call was made, traps to the Kernel and processes the system calls. In such an arrangement there is said to be a floating Master as different processors execute operating system at different times.


Message Passing Multi-Computer Systems allow a number of CPU-Memory pairs (called node) to connect by some kind of high-speed interconnection. The Basic node of Multi Computer system consists of CPU, memory, a network interface and some times a hard disk but the Graphic adapter, monitor, keyboard and mouse are nearly always absent. Each memory is local to a single CPU and can only be directly accessed by that CPU. There is no shared memory in this design. So without a shared address space processors communicate by sending multiword messages over the interconnection (Message Passing) in order to share computational tasks. These systems are also known by a variety of names including Cluster Computers and COWS (Cluster Of Workstations).


These Multi-Computer systems can be either
Asymmetric Multi-Computers or
Symmetric Multi-Computers

1. In Asymmetric Multi-Computers, a front end computer interact with user as users may log into the front end computer which executes a full, multi-programmed operating System and provide all functions for program development. Other than this Front End Computer, other nodes of the Multi-Computer systems are Back End Computers, which are reserved for executing the parallel programs.
2. In Symmetric Multi-Computer operating system execute the same OS (Multi Programmed OS) and has identical functionality. User may log onto any computer to edit and compile their programs and any other computer may be called upon to execute a parallel program. This configuration of Multi Computer system solves the problem of single point of failure in Asymmetric Multi-Computer systems.

· Loosely Coupled Systems:
These types of Multi processor systems are also referred to as Distributed Systems. These are based on multiple standalone single or dual Processor Computers interconnected via a high-speed communication system (gigabit Ethernet is common). The intent of the distributed system is to turn a loosly connected bunch of machines into a cohrent system based upon one concept. This is done by having another layer of software on the top of the Operating System. This Layer is called Middleware.


Desireable Properties of MultiProcessor Systems:

Process Recoverability: - If aprocessor fails the process running on it should be recoverable. Another processor must be assigned to it. This can be achieved by maintaining a shared register file that keep a record of the state for each active process in the system.

Efficient Context Switching: - While executing parallel programs, it is needed to swap the processes in and out of the memory for efficient utilization of the resources. The processors must have efficient mechanisms to support Operating System in switching the context.

Large Virtual and Physical address space: - As the size of the problem being solved on the parallel machines, increases there is need for large memory space and addressing capacities.

Effective Synchronization Primitives: - Multiple processes that constitute a parallel program need to cooperate to compute results. This is possible by sharing data and providing access to shared data. To maintain the integrity of the data, access needs to be allowed only in exclusive mode.

Interprocess Communication Mechanism: - Multiprocessor systems must provide communication between cooperating processes in the form of signals, interrupts and messages.


Q2. What do you mean by programming model? Which are various Parallel Programming Models available?
Ans:
A programming model is a collection of program abstractions providing a programmer a simplified and transparent view of computer Hardware/Software system. Parallel programming models are specifically designed for multiprocessors, multi computer, SIMD or vector computers. There are five such models described bellow that differ in the way these processes share data, achieve synchronization and communication:

1. Shared Memory Programming: -
Multiprocessor programming is based on the use of shared variables in commonly accessible memory for communication and sharing data. Besides sharing variables in a common address space communication also takes place through software signals and interrupts. As multiple processors may attempt to access the shared data processes must ensure exclusive access to the critical sections (Part of the program accessing the shared resources or variables).
The implementation of the model is supported in various ways on different platforms.
· On UNIX platform it is available in the form of linkable libraries for creation of processes, shared memory blocks, semaphores and IPC mechanisms.
· This model is also available in the form of multithreading libraries.

2. Message Passing: -
Multi computer employ message passing as the mechanism for inter process communication. In this model, two processes residing on two different nodes communicate with each other by passing messages over communication channel. The message may be instruction, data, and synchronisation or interrupt signal.
Message passing model does not require mechanism for mutual exclusion for access to shared data as there is no way for processes to share each others address space.
The implementation of this model can be done by two ways as explained bellow:

a. Synchronous Message Passing: - It requires both the sender and receiver to be synchronized just like in telephone call communication. No buffering of message is done by communication channel.
The receiver is always blocked waiting for the message to arrive.
The sender is also blocked till receiver receives and acknowledges the message.
This mode of communication is suitable for tightly coupled message passing multi computer systems where communication delay overhead is sufficiently small.

b. Asynchronous Message Passing: - This mode of the model does not impose blocking on the sender. The outgoing messages get buffered in the communication channel and are delivered to target when target process chooses to look for it.
This mode of communication is suitable for loosely couples systems that are made up of networked autonomous machines.

3. Data-parallel Model: -
This model for SIMD processors is an extension of the sequential programming
The language compiler for a specific machine must translate the source code to executable object code, which will exploit the parallelism in the hardware. For Example: - Fortran is tailored for data parallelism.
The compilers must be aware of underlying interconnection topology to generate optimal code for array processor.
Synchronization of data parallel programs is done at compile time rather than at run time.

4. Object Oriented Model: -
In this model mapping of execution units to objects is achieved. These objects are dynamically created and manipulated. Sending and receiving messages among the objects achieve communication.
Concurrent programs are built from low level objects such as processes, threads, and semaphores into high level objects like monitors and program modules.



5. Functional and Logical Models: -
A functional programming language emphasizes the functionality of a program. There is no concept of storage, assignment and branching in functional programming. The evaluation of the function produces the same result regardless the order in which its arguments are evaluated.
Logical Programming is based upon predicate logic. This model is suitable for knowledge processing dealing with large database. This model adopts an implicit search strategy and support parallelism.
Both of these models are used in Artificial Intelligence Applications.



Q3. What are Abstract Models available for Sequential and Parallel Machines/Computers?
Ans:
The purposes of using such models are:
To get feel of the capacities of the machines without bothering about the specific constraints of the real life machines.
It is convenient to develop an algorithm for a general model and then to map it to the actual machine.

The abstract models available for Sequential as well as for parallel machines are:
RAM (Random Access Machine) à Abstract model of sequential computer.




P-RAM (Parallel RAM) à Abstract model of Parallel Computer.