操作系统实验

badmonkey 2020年05月18日 772次浏览

Dekker互斥算法

核心代码如下：

const int g_totalThreads = 2;
/*实现方法二，Dekker互斥算法*/
/*在下面定义算法相关的全局变量*/
int flag[2]= {0,0}; //表示线程是否想进入临界区
int turn = 0; // 表示轮到的进程编号
//参数id为当前的线程号
void Lock(int id)
{
    /*实现方法二，Dekker互斥算法*/
    // 首先将flag置为1,想要进入临界区
    flag[id] = 1;
    //判断对方是否也想进入临界区
    int Wait_count = 0;
    while(flag[(id^1)])
    {
        // 轮到了对方，那么自己就因该忙等，为了不干扰对方的进度，将自己的flag先暂时置为0，最后再恢复
        if(turn == (id^1))
        {
            flag[id] = 0;
        }
        // 忙等。等到自己的轮次，为止。随便记录一下等待次数

        while(turn == (id^1))
        {
            Wait_count++;
        };
        // 终于轮到了我了。。再把之前的flag变回来
        flag[id] = 1;
    }
    // 顺便输出一下我等了多久qaq
    //std::cout<<"I Have waited "<<Wait_count<<" times"<<std::endl;
    // 进入临界区。。
}
//参数id为当前的线程号
void unLock(int id)
{

    /*实现方法二，Dekker互斥算法*/
    //从临界区出来了。。就应该老实点。把位置让出来
    turn = (id^1);
    // 然后。将flag置为0
    flag[id] = 0;

}

实验结果

输出效果算法效率
image-20200518102636487image-20200518102801452

可以看到，算法效率还可以接受。除了第一次会出现忙等很多次。其他情况忙等次数为0

Peterson互斥算法

核心代码如下:

const int g_totalThreads = 2;
/*实现方法二，Dekker互斥算法*/
/*在下面定义算法相关的全局变量*/
int flag[2]= {0,0}; //表示线程是否想进入临界区
int turn = 0; // 表示轮到的进程编号
//参数id为当前的线程号
void Lock(int id)
{
    /*实现方法二，Peterson互斥算法*/
    // 自己要临界区的时候，同时把turn转给对方。防止两个人同时想进临界区。出现问题
    flag[id] = 1;
    turn = id^1;
    int Wait_count = 0;
    // 忙等对方,统计等待次数
    while(flag[id^1]&&turn == id^1)
    {
        Wait_count++;
    }
    //进入临界区，输出等待次数
    //std::cout<<"I Have waited "<<Wait_count<<" times  ";
    // 进入临界区。。
}
//参数id为当前的线程号
void unLock(int id)
{

    /*实现方法二，Peterson互斥算法*/
    // 出了临界区,将自己的flag置为0
    flag[id] = 0;
}

实验结果：

实验结果算法效率
image-20200518105431229image-20200518105544368

可以看到总体上和Derkker算法效率不相上下，但是编程实现更加简单。

Lamport互斥算法

核心代码:

const int g_totalThreads = 5;
/*实现方法三，Lamport互斥算法*/
/*在下面定义算法相关的全局变量*/
int choosing[g_totalThreads]= {0,0,0,0,0}; //1表示正在抓号，0表示没抓号，或者已经抓完
int number[g_totalThreads] = {0,0,0,0,0};// 表示抓的号数
//参数id为当前的线程号
void Lock(int id)
{
    /*实现方法三，Lamport互斥算法*/
    //互斥操作，表示当前进程正在抽号
    choosing[id] = 1;
    // 抽号的时候选择最大的编号，进行加1，保证序列递增
    for(int j=0; j<g_totalThreads; j++)
    {
        if(number[id]<number[j])
        {
            number[id] = number[j];
        }
    }
    number[id]++;
    // 抽号完毕
    choosing[id] = 0;
    // 开始判断是否进入临界区，以及是否忙等
    int Wait_count = 0;
    for(int j=0;j<g_totalThreads;j++){
        // j 号进程正在抽号,需要忙等
        while(choosing[j]){
            Wait_count++;
        }
        // j号进程优先级比较高，需要忙等
        while(number[j]!=0 && number[id]==number[j] && id>j){
            Wait_count++;
        }

    }
    // 可以进入临界区了
    //std::cout<<"I Have waited "<<Wait_count<<" times ";
}
//参数id为当前的线程号
void unLock(int id)
{

    /*实现方法三，Lamport互斥算法*/
    // 离开临界区
    number[id] = 0;
}

实验结果

实验结果算法效率
image-20200518113143237image-20200518113318017

可以看到算法效率比较高，几乎没有忙等。

Eisenberg-Mcguire 互斥算法

核心代码如下：

const int g_totalThreads = 5;
/*实现方法三，Eisenberg-Mcguire互斥算法*/
/*在下面定义算法相关的全局变量*/
#define idle 0      // 进程不想进入临界区
#define want_in 1   // 进程想进如临界区
#define in_cs 2     // 进程想进入临界区，或者已经进入临界区
int turn = 0;       // 当前的进程编号
int flag[g_totalThreads] = {0,0,0,0,0}; // 进程的意向
//参数id为当前的线程号
void Lock(int id)
{
    /*实现方法三，Eisenberg-Mcguire互斥算法*/
    // 当前进程向进入临界区
    int j = 0;
    int Wait_count = 0;
    do
    {
        flag[id] = want_in;
        j = turn;
        // 扫描当前进程前面的左右进程，判断自己是否可以进入临界区
        while(j!=id)
        {
            // 如果之前的进程出现了，want_in 或者 in_cs 需要重新开始扫描,即忙等一次
            if(flag[j]!=idle)
            {
                Wait_count++;
                j = turn;
            }
            else
            {
                // 否则继续向前扫描
                j = (j+1)%g_totalThreads;
            }
        }
        //首先将自己的意向置为in_cs，然后扫描前面的进程
        flag[id] = in_cs;
        j = 0;
        // 如果其他所有进程，都不是in_cs才能进入临界区
        while(j<g_totalThreads && (j==id || flag[j]!=in_cs))
        {
            j++;
        }
    }
    while(j<g_totalThreads);
    // 这个时候可以进入临界区了
    turn = id;
    //std::cout<<"I Have waited "<<Wait_count<<" times ";
}
//参数id为当前的线程号
void unLock(int id)
{

    /*实现方法三，Eisenberg-Mcguire互斥算法*/
    // 离开临界区
    // 从turn的下一个开始找第一个想进入临界区的进程
    int j = (turn+1)%g_totalThreads;
    while(flag[j]==idle){
        j = (j+1)%g_totalThreads;
    }
    // 替换当前的turn
    turn = j;
    flag[id] = idle;
}

实验结果：

实验结果算法效率
image-20200518121351800image-20200518121705528

通过比较可以发现相对于Lamport算法，Eisenberg-Mcguire算法不仅实现复杂，而且效率相对低下。

四种算法的完整代码如下，删掉对应注释即可

// UserLock.cpp : 定义控制台应用程序的入口点。
//

#include <iostream>
#include <windows.h>
//#include <tchar.h>
//#include <StrSafe.h>
#include <process.h>       // For _beginthreadex
#include <math.h>
#include <time.h>

// This macro function calls the C runtime's _beginthreadex function.
// The C runtime library doesn't want to have any reliance on Windows' data
// types such as HANDLE. This means that a Windows programmer needs to cast
// values when using _beginthreadex. Since this is terribly inconvenient,
// I created this macro to perform the casting.
typedef unsigned(__stdcall *PTHREAD_START) (void *);

#define chBEGINTHREADEX(psa, cbStackSize, pfnStartAddr, \
   pvParam, dwCreateFlags, pdwThreadId)                 \
      ((HANDLE)_beginthreadex(                          \
         (void *)        (psa),                         \
         (unsigned)      (cbStackSize),                 \
         (PTHREAD_START) (pfnStartAddr),                \
         (void *)        (pvParam),                     \
         (unsigned)      (dwCreateFlags),               \
         (unsigned *)    (pdwThreadId)))


//调节线程睡眠的时间区间
const int MIN = 200, MAX = 1000;

volatile LONG g_fShutdown = FALSE;  // Signals for threads to die

// Handles to all client threads
HANDLE g_hThreads[MAXIMUM_WAIT_OBJECTS];

//注意，如果要实现Dekker或Peterson互斥算法，需要将线程数量改为2
//注意，如果要实现Lamport或Eisenberg-Mcguire互斥算法，需要将线程数量最少改为5
const int g_totalThreads = 5;
//const int g_totalThreads = 2;



/*实现方法一，利用Windows内核对象*/
//全局锁，以mutex形式实现
HANDLE g_hLock;

/*实现方法二，Dekker或Peterson互斥算法*/
/*在下面定义算法相关的全局变量*/

//int flag[2]= {0,0}; //表示线程是否想进入临界区
//int turn = 0; // 表示轮到的进程编号


/*实现方法三，Lamport或Eisenberg-Mcguire互斥算法*/
/*在下面定义算法相关的全局变量*/
//int choosing[g_totalThreads]= {0,0,0,0,0}; //1表示正在抓号，0表示没抓号，或者已经抓完
//int number[g_totalThreads] = {0,0,0,0,0};// 表示抓的号数
#define idle 0      // 进程不想进入临界区
#define want_in 1   // 进程想进如临界区
#define in_cs 2     // 进程想进入临界区，或者已经进入临界区
int turn = 0;       // 当前的进程编号
int flag[g_totalThreads] = {0,0,0,0,0}; // 进程的意向
//参数id为当前的线程号
void Lock(int id)
{
    /*****实现某一种算法时，需要将其他算法注释掉*****/


    /*实现方法一，利用Windows内核对象*/
    //WaitForSingleObject(g_hLock, INFINITE);

    /*实现方法二，Dekker或Peterson互斥算法*/
    // 首先将flag置为1,想要进入临界区
    /*
    flag[id] = 1;
    //判断对方是否也想进入临界区
    int Wait_count = 0;
    while(flag[(id^1)])
    {
        // 轮到了对方，那么自己就因该忙等，为了不干扰对方的进度，将自己的flag先暂时置为0，最后再恢复
        if(turn == (id^1))
        {
            flag[id] = 0;
        }
        // 忙等。等到自己的轮次，为止。随便记录一下等待次数

        while(turn == (id^1))
        {
            Wait_count++;
        };
        // 终于轮到了我了。。再把之前的flag变回来
        flag[id] = 1;
    }
    // 顺便输出一下我等了多久qaq
    std::cout<<"I Have waited "<<Wait_count<<" times  ";
    // 进入临界区。。
    */
    /*
    // 自己要临界区的时候，同时把turn转给对方。防止两个人同时想进临界区。出现问题
    flag[id] = 1;
    turn = id^1;
    int Wait_count = 0;
    // 忙等对方,统计等待次数
    while(flag[id^1]&&turn == id^1)
    {
        Wait_count++;
    }
    //进入临界区，输出等待次数
    std::cout<<"I Have waited "<<Wait_count<<" times  ";
    */
    /*实现方法三，Lamport或Eisenberg-Mcguire互斥算法*/
    /*
    //互斥操作，表示当前进程正在抽号
    choosing[id] = 1;
    // 抽号的时候选择最大的编号，进行加1，保证序列递增
    for(int j=0; j<g_totalThreads; j++)
    {
        if(number[id]<number[j])
        {
            number[id] = number[j];
        }
    }
    number[id]++;
    // 抽号完毕
    choosing[id] = 0;
    // 开始判断是否进入临界区，以及是否忙等
    int Wait_count = 0;
    for(int j=0;j<g_totalThreads;j++){
        // j 号进程正在抽号,需要忙等
        while(choosing[j]){
            Wait_count++;
        }
        // j号进程优先级比较高，需要忙等
        while(number[j]!=0 && number[id]==number[j] && id>j){
            Wait_count++;
        }

    }
    // 可以进入临界区了
    //std::cout<<"I Have waited "<<Wait_count<<" times ";
    */
    // 当前进程向进入临界区
    int j = 0;
    int Wait_count = 0;
    do
    {
        flag[id] = want_in;
        j = turn;
        // 扫描当前进程前面的左右进程，判断自己是否可以进入临界区
        while(j!=id)
        {
            // 如果之前的进程出现了，want_in 或者 in_cs 需要重新开始扫描,即忙等一次
            if(flag[j]!=idle)
            {
                Wait_count++;
                j = turn;
            }
            else
            {
                // 否则继续向前扫描
                j = (j+1)%g_totalThreads;
            }
        }
        //首先将自己的意向置为in_cs，然后扫描前面的进程
        flag[id] = in_cs;
        j = 0;
        // 如果其他所有进程，都不是in_cs才能进入临界区
        while(j<g_totalThreads && (j==id || flag[j]!=in_cs))
        {
            j++;
        }
    }
    while(j<g_totalThreads);
    // 这个时候可以进入临界区了
    turn = id;
    //std::cout<<"I Have waited "<<Wait_count<<" times ";
}


//参数id为当前的线程号
void unLock(int id)
{
    /*****实现某一种算法时，需要将其他算法注释掉*****/

    /*实现方法一，利用Windows内核对象*/
    //ReleaseMutex(g_hLock);

    /*实现方法二，Dekker或Peterson互斥算法*/
    /*
    //从临界区出来了。。就应该老实点。把位置让出来
    turn = (id^1);
    // 然后。将flag置为0
    flag[id] = 0;
    */
    // 出了临界区,将自己的flag置为0
    //flag[id] = 0;
    /*实现方法三，Lamport或Eisenberg-Mcguire互斥算法*/
    // 离开临界区
    //number[id] = 0;
    // 从turn的下一个开始找第一个想进入临界区的进程
    int j = (turn+1)%g_totalThreads;
    while(flag[j]==idle){
        j = (j+1)%g_totalThreads;
    }
    // 替换当前的turn
    turn = j;
    flag[id] = idle;
}

DWORD WINAPI ClientThread(PVOID pvParam)
{

    int nThreadNum = PtrToUlong(pvParam);
    int nRequestNum = 0;

    //rand init for different threads
    LARGE_INTEGER nFrequency;
    if (::QueryPerformanceFrequency(&nFrequency))
    {
        LARGE_INTEGER nStartCounter;
        ::QueryPerformanceCounter(&nStartCounter);
        ::srand((unsigned)nStartCounter.LowPart);
    }

    while (!g_fShutdown)
    {

        Lock(nThreadNum);
        // Keep track of the current processed element
        nRequestNum++;

        // Only output first 30 times.
        if(nRequestNum < 30)
            std::cout << "Thread " << nThreadNum << " get lock!" << std::endl;

        unLock(nThreadNum);

        // [MIN, MAX]
        int t = rand() % (MAX - MIN + 1) + MIN;

        /*可以把下面一行注释掉，观察不同的实验结果*/
        Sleep(t);   // Wait for scheduling another time
    }

    return(0);
}


int main()
{

    g_hLock = CreateMutex(NULL, FALSE, NULL);
    DWORD dwThreadID;

    // Create threads
    int  nNumThreads = 0;
    for (int x = 0; x < g_totalThreads; x++)
        g_hThreads[nNumThreads++] =
            chBEGINTHREADEX(NULL, 0, ClientThread, (PVOID)(INT_PTR)x,
                            0, &dwThreadID);

    char a;
    // Input any char to quit!
    std::cin >> a;

    g_fShutdown = TRUE;

    // Wait for all the threads to terminate & then cleanup
    WaitForMultipleObjects(nNumThreads, g_hThreads, TRUE, INFINITE);
    while (nNumThreads--)
        CloseHandle(g_hThreads[nNumThreads]);
    return 0;
}

思考题

我认为单CPU的互斥算法不能用在多CPU上，因为在多CPU中指令可能并行执行，导致指令的顺序可能按照非预期的顺序执行，进而导致多个进程同时进入一个临界区。

总结

本次实验回顾了学习过的几种经典互斥算法，提高了对算法的认识，从理论层面提升到了基本实践的程度。为进一步的学习打下了良好的基础。

上一篇： 浅析MT19937伪随机数生成算法