StudentShare
Contact Us
Sign In / Sign Up for FREE
Search
Go to advanced search...
Free

Mutual Exclusion in Multiprocessor Systems - Research Proposal Example

Cite this document
Summary
The paper "Mutual Exclusion in Multiprocessor Systems" aims at studying the possible mutual exclusion algorithms that are employed in a uni-processor system and in a multi-processor system. It is important for the programs to recognize the usage of any of the resources…
Download full paper File format: .doc, available for editing
GRAB THE BEST PAPER97.3% of users find it useful
Mutual Exclusion in Multiprocessor Systems
Read Text Preview

Extract of sample "Mutual Exclusion in Multiprocessor Systems"

Mutual Exclusion in Multi Processing Systems The Problem In any processing environment that runs more than one program or task at the same time has the problem of restricting resource access by multiple processes at the same time. In the course of a normal execution of any two programs on the same processor (uniprocessor systems) there is always a possibility that the programs might request for the same resource. If the resource is employed by one program and if the other program should request for it, then either a queue gets built up if it could be queued. Such issues can happen with a multi processor systems as well on a larger scale. This issue can be resolved by employing an appropriate mutual exclusion of the programs and their resources so that no two programs would request for the same resource if one of them is using it already. Therefore, under many occasions, it is important for the programs to recognise the usage of any of the resources and should provide for resolving the same at the earliest possible opportunity. This paper aims at studying the possible mutual exclusion algorithms that are employed in a uni-processor system and in a multi-processor system. Methodology In this study on the mutual exclusion, the following methodology will be adopted: 1. The problems that are resolved by the mutual exclusion are identified and listed out. 2. The solutions and the algorithms that are normally adopted for resolving the problems listed above are also listed and identified. 3. Both are analysed and a comprehensive solution is noted. This is then marked out in the recommendations or conclusions as the best fit for the problems at hand. Adapting this methodology, the paper is presented as below. Existing Literature Basics With reference to the execution of a code or a section of a code, these should not be executed by two processes at the same time. They are to be critical code. Assuming that there will be multiple processes running on multiple processors, there could be more than one process requesting for the same resource. It is important for all the requesting processes to allow one process to run at a time. Mutual exclusion algorithms should ideally provide lee-way for the following options: 1. Freedom from deadlock: Locking is the simplest way of avoiding repeat use of critical processes. While locking can be effective for stopping execution of a job, when another one is running, it might not be fool proof. For instance, if process 1 locks a critical section A for its use and it makes use of section B for execution of the section A and suppose process 2 locks section B and for its execution if it needs section A which is locked already by process 1, then a dead lock occurs. (Figure 1). Any successful mutual exclusion should also avoid deadlocking. Figure 1. Deadlocking 2. Freedom from Livelocking: This is a desirable requirement for the algorithms offering the mutual exclusion. This would ensure that there is no permanent lock existing for any process; a corollary of the deadlocking. But it also says that if some process wants to enter a critical section, one such process will enter the critical section. This implies that the one that enters the critical section need not be the one that is requesting now but could be the one in the queue already. 3. Freedom from starvation: This is one of the desirable features of the algorithms for mutual exclusion. It is important that every process requesting for an entry to a critical section, eventually enters it even if there is a time delay. The Algorithms The simplest of the algorithms would be the spin lock. There could be an indication that would let the processes looking for a critical section would know whether it is occupied or not. If it is so, then the process trying to use the critical section would go into a spin which would keep checking the critical section for availability. Else wait for a short while before trying again. This will be looped indefinitely. Every process will eventually get through when the section becomes free. The other method is to maintain a queue list and an indication telling the queue whether the resource is free or under use. These are the semaphores that comprise of the queue and an indicator. The queue would ensure the first come first served on the process with the option to alter the priority of execution. The first of the major solutions to the problem starts with the publication of Dijkstra (Dijkstra, E. W., September 1965) in 1965. This addressed the problem and provided for the freedoms of deadlock and livelock but did not take care of the starvation which was addressed by the Donald Knuth (Knuth, Donald E., May 1966) solution. But both these solutions were pretty complex implementations and was not adopted very well. Apart from this, the solutions assumed that many of the steps involving reads and writes into memory are atomic, which in reality is untrue. Similarly, these algorithms did not take care of possible failure of the hardware or a system crash during the execution of the critical section. These issues were sorted out and a simpler solution was provided by Leslie Lamport (Lamport, Leslie, August 1974) in 1974 but this was also preceded by a much simpler solution of Gary Peterson (Peterson, G. L., 13 June 1981) which continues to be the simplest and the easiest to implement. However, further and detailed study of the problems thrown up by mutual exclusion made sure there were other issues which need to be addressed beyond the fundamental ones. When there is a large shared data structure, then the issue of concurrent reading arises again. A number of solutions came up to take care of the issues raised. Concurrent reading and writing solution that would ensure that the readings can take place concurrently while at the same time writing will be mutually exclusive of other writes and the reads. This was modified by Leslie Lamport (November 1977) to enable non exclusivity of the reads and exclusivity of writes alone between themselves. While for the reads, multiple reads, he suggested, are to be executed to ensure that the data collected is right and is not changing. This was found to be better when compared with a wait lock that could take much longer time. But then, this also had the possibility of committing a mistake. Some of the complications were brought in when there are multiple processors and having multiple memories shared across them. This would involve remote memory access during the course of contention which in itself would produce delays during the mutual exclusion algorithm. Therefore, in order to ensure that the exclusion algorithm does not lose out on the time taken and on the efficiency of the job, a number of other algorithms were suggested (M. Merritt and G. Taubenfeld, October 2000). Mutual exclusion algorithms that are adaptive are gathering interest. The adaptive algorithms have a time complexity that is a function of the number of contending processes. It has also been proved by a number of researchers (G. Graunke and S. Thakkar, June 1990) that the local spin algorithms scale well when the number of contending processes increases whereas the others are not (Y.-J. Kim and J. Anderson, January 2007). Local spin algorithms use the local memory partition for all its access in lieu of using a remote partition for mutual exclusion local spinning purposes. This would ensure that the memory contention is minimal and any delay caused therein is reduced grossly. Conclusion While many algorithms have been stated, for simpler requirements even with specific handicaps in the implementation might be sufficient for selective projects. We need to evaluate the requirement of the project to ascertain which of the methods of mutual exclusion could be adopted for the purpose. Though, the best available at this point in time could be derived out of such algorithms as adaptive local spinning as suggested by Anderson and Kim. However, we might even adopt one of the other methods suggested by Lamport (February 1987) in his fast mutual exclusion algorithm and subsequently improved upon by Styer (August 1992). In either of the cases, we find that the algorithms are reasonably resilient and could be implemented for applications that are distributed and multi processor ones. Whereas, in simple multi process applications with uniprocessor systems, it is always comfortable to implement the simplest form of the algorithm as suggested by Peterson where memory contention is not a major issue. References 1. Dijkstra, E. W., (September 1965) Solution of a problem in concurrent programming control. Communications of the ACM 8, 9, 569. 2. Knuth, Donald E. (May 1966) Addition comments on a problem in concurrent programming control. Communications of the ACM 9, 5, 321--322. 3. Lamport, Leslie. (August 1974) A new solution of Dijkstras concurrent programming problem. Communications of the ACM 17, 8, 453--455. 4. Peterson, G. L. (13 June 1981) Myths about the mutual exclusion problem. Information Processing Letters 12, 3, 115--116. 5. Lamport, Leslie, (November 1977) Concurrent reading and writing. Communications of the ACM 20, 11, 806--811. 6. M. Merritt and G. Taubenfeld. (October 2000) Computing with infinitely many processes. In Proceedings of the 14th International Symposium on Distributed Computing, pages 164–178. Lecture Notes in Computer Science1914, Springer-Verlag. 7. G. Graunke and S. Thakkar. (June 1990) Synchronization algorithms for shared-memory multiprocessors. IEEE Computer, 23:60–69. 8. Y.-J. Kim and J. Anderson, (January 2007), " Adaptive Mutual Exclusion with Local Spinning ", Distributed Computing , Volume 19, Number 3, pp. 197-236. 9. Lamport, Leslie. (February 1987) A fast mutual exclusion algorithm. ACM Transactions on Computer Systems 5, 1, 1--11. 10. E. Styer. (August 1992) Improving fast mutual exclusion. In Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing, pages 159–168. Read More
Cite this document
  • APA
  • MLA
  • CHICAGO
(Mutual Exclusion in Multiprocessor Systems Research Proposal Example | Topics and Well Written Essays - 1500 words, n.d.)
Mutual Exclusion in Multiprocessor Systems Research Proposal Example | Topics and Well Written Essays - 1500 words. https://studentshare.org/technology/1539175-mutual-exclusion-in-multiprocessor-systems
(Mutual Exclusion in Multiprocessor Systems Research Proposal Example | Topics and Well Written Essays - 1500 Words)
Mutual Exclusion in Multiprocessor Systems Research Proposal Example | Topics and Well Written Essays - 1500 Words. https://studentshare.org/technology/1539175-mutual-exclusion-in-multiprocessor-systems.
“Mutual Exclusion in Multiprocessor Systems Research Proposal Example | Topics and Well Written Essays - 1500 Words”. https://studentshare.org/technology/1539175-mutual-exclusion-in-multiprocessor-systems.
  • Cited: 0 times

CHECK THESE SAMPLES OF Mutual Exclusion in Multiprocessor Systems

Distributed and Parallel Systems

With this solid background of multiprocessor systems, parallel computing, distributed systems and shared memory; speed-up performance law such as the Amdahl's law was introduced to throw light on algorithm design for speed-up and operational efficiency of parallel system.... Shared memory based parallel computing systems have multiple processors that access all available memory as a global address space.... In wide-spread distributed systems, work and information are physically distributed, implying that computing needs should be distributed....
15 Pages (3750 words) Term Paper

Synchronized Access to Shared Memory in a Multi Core Computer

The paper 'Synchronized Access to Shared Memory in a Multi-Core Computer' describes various techniques how to maintain control over memory access by using Hardware and Software co-ordination when A Chip-Level multiprocessor or a Multi-Core Processor has two or more independent CPUs integrated on a single Integrated Circuit.... hellip; A multi-core processor (or chip-level multiprocessor, CMP) combines two or more independent cores (normally a CPU) into a single package composed of a single integrated circuit....
4 Pages (1000 words) Lab Report

Gaps in Security Management of a Company

In the essay “Gaps in Security Management of a Company” the author discusses importance of security management and an attempt to show why the factor of security management is also considered to be a part of the business strategies.... hellip; The author states that in the recent years it has been observed that wit the advent of IT and Internet technologies, the rate of intervention to the affairs of a business has increased to a considerable extent....
20 Pages (5000 words) Essay

Symmetrical and Master-Slave Multiprocessing Architecture

In the similar manner all the processors in the symmetrical multiprocessing architecture share the memory, input and output devices, interrupts systems and other relevant system resources (Lyonnard, Yoo, Baghdadi & Jerraya, 2001).... Utilizing more than one processing units allows the programs to be executed and processed by taking less time and less burdening the central processing system....
2 Pages (500 words) Assignment

Multiprocessor Systems and Applications

It is difficult to obtain their spare parts (Darlington and Ghanem, 1993). The multiprocessor systems and Applications multiprocessor systems and Applications Multiprocessor strategies are procedures in accessible programming process.... Applications may experience challenges when operating a multiprocessor processor because of practices they create which are acceptable only to one-processor systems....
1 Pages (250 words) Essay

Distributed and Parallel Systems

With this solid background of multiprocessor systems, parallel computing, distributed systems, and shared memory; speed-up performance law such as the Amdahl's law was introduced to throw light on algorithm design for speed-up and operational efficiency of the parallel system.... The writer of the paper "Distributed and Parallel systems" suggests that in distributed and parallel computing, the interconnection between processes plays a significant role.... Shared memory based parallel computing systems have multiple processors that access all available memory as a global address space....
16 Pages (4000 words) Research Paper

The Issue of Gender in Relation to Inclusion and Exclusion

This essay "The Issue of Gender in Relation to Inclusion and Exclusion" explores how we are "engendered" (male and female) and what does this mean in relation to inclusion and exclusion in certain aspects of our society.... ow are we "engendered"(male and female) and what does this mean in relation to inclusion/exclusion in certain aspects of our society?... And whether the technology has changed the dynamics in terms of inclusion and exclusion....
7 Pages (1750 words) Essay

Social Inclusion and Social Exclusion

The paper “Social Inclusion and Social exclusion” highlights things that all the society.... The world is a wide society where certain things interplay in the social circles; the desire to belong, social exclusion and social inclusion (Wilson & Beresford, 2000).... Social exclusion is where individuals are marginalized, alienated or even disenfranchised because they are perceived to be different from the rest.... n Sula by Tom Morrison, the main character, Sula, is a victim of social exclusion....
5 Pages (1250 words) Book Report/Review
sponsored ads
We use cookies to create the best experience for you. Keep on browsing if you are OK with that, or find out how to manage cookies.
Contact Us