Mutual Exclusion in Multiprocessor Systems - Research Proposal Example

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