中国石油大学操作系统课程设计

中国石油大学（华东）

操作系统课程设计

设计报告

螺旋 字符串Matrix 对比

Ncurse 脚Floppy 驱动 进程

界面 本 Linux Driver 汇总

线程

警察小偷

线程

哲学家

系统

调用

Shell

编写

模拟

内存

评语

中国石油大学（华东）计算机科学与技术学院

成绩

要求（本页打印）：

1、 双面打印，内容篇幅不要过长（每个实验不要超过3页），禁止贴全部程序，只贴关键代码即可。

2、 禁止抄袭

3、 实验列表如下：

实验1：螺旋矩阵实验 —— Linux下的C编程

实验2：字符串对比实验 —— Linux下的C编程

实验3：界面编写实验 —— 基于NCurses的文本界面

实验4：脚本编写实验 —— 批量建立和删除用户

实验5：内核定制实验 —— FloppyLinux的实现

实验6：驱动程序实验 —— 实现驱动程序插入内核并调用

实验7：进程汇总实验 —— 创建、信号量机制和管道

实验8：线程操作实验 —— 警察小偷的PV操作

实验9：线程操作实验 —— 哲学家进餐的资源竞争

实验10：系统调用实验 —— 添加系统调用

实验11：终端编写实验 —— 模拟终端shell

实验12：内存模式实验 —— 实现malloc和free的内存模拟过程

4、 每个实验要求格式如下（内容使用5号字）：

实验：实验题目

一、 实验情景描述

二、 实验原理

三、 关键代码（包括截图）

四、 实验结果及说明总结

实验1：螺旋矩阵实验 —— Linux下的C编程

一、实验情景描述

完成一个程序，要求输入两个数字即可形成相应的字母螺旋矩阵。

例如输入5，6，则程序会生成如下5行6列的矩阵，Z之后循环至A：

A B C D E F

R S T U V G

Q B C D W H

P A Z Y X I

O N M L K J

二、实验原理

完成程序ju.c,并用Makefile完成编译。

三、关键代码

Makefile如下

CC=gcc

OBJS=ju.o

EXEC=ju

all:$(EXEC)

$(EXEC):$(OBJS)

$(CC) -o $@ $(OBJS)

clean:

rm -f $(OBJS) $(EXEC)

ju.c部分代码如下

int total = 1;

char digit = 65;

x = 0, y = 0;

a[x][y] = 65;

while(total < m*n){

while(y+1

if(digit>=90){

digit = 64;

}

a[x][++y] = ++digit;

++total;

}

while(x+1

if(digit>=90){

digit = 64;

}

a[++x][y] = ++digit;

++total;

}

while(y-1>=0&&!a[x][y-1]){

if(digit>=90){

digit = 64;

}

a[x][--y] = ++digit;

++total;

}

while(x-1>=0&&!a[x-1][y]){

if(digit>=90)

{ digit = 64;}

a[--x][y] = ++digit;

++total; }}

四、实验结果

实验2：字符串对比实验 —— Linux下的C编程

一、 实验情景描述

完成一个程序，输入两个字符串，判断其中一个字符串是否是另一个的子串，如果是则输出true，否则输出false。

二、 实验原理

完成程序ju.c,并用Makefile完成编译。

CC=gcc

OBJS=mystring.o

EXEC=mystring

all:$(EXEC)

$(EXEC):$(OBJS)

$(CC) -o $@ $(OBJS)

clean:

rm -f $(OBJS) $(EXEC)

三、 关键代码（包括截图）

Ju.c的部分代码如下：

int main()

{

char s1[N],s2[N];

gets(s1);

gets(s2);

if ( strstr(s1,s2) )

{

printf("truen");

}

else

{

printf("falsen");

}

return 0;

}

四、 实验结果及说明总结

实验3：界面编写实验 —— 基于NCurses的文本界面

一、 实验情景描述

将螺旋矩阵程序和字符串程序集成在基于Ncurse的文本界面上，对其进行实现。

二、 实验原理

Ncurses是一个能提供功能键定义(快捷键),屏幕绘制以及基于文本终端的图形互动功能的动态库。

其中，libncurses库用来在显示器上显示文本界面。

二、 关键代码

部分代码如下：

int x=StartX,y=StartY,ch;

initial();

box(stdscr,0,0);

attron(A_REVERSE);

mvaddstr(0,20,"TCS NAS Server v1.13 by CyberAct");

attroff(A_REVERSE);

mvaddstr(6,19,"[*] juzheng");

mvaddstr(8,19,"[*] mystring");

mvaddstr(18,19,"[*] Exit");

move(y,x);

do

{

ch=getch();

switch(ch)

{

case KEY_UP :

if(y>=7) y=y-2;

else y=y;

break;

case KEY_DOWN :

if(y<=17) y=y+2;

else y=y;

break;

case 'r' :

if(y==18)

{

endwin();

exit(1);

}

else if(y==16) system("sudo -b /sbin/init 0");

else if(y==14) system("sudo -b /sbin/init 6");

else if(y==6)

{

endwin();

system("./ju");

}

else if(y==8)

{

endwin();

system("./mystring");

}

else if(y==10)

{

endwin();

clear();

}

else if(y==12)

{

endwin();

clear();

}

break;

case 27 :

endwin();

exit(1);

default :

break;

}

move(y,x);

}

while(1);

}

四、 实验结果

实验4：脚本编写实验 —— 批量建立和删除用户

一、 实验情景描述

此shell程序实现给系统添加四个新组，每个组代表一个班级，每个班级中添加30个用户。

二、 实验原理

Shell脚本以文本方式存储，并且必须通过Shell解释后才能够执行。Shell本身是一个程序，负责解释和执行用户输入的命令，也可以用来进行程序设计，它是用户和Linux系统交互的纽带。

因为Shell脚本是以文本方式进行存储的，所以可以用任何的文本编辑器来编辑。在文本中输入要执行的Shell命令或Linux命令并保存为一个新的文件。当要运行这个脚本时，可调用这个脚本来执行其中的所有指令。

三、 关键代码

部分代码如下：

#!/bin/sh

for class in 1 2 3 4

do

for number in $(seq 01 30)

do

USERNAME=stu${class}${number}

useradd $USERNAME

chown -R $USERNAME /home/$USERNAME

done

done

四、 实验结果

实验5：内核定制实验 —— FloppyLinux的实现

一、 实验情景描述

使用软盘进行GRUB配置，之后使用make menuconfig进行内核配置，之后使用Busybox编译生成一个新的根文件系统，把这些整合到软盘中完成FloppyLinux。

二、 实验原理

首先打开RedHat虚拟机，将老师给的2文件拷贝到虚拟机中。

为虚拟机增加虚拟软盘

在软盘上安装引导器(grub)。

首先对软盘建立ex2文件系统,之后将系统中grub目录下的引导文件stage1，stage2复制到软盘

最后配置grub信息

配置busybox相关选项

a.在根目录下新建floppylinux目录，floppylinux下再新建floppylinux，将2复制到第二个floppylinux下。

b.进入busybox-1.00文件夹

make menuconfig之后进入配置界面。

编译并安装busybox

建立临时目录，该目录为软盘的文件系统

建立设备列表

建立启动配置文件，之后建立连接文件

制作镜像文件，将先前做好的floppylinux根文件系统拷贝到ram1上。

检查，用loop设备来把他重新挂载到文件系统里，之后压缩镜像文件

查看压缩之后的大小，大约在403k左右

编译linux系统内核，完成配置，执行完毕之后会生成一个bzImage文件，大约在660k左右

整合启动盘，重启电脑，输入回车即可输入linux的命令，进入floppylinux。

三、 关键代码

每一步骤的部分代码如下:

[root@localhost root]#mke2fs /dev/fd0

[root@localhost root]#mount /dev/fd0 /mnt/floppy

[root@localhost floppy]# mkdir boot

[root@localhost floppy]# mkdir boot/grub

[root@localhost floppy]# cp /boot/grub/stage1 /mnt/floppy/boot/grub/

[root@localhost floppy]# cp /boot/grub/stage2 /mnt/floppy/boot/grub/

[root@localhost floppylinux]# tar -xjvf 2

[**************************]#makemenuconfig[root@localhost _install]# mkdir /floppylinux/floppylinux/floppyImage

[root@localhost floppyImage]#

/floppylinux /

cp

floppylinux/ /floppylinux/floppylinux/busybox-1.00/_install/*

floppyImage/ -r

[root@localhost floppyImage]# mkdir dev etc etc/init.d proc mnt tmp var

[root@localhost floppyImage]# chmod 755 dev etc etc/init.d bin mnt tmp var

[root@localhost floppyImage]# chmod 555 proc

[root@localhost etc]# vi inittab

inittab内容为:

::sysinit:/etc/init.d/rcS

::askfirst:/bin/sh

[root@localhost etc]# vi fstab

fstab内容为

proc /proc proc defaults 0 0

[********************]#vircSrcS内容为:

#!/bin/sh

mount –a

[root@localhost grub]# vi

内容为:

timeout 0

default 10

title FloppyLinux

root (fd0)

kernel /boot/bzImage

initrd /

[root@localhost grub]# ln -s

四、 实验结果

实验6：驱动程序实验 —— 实现驱动程序插入内核并调用

一、实验情景描述

在其中编写驱动程序matrixdriver.c文件和Makefile文件。之后编译生成驱动程序模块。基于该驱动程序模块编写测试程序matrixtest.c文件。然后将驱动程序模块装入到目标开发板上，建立设备结点并连接，运行测试程序测试之。

设定驱动程序实现的字符设备，主设备号为111，此设备号为0。实现的功能是，将驱动程序和第二章的第三题结合起来。即测试程序输入两个数字，在驱动程序即可形成相应的字母螺旋矩阵。

二、实验原理

首先完成三个脚本的内容。分别编写matrixdriver.c、Makefile和matrixtest.c。其中matrixdriver.c是驱动程序，matrixtest.c是测试程序。完成编写之后，执行make，生成驱动模块evan.o和可执行文件test_demo。之后首先在/dev目录下建立设备结点，并插入驱动模块。之后运行程序matrixtest。完成之后，卸载驱动模块，删除结点。

三、 关键代码

matrixtest.c部分代码如下：

void showbuf(char *buf,int m,int n)

{

int i,j=0;

int a[1024][1024];

for(i=0;i

{

for(j=0;j

{

a[i][j]=buf[i*n+j];

}

}

for(i=0;i

{

for(j=0;j

{

printf(" %c ",a[i][j]);

}

printf("n");

}

}

Matrixdriver.c部分代码如下：

while(total < m*n){

while(y+1

if(digit>=90){

digit = 64;

}

a[x][++y] = ++digit;

++total;

}

while(x+1

if(digit>=90){

digit = 64;

}

a[++x][y] = ++digit;

++total;

}

while(y-1>=0&&!a[x][y-1]){

if(digit>=90){

digit = 64;

}

a[x][--y] = ++digit;

++total;

}

while(x-1>=0&&!a[x-1][y]){

if(digit>=90){

digit = 64;

}

a[--x][y] = ++digit;

++total;

}

}

int i,j,k=0;

for(i=0;i

for(j=0;j

}

static ssize_t evan_write(struct file *filp, char *buffer, size_t count)

{

int m,n;

copy_from_user(drv_buf,buffer,count);

m=(int)(drv_buf[0]);

n=(int)(drv_buf[1]);

solve(m,n);

return count;

}

static ssize_t evan_read(struct file *filp, char *buffer, size_t count,loff_t *ppos)

{

if (count>MAX_BUF_LEN) count=MAX_BUF_LEN;

copy_to_user(buffer,drv_buf,count);

printk("user read data from drivers!n");

return count;

}

drv_buf[k++]=a[i][j];

四、 实验结果

实验7：进程汇总实验 —— 创建、信号量机制和管道

一、 实验情景描述

进程是在CPU及内存中运行的程序代码，是动态执行的代码。在一个操作系统中，每个正在运行的工作都可以称为进程（process）。它包括进程标识符和相关的数据，相关数据又包含进程变量、外部变量以及进程堆栈等。当一个进程启动之后，系统会指定一个唯一的数值来作为该进程的进程标识符，即PID。

二、 实验原理

1.编写fork.c和Makefile文件。理解新进程的建立和消除zombie进程的过程。

2.编写signal.c和Makefile文件。理解kill函数和signal函数的用法，并且理解SIGALRM的用法。signal()：用来接收一个指定类型的信号，并调用相关的信号处理函数。

kill()：用来传送sig参数所指定的信号给pid参数所指定的进程。

3.管道（pipe）也是进程通信方式的一种。它用来连接一个进程的输入和另一个进程的输出，是一种单向的通信方式。

3.1编写pipe.c和Makefile文件。理解管道的建立，以及管道的特征和通信等内容。

pipe()：该函数运行之后会打开两个文件描述符。其中fd[0]用来读取，fd[1]用来写入。

如果pipe()函数运行成功，则返回0；如果发生错误，返回-1。

3.2编写popen.c和Makefile文件。理解高级管道的建立和使用。

popen()：建立一个管道。

如果函数运行成功，则返回文件指针；如果发生错误，返回NULL。

3.3编写fifo1.c、fifo2.c和Makefile文件。理解有名管道的建立和使用。

FIFO即有名管道。它可以在不相关的进程之间进行通信。因为它是通过系统中的文件进行通信，其他的进程只要知道FIFO文件名称，即可加入通信；另外FIFO可以同时具有多个读取端和写入端，多个进程可以同时写入同一个FIFO文件，多个进程也可以同时读取同一个FIFO文件

三、 关键代码

部分代码如下：

process()

{

int x=StartX,y=StartY,ch;

initial();

box(stdscr,0,0);

attron(A_REVERSE);

mvaddstr(0,20,"process");

attroff(A_REVERSE);

mvaddstr(6,19,"[*] fork");

mvaddstr(8,19,"[*] signal");

mvaddstr(10,19,"[*] pipe");

mvaddstr(12,19,"[*] popen");

mvaddstr(14,19,"[*] fifo");

mvaddstr(16,19,"[*] Exit");

move(y,x);

do{

ch=getch();

switch(ch){

case KEY_UP : if(y==16) y=14;

else if(y==14) y=12;

else if(y==12) y=10;

else if(y==10) y=8;

else if(y==8) y=6;

else y=y;

break;

case KEY_DOWN : if(y==6) y=8;

else if(y==8) y=10;

else if(y==10) y=12;

else if(y==12) y=14;

else if(y==14) y=16;

else y=y;

break;

case 'r' :

if(y==16) {endwin();clear();main();}

if(y==6) { endwin();system("./fork");}

if(y==8) {endwin();system("./signal");}

if(y==10) {endwin();system("./pipe");}

if(y==12) {endwin();system("./popen");}

if(y==14) {endwin();system("./fifo1");}

break;

case 't' :

if(y==6) y=8;

else if(y==8) y=10;

else if(y==10) y=12;

else if(y==12) y=14;

else if(y==14) y=16;

else if(y==16) y=6;

break;

case 27 : endwin();clear();main();

default :

break;

}

move(y,x);

}while(1);

}

四、 实验结果

实验8：线程操作实验 —— 警察小偷的PV操作

一、 实验情景描述

警察和小偷被手铐绑在一起，需要共同逃亡200m，手铐长度3m。使用基于Ncurse的文本界面显示警察与小偷的动态追逐效果。

二、 实验原理

使用了进程互斥锁mutex，创建了两个进程void *thief(void *args)和void *police(void *args)，利用随机数种子产生1-6的随机数，即警察或小偷的一次最大前进距离为6米，假设其中一人落后3米，即可前进6米

三、 关键代码

部分代码如下：

/**thief go first and police follow**/

void *thief(void *args)

{

int rand1;

while(1){

pthread_mutex_lock(&mutex);

srand((unsigned)time(NULL));/**随机种子**/

rand1=rand()%6+1;

if(my_thief-my_police<3)

{ //thief can run

if(my_thief+rand1

my_thief+=rand1;

else

my_thief=my_police+3;

}

pthread_mutex_unlock(&mutex);

sleep(1);

}

}

void *police(void *args)

{

int rand2;

while(1){

pthread_mutex_lock(&mutex);

srand((unsigned)time(NULL));/**随机种子**/

rand2=rand()%6+1;

if(my_police-my_thief<3){ //thief can run

if(my_police+rand2

my_police+=rand2;

else

my_police=my_thief+3;

}

//printf("police:%dn",my_police);

pthread_mutex_unlock(&mutex);

sleep(1);

}

}

int main()

{

pthread_t t1,t2;

pthread_create(&t1,NULL,thief,NULL);

pthread_create(&t2,NULL,police,NULL);

initscr();

crmode();

noecho();

int px,py;

px=0;py=0;

char ball1='p';

int tx,ty;

tx=0;ty=2;

char ball2='t';

while(1)

{

clear();

mvaddch(py,px,ball1);

mvaddch(ty,tx,ball2);

refresh();

px=my_police;

tx=my_thief;

if(my_police>=50 || my_thief>=50)

{

if(my_police>my_thief)

mvaddstr(14,16,"the first come is the police");

else

mvaddstr(14,16,"the first come is the thief");

break;

}

}

}

四、 实验结果

实验9：线程操作实验 —— 哲学家进餐的资源竞争

一、 实验情景描述

编程实现哲学家进餐模型。所谓的哲学家进餐模型，即有五个哲学家围坐在一圆桌旁，桌中央有一盆面条，每两人之间放一只筷子，即总共五根筷子。每个哲学家的行为是思考或者吃面条。为了吃面条，每个哲学家必须只能直接从自己的左边或右边去取筷子，两根筷子都取到了才能够吃面条。而吃完一根面条之前，哲学家不会放掉手里的筷子。

二、 实验原理

选用互斥锁mutex，如创建5个， pthread_mutex_t m[5];

模型抽象：

6个哲学家 --> 6个线程； 6支筷子 --> 6把互斥锁 int left(左手)， right(右手)

6个哲学家使用相同的逻辑，可通用一个线程主函数，void *tfn(void *arg)，使用参数来表示线程编号：int thread_num = (int)arg;

哲学家线程根据编号知道自己是第几个哲学家，而后选定锁，锁住，吃饭。否则哲学家thinking。

A B C D E F

6支筷子，在逻辑上形成环： 0 1 2 3 4 5 分别对应6个哲学家

振荡：如果每个人都攥着自己左手的锁，尝试去拿右手锁，拿不到则将锁释放。过会儿6个人又同时再攥着左手锁尝试拿右手锁，依然拿不到。如此往复形成另外一种极端死锁的现象——振荡

避免振荡现象：只需6个人中，任意一个人，拿锁的方向与其他人相逆即可

三、 关键代码

pthread_mutex_t m[6]; //定义5把互斥锁

void *tfn(void *arg)

{

int thread_num, left, right;//thread_num：哲学家编号 left：左手 right：右手

srand(time(NULL));

thread_num = (int)arg; //为6位哲学家分配筷子 (抽象6只筷子，形成一个闭环)

if (thread_num == 6) //第6位哲学家和其他的哲学家不一样，他是先抢右边的筷子

{

left = 0;//把0（右边的筷子）赋值给左手变量，他就会先抢右边的筷子了

right = thread_num;

}

else

{ //分配好筷子，让左手拿左边的筷子，右手拿右边的筷子，这里的哲学家都是先抢左边的筷子，再抢右边的筷子的

}

while (1)

{

pthread_mutex_lock(&m[left]);//先抢左边的筷子

if (pthread_mutex_trylock(&m[right]) == 0)//尝试去抢右边的筷子

{

left = thread_num;

right =thread_num+1;

printf("t%c is eating n", 'A'+thread_num);

pthread_mutex_unlock(&m[right]);//放下右边筷子

}

}

pthread_mutex_unlock(&m[left]);//放下左边筷子

sleep(rand() % 6);

return NULL;

}

四、 实验结果

实验10：系统调用实验 —— 添加系统调用

一、 实验情景描述

该实验实现一个简单系统调用的添加，功能只是实现打印一些信息，而且能证明这个进程进入过内核态。

系统调用的编号名字：__NR_print_info；内核中系统调用的实现程序的名字：sys_print_info。

二、 实验原理

1.添加系统调用号：系统调用号在文件include/asm/unistd.h中定义，因此需要在这里添加新系统调用号：__NR_print_info。

#define __NR_io_submit

#define __NR_io_cancel

248

249

#define __NR_alloc_hugepages 250

#define __NR_free_hugepages 251

#define __NR_exit_group 252

#define __NR_lookup_dcookie 253

#define __NR_set_tid_address 258

#define __NR_print_info 259 /* added */

2.添加系统调用号之后，系统才能根据这个号作为索引去找syscall_table中的相应表项。

之后在系统调用表中添加相应的表项。系统调用表在arch/i386/kernel/entry.S中定义。系统调用处理程序（system_call）会根据eax中的索引到系统调用表（sys_call_table）中去寻找相应的表项。

.long SYMBOL_NAME(sys_ni_syscall)

.long SYMBOL_NAME(sys_ni_syscall) /* sys_epoll_wait */

.long SYMBOL_NAME(sys_ni_syscall)

.long SYMBOL_NAME(sys_set_tid_address)

.long SYMBOL_NAME(sys_print_info)

.rept NR_syscalls-(.-sys_call_table)/4

.long SYMBOL_NAME(sys_ni_syscall)

/* added ! */

.endr

3. 在kernel/sys.c文件中添加如下代码：

asmlinkage int sys_print_info(int testflag)

{

printk(KERN_EMERG " It's my syscall function!n");

return 0;

}

在这段代码中，使用到printk()函数。之前在驱动编写部分也使用过这个函数。printk()用来在终端或到系统日志中打印信息。除了第一个参数表示打印的权限级别外，printk()和printf()在其他参数的使用上基本上是一致的。这段代码实现的系统调用在内核态打印了一条信息并返回0。

4. 改动完全之后重新编译内核，并用新内核启动。为了防止新编译的内核覆盖原来的内核，可以按照下面所示改一下内核版本号。

VERSION=2

PATCHLEVEL=4

SUBLEVEL=20

EXTRAVERSION=-8 （假设原内核版本是2.4.20-8）

5. 编译完成之后可以用新内核启动。

6. 之后编写一个测试程序test_print_info.c，用来测试新的系统调用。测试程序如下：

7.编译测试程序并运行。如果系统调用成功则会在终端打印syscall succeed!。同时由于内核态中的printk()也会打印：It's my syscall function!。

四、 实验结果

实验11：终端编写实验 —— 模拟终端shell

一、 实验情景描述

实现一个模拟shell，实现如下功能

1）提示符个人标识 2）内部命令bye用来退出

3）内部命令run用来执行一个文件 4）调用/bin下的命令

二、 实验原理

Shell是指“提供使用者使用界面”的软件。它接收用户命令，然后调用相应的应用程序。同时更高级的Shell又是一种程序设计语言，它能够交互式解释和执行用户输入的命令或者自动地解释和执行预先设定好的一连串的命令。Shell是操作系统系统的用户界面，提供了用户与内核进行交互操作的接口，负责接收用户输入的命令并把其送入内核去执行。Shell介于操作系统内核与用户之间，负责解释命令行。因此实际上Shell是一个命令解释器，负责解释输入的命令。

三、 关键代码

while(1)

{

printf("1707020401$");

scanf("%s",command);

fflush(stdin);

if(strcmp(command,"run")==0)

{ run_(); }

else if(strcmp(command,"bye")==0)

{ bye_(); }

else if((strcmp(command,"print")==0))

{ print_(); }

else if(strcmp(command,"show")==0)

{ show_(); }

} return 0; }

void show_()

{ system("ls /root"); }

void bye_()

{ exit(0); }

void print_()

{ printf("1707020401guolinn"); }

void run_()

{ system("./ju"); }

四、 实验结果

实验12：内存模式实验 —— 实现malloc和free的内存模拟过程

一、实验情景描述

实现malloc和free的内存模拟过程。在malloc（）中使用首次适配方法来进行存储分配。当使用free（）释放内存时，会对相邻的存储空间合并。

为了实现虚拟存储，可以编写两个存储管理器：一个管理用户程序的虚拟地址空间，另外一个实现malloc（）和free（）。其中虚拟内存管理器可以为应用程序提供大量的内存，而内核一般会提供malloc（）。

二、 实验原理

malloc（）和free（）功能相对应：malloc用来动态申请内存空间，即从一大块内存中分配除所需要的空间，而free用来释放malloc申请的空间。分配时要留出一部分malloc（）不能分配的内核空间，这部分空间供操作系统内核使用。malloc()从堆里面获得空间，其函数返回的指针是指向堆里面的一块内存。当操作系统收到程序的申请时，就会遍历一个记录空闲内存地址的链表，然后就寻找第一个空间大于所申请空间的堆结点，并将该结点从空闲结点链表中删除，同时将该结点的空间分配给程序。如果malloc（）用完内存之后，它将会继续向内核申请内存。

三、 关键代码

typedef struct _malloc

{ size_t size;

/* Turbo C编译器 */

/*4 bytes */

/*4 bytes */

/*4 bytes total */

struct _malloc *next;

unsigned magic : 15;

unsigned used : 1;

} malloc_t;

/* total 12 bytes */

static char *g_heap_bot, *g_kbrk, *g_heap_top;

void *kmalloc(size_t size)

{ unsigned total_size;

malloc_t *m, *n;

int delta;

if(size == 0)

return NULL;

total_size = size + sizeof(malloc_t); //42 bytes + 12 blks =54

m = (malloc_t *)g_heap_bot;

if(m != NULL)

{ if(m->magic != MALLOC_MAGIC)

{ printf("*** kernel heap is corrupt in kmalloc()n");

return NULL;

}

for(; m->next != NULL; m = m->next)

{ if(m->used)

continue;

if(size == m->size)

m->used = 1;

else

{ if(total_size > m->size)

continue;

n = (malloc_t *)((char *)m + total_size);

n->size = m->size - total_size;

n->next = m->next;

n->magic = MALLOC_MAGIC;

n->used = 0;

m->size = size;

m->next = n;

m->used = 1;

} return (char *)m + sizeof(malloc_t);

}

}

delta = total_size;

n = kbrk(&delta);

if(n == NULL)

return NULL;

if(m != NULL)

m->next = n;

n->size = size;

n->magic = MALLOC_MAGIC;

n->used = 1;

if((int)total_size == delta)

n->next = NULL;

else

{ m = (malloc_t *)((char *)n + total_size);

m->size = delta - total_size - sizeof(malloc_t);

m->next = NULL;

m->magic = MALLOC_MAGIC;

m->used = 0;

n->next = m;

}

return (char *)n + sizeof(malloc_t);

}

void kfree(void *blk)

{

malloc_t *m, *n;

m = (malloc_t *)((char *)blk - sizeof(malloc_t));

if(m->magic != MALLOC_MAGIC)

{

printf("*** attempt to kfree() block at 0x%p "

"with bad magic valuen", blk);

return;

}

n = (malloc_t *)g_heap_bot;

if(n->magic != MALLOC_MAGIC)

{

printf("*** kernel heap is corrupt in kfree()n");

return;

}

for(; n != NULL; n = n->next)

{

if(n == m)

break;

}

if(n == NULL)

{

printf("*** attempt to kfree() block at 0x%p "

"that is not in the heapn", blk);

return;

}

m->used = 0;

for(m = (malloc_t *)g_heap_bot; m != NULL; m = m->next)

{

while(!m->used && m->next != NULL && !m->next->used)

{

m->size += sizeof(malloc_t) + m->next->size;

m->next = m->next->next;

}

}

}

四、 实验结果