操作系统实践报告

多进程题目

sh1.c: 实现shell程序，要求具备如下功能

∙支持命令参数

∙$ echo arg1 arg2 arg3

∙$ ls /bin /usr/bin /home

∙实现内置命令cd、pwd、exit

∙$ cd /bin

∙$ pwd

∙/bin

思路：

说明：首先设置一个死循环模仿shell终端，读取用户的输入，并且根据空格将输入拆分成字符串数组，然后调用excute这个子函数进行处理。

1.echo

根据数组第一个元素来判断命令是什么，判断出是ehco后，fork一个新的进程，将其后的内容一个个输出出来，并且父进程等待子进程退出后再执行，确保输出在屏幕上时不被打断。

2.ls

读取用户输入并且根据拆分的数组判断出是ls命令后，fork一个新的进程，调用execlp函数将/bin/ls下的ls程序装入子进程并将拆分的数组参数部分传递给ls即可，同样的，父进程等待子进程退出，确保输出在屏幕上不被打断。

3.cd

同样是根据输入并拆分成数组后判断出是cd命令后，fork一个新的进程，然后调用chdir并将拆分数组的参数部分传递给chdir作为实参即可。

4.pwd

同样是根据输入并拆分成数组后判断出是pwd命令后，fork一个新的进程，然后调用system("pwd")即可，此命令也可以用来验证上面的cd命令是否正确执行。

5.exit

根据用户输入逼格拆分的数组判断出是exit命令后，excute子函数返回-1，在循环中检测excute的返回值，如果是-1则直接return，退出模仿的shell终端。

sh2.c: 实现shell程序，要求在第1版的基础上，添加如下功能

∙实现文件重定向

∙$ echo hello >log

∙$ cat log

∙Hello

思路：

     接sh1.c的描述，若判断出是echo命令后，要再次判断拆分的字符串数组中有无“>”出现，如果   有，则把“>”之前、echo之后的内容作为输出，把“>”之后到“>”之后的第一个空白字符作为文件名，fopen创建文件并fwrite将输出内容输出到该文件中，并关闭文件。

sh1.c和sh2.c的源代码：

#include

#include

#include

#include

#include

#include

#include

#define LEN 256

#define WIDTH 256

#define HEIGHT 10

void split(char source[],char dest[HEIGHT][WIDTH])

{

    char *p;

    p=strsep(&source," ");

    int i=0;

    for(i=0;p[i]!='\\0';i++){

        dest[0][i]=p[i];

    }

    dest[0][i]='\\0';

    int j=1;

    while(p){

        p=strsep(&source," ");

        if(p){

            for(i=0;p[i]!='\\0';i++){

                dest[j][i]=p[i];

            }

            dest[j][i]='\\0';

            j++;

        }

    }

}

int execute(char comm[HEIGHT][WIDTH])

{

    if(strcmp(comm[0],"echo")==0){

        int pid=fork();

        if(pid==0){

            int i=0;

            int is=0;

            for(i=1;comm[i][0]!='\\0';i++){

             if(comm[i][0]=='>'){

                    is=1;

                    break;    

                }

            }

            if(is==1){

                puts(comm[i+1]);

                FILE *fp=fopen(comm[i+1],"w+");

                int j=0;

             for(j=1;j                    fseek(fp,0,SEEK_END);

                    fwrite(comm[j],strlen(comm[j]),1,fp);

                }

                fclose(fp);

            }else{

                int j=0;

                for(j=1;comm[j][0]!='\\0';j++){

                    printf("%s",comm[j]);

                    printf(" ");

                }

                printf("\\n");                

            }

        }else{

            int status;

            wait(&status);

        }

    }else if(strcmp(comm[0],"ls")==0){

        int pid=fork();

        if(pid==0){

            if(comm[1][0]=='\\0'){

                execlp("/bin/ls

            }else{

                execlp("/bin/ls

            }

        }else{

            int status;

            wait(&status);

        }

    }else if(strcmp(comm[0],"cd")==0){

            int pid=fork();

            if(pid==0){

                chdir(comm[1]);

            }else{

                int status;

                wait(&status);        

            }

    }else if(strcmp(comm[0],"pwd")==0){

            int pid=fork();

            if(pid==0){

                system("pwd");

            }else{

                int status;

                wait(&status);        

            }

    }else if(strcmp(comm[0],"exit")==0){

        return -1;    

    }

    return 1;

}

int main()

{

    while(1){

        char command[LEN];

        char splitArray[HEIGHT][WIDTH]={{'\\0'}};

        printf("%s

        gets(command);

        split(command,splitArray);

        int i=0;

        if(-1==execute(splitArray)){

            return 0;

        }

    }

}

sh3.c: 实现shell程序，要求在第2版的基础上，添加如下功能

∙实现管道

∙$ cat /etc/passwd | wc -l

∙实现管道和文件重定向

∙$ cat input.txt

∙3

∙2

∙1

∙3

∙2

∙1

∙$ cat output.txt

∙$ cat output.txt

∙1

∙2

∙3

思路：

首先读取用户输入，以“|”为分隔符将输入分割成字符串数组，然后在一个while循环中依次执行下面的动作：代码中通过pipe()函数来创建管道，创建之后父进程和子进程一个只能向管道写内容，一个只能向管道读内容。然后利用dup()函数来把进程的输入流或者输出流重定向到管道里，这样就能实现管道的操作。实现的时候注意可以使用多个“|”来迭代进行管道操作，需要使用一个循环来处理。用system执行每一条命令，同时还要注意最后一个操作的输出流是标准输出（即屏幕），不需要重定向到管道里，需要特殊处理一下。

源代码：

#include

#include

#include

#include

#include

#include

#include

#define LEN 256

#define WIDTH 256

#define HEIGHT 10

void split(char source[],char dest[HEIGHT][WIDTH])

{

    char *p;

    p=strsep(&source,"|");

    int i=0;

    for(i=0;p[i]!='\\0';i++){

        dest[0][i]=p[i];

    }

    dest[0][i]='\\0';

    int j=1;

    while(p){

        p=strsep(&source,"|");

        if(p){

            for(i=0;p[i]!='\\0';i++){

                dest[j][i]=p[i];

            }

            dest[j][i]='\\0';

            j++;

        }

    }

}

main(){

    char command[LEN];

    char splitArray[HEIGHT][WIDTH]={{'\\0'}};

    printf("%s

    gets(command);

    split(command,splitArray);

    int i=0;

    for(i=0;splitArray[i][0]!='\\0';i++){

        puts(splitArray[i]);    

    }

    int p[2];

    pipe(p); 

    int j=0;

    for(j=0;splitArray[j+1][0]!='\\0';j++){

        if (fork() == 0) {

        // Child process

            close(0);

            close(p[0])

            close(p[1]);

            dup(p[0]); 

            system(splitArray[j]);

        } else {

            //Parent process

            close(1); 

            close(p[0])

            close(p[1]);

            dup(p[1]); 

            system(splitArray[j+1]);

        }        

    }

}

多线程题目

pi1.c: 使用2个线程根据莱布尼兹级数计算PI

∙莱布尼兹级数公式: 1 - 1/3 + 1/5 - 1/7 + 1/9 - ... = PI/4

∙主线程创建1个辅助线程

∙主线程计算级数的前半部分

∙辅助线程计算级数的后半部分

∙主线程等待辅助线程运行結束后,将前半部分和后半部分相加

思路：

计算公式前1000项，主线程计算前5000项，子线程计算后5000项，主进程等待子进程结束，通过pthread_join(sub,(void **)&result);的result参数获取子进程计算结果再相加即可。

源代码：

#include

#include

#include

#include

#define LEN 10000 

struct result{

  float sum;

};

void *subThread(){

  int i;

  float j;

  struct result *result;

  float sum1=0,sum2=0,sum=0;

for(i=LEN/2+1;i<=LEN;i++){

    j=i;

    if(i%2==0){

      sum1+=1/(2*j-1);

    }

//  printf("%f\\n",sum2);

    if(i%2==1){

      sum2+=1/(2*j-1);

    }

  }

 // printf("%f\\n",sum1);

  sum=sum2-sum1;

 // printf("%f\\n",sum);

// printf("%f\\n",sum);

  result=malloc(sizeof(result));

result->sum=sum;

  return result;

}

int main(){

  int i;

  float j;

  float sum1=0,sum2=0,sum=0;

for(i=1;i<=LEN/2;i++){

    j=i;

    if(i%2==0){

      sum1+=1/(2*j-1);

    }

    if(i%2==1){

      sum2+=1/(2*j-1);

    }

  }

  sum=sum2-sum1;

//  printf("%f\\n",sum);

  pthread_t sub;

  pthread_create(&sub,NULL,subThread,NULL);

  struct result *result;

  pthread_join(sub,(void **)&result);

sum+=result->sum;

  printf("%f\\n",sum);

  return 0;

} 

pi2.c: 使用N个线程根据莱布尼兹级数计算PI

∙与上一题类似，但本题更加通用化，能适应N个核心，需要使用线程参数来实现

∙主线程创建N个辅助线程

∙每个辅助线程计算一部分任务，并将结果返回

∙主线程等待N个辅助线程运行结束，将所有辅助线程的结果累加

思路：

设计算公式前1000项，读取用户输入的线程数目N，通过pthread_create(&workers[i-1],NULL,compute,myparam);产生N个线程，并且通过myparam设置每一个线程计算的起始项和终止项，通过pthread_join(workers[j],(void **)&myresult);等待每个线程结束并通过result获取结果，将结果相加即可。

源代码：

#include

#include

#include

#include

#define LEN 10000

#define MAX_WORKERS 100

struct param{

  int start;

  int end;

};

struct result{

  float sum;

};

void *compute(void *arg){

  int i;

  float j;

  struct param *myparam;

  myparam=(struct param *)arg;

int start=myparam->start;

int end=myparam->end;

  struct result *myresult;

  float sum1=0,sum2=0,sum3=0;

for(i=start;i<=end;i++){

    j=i;

    if(i%2==0){

      sum1+=1/(2*j-1);

    }

    if(i%2==1){

      sum2+=1/(2*j-1);

    }

  }

  myresult=malloc(sizeof(struct result));

myresult->sum=sum2-sum1;

  return myresult;

}

int main(){

  int thread_num=1;

  struct param myparams[MAX_WORKERS+1];

  pthread_t workers[MAX_WORKERS];

  printf("please input thread number:");

  scanf("%d",&thread_num);

  int i;

  myparams[0].start=0;

  myparams[0].end=0;

for(i=1;i<=thread_num-1;i++){

   struct param *myparam; 

   myparam=&myparams[i];

myparam->start=myparams[i-1].end+1;

myparam->end=myparams[i].start+(LEN/thread_num)-1;

   pthread_create(&workers[i-1],NULL,compute,myparam);

  }

  myparams[thread_num].start=myparams[thread_num-1].end+1;

  myparams[thread_num].end=LEN;

  pthread_create(&workers[thread_num-1],NULL,compute,&myparams[thread_num]);

  int j;

  float sum=0;

for(j=0;j   struct result *myresult;

    pthread_join(workers[j],(void **)&myresult);

sum+=myresult->sum;

   free(myresult);

   }

   printf("%f\\n",sum);

  return 0；

}

sort.c: 多线程排序

∙主线程创建一个辅助线程

∙主线程使用选择排序算法对数组的前半部分排序

∙辅助线程使用选择排序算法对数组的后半部分排序

∙主线程等待辅助线程运行結束后,使用归并排序算法归并数组的前半部分和后半部分

思路：

主线程排序数组的前半部分，辅助线程排序后半部分，pthread_create(&worker_id,NULL,&sort,&pa);中pa传递的是数组的首地址，主线程等辅助线程结束后，再调用merge将数组合并为有序。

源代码：

#include

#include

#include

#include

#define LEN 10

int array[LEN]={0,3,8,6,2,9,5,4,1,7};

struct param{

  int *arr;

};

void *sort(void *arg){

 struct param *mypa;

  mypa=(struct param *)arg;

  int i=0;

  int j=0;

  int min=0;

  int temp=0;

for(i=LEN/2;i   min=i;

for(j=i;j if(mypa->arr[min]>mypa->arr[j])min=j;

   }

temp=mypa->arr[min];

mypa->arr[min]=mypa->arr[i];

mypa->arr[i]=temp;

  }

}

void merge(){

  int i=0;

  int a[LEN/2];

  int b[LEN/2];

for(i=0;i    a[i]=array[i];

    b[i]=array[i+LEN/2];

  }

/* for(i=0;i    printf("%d\\n",a[i]);

  }*/

  int tm=0;

  int ti=0,tj=0;

while(ti if(a[ti]      array[tm]=a[ti];

      ti++;

    }else{

      array[tm]=b[tj];

      tj++;

    }

    tm++;

  }

}

int main()

{

  struct param pa;

  pa.arr=array;

  int ti=0,tj=0,tmin=0;

for(ti=0;ti    tmin=ti;

for(tj=ti;tj if(array[tmin]>array[tj])tmin=tj;

    }

    int temp=array[tmin];

    array[tmin]=array[ti];

    array[ti]=temp;

  }

  pthread_t worker_id;

  pthread_create(&worker_id,NULL,&sort,&pa);

  pthread_join(worker_id,NULL);

  merge();

  int i=0;

for(i=0;i    printf("%d\\n",array[i]);

  }

}

pc1.c: 使用条件变量解决生产者、计算者、消费者问题

∙系统中有3个线程：生产者、计算者、消费者

∙系统中有2个容量为4的缓冲区：buffer1、buffer2

∙生产者生产'a'、'b'、'c'、‘d'、'e'、'f'、'g'、'h'八个字符，放入到buffer1

∙计算者从buffer1取出字符，将小写字符转换为大写字符，放入到buffer2

∙消费者从buffer2取出字符，将其打印到屏幕上

思路：

类似于生产者和消费者，在问题中，生产者、计算者相对应buffer1是生产者、消费者，二者互斥的进入buffer1，并且当buffer1满时，生产者等待，当buffer1空时，且计算值要从中取数据时，计算者等待。同理，计算者、消费者相对应buffer2是生产者和消费者，二者互斥的进入buffer2，当buffer2满时，且计算者要向其中放入数据时，计算者应等待，当buffer2空时，消费者应等待。

源代码：

#include

#include

#define CAPACITY 4

int buffer1[CAPACITY];

int buffer2[CAPACITY];

int in1;

int out1;

int in2;

int out2;

int buffer2_is_empty()

{

    return in2 == out2;

}

int buffer2_is_full()

{

    return (in2 + 1) % CAPACITY == out2;

}

int buffer1_is_empty()

{

    return in1 == out1;

}

int buffer1_is_full()

{

    return (in1 + 1) % CAPACITY == out1;

}

int get_item()

{

    int item;

    item = buffer2[out2];

    out2 = (out2 + 1) % CAPACITY;

    return item;

}

void put_item(int item)

{

    buffer1[in1] = item;

    in1 = (in1 + 1) % CAPACITY;

}

int cal_get_item()

{

    int item;

    item = buffer1[out1];

    out1 = (out1 + 1) % CAPACITY;

    return item;

}

void cal_put_item(int item)

{

    buffer2[in2] = item;

    in2 = (in2 + 1) % CAPACITY;

}

pthread_mutex_t mutex1;

pthread_cond_t wait_empty_buffer1;

pthread_cond_t wait_full_buffer1;

pthread_mutex_t mutex2;

pthread_cond_t wait_empty_buffer2;

pthread_cond_t wait_full_buffer2;

#define ITEM_COUNT (CAPACITY * 2)

void *consume(void *arg)

{

    int i;

    int item;

for (i = 0; i < ITEM_COUNT; i++) {

        pthread_mutex_lock(&mutex2);

       while (buffer2_is_empty())

            pthread_cond_wait(

               &wait_full_buffer2, 

               &mutex2);

        item = get_item(); 

        printf("    consume item: %c\\n", item);

        sleep(1);

        pthread_cond_signal(&wait_empty_buffer2);

        pthread_mutex_unlock(&mutex2);

    }

    return NULL;

}

void *calculate(void *arg)

{

    int i;

    int item;

for (i = 0; i < ITEM_COUNT; i++) {

        pthread_mutex_lock(&mutex1);

       while (buffer1_is_empty())

            pthread_cond_wait(

               &wait_full_buffer1, 

               &mutex1);

        item = cal_get_item(); 

        item+='A'-'a';

        pthread_cond_signal(&wait_empty_buffer1);

        pthread_mutex_unlock(&mutex1);

        pthread_mutex_lock(&mutex2);

        while (buffer2_is_full()) 

            pthread_cond_wait(&wait_empty_buffer2, &mutex2);

        cal_put_item(item);

        pthread_cond_signal(&wait_full_buffer2);

        pthread_mutex_unlock(&mutex2);

    }

    return NULL;

}

void produce()

{

    int i;

    int item;

for (i = 0; i < ITEM_COUNT; i++) {

        pthread_mutex_lock(&mutex1);

        while (buffer1_is_full()) 

            pthread_cond_wait(&wait_empty_buffer1, &mutex1);

        item = i + 'a';

        printf("produce item: %c\\n", item);

        put_item(item);

        sleep(1);

        pthread_cond_signal(&wait_full_buffer1);

        pthread_mutex_unlock(&mutex1);

    }

}

int main()

{

    pthread_t consumer_tid;

    pthread_t calculate_tid;

    pthread_mutex_init(&mutex1, NULL);

    pthread_cond_init(&wait_empty_buffer1, NULL);

    pthread_cond_init(&wait_full_buffer1, NULL);

    pthread_mutex_init(&mutex2, NULL);

    pthread_cond_init(&wait_empty_buffer2, NULL);

    pthread_cond_init(&wait_full_buffer2, NULL);

    pthread_create(&calculate_tid, NULL, calculate, NULL);

    pthread_create(&consumer_tid, NULL, consume, NULL);

    produce();

    return 0;

}

pc2.c: 使用信号量解决生产者、计算者、消费者问题

∙功能和前面的实验相同，使用信号量解决

思路：

    类似于pc1.c

源代码：

#include

#include

#include

typedef struct {

    int value;

    pthread_mutex_t mutex;

    pthread_cond_t cond;

} sema_t;

void sema_init(sema_t *sema, int value)

{

sema->value = value;

pthread_mutex_init(&sema->mutex, NULL);

pthread_cond_init(&sema->cond, NULL);

}

void sema_wait(sema_t *sema)

{

pthread_mutex_lock(&sema->mutex);

sema->value--;

while (sema->value < 0)

pthread_cond_wait(&sema->cond, &sema->mutex);

pthread_mutex_unlock(&sema->mutex);

}

void sema_signal(sema_t *sema)

{

pthread_mutex_lock(&sema->mutex);

++sema->value;

pthread_cond_signal(&sema->cond);

pthread_mutex_unlock(&sema->mutex);

}

#define CAPACITY 4

int buffer1[CAPACITY];

int buffer2[CAPACITY];

int in1;

int out1;

int in2;

int out2;

int buffer1_is_empty()

{

    return in1 == out1;

}

int buffer1_is_full()

{

    return (in1 + 1) % CAPACITY == out1;

}

int buffer2_is_empty()

{

    return in2 == out2;

}

int buffer2_is_full()

{

    return (in2 + 1) % CAPACITY == out2;

}

int get_item()

{

    int item;

    item = buffer2[out2];

    out2 = (out2 + 1) % CAPACITY;

    return item;

}

void put_item(int item)

{

    buffer1[in1] = item;

    in1 = (in1 + 1) % CAPACITY;

}

int cal_get_item()

{

    int item;

    item = buffer1[out1];

    out1 = (out1 + 1) % CAPACITY;

    return item;

}

void cal_put_item(int item)

{

    buffer2[in2] = item;

    in2 = (in2 + 1) % CAPACITY;

}

sema_t mutex_sema1;

sema_t empty_buffer_sema1;

sema_t full_buffer_sema1;

sema_t mutex_sema2;

sema_t empty_buffer_sema2;

sema_t full_buffer_sema2;

#define ITEM_COUNT (CAPACITY * 2)

void *consume(void *arg)

{

    int i;

    int item;

for (i = 0; i < ITEM_COUNT; i++) {

        sema_wait(&full_buffer_sema2);

        sema_wait(&mutex_sema2);

        item = get_item(); 

        sema_signal(&mutex_sema2);

        sema_signal(&empty_buffer_sema2);

        printf("    consume item: %c\\n", item);

    }

    return NULL;

}

void *calculate()

{

    int i;

    int item;

for (i = 0; i < ITEM_COUNT; i++) {

        sema_wait(&full_buffer_sema1);

        sema_wait(&mutex_sema1);

        item = cal_get_item(); 

        item+='A'-'a';

        sema_signal(&mutex_sema1);

        sema_signal(&empty_buffer_sema1);

        sema_wait(&empty_buffer_sema2);

        sema_wait(&mutex_sema2);

        cal_put_item(item);

        sema_signal(&mutex_sema2);

        sema_signal(&full_buffer_sema2);

    }

}

void produce()

{

    int i;

    int item;

for (i = 0; i < ITEM_COUNT; i++) {

        sema_wait(&empty_buffer_sema1);

        sema_wait(&mutex_sema1);

        item = i + 'a';

        put_item(item);

        sema_signal(&mutex_sema1);

        sema_signal(&full_buffer_sema1);

        printf("produce item: %c\\n", item);

    }

}

int main()

{

    pthread_t consumer_tid;

    pthread_t calculate_tid;

    sema_init(&mutex_sema1, 1);

    sema_init(&empty_buffer_sema1, CAPACITY - 1);

    sema_init(&full_buffer_sema1, 0);

    sema_init(&mutex_sema2, 1);

    sema_init(&empty_buffer_sema2, CAPACITY - 1);

    sema_init(&full_buffer_sema2, 0);

    pthread_create(&consumer_tid, NULL, consume, NULL);

    pthread_create(&calculate_tid, NULL, calculate, NULL);

    produce();

    return 0;

}

ring.c: 创建N个线程，它们构成一个环

∙创建N个线程：T1、T2、T3、… TN

∙T1向T2发送整数1

∙T2收到后将整数加1

∙T2向T3发送整数2

∙T3收到后将整数加1

∙T3向T4发送整数3

∙…

∙TN收到后将整数加1

∙TN向T1发送整数N

思路：

设置三个全局变量N、count和finalData，主线程创建一个子线程，该子线程执行add函数，并且等待子线程介入，其中add函数执行加一操作并且add函数中也创建新的线程执行add函数，并且等待新的线程结束，并将count加一并判断是否小于N，一旦等于N则不再创建新的线程并将计算结果赋值给finalData。在主线程中设置一个while循环，将finalData作为参数传递给主线程创建的第一个子线程。

源代码：

#include

#include

#include

#include

#define N 2

int count=0;

pthread_t workers[N+1];

pthread_t init_id;

int finalData;

struct param

{    

    int data;

};

void *addmm(void *arg){

    count++;

    sleep(1);

    struct param *pa=(struct param *)arg;

    pthread_t id;

    printf("%lu",pthread_self());

    printf(":");

printf("%d",pa->data);

    printf("\\n");

if(count     pa->data++;

        pthread_create(&id,NULL,addmm,pa);

        pthread_join(id,NULL);

        return NULL;

    }else{

     pa->data++;

     finalData=pa->data;

        return NULL;

    }

}

int main(){

    struct param mpa;

    mpa.data=1;

    struct result *re;

    while(1){

        pthread_create(&init_id,NULL,addmm,&mpa);

        pthread_join(init_id,(void **)&re);

        mpa.data=finalData;

    }

}