Report on Lock Free Binary Search Algorithms
Added on 2020-05-04
21 Pages5837 Words100 Views
Running head: Lock Free Binary Search AlgorithmsLock Free Binary Search AlgorithmsName of the StudentName of the universityAuthor note
1Lock Free Binary Search AlgorithmsExecutive summary:The aim of the report is to analysis the lock-free structure of the binary search tree and thecorresponding concurrencies present in the methodology of the proposed algorithm. The resultsindicate the benefits of the tree data structure and the comparatively output that are beingwitnessed in the process of the analysis. This report provides the propositions of the futurerelated work in the field of lock-free BSTs. The internal BST has also proved to be beneficialover the existing external BSTs. An online survey was conducted for the same to achieve theobjectives as is set in the provided query list. The results indicate the linearisable of the nodepointers and deadlock prevention. The report concludes the future scope of researches and thebenefits of a lock-free structure. It is recommended to adapt the proposed methodologies toprevent any limitations to the access of any functions relative to the data present or inserted.
2Lock Free Binary Search AlgorithmsTable of ContentsINTRODUCTION:..........................................................................................................................31. MOTIVATION:...........................................................................................................................42. Overview:...................................................................................................................................53. Detailed Description:..................................................................................................................83.1 Structures:..............................................................................................................................94. Concurrency:..............................................................................................................................145. Related Work:............................................................................................................................156. Conclusion and Future Work:....................................................................................................17Bibliography..................................................................................................................................18
3Lock Free Binary Search AlgorithmsIntroduction:Recent researches oriented around the concurrent search tress that is a binary search treebest be described as a graphical presentation in which nodes follow up with specific componentswith left and right sub trees. The research and evaluation on the concurrent search tress hasprovided the necessary solutions, which is directly dependent on either the locking segments ofthe data framework or the exhibit suboptimal memory utility. Trees are not as significant to beplaced parallelized segment for the fact that they comprise multiple networks of mutable sectorsper node but the overall search that is a time relative issue compared with the simpler existingstructures as such the linked lists properties creates a demand for them. Utilizing certaincomponent, in this report a binary search tree, parallel in nature is created. The components soused are single-word reads, writes and the compare-and-swap. Accordingly, following thisalgorithm operations are only contend at the instances wherein, the concurrent updates are seento affect the similar node/ nodes. Updates are relatively non-blocking for the fact that the presentthreads are capable of accomplishing the operations based on the correlations among them andeach of the performed operations is linearisable. Evidences based on various experimentalmethodologies reveal the mentioned process to be faster as compared to the alternative solutionsand proves to be scalable compared to the large numbers of concurrently threads set to execute.This, in majority scenarios, outperforms the concurrent skip enlistments as set to test. Testifying,it shows or reveals that there is 65% more throughputs in the instance of the performancedifference is averaged in each experiment. Additionally, relative memory prints are smallercompared to the other examined structures.
4Lock Free Binary Search Algorithms1. Motivation:The present CPU configurations have achieved a relative stagnant level in relevance tothe single-threaded throughputs; with evolution in the configuration of chips, which in turnprovides smaller increments. The designers of the hardware have intended on the increment ofthe processing units per CPU arrangement. However, this introduced the necessity of improvedalgorithms that would be efficient enough to utilize the developed processing resources[ CITATION How12 \l 1033 ].Multiple threads should be capable of communication and synchronization proactively asan unit through the shared data structures present in the memory. The efficiency relative to theseData Structures might prove to be beneficial and crucial to the evaluation of performances whilethe relevant designs are considered difficult [ CITATION Ell14 \l 1033 ]. When, there is apresence of high value thread inter-leavings makes the configured algorithm to be difficult to beconsidered. An efficient measure oriented around the concept of unblocking or as mentioned,utilizing the term ‘lock-free’ is an implementation surrounding a shared object to make it easilyaccessible to the contentious proceedings. This systemized strategic implementation provides theguarantee of the system to progress even in the presence of one to multiple thread failures. Thiscan be conceptually put forward that the shared object is protected from any further accessrelative to any lock-related limitations. These limitations enlist the priority inversion, deadlockand convoying [ CITATION Cra13 \l 1033 ]. In this report, an algorithm is introduced for a relatively binary search tree (BST). Thisproves to be compatible with the other available systems based on the reliance relative to the
5Lock Free Binary Search Algorithmscommonly adaptable and available operations. These common components are: Word readswrites and compare-swap (CAS) concepts [ CITATION Cra13 \l 1033 ]. Traversing thestructural tree is possible only in the space of read only memory without interfering with theconcurrent updates available. Majority of the updates oriented towards the internal structure ofthe tree system is potentially tolerated without any triggering towards rebooting. This report in a descriptive manner provides the algorithm configuration and the relevantoperations of the same followed by a detailed evaluation of a C++ configured implementation inthe upcoming sections. The report advances with the further briefing of the management issuesand the much-required solutions to them, put forward as efficient measures. Consequently, aproof schematic relative to the non-blocking operation and linearisability properties would bediscussed. This is a well-known fact that the constructed algorithm serves a good throughput ascompared with the set of concurrent algorithms and this is recorded to be better in the context ofscaling with the increment in number of threads [ CITATION Par12 \l 1033 ]. 2. Overview:This algorithm is set with a specific configuration to benefit the data structure interfaceset in an abstract framework. A set is recorded to comprise a set of unique set of keys withrelevant valuation oriented with specific methodologies and conditions. The consists ofinstructions likely as to: firstly, concerning the addition of a key (k)n to the existing set of whichit is still not a part, the instruction ‘add(k)’ is applied. Similarly, the removal of any key from theoriented set ‘remove (k)’ is instructed, when the same is already a member of the targeted set.Another important or major examination lies on the grounds to identify the existence of avariable or a key in the set; this uses the instruction ‘contains (k)’. The core orientation beneath
End of preview
Want to access all the pages? Upload your documents or become a member.