操作系统实验系列二: 进程通信与内存管理

进程软中断

管道通信

内存分配与回收/页面置换

1. 进程软中断

1.1 实验内容

使用系统调用 fork()创建两个子进程

用系统调用 signal()让父进程捕捉键盘上发出的中断信号(即按 delete 键)或过了五秒的时钟信号

当父进程接收到这两个软中断的某一个后，父进程用系统调用 kill()向两个子进程分别发出整数值为 16 和 17 软中断信号

子进程获得对应软中断信号，然后分别输出下列信息后终止
Child process 1 is killed by parent !!
Child process 2 is killed by parent !!

父进程调用 wait()函数等待两个子进程终止后，输入以下信息，结束进程执行
Parent process is killed!!

多运行几次编写的程序，简略分析出现不同结果的原因.

1.2 实验与分析

最初认为运行结果会怎么样,实际的结果什么样,有什么特点,试对产生该现象的原因进行分析.

kill 命令在程序中使用了几次,每次的作用是什么,执行后的现象是什么.

使用 kill 命令可以在进程的外部杀死进程.进程怎样能主动退出,这两种退出方式哪种更好一些.

把程序源代码附到实验报告后

1.2.1 预期与实际效果及分析

原本的子进程程序:

else{                                                                                                                            // 等待进程1被杀死的中断号16
    wait_flag = 1;
    signal(16, stop);
    printf("\n Child process 1 is killed by parent !!\n");
    exit(0);
}

以为程序会停在 signal 处,等待父进程发送信号后继续运行
实际上子进程直接结束了,5 秒后父进程结束
查看 signal 的函数定义,发现 signal 仅仅定义了信号的处理方式,而没有阻塞进程

增加阻塞进程的部分

    else{                                                                                                                            // 等待进程1被杀死的中断号16
        signal(16, stop);
        while(wait_flag);                                                                                                 //阻塞子进程1
        printf("\n Child process 1 is killed by parent !!\n");
        exit(0);
    }
}
void stop(){
    printf("process  stop!!!");
    wait_flag=0;
}

原本以为全局变量不会被子进程复制到自己的区域，中间发生了一点错误．

最终截图:
由时钟信号触发父进程继续执行

由键盘中断触发父进程继续执行

1.2.2 kill 命令的分析

kill 命令共执行了两次,分别向子进程 1 发送 16 号软中断信息,向子进程 2 发送 17 号软中断信息.

执行的结果是触发两个子进程提前绑定的处理函数.

1.2.3 中断的退出

进程主动退出可以使用 exit()函数.
也可以由 kill 软中断触发退出流程

进程主动退出的时候可以自行保存相关数据等,所以进程主动退出更好一点.

1.2.4 源代码

//=========================
//  author: bibibi
//  description: 进程软中断实验
//=========================
#include <stdio.h>
#include <signal.h>
#include <unistd.h>
#include <sys/types.h>
int wait_flag;                          //全局阻塞变量
void stop();
void parent_stop();
main()
{
    int pid1, pid2;                                                                                 // 定义两个进程号变量
    signal(SIGINT, parent_stop);                                                        //设置键盘中断
    //signal(SIGTSTP, stop);                                                                 //设置键盘中断
    wait_flag=1;

    while ((pid1 = fork()) == -1);                                                                            // 创建子进程1

    if (pid1 > 0){                                                                                  //父进程路径

        while ((pid2 = fork()) == -1);                                                                                                // 创建子进程2
        if (pid2 > 0){                                                                              //父进程路径

            sleep(5);                                                                               //父进程阻塞

            kill(pid1, 16);                                                                               // 杀死进程1发中断号16
            kill(pid2, 17);                                                                       // 杀死进程2发终端号17
            wait(0);                                                                                 // 等待第1个子进程1结束的信号
            wait(0);                                                                                 // 等待第2个子进程2结束的信号
            printf("\n Parent process is killed !!\n");
            exit(0);                                                                                 // 父进程结束
        }
        else{
            signal(17,stop);                                                                                                                 // 等待进程2被杀死的中断号17
            while(wait_flag);                                                                                                               //阻塞子进程2
            printf("\n Child process 2 is killed by parent !!\n");
            exit(0);
        }
    }
    else{                                                                                                                            // 等待进程1被杀死的中断号16
        signal(16, stop);
        while(wait_flag);                                                                                                 //阻塞子进程1
        printf("\n Child process 1 is killed by parent !!\n");
        exit(0);
    }
}
void stop(){
    printf("child  stop!!!\r\n");
    wait_flag=0;
}
void parent_stop(){
    printf("parent stop!!!\r\n");
}

2. 进程的管道通信

2.1 实验内容

最初认为运行结果会怎么样,实际的结果什么样,有什么特点,试对产生该现象的原因进行分析.

实验中管道通信是怎样实现同步与互斥的?如果不控制同步与互斥会发生什么后果.

把程序源代码附到实验报告后.

2.2 实验与分析

2.2.1 预期与实际效果及分析

本以为有了文件锁,两个子进程可以分别写入然后顺利由父进程读取,但是碰到了问题.
两个子进程确实是分别写入的,但是写入得太快了,父进程会一次全部读出来,导致父进程会阻塞在第二次读操作.
这个问题通过将子进程创建后马上锁定,然后由父进程控制唤醒解决了

第二个问题是如果子进程还未来得及设置信号的处理,父进程已经发送了唤醒信号,子进程会错过去然后整个程序卡死.
这个问题通过创建完所有子进程后父进程休眠 1s 解决

最终的运行效果

2.2.2 同步与互斥分析

两个子进程写入同一个管道需要考虑互斥的问题,而读写双方进程需要考虑同步的问题.

互斥问题是通过 C 标准函数 flock()解决的.
同步问题是通过使子进程自旋等待的方法解决的.(但是这种方法明显很浪费资源,除此之外可以通过系统原语将子进程挂机和唤醒)

2.2.3 源代码

//=========================
//  author: bibibi
//  description: 进程间管道通信
//=========================
#include <unistd.h>
#include <signal.h>
#include <stdio.h>
#include<sys/file.h>
int pid1, pid2;                                                     // 定义两个进程变量
int process_pause;
void restart();
main(){

    int fd[2];
    char OutPipe[100], InPipe[100];                                          // 定义两个字符数组
    pipe(fd);                                                                                       // 创建管道
    process_pause=1;                                                                    //创建信号量

    while ((pid1 = fork()) == -1);                                                  //创建子进程1
    if (pid1 == 0){                                                                                                               //子进程1创建成功

        signal(17,restart);                                                                                                   //使用信号量锁定子进程
        while(process_pause);

        flock(fd[1],LOCK_EX|LOCK_NB);                                                                       // 锁定管道写入端
        sprintf(OutPipe, "\n Child process 1 is sending message!\n");               // 给Outpipe赋值
        write(fd[1],OutPipe,strlen(OutPipe));                                                           // 向管道写入数据
        flock(fd[1],LOCK_UN);                                                                                        // 解除管道的锁定

        exit(0);                                                                                                                     // 结束子进程1
    }
    else{                                                                                             //父进程路径
        while ((pid2 = fork()) == -1);                                             //创建子进程2
        if (pid2 == 0){                                                                                                          //子进程2创建成功

            signal(17,restart);                                                                                              //使用信号量锁定子进程
            while(process_pause);

            flock(fd[1],LOCK_EX|LOCK_NB);                                                                  //锁定管道写入端
            sprintf(OutPipe, "\n Child process 2 is sending message!\n");          //给Outpipe赋值
            write(fd[1], OutPipe, strlen(OutPipe));                                                     // 向管道写入数据
            flock(fd[1],LOCK_UN);                                                                                    // 解除管道的锁定

            exit(0);                                                                                                                // 结束子进程2
        }
        else{                                                                                     //父进程路径
            sleep(1);                                                                         //等待子进程就绪

            kill(pid1,17);                                                                  //唤醒子进程1
            read(fd[0],InPipe,sizeof(InPipe));                           //从管道中读出数据
            printf("%s\n", InPipe);                                               // 显示读出的数据

            kill(pid2,17);                                                                //唤醒子进程2
            read(fd[0],InPipe,sizeof(InPipe));                           //从管道中读出数据
            printf("%s\n", InPipe);                                               // 显示读出的数据

            exit(0);                                                                            // 父进程结束
        }
    }
}

//重启子进程
void restart(){
    process_pause=0;
}

3. 内存分配与回收/页面置换

选做实验我选的时页面置换实验

FIFO 策略

LRU 策略

3.1 FIFO 策略

page 与 pagecontrol 的对应关系

(page[i]==n) 表示 page[i]已存入内存块 n 中
(page[i]==-1) 表示没有存入内存
(pagecontrol[i]==n) 表示内存块 n 存放了 page[i]
(pagecontrol[i]==-1) 表示内存块 n 未使用

数据结构
使用队列数据结构

分析
FIFO 策略的命中率约等于内存块与进程块个数之比

//=========================
//  author: bibibi
//  description: FIFO_PAGE_REPLACE
//=========================
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

static int  ap=100;                                      //进程页面数
static int pp=30;                                        //内存分配页面数
static int total_instruction=100;           //记录所有页面总的命中次数
static int diseffect=0;                           //记录未命中次数,即缺页中断发生次数

//用来判断两数字是否相等的函数
int equal(int a,int b){
    return (a==b)?0:-1;
}

//FIFO页面置换
int FIFO(){
    int page[ap];                                   //进程页面
    int pagecontrol[pp];                    //内存分配的页面
    int page_head=0;                         //队列头
    int page_tail=pp-1;                      //队列尾
    int *base=&pagecontrol;          //内存分配页面的基地址

    int work[total_instruction];     //进程操作的顺序
    int work_index=0;                       //进程当前操作的下标

    srand((int)time(0));                                                         //初始化随机种子
    for(int i=0;i<ap;i++) page[i]=-1;                                   //初始化进程页面
    for(int i=0;i<pp;i++) pagecontrol[i]=-1;                    //初始化内存分配的页面
    for(int i=0;i<total_instruction;i++)                             //初始化进程操作的顺序
        work[i]=(int)(total_instruction*(rand()/(RAND_MAX+1.0)));

    //算法执行过程
    while(work_index<total_instruction){                    //如果存在下一个进程操作

        //lfind(work[work_index], base, &pp, sizeof(pagecontrol[0]), equal) == NULL

        if(page[work[work_index]]!=-1){          //如果在内存分配页面数组中存在
            work_index++;
        }
        else{                           //未命中
            if(page_head==page_tail){                                         //队列已满
                page[pagecontrol[page_tail]]=-1;                                 //取出一个进程页
                page_tail=(page_tail+1)%pp;                                         //队列尾修改
                pagecontrol[page_head]=work[work_index];          //添加进程
                page[work[work_index]]=page_head;                        //加入一个进程
                page_head=(page_head+1)%pp;                                  //队列头修改
            }
            else{                                                                                   //队列未满
                pagecontrol[page_head]=work[work_index];
                page[work[work_index]]=page_head;
                page_head=(page_head+1)%pp;
            }

            diseffect++;
            work_index++;
        }
    }

    printf("总命中率: %f \r\n",(1-((float)diseffect)/(float)total_instruction));                                 //输出命中率
}

int main(){

    //执行FIFO策略的页面替换
    FIFO();

    return 0;
}

3.2 LRU 策略

数据结构

对于内存块,同时使用两种数据结构:
1. 数组,便于定位,使得进程块中的一个 int 属性可以唯一地对应一个内存块,数组中每一个元素都是一个双向链表的节点
2. 含头尾节点的双向链表,使得命中后调整和添加操作都可以达到 O(1)复杂度
对于进程块,使用数组,数组为-1 表示不在内存中,数组元素大于等于 0 则表示在内存中的数组描述地址

算法简述

如果进程块在内存中(命中),则将其对应的链表节点(通过进程块对应的内存数组下标找到)调整到最前面
如果没有命中,则将进程块填入最后一个节点,再将最后一个节点调整到最前面

page 与 pagecontrol 的对应关系

pagecontrol[i].controlindex 表示节点在数组描述中的下标
pagecontrol[i].pageindel 表示节点中存放的进程块下标
pagecontrol[i].preptr 指向上一个节点
pagecontrol[i].postptr 指向下一个节点
page[i]=-1 表示进程块不在内存中
page[i]>=0 表示进程快在内存的数组描述中的下标

分析

由于操作顺序是随机生成的,其实是不满足局部性原理的,这种情况下所有的策略的命中率应该都大致等于内存块数量与进程块数量的比值
如果满足局部性原理的话,LRU 策略的命中率应该是更高的

//=========================
//  author: bibibi
//  description: LRU_PAGE_REPLACE
//=========================
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

static int  ap=100;                                      //进程页面数
static int pp=30;                                        //内存分配页面数
static int total_instruction=100;         //记录所有页面总的命中次数
static int diseffect=0;                             //记录未命中次数,即缺页中断发生次数

typedef struct LRU_PAGE                     //记录使用记录的双向链表
{
    int control_index;                                            //内存分页数组的下标
    int page_index;                                                //记录在内存分配页面中的下标
    struct LRU_PAGE* preptr;                           //指向使用时间更近的块
    struct LRU_PAGE* postptr;                        //指向使用时间更远的块
}LRU_PAGE ;



//LRU页面置换
int LRU(){
    int page[ap];                                                   //进程页面
    LRU_PAGE pagecontrol[pp];                    //内存分配的页面

    int work[total_instruction];     //进程操作的顺序
    int work_index=0;                       //进程当前操作的下标

    srand((int)time(0));                                                         //初始化随机种子
    for(int i=0;i<ap;i++) page[i]=-1;                                    //初始化进程页面
    for(int i=0;i<total_instruction;i++)                             //初始化进程操作的顺序
        work[i]=(int)(total_instruction*(rand()/(RAND_MAX+1.0)));

    for(int i=0;i<pp-1;i++){                                                         //初始化内存分配的页面
        pagecontrol[i].control_index=i;
        pagecontrol[i].page_index=-1;
        pagecontrol[i].postptr=&pagecontrol[i+1];
        pagecontrol[i+1].preptr=&pagecontrol[i];
    }
    pagecontrol[pp-1].control_index=pp-1;
    pagecontrol[pp-1].page_index=-1;

    LRU_PAGE head,tail;                     //声明空白的头和尾节点
    head.postptr=&pagecontrol[0];
    tail.preptr=&pagecontrol[pp-1];
    pagecontrol[0].preptr=&head;
    pagecontrol[pp-1].postptr=&tail;
    int temp_index=0;

    //算法执行过程
    while(work_index<total_instruction){                    //如果存在下一个进程操作

        //lfind(work[work_index], base, &pp, sizeof(pagecontrol[0]), equal) == NULL
       temp_index = page[work[work_index]];

        if(temp_index!=-1){          //如果在内存分配页面数组中存在
            work_index++;

            //命中,调整常用块的双向链表
            (pagecontrol[temp_index].preptr)->postptr=(pagecontrol[temp_index].postptr);
            (pagecontrol[temp_index].postptr)->preptr=(pagecontrol[temp_index].preptr);
            pagecontrol[temp_index].preptr=&head;
            pagecontrol[temp_index].postptr=head.postptr;
            head.postptr=&(pagecontrol[temp_index]);
            (pagecontrol[temp_index].postptr)->preptr=&pagecontrol[temp_index];
        }
        else{                           //未命中

            (tail.preptr)->page_index=work[work_index];                     //将进程块放入链表最后一个节点
            page[work[work_index]]=(tail.preptr)->control_index;

            (head.postptr)->preptr=tail.preptr;
            (tail.preptr)->postptr=head.postptr;                                        //将最后一个节点转移到第一个节点
            head.postptr=tail.preptr;
            tail.preptr=(tail.preptr)->preptr;
            (tail.preptr)->postptr=&tail;
            (head.postptr)->preptr=&head;

            diseffect++;
            work_index++;
        }
    }

    printf("总命中率: %f \r\n",(1-((float)diseffect)/(float)total_instruction));                                 //输出命中率
}

int main(){

    //执行LRU策略的页面替换
    LRU();

    return 0;
}