Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms

《Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Simple,Fast,andPracticalNon-BlockingandBlockingConcurrentQueueAlgorithmsMagedM.MichaelMichaelL.ScottDepartmentofComputerScienceUniversityofRochesterRochester,NY14627-0226fmichael,scottg@cs.rochester.eduAbstract1IntroductionConcurrentFIFOqueuesarewidelyusedinparallelap-Drawingideasfrompreviousauth

2、ors,wepresentanewplicationsandoperatingsystems.Toensurecorrectness,non-blockingconcurrentqueuealgorithmandanewtwo-concurrentaccesstosharedqueueshastobesynchronized.lockqueuealgorithminwhichoneenqueueandonede-Generally,algorithmsforconcurrentdatastructures,in-queuecanproceedconcurrently.Bothalgorit

3、hmsaresim-cludingFIFOqueues,fallintotwocategories:blockingple,fast,andpractical;weweresurprisednottofindthemandnon-blocking.Blockingalgorithmsallowasloworde-intheliterature.Experimentsona12-nodeSGIChallengelayedprocesstopreventfasterprocessesfromcompletingmultiprocessorindicatethatthenewnon-blockin

4、gqueueoperationsontheshareddatastructureindefinitely.Non-consistentlyoutperformsthebestknownalternatives;itisblockingalgorithmsguaranteethatifthereareoneormoretheclearalgorithmofchoiceformachinesthatprovideaactiveprocessestryingtoperformoperationsonashareduniversalatomicprimitive(e.g.compareandswap

5、ordatastructure,someoperationwillcompletewithinafiniteloadlinked/storeconditional).Thetwo-locknumberoftimesteps.Onasynchronous(especiallymulti-concurrentqueueoutperformsasinglelockwhenseveralprogrammed)multiprocessorsystems,blockingalgorithmsprocessesarecompetingsimultaneouslyforaccess;itap-suffers

6、ignificantperformancedegradationwhenaprocesspearstobethealgorithmofchoiceforbusyqueuesonma-ishaltedordelayedataninopportunemoment.Possiblechineswithnon-universalatomicprimitives(e.g.testsourcesofdelayincludeprocessorschedulingpreemption,andset).Sincemuchofthemotivationfornon-blockingpagefaults,andc

7、achemisses.Non-blockingalgorithmsalgorithmsisrootedintheirimmunitytolarge,unpre-aremorerobustinthefaceoftheseevents.dictabledelaysinprocessexecution,wereportexperimentalManyresearchershaveproposedlock-freealgorit