The Application Of GNU/Linux System Randomness In Sequential Lock

With the development of computer science and technology,the hardware technology of the computer is constantly improved and improved,which requires the software operating system running on the hardware to constantly adapt to the new hardware equipment.The synchronization mechanism,as an important part of the operating system,also needs to be constantly improved to make full use of CPU resources.With the increasing popularity of multi-core and core in life,the traditional lock exposes a serious problem,and the scalability is poor,which leads to the decrease of CPU utilization.Many kernel maintainers to start looking for a new algorithm to replace the traditional locking mechanism,in the current stable version of the Linux kernel,two kinds of lock-free algorithm has been applied,they respectively are RCU(Read-Copy-Update)and seqlock,also there are many unlocked algorithm is not added to the kernel thread,but has been published,such as the PWCS(Probabilistic Write / Copy-Select)of professor Nicholas Mc Guire.Sequential locks have been applied to the Linux operating system,solving the writer's hunger problem of traditional read-write locks and unlocking access for readers,but the mechanism can't control the reader's waiting time.If sequential locks are applied in a scenario where the number of writers is more numerous,the reader may be unable to read the data for a long time because of repeated attempts to read the failure.This seriously affects computer performance,especially in real-time systems.Based on the design idea of PWCS,this paper increases the number of copies of Shared data and reduces the waiting time of readers.On the basis of the improvement,we use the inherent randomness of Linux system,makes the reader start position is no longer a fixed,while reading copy from each copy of probability are equal,so as to further reduce the waiting time of the readers,and puts forward the design thinking of“probabilistic seqlock”.We test the probabilistic sequential lock in practice through a large number of examples.The waiting time of the reader in the probabilistic sequential lock is much less than that of the traditional sequential lock.In addition,this paper uses the method of model checking to verify the probabilistic sequential lock,because the mathematical method can automatically detect all the situations and save a lot of work.In this method,we use the continuous-time Markov chain model to establish a model for the probabilistic sequential lock and use the probabilistic model checking tool PRISM to program it.Finally,this mathematical way proves that the performance of the probabilistic sequential lock is indeed better than traditionalsequential lock.