Homeworkz

banker.c

#include<stdio.h>
#include<stdlib.h>
#include <sys/time.h>
#include <pthread.h>

typedef struct state {
  int *resource;
  int *available;
  int **max;
  int **allocation;
  int **need;
} State;

// Global variables
int m, n;
State *s = NULL;

// Mutex for access to state.
pthread_mutex_t state_mutex;

// Function declarations
int **allocate_int_matrix(int m, int n);

/* Random sleep function */
void Sleep(float wait_time_ms)
{
  // add randomness
  wait_time_ms = ((float)rand())*wait_time_ms / (float)RAND_MAX;
  usleep((int) (wait_time_ms * 1e3f)); // convert from ms to us
}

/* Return 1 if any values are false, else return 0 */
int any_false(int vals[], int len)
{
  int i;
  for (i = 0; i < len; i++)
  {
    if(vals[i]) return 0;
  }
  return 1;
}

int lessOrEqual(int  *vals1, int *vals2, int len) /* returns bool */
{
  int i;
  for (i = 0; i < len; i++)
  {
    if(vals1[i] > vals2[i]) return 0;
  }
  return 1;
}

int **copy_matrix(int **matrix) {
  int i, j;
  int **new_matrix = allocate_int_matrix(m, n);
  for(i = 0; i < m; i++) {
    for(j = 0; j < n; j++) {
      new_matrix[i][j] = matrix[i][j];
    }
  }

  return new_matrix;
}

void print_vector(int *vector) {
  int i;
  for(i = 0; i < n; i++) {
      printf("%i ", vector[i]);
    }
    printf("\n");
  
}

void print_matrix(int **matrix) {
  int i,j;
  for(i = 0; i < m; i++) {
    for(j = 0; j < n; j++) {
      printf("%i ", matrix[i][j]);
    }
    printf("\n");
  }
}

/* Allocate resources in request for process p, only if it 
   results in a safe state and return 1, else return 0 */
int resource_request(int p, int *request)
{
  pthread_mutex_lock(&state_mutex);
  int i;

  int **newAllocation = copy_matrix(s->allocation);
  int **newNeed = copy_matrix(s->allocation);
  /* Step 1: Allocate work and finish vectors */
  int work[n];
  int finish[m];

  for(i = 0; i < n; i++) {
    work[i] = s->available[i];
    newAllocation[p][i] += request[i];
    newNeed[p][i] -= request[i];
  }

  for(i = 0; i < m; i++) {
    finish[i] = 0;
  }

  /* Step 2 */
  int c;
  while (any_false(finish, m))
  {
    c = 0;
    for (i = 0; i < m; i++)
    {
      if (!finish[i] && lessOrEqual(newNeed[i], &work[i], n))
      {
        int j;
        for (j = 0; j < n; j++)
	{
          work[j] = work[j] + newAllocation[i][j];
	}
        finish[i] = 1;
        c = 1;
      }
    }

    if(c == 0) break;
  }
 
  if(!any_false(finish, m)) {
    for(i=0;i<n;++i) {
      s->allocation[p][i] += request[i];
      s->need[p][i] -= request[i];
      s->available[i] -= request[i]; 
    }
    printf("Got moar resawsiz:\n");
    printf("Request: \n");
    print_vector(request);
    printf("Allocation:\n");
    print_matrix(s->allocation);
    pthread_mutex_unlock(&state_mutex);
    //return 1;
  } else
  {
    pthread_mutex_unlock(&state_mutex);
    return 0;
  }
}

/* Release the resources in request for process p */
void resource_release(int p, int *request)
{
  pthread_mutex_lock(&state_mutex);
  int i;
  for(i=0;i<n;++i) {
    s->allocation[p][i] -= request[i];
    s->need[p][i] += request[i];
    s->available[i] += request[i]; 
  }
  pthread_mutex_unlock(&state_mutex);
}



/* Generate a request vector */
void generate_request(int i, int *request)
{
  int j, sum = 0;
  while (!sum) {
    for (j = 0;j < n; j++) {
      request[j] = s->need[i][j] * ((double)rand())/ (double)RAND_MAX;
      sum += request[j];
    }
  }
  printf("Process %d: Requesting resources.\n",i);
}

/* Generate a release vector */
void generate_release(int i, int *request)
{
  int j, sum = 0;
  while (!sum) {
    for (j = 0;j < n; j++) {
      request[j] = s->allocation[i][j] * ((double)rand())/ (double)RAND_MAX;
      sum += request[j];
    }
  }
  printf("Process %d: Releasing resources.\n",i);
}

/* Threads starts here */
void *process_thread(void *param)
{
  /* Process number */
  int i = (int) (long) param, j;
  /* Allocate request vector */
  int *request = malloc(n*sizeof(int));
  while (1) {
    /* Generate request */
    generate_request(i, request);
    while (!resource_request(i, request)) {
      /* Wait */
      Sleep(100);
    }
    /* Generate release */
    generate_release(i, request);
    /* Release resources */
    resource_release(i, request);
    /* Wait */
    Sleep(1000);
  }
  free(request);
}

int main(int argc, char* argv[])
{
  /* Get size of current state as input */
  int i, j;
  printf("Number of processes: ");
  scanf("%d", &m);
  printf("Number of resources: ");
  scanf("%d", &n);

  /* Allocate memory for state */
  s = (State *) malloc(sizeof(State));
  s->resource = (int *) malloc(sizeof(int)*n);
  s->available = (int *)malloc(sizeof(int)*n);
  s->max = (int **)allocate_int_matrix(m, n);
  s->allocation = (int **)allocate_int_matrix(m, n);
  s->need = (int **)allocate_int_matrix(m, n);
  if (s == NULL) { printf("\nYou need to allocate memory for the state!\n"); exit(0); };

  /* Get current state as input */
  printf("Resource vector: ");
  for(i = 0; i < n; i++)
    scanf("%d", &s->resource[i]);
  printf("Enter max matrix: ");
  for(i = 0;i < m; i++)
    for(j = 0;j < n; j++)
      scanf("%d", &s->max[i][j]);
  printf("Enter allocation matrix: ");
  for(i = 0; i < m; i++)
    for(j = 0; j < n; j++) {
      scanf("%d", &s->allocation[i][j]);
    }
  printf("\n");

  /* Calcuate the need matrix */
  for(i = 0; i < m; i++)
    for(j = 0; j < n; j++)
      s->need[i][j] = s->max[i][j]-s->allocation[i][j];

  /* Calcuate the availability vector */
  for(j = 0; j < n; j++) {
    int sum = 0;
    for(i = 0; i < m; i++)
      sum += s->allocation[i][j];
    s->available[j] = s->resource[j] - sum;
  }

  /* Output need matrix and availability vector */
  printf("Need matrix:\n");
  for(i = 0; i < n; i++)
    printf("R%d ", i+1);
  printf("\n");
  for(i = 0; i < m; i++) {
    for(j = 0; j < n; j++)
      printf("%d  ",s->need[i][j]);
    printf("\n");
  }
  printf("Availability vector:\n");
  for(i = 0; i < n; i++)
    printf("R%d ", i+1);
  printf("\n");
  for(j = 0; j < n; j++)
    printf("%d  ",s->available[j]);
  printf("\n");

  /* If initial state is unsafe then terminate with error */

  /* Seed the random number generator */
  struct timeval tv;
  gettimeofday(&tv, NULL);
  srand(tv.tv_usec);
  
  /* Create m threads */
  pthread_t *tid = malloc(m*sizeof(pthread_t));
  for (i = 0; i < m; i++)
    pthread_create(&tid[i], NULL, process_thread, (void *) (long) i);
  
  /* Wait for threads to finish */
  pthread_exit(0);
  free(tid);

  /* Free state memory */
}

int **allocate_int_matrix(int m, int n)
{
  /* Allocate memory for the elements */
  int *mem = malloc(m * n * sizeof(int));
  /* Allocate memory for the matrix array */
  int **mat = malloc(m * sizeof(int *));
  /* Setup array */
  if (mem != NULL && mat != NULL) {
    int i;
    for (i = 0; i < m; ++i) {
      mat[i] = &mem[i * n];
    }
  } else {
    printf("Out of memory!\n"); exit(-1);
  }
  return mat;
}

list.c

/******************************************************************************
   list.c

   Implementation of simple linked list defined in list.h.

******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include "list.h"

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

/* list_new: return a new list structure */
List *list_new(void)
{
  List *l;

  l = (List *) malloc(sizeof(List));
  l->len = 0;

  /* insert root element which should never be removed */
  l->first = l->last = (Node *) malloc(sizeof(Node));
  l->first->elm = NULL;
  l->first->next = NULL;
  return l;
}

/* list_add: add node n to list l as the last element */
void list_add(List *l, Node *n)
{
  pthread_mutex_lock(&mutex);
  l->last->next = n;
  l->last = n;
  pthread_mutex_unlock(&mutex);
}

/* list_remove: remove and return the first (non-root) element from list l */
Node *list_remove(List *l)
{
  // If list is empty
  if(l->first->next == NULL) {
    return NULL;
  }

  pthread_mutex_lock(&mutex);
  Node *first_non_root = l->first->next;
  Node *second_non_root = l->first->next->next;
  l->first->next = second_non_root;

  // Last element was removed, list is empty now.
  if(second_non_root == NULL) {
    l->last = l->first;
  }
  pthread_mutex_unlock(&mutex);

  return first_non_root;
}

/* node_new: return a new node structure */
Node *node_new(void)
{
  Node *n;
  n = (Node *) malloc(sizeof(Node));
  n->elm = NULL;
  n->next = NULL;
  return n;
}

/* node_new_str: return a new node structure, where elm points to new copy of s */
Node *node_new_str(char *s)
{
  Node *n;
  n = (Node *) malloc(sizeof(Node));
  n->elm = (void *) malloc((strlen(s)+1) * sizeof(char));
  strcpy((char *) n->elm, s);
  n->next = NULL;
  return n;
}

int list_length(List *l)
{
  int size;
  Node *n;
  size = 0;
  pthread_mutex_lock(&mutex);
  for(n = l->first; n != l->last && n != NULL; n = n->next) size++;
  pthread_mutex_unlock(&mutex);

  return size;
}

listtest.c

/******************************************************************************
   Test of list.c

******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include "list.h"

#define THREAD_COUNT 100
#define ELM_PER_THREAD 200000

// FIFO list;
List *add_list;
List *remove_list;

void *add_runner(void *param);
void *remove_runner(void *param);

int thread_count, elm_per_thread, total_elm;
int remove_array[THREAD_COUNT*ELM_PER_THREAD];

pthread_mutex_t remove_mutex = PTHREAD_MUTEX_INITIALIZER;

int main(int argc, char* argv[])
{
  // Initialize
  add_list = list_new();
  remove_list = list_new();
  thread_count = THREAD_COUNT;
  elm_per_thread = ELM_PER_THREAD;
  total_elm = thread_count * elm_per_thread;
  int i;
  int testsFailed;
  testsFailed = 0;

  /*
  / Add test BEGIN
  */
  pthread_t add_thread_ids[thread_count];
  for(i = 0; i < thread_count; i++) {
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_create(&add_thread_ids[i],&attr,add_runner,(void *) i);
  }

  for(i = 0; i < thread_count; i++) pthread_join(add_thread_ids[i], NULL);

  int list_size = list_length(add_list);
  printf("Add test:\nList size: %i, should be: %i\n", list_size, total_elm);
  if(list_size != total_elm) testsFailed = 1;

  /*
  / Add test END
  */


  /*
  / Remove test BEGIN
  */

  // Prepare remove test
  for(i = 0; i < total_elm; i++) {
    remove_array[i] = 0;
    char buffer[8];
    sprintf(buffer, "%i", i);
    list_add(remove_list, node_new_str(buffer));
  }

  pthread_t remove_thread_ids[thread_count];
  for(i = 0; i < thread_count; i++) {
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_create(&remove_thread_ids[i],&attr,remove_runner,(void *) i);
  }
  for(i = 0; i < thread_count; i++) pthread_join(remove_thread_ids[i], NULL);

  list_size = list_length(remove_list);
  printf("Remove test:\nList size: %i, should be: %i\n", list_size, 0);
  if(list_size != 0) testsFailed = 1;

  for(i = 0; i < total_elm; i++) {
    if(remove_array[i] != 1) {
      printf("Element %i was removed %i times\n", i, remove_array[i]);
      testsFailed = 1;
      break;
    }
  }

  /*
  / Remove test END
  */

  if(!testsFailed) {
    printf("Tests suceeded!\n");
  }

  return 0;
}

void *add_runner(void *param)
{
  int tnum = (int) param;
  int i;  
  for(i = 0; i < elm_per_thread; i++) {
    char buffer[8];
    sprintf(buffer, "%i", i);
    list_add(add_list, node_new_str(buffer));	
  }
  
  pthread_exit(0);
}

void *remove_runner(void *param)
{
  int tnum = (int) param;
  int i;  
  Node *n;
  for(i = 0; i < elm_per_thread; i++) {
    n = list_remove(remove_list);
    pthread_mutex_lock(&remove_mutex);
    remove_array[atoi(n->elm)]++;
    pthread_mutex_unlock(&remove_mutex);
  }
  
  pthread_exit(0);
}

procon.c

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include "list.h"

List *fifo;

int pro_count;
int con_count;
int buffer_size;
int product_count;
int produced_count = 0; // How many have we produced?
int consumed_count = 0; // How many have we consumed?

sem_t empty;
sem_t full;
sem_t pro_mutex;
sem_t con_mutex;

void *producer(void *param);
void *consumer(void *param);
void my_sleep(float wait_time_ms);

int main(int argc, char* argv[])
{
  // Our fifo buffer
  fifo = list_new();

  // Collect input from args
  pro_count = atoi(argv[1]);
  con_count = atoi(argv[2]);
  buffer_size = atoi(argv[3]);
  product_count = atoi(argv[4]);

  // Initialize semaphores
  sem_init(&empty, 0, buffer_size);
  sem_init(&full, 0, 0);
  sem_init(&pro_mutex, 0, 1);
  sem_init(&con_mutex, 0, 1);

  // Create thread id arrays
  pthread_t pro_thread_ids[pro_count];
  pthread_t con_thread_ids[con_count];

  // Create producer threads
  int i;
  for(i = 0; i < pro_count; i++) {
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_create(&pro_thread_ids[i],&attr,producer,(void *) i);
  }

  // Create consumer threads
  for(i = 0; i < con_count; i++) {
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_create(&con_thread_ids[i],&attr,consumer,(void *) i);
  }

  // Join threads
  for(i = 0; i < pro_count; i++) pthread_join(pro_thread_ids[i], NULL);
  for(i = 0; i < con_count; i++) pthread_join(con_thread_ids[i], NULL);

  return 0;
}

void *producer(void *param)
{
  int producer_number = (int) param;
  while(1) {
    // Wait if there are no empty spots
    while(sem_trywait(&empty) == -1) {
      if(produced_count >= product_count) return;
    }

    // Produce item
    char buffer[8];
    sem_wait(&pro_mutex);
    if(produced_count >= product_count) { sem_post(&pro_mutex); return; }
    sprintf(buffer, "Item_%i", produced_count++);
    sem_post(&pro_mutex);
    list_add(fifo, node_new_str(buffer));

    printf("Producer %i produced %s. Items in buffer: %i (out of %i).\n", producer_number, buffer, produced_count-consumed_count, buffer_size);
    my_sleep(1000);
    sem_post(&full); // Signal that a spot has been filled
  }

}

void *consumer(void *param)
{
  int consumer_number = (int) param;
  while(1) {
    while(sem_trywait(&full) == -1) {
      if(consumed_count >= product_count) return;
    }

    // Consume item
    Node *n = list_remove(fifo);
    if(n == NULL) printf("Node is null\n");
    char *item = (char *)n->elm;

    sem_wait(&con_mutex);
    consumed_count++;
    sem_post(&con_mutex);

    printf("Consumer %i consumed %s. Items in buffer: %i (out of %i).\n", consumer_number, item, produced_count-consumed_count, buffer_size);
    my_sleep(1000);
    sem_post(&empty); // Signal that an item has been consumed
  }
}

/* Random sleep function */
void my_sleep(float wait_time_ms)
{
  // Seed the random number generator
  struct timeval tv;
  gettimeofday(&tv, NULL);
  srand(tv.tv_usec);
  wait_time_ms = ((float)rand())*wait_time_ms / (float)RAND_MAX;
  usleep((int) (wait_time_ms * 1e3f)); // convert from ms to us
}