作業系統實驗2－互斥與同步

實驗分兩部分，第一部分，實作互斥

思路很簡單，利用信号量，将其值初始化為1，semaphore resource = {1,NULL};

擷取資源時做P（）操作，釋放資源使用權時做V（）操作。

是以

void p1( )
{
    long i, j, k;

    p(&semlock); //擷取資源使用權，如果不能擷取，會被放到信号量隊列中等待資源可用被喚醒
    //中間過程相當于是在使用這個資源（模拟）
    for(i=0; i<40; i++)
    {
        putchar('a');

        for(j=0; j<1000; j++)
            for(k=0; k<20000; k++);
    }
    v(&semlock); //釋放資源，信号量值加1，隊列中第一個線程會被喚醒（如果隊列不為空）
}

void p2( )
{
    long i, j, k;
    p(&semlock);  //同p1()
    for(i=0; i<20; i++)
    {
        putchar('b');

        for(j=0; j<1000; j++)
            for(k=0; k<20000; k++);
    }
    v(&semlock);
}

另外，我們要更改Find()排程程式，找到沒有被阻塞的線程來排程

int Find()
{
    int i,j;

    for(i = 1; i < NTCB; i++)
    {
        if(tcb[i].state != FINISHED && tcb[i].state != BLOCKED) return i;
    }

    return 0;
}

到這裡，互斥鎖就完成了。上最終代碼：

#include <stdlib.h>
#include <dos.h>
#include <stdio.h>

#define GET_INDOS 0x34        /* 34H 系統功能調用    */
#define GET_CRIT_ERR 0x5d06    /* 5D06H号系統功能調用 */

#define BLANK -1
#define FINISHED 0       /*     終止    */
#define RUNNING 1        /*   執行  */
#define READY 2          /*   就緒  */
#define BLOCKED 3        /*   阻塞  */
#define NTCB 3       /* 系統線程的最大數 */

#define TL 10           /* 時間片大小  */
#define NBUF 10        /* 消息緩沖區數目 */
#define NTEXT 50             /* 文本輸出大小  */

char far* intdos_ptr=0;
char far* crit_err_ptr=0;
int timecount=0;
int current=-1;

typedef unsigned int UINT16;

typedef struct/* 信号量 */
{
    int value;
    struct TCB* wq;
} semaphore;

int critical = 0; //

semaphore semlock = {1,NULL};

struct TCB            /* 線程控制塊  */
{
    unsigned char* stack;          /* 堆棧的起始位址  */
    unsigned ss;
    unsigned sp;            /* 堆棧段址和堆棧指針 */
    char state;             /* 程序狀态   */
    char name[10];          /* 線程的外部辨別符  */
    int value;             /*優先級*/
    struct TCB* next;       /* 指向控制快指針  */
    semaphore mutex;        /* 互斥信号量   */
} tcb[NTCB];

struct int_regs           /* 堆棧現場保護和恢複結構體 */
{
    unsigned BP,DI,SI,DS,ES,DX,CX,BX,AX,IP,CS,Flags,off,seg;
};

typedef int(far* codeptr)(void);

void interrupt(*old_int8)(void);


int DosBusy(void);
void InitIndos(void);
void InitTcb();
void interrupt new_int8(void);
void interrupt swtch();

void p(semaphore *sem);
void v(semaphore *sem);

int Create(char* name,codeptr code,int stacklen,int prio);  /* 建立線程 */
void Destroy(int i);

void p1( )
{
    long i, j, k;

    p(&semlock);
    for(i=0; i<40; i++)
    {
        putchar('a');

        for(j=0; j<1000; j++)
            for(k=0; k<20000; k++);
    }
    v(&semlock);
}

void p2( )
{
    long i, j, k;
    p(&semlock);
    for(i=0; i<20; i++)
    {
        putchar('b');

        for(j=0; j<1000; j++)
            for(k=0; k<20000; k++);
    }
    v(&semlock);
}


void InitInDos()      /* 取得INDOS标志和嚴重錯誤标志位址 */
{
    union REGS regs;
    struct SREGS segregs;

    regs.h.ah=GET_INDOS;      /* 使用34H号系統功能調用 */
    intdosx(&regs,&regs,&segregs);

    intdos_ptr=MK_FP(segregs.es,regs.x.bx);
    if(_osmajor<3)
        crit_err_ptr=intdos_ptr+1;      /* 嚴重錯誤在INDOS後一位元組處 */
    else if(_osmajor==3&&_osminor==0)
        crit_err_ptr=intdos_ptr-1;      /* 嚴重錯誤在INDOS前一位元組處 */
    else
    {
        regs.x.ax=GET_CRIT_ERR;
        intdosx(&regs,&regs,&segregs);
        crit_err_ptr=MK_FP(segregs.ds,regs.x.si);
    }
}

int DosBusy(void)            /* 判斷DOS是否忙 */
{
    if(intdos_ptr&&crit_err_ptr)
        return(*intdos_ptr||*crit_err_ptr);  /* DOS忙,傳回嚴重錯誤标志 */
    else
        return(-1);         /* DOS不忙 */
}

void InitTcb()           /* 初始化線程 */
{
    int i;

    for(i=0; i<NTCB; i++)
    {
        tcb[i].state=BLANK;       /* 初始狀态标志   */

        tcb[i].mutex.value=1;
        tcb[i].mutex.wq=NULL;
    }
}

void Destroy(int i)
{

    if(tcb[i].state==RUNNING)
    {
        disable();
        tcb[i].state=FINISHED;
        strcpy(tcb[i].name,NULL);
        free(tcb[i].stack);
        tcb[i].ss=0;
        tcb[i].sp=0;
        enable();
    }

// return;
}

void over()
{
    Destroy(current);
    swtch();
}


int Create(char *name,codeptr code,int stacklen,int value)
{
    int i;
    char *p;
    struct int_regs *pt;
    unsigned int *pp;

    for(i=1; i<NTCB; i++)
    {
        if(tcb[i].state==BLANK||tcb[i].state==FINISHED)
            break;
    }
    if(i==NTCB)
        return-1;

    tcb[i].value=value;
    strcpy(tcb[i].name,name);
    tcb[i].stack=(p=(unsigned char*)malloc(stacklen));
    memset(tcb[i].stack, 0xff, stacklen);
    p=p+stacklen;

    pt=(struct int_regs*)p;
    pt--;
    pt->Flags=0x200;
    pt->CS=FP_SEG(code);
    pt->IP=FP_OFF(code);

    pt->off=FP_OFF(over);
    pt->seg=FP_SEG(over);
    pt->DS=_DS;
    pt->ES=_ES;
    tcb[i].sp=FP_OFF(pt);
    tcb[i].ss=FP_SEG(pt);


    tcb[i].state=READY;

    return i;
}


void tcb_state()        /* 線程狀态資訊 */
{
    int i;

    for(i=0; i<NTCB; i++)
        if(tcb[i].state!=BLANK)
        {
            switch(tcb[i].state)
            {
            case FINISHED:
                printf("\ntcb[%d] is FINISHED\n",i);
                break;

            case RUNNING:
                printf("tcb[%d] is RUNNING\n",i);
                break;
            case READY:
                printf("tcb[%d] is READY\n",i);
                break;
            case BLOCKED:
                printf("tcb[%d] is BLOCKED\n",i);

                break;
            }
        }
}

int all_finished()
{
    int i;

    for(i=1; i<NTCB; i++)
        if(tcb[i].state==RUNNING||tcb[i].state==BLOCKED||tcb[i].state==READY)
            return 0;

    return 1;
}

int Find()
{
    int i,j;

    for(i = 1; i < NTCB; i++)
    {
        if(tcb[i].state != FINISHED && tcb[i].state != BLOCKED) return i;
    }

    return 0;
}

void interrupt new_int8(void)       /* CPU 排程*/
{
    int i;

    (*old_int8)();      /* 指向原來時鐘中斷處理過程入口的中斷處理函數指針 */
    timecount++;

    if(timecount==TL)        /* 時間片是否到? */
    {
        if(!DosBusy())     /* DOS是否忙? */
        {
            disable();

            tcb[current].ss=_SS;     /* 儲存現場 */
            tcb[current].sp=_SP;

            if(tcb[current].state==RUNNING)
                tcb[current].state=READY;

            i=Find();
            if(i<0)
                return;

            _SS=tcb[i].ss;
            _SP=tcb[i].sp;
            tcb[i].state=RUNNING;
            current=i;
            timecount=0;      /* 重新計時 */

            enable();
        }
        else
            return;
    }
    else
        return;
}

void interrupt swtch()            /* 其他原因CPU排程  */
{
    int i;

    if(tcb[current].state!=FINISHED
            &¤t!=0&&tcb[current].state!=BLOCKED) /* 目前線程還沒結束 */
        return;

    i=Find();
    if(i<0)
        return;

    disable();
    tcb[current].ss=_SS;
    tcb[current].sp=_SP;

    if(tcb[current].state==RUNNING)
        tcb[current].state=READY;      /* 放入就緒隊列中 */

    _SS=tcb[i].ss;
    _SP=tcb[i].sp;        /* 儲存現場 */

    tcb[i].state=RUNNING;
    current=i;
    enable();
}

void block(struct TCB **p)         /* 阻塞原語 */
{
    struct TCB *pp;

    tcb[current].state=BLOCKED;

    if((*p)==NULL)
        *p=&tcb[current];    /* 阻塞隊列空,直接放入 */
    else
    {
        pp=*p;
        while(pp->next)
            pp=pp->next;         /* 找到阻塞隊列最後一個節點 */

        pp->next=&tcb[current];      /* 放入阻塞隊列 */
    }
    tcb[current].next=NULL;
    swtch();       /* 重新進行CPU排程 */
}

void wakeup_first(struct TCB **p)    /* 喚醒隊首線程 */
{
    struct TCB *pl;

    if((*p)==NULL)
        return;

    pl=(*p);
    (*p)=(*p)->next;     /* 得到阻塞隊列隊首線程 */
    pl->state=READY;        /* 修為就緒狀态 */
    pl->next=NULL;
}

void p(semaphore *sem)
{
    struct TCB **qp;

    disable();
    sem->value=sem->value-1;

    if(sem->value<0)
    {
        qp=&(sem->wq);
        block(qp);
    }
    enable();
}

void v(semaphore*sem)
{
    struct TCB **qp;

    disable();
    qp=&(sem->wq);
    sem->value=sem->value+1;

    if(sem->value>=0)
        wakeup_first(qp);

    enable();
}

void main()
{
    long i, j, k;

    InitInDos();
    InitTcb();


    old_int8=getvect(8);

    strcpy(tcb[0].name,"main");
    tcb[0].state=RUNNING;
    tcb[0].value=0;
    current=0;

    Create("p1",(codeptr)p1,1024,5);
    Create("p2",(codeptr)p2,1024,5);

    disable();
    setvect(8, new_int8);
    enable();

    while(!all_finished());
    {
    }

    tcb[0].name[0]='\0';
    tcb[0].state=FINISHED;
    setvect(8,old_int8);

    tcb_state();

    printf("\n Muli_task system teminated \n");
}

第二部分，同步問題，我們用最經典的生産者消費者來說明。

首先，定義臨界資源通路信号裡：semaphore resource = {0,NULL};，注意，值初始化為0；

接下來，生産者與消費者代碼實作：

void p1( )        // 生産者
{
    long i, j, k;

    for(i=0; i<40; i++)
    {
        putchar('a');
        for(j=0; j<1000; j++)
            for(k=0; k<20000; k++);
    } // 前面的過程就是生産者一直在生産的過程，現在生産完成了，v操作通知消費者消費咯
    v(&resource);
}

void p2( )        //消費者
{
    long i, j, k;
    p(&resource); //看看有沒有可用的資源來消費，若沒有，則被放到信号裡resource的隊列中，直至資源可用被喚醒
    // 下面就是消費者消費過程（模拟，别當真）
    for(i=0; i<20; i++)
    {
        putchar('b');
        for(j=0; j<1000; j++)
            for(k=0; k<20000; k++);
    }
}

好，上最終代碼：

#include <stdlib.h>
#include <dos.h>
#include <stdio.h>

#define GET_INDOS 0x34        /* 34H 系統功能調用    */
#define GET_CRIT_ERR 0x5d06    /* 5D06H号系統功能調用 */

#define BLANK -1
#define FINISHED 0       /*     終止    */
#define RUNNING 1        /*   執行  */
#define READY 2          /*   就緒  */
#define BLOCKED 3        /*   阻塞  */
#define NTCB 3       /* 系統線程的最大數 */

#define TL 10           /* 時間片大小  */
#define NBUF 10        /* 消息緩沖區數目 */
#define NTEXT 50             /* 文本輸出大小  */

char far* intdos_ptr=0;
char far* crit_err_ptr=0;
int timecount=0;
int current=-1;

typedef unsigned int UINT16;

typedef struct/* 信号量 */
{
    int value;
    struct TCB* wq;
} semaphore;

semaphore resource = {0,NULL};  //

struct TCB            /* 線程控制塊  */
{
    unsigned char* stack;          /* 堆棧的起始位址  */
    unsigned ss;
    unsigned sp;            /* 堆棧段址和堆棧指針 */
    char state;             /* 程序狀态   */
    char name[10];          /* 線程的外部辨別符  */
    int value;             /*優先級*/
    struct TCB* next;       /* 指向控制快指針  */
    semaphore mutex;        /* 互斥信号量   */
} tcb[NTCB];

struct int_regs           /* 堆棧現場保護和恢複結構體 */
{
    unsigned BP,DI,SI,DS,ES,DX,CX,BX,AX,IP,CS,Flags,off,seg;
};

typedef int(far* codeptr)(void);

void interrupt(*old_int8)(void);


int DosBusy(void);
void InitIndos(void);
void InitTcb();
void interrupt new_int8(void);
void interrupt swtch();

void p(semaphore *sem);
void v(semaphore *sem);

int Create(char* name,codeptr code,int stacklen,int prio);  /* 建立線程 */
void Destroy(int i);


void p1( )        // 生産者
{
    long i, j, k;

    for(i=0; i<40; i++)
    {
        putchar('a');
        for(j=0; j<1000; j++)
            for(k=0; k<20000; k++);
    }
    v(&resource);
}

void p2( )        //消費者
{
    long i, j, k;
    p(&resource);
    for(i=0; i<20; i++)
    {
        putchar('b');
        for(j=0; j<1000; j++)
            for(k=0; k<20000; k++);
    }
}



void InitInDos()      /* 取得INDOS标志和嚴重錯誤标志位址 */
{
    union REGS regs;
    struct SREGS segregs;

    regs.h.ah=GET_INDOS;      /* 使用34H号系統功能調用 */
    intdosx(&regs,&regs,&segregs);

    intdos_ptr=MK_FP(segregs.es,regs.x.bx);
    if(_osmajor<3)
        crit_err_ptr=intdos_ptr+1;      /* 嚴重錯誤在INDOS後一位元組處 */
    else if(_osmajor==3&&_osminor==0)
        crit_err_ptr=intdos_ptr-1;      /* 嚴重錯誤在INDOS前一位元組處 */
    else
    {
        regs.x.ax=GET_CRIT_ERR;
        intdosx(&regs,&regs,&segregs);
        crit_err_ptr=MK_FP(segregs.ds,regs.x.si);
    }
}

int DosBusy(void)            /* 判斷DOS是否忙 */
{
    if(intdos_ptr&&crit_err_ptr)
        return(*intdos_ptr||*crit_err_ptr);  /* DOS忙,傳回嚴重錯誤标志 */
    else
        return(-1);         /* DOS不忙 */
}

void InitTcb()           /* 初始化線程 */
{
    int i;

    for(i=0; i<NTCB; i++)
    {
        tcb[i].state=BLANK;       /* 初始狀态标志   */

        tcb[i].mutex.value=1;
        tcb[i].mutex.wq=NULL;
    }
}

void Destroy(int i)
{

    if(tcb[i].state==RUNNING)
    {
        disable();
        tcb[i].state=FINISHED;
        strcpy(tcb[i].name,NULL);
        free(tcb[i].stack);
        tcb[i].ss=0;
        tcb[i].sp=0;
        enable();
    }

// return;
}

void over()
{
    Destroy(current);
    swtch();
}


int Create(char *name,codeptr code,int stacklen,int value)
{
    int i;
    char *p;
    struct int_regs *pt;
    unsigned int *pp;

    for(i=1; i<NTCB; i++)
    {
        if(tcb[i].state==BLANK||tcb[i].state==FINISHED)
            break;
    }
    if(i==NTCB)
        return-1;

    tcb[i].value=value;
    strcpy(tcb[i].name,name);
    tcb[i].stack=(p=(unsigned char*)malloc(stacklen));
    memset(tcb[i].stack, 0xff, stacklen);
    p=p+stacklen;

    pt=(struct int_regs*)p;
    pt--;
    pt->Flags=0x200;
    pt->CS=FP_SEG(code);
    pt->IP=FP_OFF(code);

    pt->off=FP_OFF(over);
    pt->seg=FP_SEG(over);
    pt->DS=_DS;
    pt->ES=_ES;
    tcb[i].sp=FP_OFF(pt);
    tcb[i].ss=FP_SEG(pt);


    tcb[i].state=READY;

    return i;
}


void tcb_state()        /* 線程狀态資訊 */
{
    int i;

    for(i=0; i<NTCB; i++)
        if(tcb[i].state!=BLANK)
        {
            switch(tcb[i].state)
            {
            case FINISHED:
                printf("\ntcb[%d] is FINISHED\n",i);
                break;

            case RUNNING:
                printf("tcb[%d] is RUNNING\n",i);
                break;
            case READY:
                printf("tcb[%d] is READY\n",i);
                break;
            case BLOCKED:
                printf("tcb[%d] is BLOCKED\n",i);

                break;
            }
        }
}

int all_finished()
{
    int i;

    for(i=1; i<NTCB; i++)
        if(tcb[i].state==RUNNING||tcb[i].state==BLOCKED||tcb[i].state==READY)
            return 0;

    return 1;
}

int Find()
{
    int i,j;


    i=current;

    while(tcb[i=((i+1)%NTCB)].state!=READY ||i==current);


    return i;
}

/*
int Find()
{
   int i,index,max_pri;
   i = index = max_pri = 0;
   for( ; i < NTCB; i++)
   {
       if(tcb[i].state != FINISHED && tcb[i].state != BLOCKED && tcb[i].value > max_pri)
       {
           index = i;
           max_pri = tcb[i].value;
       }
   }
   return index;
}
*/

void interrupt new_int8(void)       /* CPU 排程*/
{
    int i;

    (*old_int8)();      /* 指向原來時鐘中斷處理過程入口的中斷處理函數指針 */
    timecount++;

    if(timecount==TL)        /* 時間片是否到? */
    {
        if(!DosBusy())     /* DOS是否忙? */
        {
            disable();

            tcb[current].ss=_SS;     /* 儲存現場 */
            tcb[current].sp=_SP;

            if(tcb[current].state==RUNNING)
                tcb[current].state=READY;

            i=Find();
            if(i<0)
                return;

            _SS=tcb[i].ss;
            _SP=tcb[i].sp;
            tcb[i].state=RUNNING;
            current=i;
            timecount=0;      /* 重新計時 */

            enable();
        }
        else
            return;
    }
    else
        return;
}

void interrupt swtch()            /* 其他原因CPU排程  */
{
    int i;

    if(tcb[current].state!=FINISHED
            &¤t!=0&&tcb[current].state!=BLOCKED) /* 目前線程還沒結束 */
        return;

    i=Find();
    if(i<0)
        return;

    disable();
    tcb[current].ss=_SS;
    tcb[current].sp=_SP;

    if(tcb[current].state==RUNNING)
        tcb[current].state=READY;      /* 放入就緒隊列中 */

    _SS=tcb[i].ss;
    _SP=tcb[i].sp;        /* 儲存現場 */

    tcb[i].state=RUNNING;
    current=i;
    enable();
}

void block(struct TCB **p)         /* 阻塞原語 */
{
    struct TCB *pp;

    tcb[current].state=BLOCKED;

    if((*p)==NULL)
        *p=&tcb[current];    /* 阻塞隊列空,直接放入 */
    else
    {
        pp=*p;
        while(pp->next)
            pp=pp->next;         /* 找到阻塞隊列最後一個節點 */

        pp->next=&tcb[current];      /* 放入阻塞隊列 */
    }
    tcb[current].next=NULL;
    swtch();       /* 重新進行CPU排程 */
}

void wakeup_first(struct TCB **p)    /* 喚醒隊首線程 */
{
    struct TCB *pl;

    if((*p)==NULL)
        return;

    pl=(*p);
    (*p)=(*p)->next;     /* 得到阻塞隊列隊首線程 */
    pl->state=READY;        /* 修為就緒狀态 */
    pl->next=NULL;
}

void p(semaphore *sem)
{
    struct TCB **qp;

    disable();
    sem->value=sem->value-1;

    if(sem->value<0)
    {
        qp=&(sem->wq);
        block(qp);
    }
    enable();
}

void v(semaphore*sem)
{
    struct TCB **qp;

    disable();
    qp=&(sem->wq);
    sem->value=sem->value+1;

    if(sem->value>=0)
        wakeup_first(qp);

    enable();
}

void main()
{
    long i, j, k;

    InitInDos();
    InitTcb();


    old_int8=getvect(8);

    strcpy(tcb[0].name,"main");
    tcb[0].state=RUNNING;
    tcb[0].value=0;
    current=0;

    Create("p1",(codeptr)p1,1024,5);
    Create("p2",(codeptr)p2,1024,5);

    disable();
    setvect(8, new_int8);
    enable();

    while(!all_finished());
    {
    }

    tcb[0].name[0]='\0';
    tcb[0].state=FINISHED;
    setvect(8,old_int8);

    tcb_state();

    printf("\n Muli_task system teminated \n");
}

好了，打完收工。

作業系統實驗2－互斥與同步

繼續閱讀

WIN10下指令行禁用編輯模式

Linux指令行下載下傳檔案和安裝RAR

使用 Windows 指令行删除結果

Win10系統怎麼開啟Linux Bash指令行？

Linux指令行通配符

windows和linux下使用指令行執行jmeter

sip presence , subscribe 和 notify 中文

終端環境之tmux

【Tomcat】Tomcat參數調優:連接配接數和并發數

[Linux] diff 查找檔案的異同

作業系統（python）多程序學習

ACS基本配置-權限等級管理

傳說FreeBSD等比Linux更穩定，更“健壯”

無人機--飛控科普

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins