高级操作系统之同步锁代码

高级操作系统之同步锁代码

读优先

#define N 10
#define M 10
#define READTIMES 100000
#define WRITETIMES 100000

#include "csapp.h"

int readcnt;    /* Initially 0 */
sem_t mutex, w; /* Both initially 1 */

void *read_thread(void *vargp);
void *write_thread(void *vargp);

int main() {
	readcnt = 0;
	pthread_t readers[N];
	pthread_t writers[M];
 	sem_init(&mutex, 0, N);
	sem_init(&w, 0, 1);

	int i;
	for (i=0;i<N;i++) 
		Pthread_create(&readers[i], NULL, read_thread, (void *)i);
	for (i=0;i<M;i++) 
		Pthread_create(&writers[i], NULL, write_thread, (void *)i);

	for (i=0;i<N;i++) 
		Pthread_join(readers[i], NULL);
	for (i=0;i<M;i++)
		Pthread_join(writers[i], NULL);
}

void *read_thread(void *vargp)
{   
	for (int i=0;i<READTIMES;i++) {
		P(&mutex);
		readcnt++;
		if (readcnt == 1) /* First in */
			P(&w);
		V(&mutex);
		
		/* Reading happens here */
		printf("Reader (%d) is reading, readcnt = %d, i=%d\n", (int)vargp, readcnt, i);
		if (i==READTIMES-1)
			printf("Reader (%d) finished!\n", (int)vargp);

		P(&mutex);
		readcnt--;
		if (readcnt == 0) /* Last out */
			V(&w);
		V(&mutex);
	}
}

void *write_thread(void *vargp)
{
	for (int i=0;i<WRITETIMES;i++) {
		P(&w);

		/* Writing here */
		printf("writing...i=%d\n", i);
		if(i==WRITETIMES-1)
			printf("Writer (%d) finished!\n", (int)vargp);

		V(&w);
	}
}

读写公平

#define N 10
#define READTIMES 100000
#define WRITETIMES 10000

#include "csapp.h"

sem_t common_sem, w; /* Both initially 1 */

void *read_thread(void *vargp);
void *write_thread(void *vargp);

int main() {
	pthread_t readers[N];
	pthread_t writers[N];
 	sem_init(&common_sem, 0, N);
	sem_init(&w, 0, 1);

	int i;
	for (i=0;i<N;i++) {
		Pthread_create(&readers[i], NULL, read_thread, (void *)i);
		Pthread_create(&writers[i], NULL, write_thread, (void *)i);
	}

	for (i=0;i<N;i++) { 
		Pthread_join(readers[i], NULL);
		Pthread_join(writers[i], NULL);
	}
}

void *read_thread(void *vargp)
{   
    for (int i=0;i<READTIMES;i++) {
        P(&common_sem);
        
        /* Reading happens here */
        printf("Reader (%d) is reading, i=%d\n", (int)vargp, i);
	if (i==READTIMES-1)
		printf("Reader (%d) finished!\n", (int)vargp);        

        V(&common_sem);
    }
}

void *write_thread(void *vargp)
{
    int j;
    for (int i=0;i<WRITETIMES;i++) {
        P(&w);
		for (j=0;j<N;j++) 
			P(&common_sem);
		V(&w);

        /* Writing here */
        printf("writing...i=%d\n", i);
		if(i==WRITETIMES-1)
			printf("Writer (%d) finished!\n", (int)vargp);
	
		for (j=0;j<N;j++)
        	V(&common_sem);
    }
}

写优先

#define N 10
#define M 10
#define READTIMES 100000
#define WRITETIMES 100000

#include "csapp.h"

int readcnt, writecnt;    /* Initially 0 */
sem_t r, w, rcnt, wcnt; /* Both initially 1 */

void *read_thread(void *vargp);
void *write_thread(void *vargp);

int main() {
	readcnt = 0;
	writecnt = 0;
	pthread_t readers[N];
	pthread_t writers[M];
 	sem_init(&r, 0, 1);
	sem_init(&w, 0, 1);
	sem_init(&rcnt, 0, 1);
	sem_init(&wcnt, 0, 1);

	int i;
	for (i=0;i<N;i++) 
		Pthread_create(&readers[i], NULL, read_thread, (void *)i);
	for (i=0;i<M;i++) 
		Pthread_create(&writers[i], NULL, write_thread, (void *)i);

	for (i=0;i<N;i++) 
		Pthread_join(readers[i], NULL);
	for (i=0;i<M;i++)
		Pthread_join(writers[i], NULL);
}

void *read_thread(void *vargp)
{   
    for (int i=0;i<READTIMES;i++) {
        P(&r);
		P(&rcnt);
        readcnt++;
        if (readcnt == 1) /* First in */
                P(&w);
        V(&rcnt);
		V(&r);
        
        /* Reading happens here */
        printf("Reader (%d) is reading, readcnt = %d, i=%d\n", (int)vargp, readcnt, i);
		if (i==READTIMES-1)
			printf("Reader (%d) finished!\n", (int)vargp);        

        P(&rcnt);
        readcnt--;
        if (readcnt == 0) /* Last out */
                V(&w);
        V(&rcnt);
    }
}

void *write_thread(void *vargp)
{
    for (int i=0;i<WRITETIMES;i++) {
		P(&wcnt);
		writecnt++;
		if (writecnt == 1)
			P(&r);
		V(&wcnt);

        P(&w);

        /* Writing here */
        printf("writing...i=%d\n", i);
		if(i==WRITETIMES-1)
			printf("Writer (%d) finished!\n", (int)vargp);

        V(&w);

		P(&wcnt);
		writecnt--;
		if (writecnt == 0)
			V(&r);
		V(&wcnt);
    }
}

有锁链表

#define N 100
#define Total 100000000

#include "csapp.h"

typedef struct __node_t { // basic node structure
  int             key;
  struct __node_t *next;
} node_t;

typedef struct __list_t { // basic list structure
  node_t          *head;
  pthread_mutex_t lock;
} list_t;

list_t mylist;

void List_Init(list_t *L) {
   L->head = NULL;
   pthread_mutex_init(&L->lock, NULL);
}

void *worker(void *argp) {
   for (int i=0;i<Total/N;i++) 
      List_Insert(&mylist, (int)((int)argp<<16+i));
}

void main() {
   List_Init(&mylist);
   pthread_t workers[N];
   int i;


   for (i=0;i<N;i++) {
      Pthread_create(&workers[i], NULL, worker, (void *)i);
   }
   for (i=0;i<N;i++) {
      Pthread_join(workers[i], NULL);
   }

}

void List_Insert(list_t *L, int key) {
   // synchronization not needed
   node_t *new = malloc(sizeof(node_t));
   if (new == NULL) {
      perror("malloc");
      return;
   }
   new->key = key; 

   // just lock critical section
   pthread_mutex_lock(&L->lock);
   new->next = L->head; 
   L->head = new;
   pthread_mutex_unlock(&L->lock);
}


int List_Lookup(list_t *L, int key) {
   int rv = -1;
   pthread_mutex_lock(&L->lock);
   node_t *curr = L->head;
   while (curr) {
      if (curr->key == key) {
         rv = 0;
         break;
      }
      curr = curr->next;
   }
   pthread_mutex_unlock(&L->lock);
   return rv;
}

无锁链表

#define N 100
#define Total 100000000

#include "csapp.h"

typedef struct __node_t { // basic node structure
  int             key;
  struct __node_t *next;
} node_t;

typedef struct __list_t { // basic list structure
  node_t          *head;
//  pthread_mutex_t lock;
} list_t;

list_t mylist;

/* return 1 when swapping happens;
   retnrun 0 when not*/
int CAS(unsigned long *dst, unsigned long oldVal, unsigned long newVal)
{
    unsigned char ret;
    //printf("(%lu,%lu,%lu)", *dst, oldVal, newVal);
    __asm__ __volatile__ (
            "  lock cmpxchgq %2,%1\n"
            "  sete %0\n" // ret=zf (0:oldVal!=*dst ; 1:oldVal==*dst)
            : "=q" (ret), "=m" (*dst)
            : "r" (newVal), "m" (*dst), "a" (oldVal)
            : "memory");
    //printf("->(%lu,%lu,%lu):%d\r\n", *dst, oldVal, newVal, ret);
    //above assembly returns 0 in case of failure
    if (ret) 
        return 1;
    return 0;
}


void List_Init(list_t *L) {
   L->head = NULL;
//   pthread_mutex_init(&L->lock, NULL);
}

void printList(list_t *L) {
   node_t* p = L->head;
   printf("!! p init = %d\r\n", (int)p);
   while(p!=NULL) {
      printf("p->key = %d\n", p->key);
      p = p->next;
   }
}

int getListLen(list_t *L) {
   int len = 0;
   node_t* p = L->head;
   while(p != NULL) {
      p = p->next;
      len++;
   }
   return len;
}

void *worker(void *argp) {
   for (int i=0;i<Total/N;i++) 
      List_Insert(&mylist, i);
   //printList(&mylist);
}

void main() {

   List_Init(&mylist);
   pthread_t workers[N];
   int i;


   for (i=0;i<N;i++) {
      Pthread_create(&workers[i], NULL, worker, (void *)i);
   }
   for (i=0;i<N;i++) {
      Pthread_join(workers[i], NULL);
   }
   int len = getListLen(&mylist);
   printf("list len = %d\n", len);
}

void List_Insert(list_t *L, int key) {
   // synchronization not needed
   node_t *new = malloc(sizeof(node_t));
   if (new == NULL) {
      perror("malloc");
      return;
   }
   new->key = key; 
   
   // just lock critical section
   //pthread_mutex_lock(&L->lock);
   int tmp;
   do {
      new->next = L->head;
      tmp = CAS(&(L->head), new->next, new);
   }while(tmp == 0);
   //printf("CurNode(%lu, %d, %lu)\r\n", new, new->key, new->next);
   //printList(L);
   //L->head = new;
   //pthread_mutex_unlock(&L->lock);
}


int List_Lookup(list_t *L, int key) {
   int rv = -1;
   //pthread_mutex_lock(&L->lock);
   node_t *curr = L->head;
   while (curr) {
      if (curr->key == key) {
         rv = 0;
         break;
      }
      curr = curr->next;
   }
   //pthread_mutex_unlock(&L->lock);
   return rv;
}

版权所有，转载请注明出处 luowei.github.io.