本科生实验报告
实验课程 计算机网络与TCP/IP协议体系(2)
学院名称 信息科学与技术学院
专业名称 通信工程
学生姓名 杜立华
学生学号 201313070112
指导教师 刘飚
实验地点 6B603
实验成绩
二〇 一五 年 二 月 —— 二〇 一五 年 六 月
实验一 Linux内核通用链表的使用
实验目的
学习Linux内核通用链表的设计原理,熟练掌握Linux内核通用链表的使用。
实验内容
1、掌握Linux通用链表的创建
2、掌握通用链表添加元素、删除元素和遍历链表的方法
3、掌握通用链表的查找方法
实验要求
·待创建的链表头变量名为user_queue。
·作为链表的宿主节点类型定义如下:
struct user {
int id; /* user id */
struct list_head list;
};
·针对上述user_queue链表,要求以队列方式向其中依次添加10个类型为struct user的宿主节点,并要求这10个宿主节点的id依次为1—10
·依次遍历输出这10个宿主节点的id
·从链表中删除首个宿主节点,然后依次遍历该队列并输出余下各宿主节点的id
·在struct user结构体中增加一个username字段,用于存储该用户名字,重新以队列方式向其中依次添加10个类型为struct user的宿主节点,并要求这10个宿主节点的id依次为1—10
·在链表中搜索id值为5的节点,并输出该节点username值
实现原理
Linux的内核源文件list.h提供了所有的链表定义,以及各类链表的操作接口和实现。其中创建链表的方法如下:
LIST_HEAD(my_list);
源文件list.h中定义了如下若干接口,用于对通用链表进行各种操作:
·在指定的head后插入新节点,常用于堆栈数据结构的实现
// @newsk:即将添加的新链表节点
// @head:在此节点后添加
list_add(struct list_head *new, struct list_head *head);
·在指定的head前插入新节点,常用于队列数据结构的实现
// @newsk:即将添加的新链表节点
// @head:在此节点前添加
list_add_tail(struct list_head *new, struct list_head *head);
·从链表中删除一个指定节点
// @entry:要从链表中删除的节点
list_del(struct list_head *entry);
·根据当前链表节点指针ptr获得宿主节点指针
// @ptr:struct list_head类型的指针
// @type:链表节点所在的宿主节点的类型
// @member:嵌入宿主的链表节点的变量名
list_entry(ptr, type, member);
·遍历链表
// @pos:遍历链表时用于指示正在遍历的链表节点的指针
// @head:链表头
list_for_each(pos, head);
实现代码和运行结果
请打印本实验的程序代码和程序运行截图,并作为附件附在本实验报告后。
#include <stdio.h>
#include <malloc.h>
#include "list.h"
struct user
{
int id;
struct list_head list;
};
int main(void)
{
struct user *p;
LIST_HEAD(user_queue);
for (int i = 0; i < 10; i++)
{
p = (struct user *)malloc(sizeof(struct user));
p->id = i;
list_add_tail(&p->list, &user_queue);
}
struct list_head *q;
list_for_each(q, &user_queue)
{
p = list_entry(q, struct user, list);
printf("%d\n", p->id);
}
return 0;
}
#include <stdio.h>
#include <malloc.h>
#include "list.h"
struct user
{
char username[20];
int id;
struct list_head list;
};
int main(void)
{
struct user *p;
LIST_HEAD(head);
for (int i; i < 10; i++)
{
p = (struct user *)malloc(sizeof(struct user));
p->id = i + 1;
printf("user %2d, Please input username: ", i+1);
scanf("%s", p->username);
list_add_tail(&(p->list), &head);
}
struct list_head *tmp;
list_for_each(tmp, &head)
{
p = list_entry(tmp, struct user, list);
printf("%d\t%s\n", p->id, p->username);
}
list_for_each(tmp, &head)
{
p = list_entry(tmp, struct user, list);
if (p->id == 5)
printf("%s\n", p->username);
}
return 0;
}
实验二 Linux内核通用哈希链表的使用
实验目的
学习Linux内核通用哈希链表的设计原理,熟练掌握Linux内核通用哈希链表的使用。
实验内容
1、掌握Linux通用哈希链表的创建。
2、掌握通用哈希链表添加元素、查找元素的方法。
实验要求
1、待创建的哈希链表头数组为struct hlist_head user_hash[16],要求对该哈希链表宿主节点的name成员值进行散列,并将散列值与15进行与运算作为哈希链表宿主元素的哈希值。
2、对该哈希表的所有表头元素进行初始化,初始化操作如下,其中index的变化范围为0~15。
INIT_HLIST_HEAD (&user_hash[index]);
3、作为哈希链表元素的的宿主节点类型定义如下:
struct usermap {
struct hlist_node hlist;
unsigned char name[8];
};
4、针对上述user_hash哈希链表,要求向其中添加3个类型为struct usermap的宿主节点,并要求这3个宿主节点的name成员分别为”smith”, ”john”, ”bob”, 如下图所示:
struct hlist_head user_hash[16]5、向哈希表user_hash中添加2个新宿主元素, 其中一个宿主元素的name成员为”john”,另外一个宿主元素的name成员为”lisa”。要求若新宿主元素的name成员已经存在,则提示已经存在该用户,不再向哈希链表中加入该已经存在的宿主节点,否则向哈希链表中添加该新宿主元素。
6、遍历整个哈希表,输出所有表中已存在的宿主节点元素的name。
实现原理
Linux的内核源文件list.h提供了哈希链表的各种操作接口和实现。其中创建具有16个元素的哈希链表的方法如下:
struct hlist_head user_hash[16];
在上述user_hash数组的16个元素中存放的哈希表头元素定义如下:
struct hlist_head {
struct hlist_node *first;
};
哈希链表节点元素定义如下:
struct hlist_node{
struct hlist_node *next, **pprev;
};
本实验对哈希链表宿主节点的name值进行散列的算法如下:
unsigned int BKDRHash(unsigned char *str);
{
unsigned int seed = 131;
unsigned int hash = 0;
while(*str) {
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}
于是,本实验对一个字符串name求最终哈希值hash的方法如下:
unsigned int hash = BKDRHash(name) & 15;
内核源文件list.h定义了以下若干接口,用于对哈希链表进行各种操作:
(1)在指定的哈希链表头h所指向的链表头插入新节点
// @n:要添加的新哈希链表节点
// @h:在此哈希链表头节点后添加
hlist_add_head(struct hlist_node *n, struct hlist_head *h);
(2)根据当前哈希链表节点指针ptr获得好像链表宿主节点指针
// @ptr:struct hlist_node类型的指针
// @type:哈希链表节点所在的宿主节点的类型
// @member:嵌入宿主的哈希链表节点的变量名
hlist_entry(ptr, type, member);
(3)遍历哈希链表中某个key值所对应的链表
// @tpos:哈希链表宿主节点指针
// @pos:哈希链表节点指针
// @head:哈希链表中某key所对应的链表的头指针
// @member:嵌在哈希链表宿主节点中的哈希链表节点的变量名
hlist_for_each_entry(tpos, pos, head, member);
实现代码和运行结果
请打印本实验的程序代码和程序运行截图,并作为附件附在本实验报告后。
#include <stdio.h>
#include <string.h>
#include "list.h"
struct usermap {
struct hlist_node hlist;
unsigned char name[8];
};
void hlist_print(struct hlist_head *hl_head);
unsigned int BKDRHash(unsigned char *str);
unsigned char hash_add(struct hlist_node *hl_node, struct hlist_head *hl_head);
int main(void)
{
struct hlist_head user_hash[16];
for (int i = 0; i < 16; i++)
INIT_HLIST_HEAD(&user_hash[i]);
struct usermap user[3];
strcpy(user[0].name, "smith");
strcpy(user[1].name, "john");
strcpy(user[2].name, "bob");
for (int i = 0; i < 3; i++)
hlist_add_head(&(user[i].hlist), &user_hash[BKDRHash(user[i].name) & 15]);
hlist_print(user_hash);
struct usermap new_user[2];
strcpy(new_user[0].name, "john");
strcpy(new_user[1].name, "lisa");
for (int i = 0; i < 2; i++)
if (!hash_add(&(new_user[i].hlist), &user_hash[BKDRHash(new_user[i].name) & 15]))
printf("用户%s重复,添加失败!\n", new_user[i].name);
hlist_print(user_hash);
return 0;
}
void hlist_print(struct hlist_head *hl_head)
{
struct usermap *puser;
struct hlist_node *phnode;
for (int i = 0; i < 16; i++)
{
printf("%d\t", i);
hlist_for_each_entry(puser, phnode, &hl_head[i], hlist)
printf("%s\t", puser->name);
printf("\n");
}
}
unsigned int BKDRHash(unsigned char *str)
{
unsigned int seed = 131;
unsigned int hash = 0;
while(*str) {
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}
unsigned char hash_add(struct hlist_node *hl_node, struct hlist_head *hl_head)
{
char *name = hlist_entry(hl_node, struct usermap, hlist)->name;
struct usermap *puser;
struct hlist_node *pnode;
hlist_for_each_entry(puser, pnode, hl_head, hlist)
{
if (!strcmp(puser->name, name))
return 0;
}
hlist_add_head(hl_node, hl_head);
return 1;
}
实验三 Linux多线程程序设计
实验目的
学习Linux下多线程程序的编写,掌握IP报文分段重组模拟程序的整体框架。
实验内容
完成Linux下多线程的程序编写,利用线程同步的方法,完成多线程访问一个由Linux内核通用链表所实现的消息队列。
实验要求
7、待创建的消息队列名为msg_queue。
8、作为消息队列的消息宿主节点类型定义如下:
struct msg_buff {
int id;
struct list_head list;
};
9、针对上述msg_queue队列,要求创建两个线程1和线程2,其中线程1向该队列尾逐步添加10个类型为struct msg_buff的宿主节点,并要求者10个宿主节点的id分别为1—10。另外,在线程1向该队列添加宿主节点的同时,要求线程2从该队列头部依次取出下一个宿主节点,并输出该节点的id值。
实现原理
线程模型
本实验要求创建两个线程,分别为由main函数代表的线程1和由run函数代表的线程2。其中线程1模拟从网络持续接收消息,并将收到的消息放入消息队列中;线程2模拟网络协议处理程序,当消息队列不空时,持续从消息队列头取出下一个收到的消息并进行处理,如下图所示:
线程互斥与同步方法
由于消息队列是一临界资源,线程1和线程2将竞争访问该队列,因此必须对线程1和线程2进行互斥与同步管理。即当线程1正在向消息队列尾放入消息时,线程2必须等待线程1操作完毕并退出对临界资源的操作后,方可以从该队列头部中取出下一个消息进行处理,反之亦然。此外,当消息队列为空时,线程2将进入休眠状态,当消息队列不空时,线程2被线程1唤醒后继续处理。下面给出实现线程1和线程2互斥与同步的部分关键代码。
/* 定义访问临界资源的互斥变量 */
pthread_mutex_t mqlock = PTHREAD_MUTEX_INITIALIZER;
/* 定义条件变量 */
pthread_cond_t mqlock_ready = PTHREAD_COND_INITIALIZER;
/ * 线程1 */
int main()
{
struct msg_buff *msg;
for(;;) {
...
pthread_mutex_lock(&mqlock); /* 加锁互斥量 */
list_add_tail(msg->list, &msg_queue)); /* 消息入队列尾 */
pthread_mutex_unlock(&mqlock); /* 解锁互斥量 */
/* 通知线程2条件发生改变 */
pthread_cond_signal(&mqlock_ready);
...
}
...
return 0;
}
/ * 线程2 */
void *run(void *arg)
{
struct msg_buff *msg;
for(;;) {
pthread_mutex_lock(&mqlock); /* 加锁互斥量 */
while(list_empty(&msg_queue))
/* 消息队列空,休眠等待条件改变 */
pthread_cond_wait(&mqlock_ready, &mqlock);
/* 消息队列不空,从队列中取下一消息 */
msg = getnextmsg(msg_queue.next);
/* 解锁互斥量 */
pthread_mutex_unlock(&mqlock);
/* 处理此消息 */
handle_msg(msg);
}
}
实现代码和运行结果
请在本实验所提供的代码msg.c的基础上,完成其中的add_msg和getnextmsg函数的实现;打印本实验的程序代码和程序运行截图,并作为附件附在本实验报告后面。
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include "list.h"
#define PAUSE 3000
void *run(void *); /* 消息处理线程 */
void add_msg(int);
struct msg_buff *getnextmsg(struct list_head *);
void handle_msg(struct msg_buff *);
struct msg_buff {
int id;
struct list_head list;
};
/* 线程互斥量 */
pthread_mutex_t mqlock = PTHREAD_MUTEX_INITIALIZER;
/* 条件变量 */
pthread_cond_t mqlock_ready = PTHREAD_COND_INITIALIZER;
pthread_t tid; /* 消息处理线程id */
LIST_HEAD(msg_queue); /* 消息队列 */
int main()
{
int err = 0;
err = pthread_create(&tid, NULL, run, NULL);/* 创建并启动消息处理线程 */
for(int i = 0; i < 10; i++){
add_msg(i);/* 向消息队列添加消息 */
sleep(1);
}
return 0;
}
void add_msg(int i)
{
// 完成向队列添加消息代码
struct msg_buff *new_msg = (struct msg_buff *)malloc(sizeof(struct msg_buff));
new_msg->id = i;
pthread_mutex_lock(&mqlock);
list_add_tail(&new_msg->list, &msg_queue);
pthread_mutex_unlock(&mqlock);
pthread_cond_signal(&mqlock_ready);
}
void *run(void *arg)
{
struct msg_buff *msg;
for (;;) {
// 通过getnextmsg函数从队列中取下一消息
pthread_mutex_lock(&mqlock);
while (list_empty(&msg_queue))
pthread_cond_wait(&mqlock_ready, &mqlock);
msg = getnextmsg(&msg_queue);
pthread_mutex_unlock(&mqlock);
handle_msg(msg); /* 处理消息 */
free(msg);
}
}
struct msg_buff *getnextmsg(struct list_head *q)
{
struct msg_buff *msg;
// 完成从队列中取下一消息代码
msg = list_first_entry(q, struct msg_buff, list);
list_del(&msg->list);
return msg;
}
void handle_msg(struct msg_buff *m)
{
printf("m->id=%d\n", m->id); /* 处理此分组 */
}