《操作系统导论》第三十一章作业

这个问题是需要我们完善fork/join函数：

#include 
#include 
#include 
#include "common_threads.h"

sem_t s; 

void *child(void *arg) {
    printf("childn");
    // use semaphore here
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t p;
    printf("parent: beginn");
    // init semaphore here
    Pthread_create(&p, NULL, child, NULL);
    // use semaphore here
    printf("parent: endn");
    return 0;
}

要求按顺序打印：
parent:begin
child
parent:end
补全如下：

#include 
#include 
#include 
#include "common_threads.h"

sem_t s; 

void *child(void *arg) {
sleep(1);
    printf("childn");
    sem_post(&s);
    // use semaphore here
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t p;
    printf("parent: beginn");
    // init semaphore here
    sem_init(&s,0,0);
    Pthread_create(&p, NULL, child, NULL);
    // use semaphore here
    sem_wait(&s);
    printf("parent: endn");
    return 0;
}

补全后的代码如上，在child函数中的刚开始部分加上了sleep（1），同时初始化了信号量，如果父进程先到达，父进程被停止在了sem_wait的位置，等待子进程的完成。所以会输出我们所需要的结果。编译代码并且运行，最后的与逆行结果为：

rendezvous.c的代码如下：

#include 
#include 
#include "common_threads.h"

// If done correctly, each child should print their "before" message
// before either prints their "after" message. Test by adding sleep(1)
// calls in various locations.

sem_t s1, s2;

void *child_1(void *arg) {
    printf("child 1: beforen");
    // what goes here?
    printf("child 1: aftern");
    return NULL;
}

void *child_2(void *arg) {
    printf("child 2: beforen");
    // what goes here?
    printf("child 2: aftern");
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t p1, p2;
    printf("parent: beginn");
    // init semaphores here
    Pthread_create(&p1, NULL, child_1, NULL);
    Pthread_create(&p2, NULL, child_2, NULL);
    Pthread_join(p1, NULL);
    Pthread_join(p2, NULL);
    printf("parent: endn");
    return 0;
}

根据注释，我们知道我们需要先打印出两个before，然后再输出两个after；
所以补全代码如下：

#include 
#include 
#include "common_threads.h"

// If done correctly, each child should print their "before" message
// before either prints their "after" message. Test by adding sleep(1)
// calls in various locations.

sem_t s1, s2;

void *child_1(void *arg) {
    printf("child 1: beforen");
    sem_post(&s2);
    sem_wait(&s1);
    // what goes here?
    printf("child 1: aftern");
    return NULL;
}

void *child_2(void *arg) {
    printf("child 2: beforen");
    sem_post(&s1);
    sem_wait(&s2);
    // what goes here?
    printf("child 2: aftern");
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t p1, p2;
    printf("parent: beginn");
    // init semaphores here
    sem_init(&s1,0,0);
    sem_init(&s2,0,0);
    Pthread_create(&p1, NULL, child_1, NULL);
    Pthread_create(&p2, NULL, child_2, NULL);
    Pthread_join(p1, NULL);
    Pthread_join(p2, NULL);
    printf("parent: endn");
    return 0;
}

这段代码使用了两个信号量，第一个进程输出完before之后，让该进程睡眠然后调用另一个进程，另一个进程输出完before之后，该进程睡眠，然后第一个进程继续运行。最后的运行结果如下，题中的要求相同：

reader-writer.c的代码如下：

#include 
#include 
#include 
#include "common_threads.h"

//
// Your code goes in the structure and functions below
//

typedef struct __rwlock_t {
} rwlock_t;


void rwlock_init(rwlock_t *rw) {
}

void rwlock_acquire_readlock(rwlock_t *rw) {
}

void rwlock_release_readlock(rwlock_t *rw) {
}

void rwlock_acquire_writelock(rwlock_t *rw) {
}

void rwlock_release_writelock(rwlock_t *rw) {
}

//
// Don't change the code below (just use it!)
// 

int loops;
int value = 0;

rwlock_t lock;

void *reader(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
	rwlock_acquire_readlock(&lock);
	printf("read %dn", value);
	rwlock_release_readlock(&lock);
    }
    return NULL;
}

void *writer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
	rwlock_acquire_writelock(&lock);
	value++;
	printf("write %dn", value);
	rwlock_release_writelock(&lock);
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    assert(argc == 4);
    int num_readers = atoi(argv[1]);
    int num_writers = atoi(argv[2]);
    loops = atoi(argv[3]);

    pthread_t pr[num_readers], pw[num_writers];

    rwlock_init(&lock);

    printf("beginn");

    int i;
    for (i = 0; i < num_readers; i++)
	Pthread_create(&pr[i], NULL, reader, NULL);
    for (i = 0; i < num_writers; i++)
	Pthread_create(&pw[i], NULL, writer, NULL);

    for (i = 0; i < num_readers; i++)
	Pthread_join(pr[i], NULL);
    for (i = 0; i < num_writers; i++)
	Pthread_join(pw[i], NULL);

    printf("end: value %dn", value);

    return 0;
}

代码的完善如下：

#include 
#include 
#include 
#include "common_threads.h"

//
// Your code goes in the structure and functions below
//

typedef struct __rwlock_t {
  sem_t lock;
  sem_t write_lock;
  int reader_number;
} rwlock_t;


void rwlock_init(rwlock_t *rw) {
     sem_init(&rw->lock,0,1);
     sem_init(&rw->write_lock,0,1);
     rw->reader_number=0;
}

void rwlock_acquire_readlock(rwlock_t *rw) {
    sleep(1);
    sem_wait(&rw->lock);
    rw->reader_number++;
    if(rw->reader_number==1)
      {sem_wait=(&rw->write_lock);
}
sem_post(&rw->lock);
}

void rwlock_release_readlock(rwlock_t *rw) {
sem_wait(&rw->lock);
rw->reader_number--;
if(rw->reader_number==0)
{
sem_post(&rw->write_lock);
}
sem_post(&rw->lock);
}

void rwlock_acquire_writelock(rwlock_t *rw) {
sleep(1);
sem_wait(&rw->write_lock);
}

void rwlock_release_writelock(rwlock_t *rw) {
sem_post(&rw->write_lock);
}

//
// Don't change the code below (just use it!)
// 

int loops;
int value = 0;

rwlock_t lock;

void *reader(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
	rwlock_acquire_readlock(&lock);
	printf("read %dn", value);
	rwlock_release_readlock(&lock);
    }
    return NULL;
}

void *writer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
	rwlock_acquire_writelock(&lock);
	value++;
	printf("write %dn", value);
	rwlock_release_writelock(&lock);
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    assert(argc == 4);
    int num_readers = atoi(argv[1]);
    int num_writers = atoi(argv[2]);
    loops = atoi(argv[3]);

    pthread_t pr[num_readers], pw[num_writers];

    rwlock_init(&lock);

    printf("beginn");

    int i;
    for (i = 0; i < num_readers; i++)
	Pthread_create(&pr[i], NULL, reader, NULL);
    for (i = 0; i < num_writers; i++)
	Pthread_create(&pw[i], NULL, writer, NULL);

    for (i = 0; i < num_readers; i++)
	Pthread_join(pr[i], NULL);
    for (i = 0; i < num_writers; i++)
	Pthread_join(pw[i], NULL);

    printf("end: value %dn", value);

    return 0;
}

我们只需要将读者的数量设置的很大，写者就需要等待读者全部被释放之后，才能写，所以当数量很大时，可能会出现写者的饥饿问题。
输入指令：./reader-writer 5 5 10

程序三个参数分别为读者数，写者数，每个读者、写者进行的读写操作数

运行结果如下：

zhaolv@ubuntu:~/ostep-homework/threads-sema$ ./reader-writer  5 5 10
begin
read 0
read 0
read 0
read 0
read 0
write 1
write 2
write 3
write 4
write 5
read 5
write 6
write 7
read 7
write 8
read 8
read 8
read 8
write 9
write 10
write 11
write 12
read 12
read 12
write 13
read 13
read 13
read 13
write 14
write 15
write 16
write 17
read 17
read 17
write 18
read 18
read 18
read 18
write 19
write 20
read 20
write 21
write 22
read 22
write 23
read 23
read 23
read 23
write 24
write 25
write 26
write 27
read 27
read 27
write 28
read 28
read 28
read 28
write 29
write 30
write 31
read 31
read 31
write 32
write 33
read 33
read 33
read 33
write 34
write 35
read 35
read 35
write 36
write 37
write 38
read 38
read 38
read 38
write 39
write 40
read 40
write 41
write 42
read 42
write 43
read 43
read 43
read 43
write 44
write 45
write 46
write 47
read 47
read 47
write 48
read 48
read 48
read 48
write 49
write 50
end: value 50

reader-writer-nostarve.c的代码如下：

#include 
#include 
#include 
#include 
#include "common_threads.h"

//
// Here, you have to write (almost) ALL the code. Oh no!
// How can you show that a thread does not starve
// when attempting to acquire this mutex you build?
//

typedef __ns_mutex_t {
} ns_mutex_t;

void ns_mutex_init(ns_mutex_t *m) {
}

void ns_mutex_acquire(ns_mutex_t *m) {
}

void ns_mutex_release(ns_mutex_t *m) {
}


void *worker(void *arg) {
    return NULL;
}

int main(int argc, char *argv[]) {
    printf("parent: beginn");
    printf("parent: endn");
    return 0;
}

这里需要生产者和消费者都要运行，我们同时看到第六题需要构建一个没有饥饿的互斥量，但是这里只需要两个都运行就可以满足。所以这里我们可以设置一个写锁，第一个读者会获得写锁，接下来的读者都可以获得读锁，但是写者则不能进入，只有等到所有的读者都结束，写者才能获得写锁。
所以，这里可以补全代码为：

#include 
#include 
#include 
#include "common_threads.h"

//
// Your code goes in the structure and functions below
//

typedef struct __rwlock_t {
sem_t lock;
sem_t write_lock;
sem_t write_waiting;
int reader_number;
} rwlock_t;


void rwlock_init(rwlock_t *rw) {
sem_init(&rw->lock,0,1);
sem_init(&rw->write_lock,0,1);
sem_init(&rw->write_waiting,0,1);
rw->reader_number=0;
}

void rwlock_acquire_readlock(rwlock_t *rw) {
sleep(1);
sem_wait(&rw->write_waiting);
sem_wait(&rw->lock);
rw->reader_number++;
if(rw->reader_number==1)
{
sem_wait(&rw->write_lock);
}
sem_post(&rw->lock);
sem_post(&rw->write_waiting);
}

void rwlock_release_readlock(rwlock_t *rw) {
sem_wait(&rw->lock);
rw->reader_number--;
if(rw->reader_number==0)
{
sem_post(&rw->write_lock);
}
}

void rwlock_acquire_writelock(rwlock_t *rw) {
sleep(1);
sem_wait(&rw->write_waiting);
sem_wait(&rw->write_lock);
sem_post(&rw->write_waiting);
}

void rwlock_release_writelock(rwlock_t *rw) {
sem_post(&rw->write_lock);
}

//
// Don't change the code below (just use it!)
// 

int loops;
int value = 0;

rwlock_t lock;

void *reader(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
	rwlock_acquire_readlock(&lock);
	printf("read %dn", value);
	rwlock_release_readlock(&lock);
    }
    return NULL;
}

void *writer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
	rwlock_acquire_writelock(&lock);
	value++;
	printf("write %dn", value);
	rwlock_release_writelock(&lock);
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    assert(argc == 4);
    int num_readers = atoi(argv[1]);
    int num_writers = atoi(argv[2]);
    loops = atoi(argv[3]);

    pthread_t pr[num_readers], pw[num_writers];

    rwlock_init(&lock);

    printf("beginn");

    int i;
    for (i = 0; i < num_readers; i++)
	Pthread_create(&pr[i], NULL, reader, NULL);
    for (i = 0; i < num_writers; i++)
	Pthread_create(&pw[i], NULL, writer, NULL);

    for (i = 0; i < num_readers; i++)
	Pthread_join(pr[i], NULL);
    for (i = 0; i < num_writers; i++)
	Pthread_join(pw[i], NULL);

    printf("end: value %dn", value);

    return 0;
}

运行结果如下：

zhaolv@ubuntu:~/ostep-homework/threads-sema$ gcc -o reader-writer-nostarve reader-writer-nostarve.c -Wall -pthread
zhaolv@ubuntu:~/ostep-homework/threads-sema$ ./reader-writer-nostarve  5 5 10
begin
read 0
read 0
read 0
read 0
read 0
write 1
write 2
write 3
write 4
write 5
read 5
read 5
read 5
read 5
read 5
write 6
write 7
write 8
write 9
write 10
read 10
read 10
read 10
read 10
read 10
write 11
write 12
write 13
write 14
write 15
read 15
read 15
read 15
read 15
read 15
write 16
write 17
write 18
write 19
write 20
read 20
read 20
read 20
read 20
read 20
write 21
write 22
write 23
write 24
write 25
read 25
read 25
read 25
read 25
read 25
write 26
write 27
write 28
write 29
write 30
read 30
read 30
read 30
read 30
write 31
write 32
read 32
write 33
write 34
write 35
read 35
read 35
read 35
read 35
write 36
write 37
read 37
write 38
write 39
write 40
read 40
read 40
read 40
write 41
read 41
write 42
read 42
write 43
write 44
write 45
read 45
read 45
write 46
read 46
write 47
read 47
write 48
write 49
read 49
write 50
end: value 50

可以看到read和write都在运行。

mutex-nostrave.c的代码如下：

#include 
#include 
#include 
#include 
#include "common_threads.h"

//
// Here, you have to write (almost) ALL the code. Oh no!
// How can you show that a thread does not starve
// when attempting to acquire this mutex you build?
//

typedef __ns_mutex_t {
} ns_mutex_t;

void ns_mutex_init(ns_mutex_t *m) {
}

void ns_mutex_acquire(ns_mutex_t *m) {
}

void ns_mutex_release(ns_mutex_t *m) {
}


void *worker(void *arg) {
    return NULL;
}

int main(int argc, char *argv[]) {
    printf("parent: beginn");
    printf("parent: endn");
    return 0;
}

这里可以判断是否所有的进程都已经运行过了，之后再往后执行。
代码完善如下：

#include 
#include 
#include 
#include 
#include "common_threads.h"

//
// Here, you have to write (almost) ALL the code. Oh no!
// How can you show that a thread does not starve
// when attempting to acquire this mutex you build?
//

typedef __ns_mutex_t {
sem_t mutex;
sem_t barrier;
sem_t lock;
int num_threads;
} ns_mutex_t;

void ns_mutex_init(ns_mutex_t *m) {
sem_init(&m->barrier,0,-num_threads+1);
sem_init(&m->mutex,0,1);
}

void ns_mutex_acquire(ns_mutex_t *m) {
sem_wait(&m->lock);
}

void ns_mutex_release(ns_mutex_t *m) {
sem_post(&m->lock);
sem_post(&m->barrier);
sem_wait(&m->barrier);
sem_wait(&m->mutex);
for(int i=0;inum_threads;i++)
{
sem_post(&m->barrier);
}
sem_post(&m->mutex);
}


void *worker(void *arg) {
    return NULL;
}

int main(int argc, char *argv[]) {
    printf("parent: beginn");
    printf("parent: endn");
    return 0;
}