【操作系统】进程调度与同步

小灰灰 2023-10-17 17:32 43阅读 0赞

##### 一、实验目的 #####

>  了解操作系统中常见的进程调度算法  
>  了解在linux中利用多线程模拟实现FCFS,SJF,RR的调度过程。  
>  了解进程同步的特点，掌握利用信号量实现进程间同步的的方法。  
>  了解哲学家问题中进程之间的相互制约关系，能够合理的设置信号量。  
>  了解Linux系统下创建多线程的原理及使用方法，模拟哲学家问题的实现。

##### 二、实验项目内容 #####

> 进程调度：  
> 本实验利用线程模拟进程，实现进程间的调度算法。主要有以下内容：  
>  创建主线程，主线程的工作包括：创建子线程，保存子线程的虚拟PCB ；并负责子线程的调度。调度的基本时间单位为1s。  
>  主线程创建20个子线程，分别实现FCFS调度、SJF调度、RR调度、优先级调度和多级队列调度，并且计算每个调度的平均等待时间。（其中优先级调度和多级队列调度为选做）。  
>  对于每个子线程，在其运行期间，输出其占用的时间标号（例如，第3个线程占用了第10秒的CPU时间，输出为：“Thread3：10”）。
> 
> 进程同步：  
>  1 根据哲学家进程间的相互制约关系，设置合理的信号量及信号量初值。  
>  2 创建5个线程，分别模拟5个哲学家进程。  
>  3 在哲学家线程之间通过对信号量的P,V操作，实现线程之间的同步关系。

##### 三.试验过程及算法 #####

（一） 进程调度

![这里写图片描述][SouthEast]

> 实验步骤计算法：  
> 1. 创建主线程，主线程的工作包括：创建子线程，保存子线程的虚拟PCB ；并负责子线程的调度。调度的基本时间单位为1s。  
> 2. 主线程创建20个子线程，分别实现FCFS调度、SJF调度、RR调度、优先级调度和多级队列调度，并且计算每个调度的平均等待时间。  
> 3. 对于每个子线程，在其运行期间，输出其占用的时间标号

（二） 进程同步

![这里写图片描述][SouthEast 1]

> 实验步骤计算法：  
> 1 根据哲学家进程间的相互制约关系，设置合理的信号量及信号量初值。  
> 2 创建5个线程，分别模拟5个哲学家进程。  
> 3 在哲学家线程之间通过对信号量的P,V操作，实现线程之间的同步关系。

##### 三、实验程序代码： #####

（一）进程调度程序源码

#include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #include<unistd.h>
    #include<pthread.h>
    #include<sys/types.h>
    
    #define THREADNUM 20 //子线程数量
    
    pthread_mutex_t DeviceMutex ;
    //线程的虚拟PCB信息 
    struct VirtualPCB
    {
    int tid;
    int handlePriority;
    int arrivetime;
    int waittime;
    int runtime;
    int visited;
    int tempruntime;
    }PCBs[THREADNUM]; 
    
    //初始化PCB
    void initPCB()
    {
    int n;
    srand(time(NULL));
    for(n =0;n<THREADNUM;n++)
    {
    //用线程创建序号作为虚拟进程id
    PCBs[n].tid = n + 1;
    //用随机数随机产生虚拟PCB的值
    PCBs[n].handlePriority = 1 + rand()%19;
    PCBs[n].tempruntime=PCBs[n].runtime = 1 + rand()%19;
    //默认进程按创建顺序依次在0时刻到达
    PCBs[n].arrivetime = 0;
    PCBs[n].waittime = 0;
    PCBs[n].visited =0;
    }
    }
    
    //子线程功能实现
    void *t_print(void *arg)
    {
    int n = *(int *)arg;//get argument
    while(1)
    {
    pthread_mutex_lock(&DeviceMutex);
    printf("thread%-2d: ",n);
    printf("tid:%2d Priority:%2d runtime:%2d \n",PCBs[n-1].tid,PCBs[n-1].handlePriority,PCBs[n-1].runtime);
    pthread_mutex_unlock(&DeviceMutex);
    sleep(1);
    break;
    }
    pthread_exit(0);
    }
    
    //计算FCFS（First come first service）
    void handleFCFS()
    {
    printf("\n-----------FCFS-----------\n");
    int i,j;
    int start = 0;
    float waittime = 0;
    float avwait = 0;
    for(i=0;i<THREADNUM/2;i++)
    {
    for(j=0;j<THREADNUM;j++){
    if(PCBs[j].arrivetime==i && PCBs[j].visited==0){
    printf("Thread: %2d Start: %3d Runtime: %2d\n",PCBs[j].tid,start,PCBs[j].runtime);
    waittime = waittime + (float)start;
    start = start + PCBs[j].runtime;
    PCBs[j].visited=1;
    }
    }
    }
    avwait = waittime / (float)THREADNUM;
    printf("Total waitting time : %f\n",waittime);
    printf("Average waitting time : %f\n",avwait);
    }
    
    //计算SJF（Shortest job first）
    void handleSJF()
    {
    for(int k=0 ;k<THREADNUM;k++)
    {
    PCBs[k].visited=0;
    }
    printf("\n-------------SJF-------------\n");
    int i,j;
    int start = 0;
    float waittime = 0;
    float avwait = 0;
    for(i=1;i<THREADNUM;i++)
    {
    for(j=0;j<THREADNUM;j++){
    if(PCBs[j].runtime==i && PCBs[j].visited==0){
    printf("Thread: %2d Start: %3d Runtime: %2d\n",PCBs[j].tid,start,PCBs[j].runtime);
    waittime = waittime + (float)start;
    start = start + PCBs[j].runtime;
    PCBs[j].visited=1;
    }
    }
    }
    avwait = waittime / (float)THREADNUM;
    printf("Total waitting time : %f\n",waittime);
    printf("Average waitting time : %f\n",avwait);
    }
    
    //计算Priority
    void handlePriority()
    {
    for(int k=0 ;k<THREADNUM;k++)
    {
    PCBs[k].visited=0;
    }
    printf("\n-----------Priority-------------\n");
    int i,j;
    int start = 0;
    float waittime = 0;
    float avwait = 0;
    for(i=1;i<THREADNUM;i++)
    {
    for(j=0;j<THREADNUM;j++){
    if(PCBs[j].handlePriority==i && PCBs[j].visited==0){
    printf("Thread: %2d Start: %3d Runtime: %2d\n",PCBs[j].tid,start,PCBs[j].runtime);
    waittime = waittime + (float)start;
    start = start + PCBs[j].runtime;
    PCBs[j].visited=1;
    }
    }
    }
    avwait = waittime / (float)THREADNUM;
    printf("Total waitting time : %f\n",waittime);
    printf("Average waitting time : %f\n",avwait);
    }
    
    //计算RR（Round R）
    void handleRR(int r)
    {
    printf("\n--------------RR-------------\n");
    int start = 0;
    float waittime = 0;
    float avwait = 0;
    for(int i=0;i<THREADNUM;i++)
    {
    int totaltime = totaltime + PCBs[i].runtime;
    PCBs[i].visited=0;
    }
    for(int j=0;j<20*THREADNUM;j=j+r)
    {
    int k = (j%(20*r))/r;
    if(PCBs[k].tempruntime > 0){
    int tepruntime = r;
    if(PCBs[k].tempruntime-r<=0){
    tepruntime = PCBs[k].tempruntime;
    PCBs[k].waittime=start + tepruntime - PCBs[k].runtime;
    }
    printf("Thread: %2d Start: %3d Runtime:%2d \n",PCBs[k].tid, start,tepruntime);
    start = start + tepruntime;
    PCBs[k].tempruntime=r;
    }
    }
    for(int m=0;m<THREADNUM;m++)
    {
    waittime += PCBs[m].waittime;
    }
    avwait = waittime / (float)THREADNUM;
    printf("Total waitting time : %f\n",waittime);
    printf("Average waitting time : %f\n",avwait);
    }
    
    //Main thread execute function to create 20 children threads
    void* Children(void* vargp)
    {
    int ret[THREADNUM];
    initPCB();
    pthread_t tid[THREADNUM];
    pthread_mutex_init(&DeviceMutex,NULL);
    int i,j;
    
    for(i=0;i<THREADNUM;i++)
    {
    int k =i+1;
    
    ret[i] = pthread_create(&tid[i],NULL,&t_print, &k);
    if(ret[i] == 0) {
    sleep(1);
    }
    else{ 
    printf("thread_%2d failed!\n",i+1);
    
    } 
    }
    for(j=0;j<THREADNUM;j++)
    pthread_join (tid[i], NULL);
    pthread_mutex_destroy(&DeviceMutex);
    pthread_exit(0);
    }
    
    int main()
    {
    int ret1;
    //创建主线程
    pthread_t tid1;
    ret1 = pthread_create(&tid1,NULL,&Children,NULL);
    if(ret1 == 0) 
    {
    printf("creating child threads...\n...\n");
    sleep(20);
    }
    else{ 
    printf("Create Main Thread failed!\n");
    
    } 
    
    handleFCFS();
    handleSJF();
    handlePriority();
    printf("Please enter RR time:");
    int rr;
    //获取RR时间
    scanf("%d",&rr);
    handleRR(rr);
    return 0;
    }

（二）进程同步程序源码

#include <stdio.h> 
    #include <unistd.h>
    #include <pthread.h> 
    #define N 5 //哲学家数量
    #define LEFT (i+N-1)%N //第i位哲学家的左边 
    #define RIGHT (i+1)%N //第i位哲学家的右边
    
    //哲学家状态 
    int state[N];
    #define STATE_THINKING 11 //思考
    #define STATE_EATING 12 //吃饭
    #define STATE_HUNGRY 13 //饥饿
    //信号量 
    pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER, s[N]; 
    
    //检查哲学家状态 
    void checkState(int i) 
    {
    //当哲学家饥饿，且左右两边的哲学家均不在吃饭状态时 
    if (state[i] == STATE_HUNGRY
    && state[LEFT] != STATE_EATING&& state[RIGHT] != STATE_EATING) 
    { 
    //哲学家开始吃饭
    state[i] = STATE_EATING; 
    pthread_mutex_unlock(&s[i]); 
    } 
    } 
    void takeForks(int i) 
    { 
    pthread_mutex_lock(&mutex); 
    //当哲学家饥饿
    state[i] = STATE_HUNGRY; 
    checkState(i); 
    pthread_mutex_unlock(&mutex); 
    pthread_mutex_lock(&s[i]); 
    } 
    void putForks(int i)
    { 
    pthread_mutex_lock(&mutex); 
    //当哲学家思考
    state[i] = STATE_THINKING; 
    checkState(LEFT); 
    checkState(RIGHT); 
    pthread_mutex_unlock(&mutex); 
    } 
    //哲学家思考 
    void think(int i) 
    { 
    printf("philosopher %d is thinking...\n", i); 
    //等待一段时间 
    sleep(3); 
    } 
    //哲学家吃饭 
    void eat(int i) 
    { 
    printf("philosopher %d is eating...\n", i); 
    //等待一段时间
    sleep(2); 
    } 
    //哲学家线程的实现 
    void* creatPhilosopher(void* vargp) 
    { 
    int i = *(int*)vargp; 
    while (1) 
    { 
    think(i); 
    takeForks(i); 
    eat(i); 
    putForks(i); 
    } 
    return NULL; 
    } 
    int main() 
    { 
    int i; 
    pthread_t tidp[N]; 
    //创建5个子线程模拟哲学家行为
    for (i = 0; i < N; i++) 
    pthread_create(&tidp[i], NULL, creatPhilosopher, (void*)(&i)); 
    for (i = 0; i < N; i++)
    //等待子线程结束 
    pthread_join(tidp[i], NULL); 
    return 0; 
    }

##### 四、实验结果： #####

（一） 进程调度

> a) 结果  
> ![这里写图片描述][SouthEast 2]  
> *上图初始化20个子线程，并显示输出其属性*  
> ![这里写图片描述][SouthEast 3]  
> *上图计算FCFS调度的时间，并显示输出时间刻度*  
> ![这里写图片描述][SouthEast 4]  
> *上图计算SJF调度的时间，并显示输出时间刻度*  
> ![这里写图片描述][SouthEast 5]  
> *上图计算Priority调度的时间，并显示输出时间刻度*  
> ![这里写图片描述][SouthEast 6]  
> *上图计算RR调度的时间,输入RR=5，并显示输出时间刻度*
> 
> b) 分析  
> 实验结果如上图所示，分别显示输出20个子线程信息，并分别计算了FCFS、SJF、Priority、RR调度机制的运行时间和等待时间，4种调度均采用同一个样本，便于统计和比较。

（二） 进程同步

> a) 结果  
> ![这里写图片描述][SouthEast 7]
> 
> b) 分析  
> 程序创建5个子线程模拟5个哲学家的行为，分别标号0~4，程序中哲学家思考的时间比吃饭的时间要长，由于实验结果较长，截取其中一部分分析，哲学家们并未出现相邻同时吃饭的问题和死锁，但程序初始会出现哲学家同时思考的现象，程序结果符合实验要求。

[SouthEast]: https://img-blog.csdn.net/20171224141518977?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYWRtaW5wZA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: https://img-blog.csdn.net/20171224141539255?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYWRtaW5wZA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: https://img-blog.csdn.net/20171224142542320?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYWRtaW5wZA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 3]: https://img-blog.csdn.net/20171224142556351?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYWRtaW5wZA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 4]: https://img-blog.csdn.net/20171224142622025?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYWRtaW5wZA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 5]: https://img-blog.csdn.net/20171224142640993?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYWRtaW5wZA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 6]: https://img-blog.csdn.net/20171224142429135?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYWRtaW5wZA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 7]: https://img-blog.csdn.net/20171224142159656?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYWRtaW5wZA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast