彼得森互斥算法|集2（CPU周期和内存限制）-yiteyi-C++库

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

null

我们强烈建议参考上一篇文章中讨论的基本解决方案。彼得森互斥算法|集1 在前面的算法中，我们将解决两个问题。

CPU时钟周期的浪费

用外行的话说，当线程等待轮到它时，它会在一个长时间的while循环中结束，该循环每秒测试该条件数百万次，从而进行不必要的计算。有一种更好的等待方式，它被称为 “收益率” .

为了理解它的功能，我们需要深入了解进程调度器在Linux中的工作原理。这里提到的想法是调度器的简化版本，实际实现有很多复杂之处。

考虑下面的例子，有三个过程，P1、P2和P3。进程P3有一个类似于代码中的while循环，它不做那么有用的计算，只有当P2完成执行时，它才从循环中存在。调度程序会将所有这些任务都放入循环队列中。现在，假设处理器的时钟速度是1000000/秒，它在每次迭代中为每个进程分配100个时钟。然后，第一个P1将运行100个时钟（0.0001秒），然后是P2（0.0001秒），然后是P3（0.0001秒），现在由于没有更多进程，该循环将重复，直到P2结束，然后是P3的执行，最后是其终止。

这完全是在浪费100个CPU时钟周期。为了避免这种情况，我们相互放弃CPU时间片，即产量，这基本上结束了这个时间片，调度器选择下一个进程运行。现在，我们测试一次我们的条件，然后我们放弃CPU。考虑到我们的测试需要25个时钟周期，我们在一个时间片中节省了75%的计算量。用图形的方式说，

图片[1]-彼得森互斥算法|集2（CPU周期和内存限制）-yiteyi-C++库

考虑到处理器时钟速度为1MHz，这节省了很多钱！。不同的发行版提供了不同的功能来实现这一功能。Linux提供 sched_收益率（） .

C

                         void                                     lock(                                     int                                     self)                       
                         {                       
                                                 flag[self] = 1;                       
                                                 turn = 1-self;                       
           
                                                 while                                     (flag[1-self] == 1 &&                       
                                                 turn == 1-self)                       
                                   
                                                 // Only change is the addition of                       
                                                 // sched_yield() call                       
                                                 sched_yield();                       
                         }                       

记忆栅栏。

早期教程中的代码可能适用于大多数系统，但不是100%正确。逻辑是完美的，但大多数现代CPU采用性能优化，这可能导致无序执行。内存操作（加载和存储）的这种重新排序通常在单个执行线程中不会被注意到，但在并发程序中可能会导致不可预测的行为。考虑这个例子，

C

while (f == 0);

// Memory fence required here

print x;

在上面的例子中，编译器认为这两条语句彼此独立，因此试图通过对它们重新排序来提高代码效率，这可能会导致并发程序出现问题。为了避免这种情况，我们设置了一个内存围栏，向编译器提示跨越该围栏的语句之间可能存在的关系。

所以陈述的顺序，

flag[self]=1；转身=1-self； while（转向条件检查）屈服（）；

必须完全相同才能使锁工作，否则它将最终处于死锁状态。

为了确保这一点，编译器提供了一条指令，防止语句的顺序跨越这一障碍。对于gcc，其 __sync_synchronize（） . 所以修改后的代码变成， C语言的全面实现：

C

                         // Filename: peterson_yieldlock_memoryfence.c                       
                         // Use below command to compile:                       
                         // gcc -pthread peterson_yieldlock_memoryfence.c -o peterson_yieldlock_memoryfence                       
           
                         #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 reseting 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;                       
           
                                                 // Memory fence to prevent the reordering                       
                                                 // of instructions beyond this barrier.                       
                                                 __sync_synchronize();                       
           
                                                 // Wait until the other thread loses the                       
                                                 // desire to acquire  lock or it is your                       
                                                 // turn to get the lock.                       
                                                 while                                     (flag[1-self]==1 && turn==1-self)                       
           
                                                 // Yield to avoid wastage of resources.                       
                                                 sched_yield();                       
                         }                       
           
                         // 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()                       
                         {                       
                                                 pthread_t p1, p2;                       
           
                                                 // Initialize the lock                       
                                                 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

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

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

THE END

技术文章