彼得森互斥算法|集1（基本C实现）-yiteyi-C++库

问题： 给定两个进程i和j，您需要编写一个程序来保证这两个进程之间的互斥，而不需要任何额外的硬件支持。

null

解决方案： 有多种方法可以解决这个问题，但大多数方法都需要额外的硬件支持。最简单也是最流行的方法是使用彼得森的互斥算法。它是由彼得森在1981年开发的，不过这方面的最初工作是由提出 德克尔算法 1960年，彼得森对其进行了改进，后来被称为 彼得森算法 .

基本上，彼得森的算法通过只使用共享内存来保证互斥。它在算法中使用了两种思想：

愿意获得锁。
转向获取锁。

先决条件： C语言中的多线程

说明：

这个想法是，首先一个线程表示它想要获得一个锁并设置 标志[self]=1 然后让另一个线程有机会获得锁。如果线程希望获得锁，那么它将获得锁并将机会传递给第一个线程。如果它不希望获得锁，那么while循环将中断，第一个线程将获得机会。

C语言的实现

C

                         // Filename: peterson_spinlock.c                       
                         // Use below command to compile:                       
                         // gcc -pthread peterson_spinlock.c -o peterson_spinlock                       
           
                         #include <stdio.h>                       
                         #include <pthread.h>                       
                         #include"mythreads.h"                       
           
                         int                                     flag[2];                       
                         int                                     turn;                       
                         const                                     int                                     MAX = 1e9;                       
                         int                                     ans = 0;                       
           
                         void                                     lock_init()                       
                         {                       
                                                 // Initialize lock by resetting the desire of                       
                                                 // both the threads to acquire the locks.                       
                                                 // And, giving turn to one of them.                       
                                                 flag[0] = flag[1] = 0;                       
                                                 turn = 0;                       
                         }                       
           
                         // Executed before entering critical section                       
                         void                                     lock(                                     int                                     self)                       
                         {                       
                                                 // Set flag[self] = 1 saying you want to acquire lock                       
                                                 flag[self] = 1;                       
           
                                                 // But, first give the other thread the chance to                       
                                                 // acquire lock                       
                                                 turn = 1-self;                       
           
                                                 // Wait until the other thread looses the desire                       
                                                 // to acquire lock or it is your turn to get the lock.                       
                                                 while                                     (flag[1-self]==1 && turn==1-self) ;                       
                         }                       
           
                         // Executed after leaving critical section                       
                         void                                     unlock(                                     int                                     self)                       
                         {                       
                                                 // You do not desire to acquire lock in future.                       
                                                 // This will allow the other thread to acquire                       
                                                 // the lock.                       
                                                 flag[self] = 0;                       
                         }                       
           
                         // A Sample function run by two threads created                       
                         // in main()                       
                         void                                     * func(                                     void                                     *s)                       
                         {                       
                                                 int                                     i = 0;                       
                                                 int                                     self = (                                     int                                     *)s;                       
                                                 printf                                     (                                     "Thread Entered: %d"                                     , self);                       
           
                                                 lock(self);                       
           
                                                 // Critical section (Only one thread                       
                                                 // can enter here at a time)                       
                                                 for                                     (i=0; i<MAX; i++)                       
                                                 ans++;                       
           
                                                 unlock(self);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 // Initialized the lock then fork 2 threads                       
                                                 pthread_t p1, p2;                       
                                                 lock_init();                       
           
                                                 // Create two threads (both run func)                       
                                                 pthread_create(&p1, NULL, func, (                                     void                                     *)0);                       
                                                 pthread_create(&p2, NULL, func, (                                     void                                     *)1);                       
           
                                                 // Wait for the threads to end.                       
                                                 pthread_join(p1, NULL);                       
                                                 pthread_join(p2, NULL);                       
           
                                                 printf                                     (                                     "Actual Count: %d | Expected Count: %d"                                     ,                       
                                                 ans, MAX*2);                       
           
                                                 return                                     0;                       
                         }                       

C

                         // mythread.h (A wrapper header file with assert                       
                         // statements)                       
                         #ifndef __MYTHREADS_h__                       
                         #define __MYTHREADS_h__                       
           
                         #include <pthread.h>                       
                         #include <assert.h>                       
                         #include <sched.h>                       
           
                         void                                     Pthread_mutex_lock(pthread_mutex_t *m)                       
                         {                       
                                                 int                                     rc = pthread_mutex_lock(m);                       
                                                 assert                                     (rc == 0);                       
                         }                       
                                   
                         void                                     Pthread_mutex_unlock(pthread_mutex_t *m)                       
                         {                       
                                                 int                                     rc = pthread_mutex_unlock(m);                       
                                                 assert                                     (rc == 0);                       
                         }                       
                                   
                         void                                     Pthread_create(pthread_t *                                     thread                                     ,                                     const                                     pthread_attr_t *attr,                       
                                                 void                                     *(*start_routine)(                                     void                                     *),                                     void                                     *arg)                       
                         {                       
                                                 int                                     rc = pthread_create(                                     thread                                     , attr, start_routine, arg);                       
                                                 assert                                     (rc == 0);                       
                         }                       
           
                         void                                     Pthread_join(pthread_t                                     thread                                     ,                                     void                                     **value_ptr)                       
                         {                       
                                                 int                                     rc = pthread_join(                                     thread                                     , value_ptr);                       
                                                 assert                                     (rc == 0);                       
                         }                       
           
                         #endif // __MYTHREADS_h__                       

输出：

Thread Entered: 1Thread Entered: 0Actual Count: 2000000000 | Expected Count: 2000000000

产量为2*10 ⁹ 哪里10 ⁹ 由两个线程递增。

本文由 平克什·巴贾提亚 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章