博客

哈工大李治军老师操作系统实验之地址映射与共享

  • Post author:
  • Post category:其他


文章目录



实验目的

  • 深入理解操作系统的段、页式内存管理，深入理解段表、页表、逻辑地址、线性地址、物理地址等概念
  • 实践段、页式内存管理的地址映射过程
  • 编程实现段、页式内存管理的内存共享，从而深入理解操作系统的内存管理



实验内容

  • 用Bochs调试工具跟踪Linux 0.11 的地址翻译（地址映射）过程，了解IA-21和Linux 0.11 的内存管理机制
  • 在Ubuntu上编写多进程的生产者-消费者程序，用共享内存作为缓冲区
  • 在信号量实验的基础上，为Linux0.11 增加共享内存功能，并将生产者-消费者程序移植到Linux 0.11当中。



实验过程



1. 跟踪Linux 0.11 的地址翻译过程

略，按照教程走就不会出现问题



2. 在Ubuntu上实现多进程的生产者-消费者出现，用共享缓冲区

这部分直接给出代码,主要是知道怎么调用函数。 

//生产者producer.c
#define __LIBRARY__
#include <unistd.h>
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/types.h>

#define MAX_NUMBER 500
#define MAX_BUFFER 10

_syscall2(int, sem_open, const char*,name, unsigned int,value);
_syscall1(int, sem_wait, sem_t*, sem);
_syscall1(int, sem_post, sem_t*, sem);
_syscall1(int, sem_unlink, const char*, name);
_syscall3(int, shmget, int, key, size_t, size, int, shmflg);
_syscall3(int, shmat, int, shmid, const void *, shmaddr, int, shmflg);

int main(int argc, char * argv[]){
    sem_t* full = (sem_t*)sem_open("full", 0);
    sem_t* mutex = (sem_t*)sem_open("mutex", 1);
    sem_t* empty = (sem_t*)sem_open("empty", MAX_BUFFER);

    int position, shmid;
    int *data;
    int key = 9999;
    int i;

    shmid = shmget(key, (MAX_BUFFER+1)*sizeof(int), 0);
    data = (int*)shmat(shmid, 0, 0);
    /*
    printf("the shmid is %d, the data is %x\n", shmid, data);
    */

    for(i=0; i < MAX_NUMBER+1; i++){
        sem_wait(empty);
        sem_wait(mutex);

        position = (i % MAX_BUFFER);
        data[position] = i;

        sem_post(mutex);
        sem_post(full);
    }
    return 0;
}

//消费者consumer.c
#define __LIBRARY__
#include <unistd.h>
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/types.h>

#define MAX_NUMBER 500
#define MAX_BUFFER 10

_syscall2(int, sem_open, const char*,name, unsigned int,value);
_syscall1(int, sem_wait, sem_t*, sem);
_syscall1(int, sem_post, sem_t*, sem);
_syscall1(int, sem_unlink, const char*, name);
_syscall3(int, shmget, int, key, size_t, size, int, shmflg);
_syscall3(int, shmat, int, shmid, const void *, shmaddr, int, shmflg);

int main(int argc, char * argv[]){
    sem_t* full = (sem_t*)sem_open("full", 0);
    sem_t* mutex = (sem_t*)sem_open("mutex", 1);
    sem_t* empty = (sem_t*)sem_open("empty", MAX_BUFFER);

    int tmp, shmid;
    int position = 0;
    int *data;
    int key = 9999;

    shmid = shmget(key, (MAX_BUFFER+1)*sizeof(int), 0);
    data = (int*)shmat(shmid, 0, 0);
    /*
    printf("the shmid is %d, the data is %x\n", shmid, data);
    */
    while(1){
        sem_wait(full);
        sem_wait(mutex);

        position = (position % MAX_BUFFER);
        printf("%d: %d\n", getpid(), data[position]);
        fflush(stdout);
        if(data[position] == MAX_NUMBER){
            sem_post(mutex);
            sem_post(empty);
            break;
        }
        position++;
        
        sem_post(mutex);
        sem_post(empty);
    }
    sem_unlink("full");
    sem_unlink("mutex");
    sem_unlink("empty");
    return 0;
}



3. 在信号量的基础上为Linux0.11增加共享内存功能，并将生产者-消费者模型移植到Linux0.11进行测试

实现共享缓冲区也是通过添加系统调用实现，实验报告中已经告诉我们添加俩系统调用，因此实验步骤依然是添加系统调用的步骤。



3.1 前置知识

首先要明白：逻辑地址、线性地址、虚拟地址、物理地址之间的区别以及如何计算，这个可以看

这篇博客

。

其次明白要实现共享内存，需要进行的几个步骤：

  • 在内存当中找一块空闲空间返回

    物理地址

    。（如下图中的物理共享内存）
  • 寻找空闲的虚拟地址空间建立线性地址（段基址+段内偏移）与物理地址之间的映射关系即将填写相关页表使得

    MMU

    能通过这个页表找到最后的

    物理地址

    。（即填写图中的页表）
  • 更新逻辑地址。（即填写更新的段表）

在这里插入图片描述

这张图从左往右看是地址翻译的过程，也是地址跟踪的过程；从右往左看是我们需要实现共享内存的过程，也就是说我们要做的就是从物理地址出发，一步步使得各个进程都能看到同一块物理内存的过程！



3.2 实现过程

由于之前梳理过如何添加系统调用，因此本文直接讨论如何实现共享内存，不再叙述添加系统调用的过程。

共享内存的实现严格按照上面步骤进行。


  1. 在内存当中寻找一块空闲空间并返回物理地址

    这个实验报告当中也给出了方法：通过调用

    get_free_page

    函数，该函数会帮我们找到内存当中空闲区域并返回该区域起始

    物理地址

    。这一步我们在

    shmget

    函数中实现 

    int allkey[20];
void *allAddress[20];
int countKey;
/**
 * @brief:
 * @note   
 * @param  key: 表示该页在内存空间中的标识，由用户自定义
 * @param  size: 申请空间大小
 * @param  shmflg: 设置属性，由于实验报告没有要求，可以忽略
 * @retval 
 */
int sys_shmget(int key,size_t size,int shmflg)
{
   int i;
   /*
   首先根据标识遍历已经创建的共享内存，如果已经创建则返回共享内存地址（意味着与其他进程共享）
   */
   for(i=0;i<countKey;i++) if(allkey[i]==key)return key;
   //4096=4KB，表示一页大小。只能申请一页大小的共享内存
   if(size>4096)
    {
      errno=EINVAL;
      return -1;
    }
   /*
   如果之前没有创建过key标识的共享内存则现在创建
   */
   int tmp=get_free_page();
   if(tmp==0)
   {
       printk("Have no page!!!\n");
       errno=ENOMEM;
       return -1;
   }
   /*
   将创建好的共享内存纳入控制数组方便与其他进程共享，也是为地址映射做好准备
   */
   allkey[countKey]=key;
   allAddress[countKey]=(void*)tmp;
   countKey++;
   return key;
}


  2. 寻找空闲的虚拟地址空间建立线性地址（段基址+段内偏移）与物理地址之间的映射关系

    这一步也就是填写页表的过程，因为线性地址通过页表找到最终的物理地址，因此也是比较容易完成的，实验报告也给出了方法。在虽然给出了方法，但是我们还是需要拿出一张虚拟内存表来分析：

    在这里插入图片描述

    从虚拟内存空间示意图我们知道堆与栈之间的虚拟内存是没有被使用的，因此我们可以在这个区间申请一块内存用于建立页表与实际的物理内存进行映射。同时我们可以发现

    brk

    指针正好指向堆区顶部，我们可以利用这个指针帮我们定位需要申请的空间首地址。

    报告中选择数据段中的一段内存，而我选择

    brk

    指针后的空闲区域，幸运的是在进程

    PCB

    当中记录了brk指针的

    逻辑地址

    ，然后加上进程开始处的虚拟地址就可以得到brk指针的虚拟地址或者叫线性地址（虚拟地址=段基址+逻辑地址）。 

    /**
 * @brief ：地址映射
 * @note   
 * @param  shmid: shmget函数返回的物理地址标识，用于获得真正的物理地址
 * @param  *shmaddr: 这不是物理地址！！！，直接写0，可忽略
 * @param  shmflg: 可忽略
 * @retval 
 */
int sys_shmat(int shmid,const void *shmaddr,int shmflg)
{
    unsigned long  tmp;
    int i;
    void* result;
    //根据标识查找要映射的物理地址
    for(i=0;i<countKey;i++)if(allkey[i]==shmid)break;
    if(i==countKey)return -1;
    //result存储着真正的物理地址
    result=allAddress[i];
    //获取brk指针的逻辑地址
    tmp=current->brk;
    //current->brk+=PAGE_SIZE;
    //current->start_code:进程开始处的虚拟地址，建立线性地址与物理地址的映射关系
    if(!put_page(result,current->start_code+tmp))
    {
       errno=EINVAL;
       return -1;
    }
    return tmp;
}


  3. 更新进程虚拟内存的逻辑地址

    这一步就是更新以下段内的偏移地址（逻辑地址），因为添加了一个共享内存空间，段内其他部分的 偏移地址需要更新。在步骤2的基础上加一行位移代码就行（更新brk指针的逻辑地址）。 

    /**
 * @brief ：地址映射
 * @note   
 * @param  shmid: shmget函数返回的物理地址标识，用于获得真正的物理地址
 * @param  *shmaddr: 这不是物理地址！！！，直接写0，可忽略
 * @param  shmflg: 可忽略
 * @retval 
 */
int sys_shmat(int shmid,const void *shmaddr,int shmflg)
{
    unsigned long  tmp;
    int i;
    void* result;
    //根据标识查找要映射的物理地址
    for(i=0;i<countKey;i++)if(allkey[i]==shmid)break;
    if(i==countKey)return -1;
    //result存储着真正的物理地址
    result=allAddress[i];
    //获取brk指针的逻辑地址
    tmp=current->brk;
    //更新brk逻辑地址，由于就申请了一页空间，就把brk指针位移一个页的大小就行。
    //PAGE_SIZE=0x4000000
    current->brk+=PAGE_SIZE;
    //current->start_code:进程开始处的虚拟地址，建立线性地址与物理地址的映射关系
    if(!put_page(result,current->start_code+tmp))
    {
       errno=EINVAL;
       return -1;
    }
    //返回共享内存的首地址
    return tmp;
}

    实现共享内存的系统调用已经写好了，这里给出完整的

    shm.c

    代码 

    #include<errno.h>
#include<unistd.h>
#include<sys/wait.h>
#include<a.out.h>
#include<sys/types.h>
#include<linux/sched.h>
#include<linux/kernel.h>
int allkey[20];
void *allAddress[20];
int countKey;
/**
 * @brief:
 * @note   
 * @param  key: 表示该页在内存空间中的标识，由用户自定义
 * @param  size: 申请空间大小
 * @param  shmflg: 设置属性，由于实验报告没有要求，可以忽略
 * @retval 
 */
int sys_shmget(int key,size_t size,int shmflg)
{
   int i;
   /*
   首先根据标识遍历已经创建的共享内存，如果已经创建则返回共享内存地址（意味着与其他进程共享）
   */
   for(i=0;i<countKey;i++) if(allkey[i]==key)return key;
   //4096=4KB，表示一页大小。只能申请一页大小的共享内存
   if(size>4096)
    {
      errno=EINVAL;
      return -1;
    }
   /*
   如果之前没有创建过key标识的共享内存则现在创建
   */
   int tmp=get_free_page();
   if(tmp==0)
   {
       printk("Have no page!!!\n");
       errno=ENOMEM;
       return -1;
   }
   /*
   将创建好的共享内存纳入控制数组方便与其他进程共享，也是为地址映射做好准备
   */
   allkey[countKey]=key;
   allAddress[countKey]=(void*)tmp;
   countKey++;
   return key;
}
/**
 * @brief ：地址映射
 * @note   
 * @param  shmid: shmget函数返回的物理地址标识，用于获得真正的物理地址
 * @param  *shmaddr: 这不是物理地址！！！，直接写0，可忽略
 * @param  shmflg: 可忽略
 * @retval 
 */
int sys_shmat(int shmid,const void *shmaddr,int shmflg)
{
    unsigned long  tmp;
    int i;
    void* result;
    //根据标识查找要映射的物理地址
    for(i=0;i<countKey;i++)if(allkey[i]==shmid)break;
    if(i==countKey)return -1;
    //result存储着真正的物理地址
    result=allAddress[i];
    //获取brk指针的逻辑地址
    tmp=current->brk;
    //更新brk逻辑地址，由于就申请了一页空间，就把brk指针位移一个页的大小就行。
    //PAGE_SIZE=0x4000000
    current->brk+=PAGE_SIZE;
    //current->start_code:进程开始处的虚拟地址，建立线性地址与物理地址的映射关系
    if(!put_page(result,current->start_code+tmp))
    {
       errno=EINVAL;
       return -1;
    }
    //返回共享内存的首地址
    return tmp;
}

  4. 修改

    Linux/mm/

    目录下的

    Makefile
     

    ...
OBJS	= memory.o page.o shm.o
...
...
shm.o: shm.c ../include/errno.h ../include/unistd.h ../include/sys/wait.h \
  ../include/sys/types.h ../include/linux/sched.h ../include/a.out.h
  ../include/linux/kernel.h

    以防万一，这里也给出

    Linux/kernel

    目录下的

    Makefile

    文件 

    #
# Makefile for the FREAX-kernel.
#
# Note! Dependencies are done automagically by 'make dep', which also
# removes any old dependencies. DON'T put your own dependencies here
# unless it's something special (ie not a .c file).
#

AR	=ar
AS	=as --32
LD	=ld
LDFLAGS	=-m elf_i386 -x
CC	=gcc-3.4 -march=i386
CFLAGS	=-m32 -g -Wall -O -fstrength-reduce -fomit-frame-pointer \
	-finline-functions -nostdinc -I../include
CPP	=gcc-3.4 -E -nostdinc -I../include

.c.s:
	$(CC) $(CFLAGS) \
	-S -o $*.s $<
.s.o:
	$(AS) -o $*.o $<
.c.o:
	$(CC) $(CFLAGS) \
	-c -o $*.o $<

OBJS  = sched.o system_call.o traps.o asm.o fork.o \
	panic.o printk.o vsprintf.o sys.o exit.o \
	signal.o mktime.o sem.o

kernel.o: $(OBJS)
	$(LD) -m elf_i386 -r -o kernel.o $(OBJS)
	sync

clean:
	rm -f core *.o *.a tmp_make keyboard.s
	for i in *.c;do rm -f `basename $$i .c`.s;done
	(cd chr_drv; make clean)
	(cd blk_drv; make clean)
	(cd math; make clean)

dep:
	sed '/\#\#\# Dependencies/q' < Makefile > tmp_make
	(for i in *.c;do echo -n `echo $$i | sed 's,\.c,\.s,'`" "; \
		$(CPP) -M $$i;done) >> tmp_make
	cp tmp_make Makefile
	(cd chr_drv; make dep)
	(cd blk_drv; make dep)

### Dependencies:
sem.s sem.o: sem.c ../include/linux/kernel.h ../include/unistd.h
exit.s exit.o: exit.c ../include/errno.h ../include/signal.h \
  ../include/sys/types.h ../include/sys/wait.h ../include/linux/sched.h \
  ../include/linux/head.h ../include/linux/fs.h ../include/linux/mm.h \
  ../include/linux/kernel.h ../include/linux/tty.h ../include/termios.h \
  ../include/asm/segment.h
fork.s fork.o: fork.c ../include/errno.h ../include/linux/sched.h \
  ../include/linux/head.h ../include/linux/fs.h ../include/sys/types.h \
  ../include/linux/mm.h ../include/signal.h ../include/linux/kernel.h \
  ../include/asm/segment.h ../include/asm/system.h
mktime.s mktime.o: mktime.c ../include/time.h
panic.s panic.o: panic.c ../include/linux/kernel.h ../include/linux/sched.h \
  ../include/linux/head.h ../include/linux/fs.h ../include/sys/types.h \
  ../include/linux/mm.h ../include/signal.h
printk.s printk.o: printk.c ../include/stdarg.h ../include/stddef.h \
  ../include/linux/kernel.h
sched.s sched.o: sched.c ../include/linux/sched.h ../include/linux/head.h \
  ../include/linux/fs.h ../include/sys/types.h ../include/linux/mm.h \
  ../include/signal.h ../include/linux/kernel.h ../include/linux/sys.h \
  ../include/linux/fdreg.h ../include/asm/system.h ../include/asm/io.h \
  ../include/asm/segment.h
signal.s signal.o: signal.c ../include/linux/sched.h ../include/linux/head.h \
  ../include/linux/fs.h ../include/sys/types.h ../include/linux/mm.h \
  ../include/signal.h ../include/linux/kernel.h ../include/asm/segment.h
sys.s sys.o: sys.c ../include/errno.h ../include/linux/sched.h \
  ../include/linux/head.h ../include/linux/fs.h ../include/sys/types.h \
  ../include/linux/mm.h ../include/signal.h ../include/linux/tty.h \
  ../include/termios.h ../include/linux/kernel.h ../include/asm/segment.h \
  ../include/sys/times.h ../include/sys/utsname.h
traps.s traps.o: traps.c ../include/string.h ../include/linux/head.h \
  ../include/linux/sched.h ../include/linux/fs.h ../include/sys/types.h \
  ../include/linux/mm.h ../include/signal.h ../include/linux/kernel.h \
  ../include/asm/system.h ../include/asm/segment.h ../include/asm/io.h
vsprintf.s vsprintf.o: vsprintf.c ../include/stdarg.h ../include/string.h

    当然，由于本人知识水平有限，如果文中有重大错误，请务必告诉我，非常感谢！


版权声明：本文为zengwei1973原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。