Linux程序设计报告.doc

Linux程序设计报告

43
2020年4月19日
文档仅供参考

Linux程序设计课程设计

Linux程序设计课程组

长春工业大学
-12-24

课程设计任务书
课程设计题目：读者写者问题的设计、实现及性能分析
起止日期： .12.25- .12.29
设计地点：计算机科学与工程学院机房
任务：
1. Linux环境下分别设计并实现读者写者问题的读者优先算法、写者优先算法和无优先算法，针对测试数据得出每种算法下读者线程和写者线程的开始操作时刻和结束操作时刻；
2. 计算每个线程的等待时间、周转时间、总的等待时间、总的周转时间、读者总的等待时间、读者总的周转时间、写者总的等待时间、写者总的周转时间、平均等待时间、平均周转时间；
3. 使用适当的可视化方法（例如甘特图）对计算结果进行可视化；
4. 比较三种算法的性能。
日程：
本次设计共一周时间，参考日程安排如下：
第1天：读者优先算法设计、实现与测试；
第2天：写者优先算法设计、实现与测试；
第3天：无优先算法设计、实现与测试；
第4天：测试结果可视化及算法性能比较；
第5天：答辩。
报告：
仅写自己完成的设计成果，包括：
1． 充分注释的源代码（未写代码者略去）
2． 测试结果
3． 结果可视化
4． 性能比较
5． 参考文献
6． 心得
指导教师：
150408 焦素云 150409 王俊华

目录
第1章 设计要求 1
2.1设计目的 1
2.2设计要求 1
第2章 测试数据设计 2
第3章 算法实现 3
第4章 算法结果 3
第5章 结果可视化 4
第6章 性能分析 4
参考文献 4
心得 4

第1章 设计要求
2.1设计目的
理解临界区和进程互斥的概念，掌握用信号量和PV操作实现进程互斥的方法。
2.2设计要求
在linux环境下编写应用程序，该程序运行时能创立N个线程，其中既有读者线程又有写者线程，它们按照事先设计好的测试数据进行读写操作。
读者/写者问题描述如下：
有一个被许多进程共享的数据区，这个数据区能够是一个文件，或者主存的一块空间，甚至能够是一组处理器寄存器。有一些只读取这个数据区的线程（reader）和一些只往数据区中写数据的线程（writer）。以下假设共享数据区是文件。这些读者和写者对数据区的操作必须满足以下条件：读—读允许；读—写互斥；写—写互斥。这些条件具体来说就是：
（1）任意多的读线程能够同时读这个文件；
（2）一次只允许一个写线程往文件中写；
（3）如果一个写线程正在往文件中写，禁止任何读线程或写线程访问文件；
（4）写线程执行写操作前，应让已有的写者或读者全部退出。这说明当有读者在读文件时不允许写者写文件。
对于读者-写者问题，有三种解决方法：
1、读者优先
除了上述四个规则外，还增加读者优先的规定，当有读者在读文件时，对随后到达的读者和写者，要首先满足读者，阻塞写者。这说明只要有一个读者活跃，那么随后而来的读者都将被允许访问文件，从而导致写者长时间等待，甚至有可能出现写者被饿死的情况。
2、写者优先
除了上述四个规则外，还增加写者优先的规定，即当有读者和写者同时等待时，首先满足写者。当一个写者声明想写文件时，不允许新的读者再访问文件。
3、无优先
除了上述四个规则外，不再规定读写的优先权，谁先等待谁就先使用文件。
第2章 测试数据设计
表1 测试数据
线程名称
申请时刻
持续使用时间
"r1"
0
15
"r2"
1
15
"w1"
3
3
"r3"
4
2
"w2"
5
6
"w3"
6
10
"r4"
7
8
"r5"
9
2
"w4"
10
18
"w5"
12
2
为了验证算法的正确性，需要设计测试数据，并对测试数据进行分析，总结出在该组测试数据下，程序应该得到什么结果，然后运行程序，将程序运行结果与分析结果相比较，如果二者一致，则可认为程序是正确的。
作者设计的测试数据如表1所示，包括10个线程，其中有5个读者线程r1~r5，另外5个是写者线程w1~w5。读者线程r1在时刻0提出读请求，如果请求得到允许，r1将用15秒的时间读文件；写者线程w3在时刻6提出写请求，如果请求得到允许，w3将用10秒的时间写文件。从表中能够看出，10个线程提出请求的次序是：r1,r2,w1,r3,w2,w3,r4,r5,w4,w5。
（1）读者优先算法
线程实际读写文件顺序为：r1,r2,r3,r4,r5,w1,w2,w3,w4,w5。执行情况见表2。
表2 线程的运行状况
线程名称
申请时刻
持续时间
开始操作时刻
结束操作时刻
"r1"
0
15
0
15
"r2"
1
15
1
16
"r3"
4
2
4
6
"r4"
7
8
7
15
"r5"
9
2
9
11
"w1"
3
3
16
19
"w2"
5
6
19
25
"w3"
6
10
25
35
"w4"
10
18
35
53
"w5"
12
2
53
55
（2）写者优先算法
线程实际读写文件顺序为：r1,r2,w1,w2,w3,w4,w5,r3,r4,r5。执行情况见表3。
表3 线程的运行状况
线程名称
申请时刻
持续时间
开始操作时刻
结束操作时刻
"r1"
0
15
0
15
"r2"
1
15
1
16
"w1"
3
3
16
19
"w2"
5
6
19
25
"w3"
6
10
25
35
"w4"
10
18
35
53
"w5"
12
2
53
55
"r3"
4
2
55
57
"r4"
7
8
55
63
"r5"
9
2
55
57

（3）无优先算法
线程实际读写文件顺序为：r1,r2,w1,r3,w2,w3,r4,r5,w4,w5。执行情况见表4。
表4 线程的运行状况
线程名称
申请时刻
持续时间
开始操作时刻
结束操作时刻
"r1"
0
15
0
15
"r2"
1
15
1
16
"w1"
3
3
16
19
"r3"
4
2
19
21
"w2"
5
6
21
27
"w3"
6
10
27
37
"r4"
7
8
37
45
"r5"
9
2
37
39
"w4"
10
18
45
63
"w5"
12
2
63
65

第3章 算法实现
读者优先算法：
#include <time.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#include <string.h>
#include <fcntl.h>

#define MAX_THREAD 10
#define SNL 8

typedef struct{
char tn[3]; //name of thread
unsigned int rm; //the moment when this thread request to access data.
unsigned int pt; //duration of operation
unsigned int i; //same to rm
unsigned int b; //instance at which this thread begin to operate data
unsigned int e; //ending instance
}TEST_INFO;

//TEST_INFO test_data[MAX_THREAD];

typedef struct {
char sn[SNL+1]; //student number
TEST_INFO ti[MAX_THREAD]; //test item
}TI; //test_item_for_student
//TI test_items[STUDENTS];
TI test_item={{" 2566"},
{{"w1", 4,7},{"r1",11,14},{"r2",1,5},{"w2",8,11},{"w3",15,2},{"r3",5,8},
{"r4",12,15},{"w4",5,2},{"r5",9,12},{"r6",15,3}}
};
char r_seq[MAX_THREAD][3];
char o_seq[MAX_THREAD][3];
int sr=0;
int so=0;

int rc=0; //count how many readers are reading
pthread_mutex_t cs_d; //guarentee mutually access data
pthread_mutex_t cs_rc; //guarentee mutually access "rc"
pthread_mutex_t cs_sr; //guarentee mutually access "sr"
pthread_mutex_t cs_so; //guarentee mutually access "sr"
time_t base; //the moment when function main begin

/*
void print_answer(){
int i;

printf("%s\n",test_item.sn);
printf("name r_m p_t i_t b_t e_t\n");
for(i=0;i<MAX_THREAD;i++){
printf("%4s%4d%4d%8d%8d%8d\n",(test_item.ti)[i].tn,(test_item.ti)[i].rm,(test_item).ti[i].pt,(test_item.ti)[i].i,(test_item.ti)[i].b,(test_item.ti)[i].e);
}

printf("r_seq:");
for(i=0;i<MAX_THREAD;i++){
printf("%4s",r_seq[i]);
}
printf("\n");
printf("o_seq:");
for(i=0;i<MAX_THREAD;i++){
printf("%4s",o_seq[i]);
}
printf("\n");
}
*/

void save_answer(FILE *f){
int i;

fprintf(f,"\t%s_answer.txt\n\tr/w problem:read first\n\n",test_item.sn);
fprintf(f,"name r_m p_t i_t b_t e_t\n");
for(i=0;i<MAX_THREAD;i++){
fprintf(f,"%4s%4d%4d%8d%8d%8d\n",(test_item.ti)[i].tn,(test_item.ti)[i].rm,(test_item).ti[i].pt,(test_item.ti)[i].i,(test_item.ti)[i].b,(test_item.ti)[i].e);
}

fprintf(f,"\n");
fprintf(f,"r_seq:");
for(i=0;i<MAX_THREAD;i++){
fprintf(f,"%4s",r_seq[i]);
}
fprintf(f,"\n");
fprintf(f,"o_seq:");
for(i=0;i<MAX_THREAD;i++){
fprintf(f,"%4s",o_seq[i]);
}
fprintf(f,"\n");
}

void *r(void *td){
struct timeval t;
time_t rl=base;

sleep(((TEST_INFO *)td)->rm);
gettimeofday(&t,NULL);
((TEST_INFO *)td)->i=difftime(t.tv_sec,rl);
pthread_mutex_lock(&cs_sr);
strcpy(r_seq[sr++],((TEST_INFO *)td)->tn);
pthread_mutex_unlock(&cs_sr);

pthread_mutex_lock(&cs_rc);
rc++;
if(rc==1)pthread_mutex_lock(&cs_d);
pthread_mutex_unlock(&cs_rc);

gettimeofday(&t,NULL);
((TEST_INFO *)td)->b=difftime(t.tv_sec,rl);
pthread_mutex_lock(&cs_so);
strcpy(o_seq[so++],((TEST_INFO *)td)->tn);
pthread_mutex_unlock(&cs_so);

sleep(((TEST_INFO *)td)->pt);
gettimeofday(&t,NULL);
((TEST_INFO *)td)->e=difftime(t.tv_sec,rl);

pthread_mutex_lock(&cs_rc);
rc--;
if(rc==0)pthread_mutex_unlock(&cs_d);
pthread_mutex_unlock(&cs_rc);
return 0;
}

void *w(void *td){
struct timeval t;
time_t wl=base;
sleep(((TEST_INFO *)td)->rm);
gettimeofday(&t,NULL);
((TEST_INFO *)td)->i=difftime(t.tv_sec,wl);
pthread_mutex_lock(&cs_sr);
strcpy(r_seq[sr++],((TEST_INFO *)td)->tn);
pthread_mutex_unlock(&cs_sr);

pthread_mutex_lock(&cs_d);
gettimeofday(&t,NULL);
((TEST_INFO *)td)->b=difftime(t.tv_sec,wl);
pthread_mutex_lock(&cs_so);
strcpy(o_seq[so++],((TEST_INFO *)td)->tn);
pthread_mutex_unlock(&cs_so);

sleep(((TEST_INFO *)td)->pt);
gettimeofday(&t,NULL);
((TEST_INFO *)td)->e=difftime(t.tv_sec,wl);

pthread_mutex_unlock(&cs_d);
return 0;
}

void create_exam(){
int i=0;
pthread_t ht[MAX_THREAD];
pthread_mutex_init(&cs_d,NULL);
pthread_mutex_init(&cs_rc,NULL);
pthread_mutex_init(&cs_sr,NULL);
pthread_mutex_init(&cs_so,NULL);
struct timeval t;

gettimeofday(&t,NULL);
base=t.tv_sec;

for(i=0;i<MAX_THREAD;i++){
if((test_item.ti)[i].tn[0]=='r'){
pthread_create(&ht[i],NULL,r,&((test_item.ti)[i]));
}
else if((test_item.ti)[i].tn[0]=='w'){
pthread_create(&ht[i],NULL,w,&((test_item.ti)[i]));
}
}
for(i=0;i<MAX_THREAD;i++){
pthread_join(ht[i],NULL);
}
pthread_mutex_destroy(&cs_d);
pthread_mutex_destroy(&cs_rc);
pthread_mutex_destroy(&cs_sr);
pthread_mutex_destroy(&cs_so);
}

int main(int argc,char *argv[]){
int i=0;
int si,pos;
int fd;
FILE *fa;
char file_name[100];

create_exam();

sprintf(file_name,"%s_answer.txt",test_item.sn);
if((fa=fopen(file_name,"w"))==NULL){
printf("Error openning answer file:%s\n",file_name);
exit(3);
}
save_answer(fa);
exit(0);
}

1. 写优先算法
#include <time.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#include <string.h>
#include <fcntl.h>
#define MAX_THREAD 10
#define SNL 8

typedef struct{
char tn[3]; //name of thread
unsigned int rm; //the moment when this thread request to access data.
unsigned int pt; //duration of operation
unsigned int i; //same to rm
unsigned int b; //instance at which this thread begin to operate data
unsigned int e; //ending instance
}TEST_INFO;

//TEST_INFO test_data[MAX_THREAD];

typedef struct {
char sn[100]; //student number
TEST_INFO ti[MAX_THREAD]; //test item
}TI; //test_item_for_student
//TI test_items[STUDENTS];
TI test_item={{" 2566"},
{{"w1", 4,7},{"r1",11,14},{"r2",1,5},{"w2",8,11},{"w3",15,2},{"r3",5,8},
{"r4",12,15},{"w4",5,2},{"r5",9,12},{"r6",15,3}}
};
char r_seq[MAX_THREAD][3];
char o_seq[MAX_THREAD][3];
int sr=0;
int so=0;

int rc=0; //count how many readers are reading
pthread_mutex_t cs_d; //guarentee mutually access data
pthread_mutex_t cs_rc; //guarentee mutually access "rc"
pthread_mutex_t cs_sr; //guarentee mutually access "sr"
pthread_mutex_t cs_so; //guarentee mutually access "sr"
time_t base; //the moment when function main begin

/*
void print_answer(){
int i;

printf("%s\n",test_item.sn);
printf("name r_m p_t i_t b_t e_t\n");
for(i=0;i<MAX_THREAD;i++){
printf("%4s%4d%4d%8d%8d%8d\n",(test_item.ti)[i].tn,(test_item.ti)[i].rm,(test_item).ti[i].pt,(test_item.ti)[i].i,(test_item.ti)[i].b,(test_item.ti)[i].e);
}

printf("r_seq:");
for(i=0;i<MAX_THREAD;i++){
printf("%4s",r_seq[i]);
}
printf("\n");
printf("o_seq:");
for(i=0;i<MAX_THREAD;i++){
printf("%4s",o_seq[i]);
}
printf("\n");
}
*/

void save_answer(FILE *f){ //save the result
int i;

fprintf(f,"\t%s_answer.txt\n\tr/w problem:read first\n\n",test_item.sn);
fprintf(f,"name r_m p_t i_t b_t e_t\n");
for(i=0;i<MAX_THREAD;i++){
fprintf(f,"%4s%4d%4d%8d%8d%8d\n",(test_item.ti)[i].tn,(test_item.ti)[i].rm,(test_item).ti[i].pt,(test_item.ti)[i].i,(test_item.ti)[i].b,(test_item.ti)[i].e);
}

fprintf(f,"\n");
fprintf(f,"r_seq:");
for(i=0;i<MAX_THREAD;i++){
fprintf(f,"%4s",r_seq[i]);
}
fprintf(f,"\n");
fprintf(f,"o_seq:");
for(i=0;i<MAX_THREAD;i++){
fprintf(f,"%4s",o_seq[i]);
}
fprintf(f,"\n");
}

void *w(void *td){
struct timeval t;//结构体 精确到秒
time_t rl=base; //返回时间 main函数开始的时间

sleep(((TEST_INFO *)td)->rm);//休眠读线程进入的时间长
gettimeofday(&t,NULL);//获得当前的时间
((TEST_INFO *)td)->i=difftime(t.tv_sec,rl);//将系统时间与main主函数执行的时间差赋值给i变量（读线程进入的时间）
pthread_mutex_lock(&cs_sr);//建立互斥锁
strcpy(r_seq[sr++],((TEST_INFO *)td)->tn);
pthread_mutex_unlock(&cs_sr);//解除互斥锁

pthread_mutex_lock(&cs_rc);
rc++;
if(rc==1)pthread_mutex_lock(&cs_d);
pthread_mutex_unlock(&cs_rc);

gettimeofday(&t,NULL);//获得当前的时间
((TEST_INFO *)td)->b=difftime(t.tv_sec,rl);//将系统时间与main主函数执行的时间差赋值给b变量（读线程开始的时间）
pthread_mutex_lock(&cs_so);
strcpy(o_seq[so++],((TEST_INFO *)td)->tn);//将读线程名复制给0_seq队列
pthread_mutex_unlock(&cs_so);

sleep(((TEST_INFO *)td)->pt);//休眠写进程 持续的时间长
gettimeofday(&t,NULL);//获得当前的时间
((TEST_INFO *)td)->e=difftime(t.tv_sec,rl);//

pthread_mutex_lock(&cs_rc);
rc--;
if(rc==0)pthread_mutex_unlock(&cs_d);
pthread_mutex_unlock(&cs_rc);
return 0;
}

void *r(void *td){
struct timeval t;
time_t wl=base;
sleep(((TEST_INFO *)td)->rm);//休眠写进程进入的时间长
gettimeofday(&t,NULL);
((TEST_INFO *)td)->i=difftime(t.tv_sec,wl);//将系统时间与main主函数执行的时间差赋值给i变量（写线程进入的时间）
pthread_mutex_lock(&cs_sr);//建立互斥锁
strcpy(r_seq[sr++],((TEST_INFO *)td)->tn);// 将写线程名复制给r_seq队列
pthread_mutex_unlock(&cs_sr);//解除互斥锁

pthread_mutex_lock(&cs_d);
gettimeofday(&t,NULL);//获得当前的时间
((TEST_INFO *)td)->b=difftime(t.tv_sec,wl);//将系统时间与main主函数执行的时间差赋值给b变量（写线程开始的时间）
pthread_mutex_lock(&cs_so);
strcpy(o_seq[so++],((TEST_INFO *)td)->tn);// 将写线程名复制给o_seq队列
pthread_mutex_unlock(&cs_so);

sleep(((TEST_INFO *)td)->pt);//休眠写进程持续的时间长
gettimeofday(&t,NULL);//获取当前的时间
((TEST_INFO *)td)->e=difftime(t.tv_sec,wl);//将系统时间与main主函数执行的时间差赋值给e变量（写线程结束的时间）

pthread_mutex_unlock(&cs_d);
return 0;
}

void create_exam(){
int i=0;
pthread_t ht[MAX_THREAD];
pthread_mutex_init(&cs_d,NULL);//初始化互斥锁
pthread_mutex_init(&cs_rc,NULL);
pthread_mutex_init(&cs_sr,NULL);
pthread_mutex_init(&cs_so,NULL);
struct timeval t;

gettimeofday(&t,NULL);
base=t.tv_sec;

for(i=0;i<MAX_THREAD;i++){//分别创立读写线程的初始化
if((test_item.ti)[i].tn[0]=='r'){
pthread_create(&ht[i],NULL,r,&((test_item.ti)[i]));
}
else if((test_item.ti)[i].tn[0]=='w'){
pthread_create(&ht[i],NULL,w,&((test_item.ti)[i]));
}
}
for(i=0;i<MAX_THREAD;i++){
pthread_join(ht[i],NULL);
}
pthread_mutex_destroy(&cs_d);//销毁互斥锁
pthread_mutex_destroy(&cs_rc);
pthread_mutex_destroy(&cs_sr);
pthread_mutex_destroy(&cs_so);
}

int main(int argc,char *argv[]){
int i=0;
int si,pos;
int fd;
FILE *fa;
char file_name[100];

create_exam();

sprintf(file_name,"%s_answer.txt",test_item.sn);//从文件中读取
if((fa=fopen(file_name,"w"))==NULL){
printf("Error openning answer file:%s\n",file_name);
exit(3);
}
save_answer(fa);
exit(0);
}

2. 无优先算法
#include <time.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#include <string.h>
#include <fcntl.h>
#define MAX_THREAD 10
#define SNL 8

typedef struct{
char tn[3]; //name of thread
unsigned int rm; //the moment when this thread request to access data.
unsigned int pt; //duration of operation
unsigned int i; //same to rm
unsigned int b; //instance at which this thread begin to operate data
unsigned int e; //ending instance
}TEST_INFO;

//TEST_INFO test_data[MAX_THREAD];

typedef struct {
char sn[100]; //student number
TEST_INFO ti[MAX_THREAD]; //test item
}TI; //test_item_for_student
//TI test_items[STUDENTS];
TI test_item={{" 2566"},
{{"w1", 4,7},{"r1",11,14},{"r2",1,5},{"w2",8,11},{"w3",15,2},{"r3",5,8},
{"r4",12,15},{"w4",5,2},{"r5",9,12},{"r6",15,3}}
};
char r_seq[MAX_THREAD][3];
char o_seq[MAX_THREAD][3];
int sr=0;
int so=0;

int rc=0; //count how many readers are reading
pthread_mutex_t cs_d; //guarentee mutually access data
pthread_mutex_t cs_rc; //guarentee mutually access "rc"
pthread_mutex_t cs_sr; //guarentee mutually access "sr"
pthread_mutex_t cs_so; //guarentee mutually access "sr"
time_t base; //the moment when function main begin

/*
void print_answer(){
int i;

printf("%s\n",test_item.sn);
printf("name r_m p_t i_t b_t e_t\n");
for(i=0;i<MAX_THREAD;i++){
printf("%4s%4d%4d%8d%8d%8d\n",(test_item.ti)[i].tn,(test_item.ti)[i].rm,(test_item).ti[i].pt,(test