Multithreaded Merge Sort

another post about posix threads, we implement the merge sort using threads

  1. divide the array into 2 halves
  2. call merge_sort on both sub array each call in a thread
  3. wait for the threads to finish (using join)
  4. merge the 2 arrays

here i’ve used an array (b) of the same size of a (pre-created array) to avoid allocating new space at each merge call.

BTW using the thread doesn’t improve time complexity, this implementation is nlog(n). If you are interested in a better multi-threaded algorithm refer Introduction to Algorithms – Cormen.

also the code is on github


int* a;
int* b; //sorted array
int n;

struct index{int p,r;};

void* merge_sort(void* param){
    struct index* pr = (struct index*) param;
    int p = pr->p,  r = pr->r , ret1,ret2;
    if (p==r)
        pthread_exit(0);

    pthread_t thread1,thread2;
    struct index pr1,pr2;
    int q = (p+r)/2;
    pr1.p = p;    pr1.r = q;
    pr2.p = q+1;  pr2.r = r;

    ret1 = pthread_create(&thread1,NULL,merge_sort,(void*) &pr1);
    if (ret1>0)
        printf("failed to create new thread 1\n");

    ret2 = pthread_create(&thread2,NULL,merge_sort,(void*) &pr2);
    if (ret2>0)
        printf("failed to create new thread 2\n");

    pthread_join(thread1,NULL);
    pthread_join(thread2,NULL);

    int k = p ,i = p ,j = q+1;

    while (i<=q && j<=r){
        if (a[i] < a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++];
    }
    for (; i<=q ; i++)
        b[k++] = a[i];
    for (; j<=r ; j++)
        b[k++] = a[j];

    for (i= p ; i <= r ;i++)
        a[i] = b[i];

    pthread_exit(0);
    return NULL;
}

Multi-threaded Matrix Multiplication

in this post you’ll find the implementation of iterative matrix multiplication using posix threads.

you can find the complete code with some utility methods on github

Approach 1 (multiply1) : The computation of each element of the output matrix happens in a thread.

struct cell{int i,j;};
void *mulcell(void* param){
	//	passing a struct to overcome the limitation of passing one argument
	struct cell *cel = (struct cell*)param;
	int k, i = cel->i, j = cel->j;

	for (k = 0; k < p; ++k){
		c[i][j] += a[i][k] * b[k][j];
	}

	pthread_exit(0);
	return NULL;//will never execute
}
void multiply1(){
	// The computation of each element of the output matrix happens in a thread.
	int i,j,r,t;

	//dynamically allocate #cells threads
	pthread_t** threads = (pthread_t**) malloc(sizeof(pthread_t*)*m*n);
	struct cell** cells = (struct cell**) malloc(sizeof(struct cell*)*m*n);

	for (i = 0; i < m; ++i) {
		for (j = 0 ; j < n ; j ++){
			t = i*n + j;
			threads[t] =(pthread_t*) malloc(sizeof(pthread_t));
			cells[t] = malloc(sizeof(struct cell));
			cells[t]->i = i ; cells[t]->j = j;
			r = pthread_create(threads[t], NULL, mulcell, (void*) cells[t]);
			if (r<0)
				printf("failed to create thread at mul1 at (i,j) %d,%d\n",i,j);
		}
	}

	//wait for the threads to finish
	for (i = 0; i < m*n; ++i){
		pthread_join(*threads[i],NULL);
		free(cells[i]);
//		 no need to free threads[i] as its already freed by pthread_exit();
	}
	//free allocated memory
	free(threads);
	free(cells);
}

Approach 2 (multiply2): The  computation of each row of the output matrix happens in a thread.

void *mulrow(void* row){
	int j, i = *((int*)row) ,k;

	for (j = 0 ; j < n ; j ++)
		for (k = 0 ; k < p ; k++)
			c[i][j] += a[i][k] * b[k][j];
	pthread_exit(NULL);
	return NULL;// anyway this line won't be processes yet it's added to prevent eclipse from showing warnings
}
void multiply2(){
	//The computation of each row of the output matrix happens in a thread.
	int i,r;

	//dynamically allocate #rows threads
	pthread_t** threads = (pthread_t**) malloc(sizeof(pthread_t*)*m);
	int* rows = (int*) malloc(sizeof(int)*m);

	for (i = 0; i < m; ++i) {
		threads[i] =(pthread_t*) malloc(sizeof(pthread_t));
		rows[i] = i;
		r = pthread_create(threads[i], NULL, mulrow, (void*) &rows[i]);
		if (r<0)
			printf("failed to create thread at mul2 at i =  %d\n",i);
	}

	//wait for the threads to finish
	for (i = 0; i < m; ++i)
		pthread_join(*threads[i],NULL);

	//free allocated memory
	free(threads);
	free(rows);
}

here is a benchmark method which i’ve used to calculate the average running time.

long long benchmark(int nElements, int itrNum , void(*myfn)()){
	n = m = p = nElements;
	a = (int**) malloc(sizeof(int*)*nElements);
	b = (int**) malloc(sizeof(int*)*nElements);
	c = (int**) malloc(sizeof(int*)*nElements);

	int i,j,k;
	long long averagetime =0 ,t1,t2;
	for (i = 0; i < nElements; ++i){
		a[i] = (int*) malloc(sizeof(int)*nElements);
		b[i] = (int*) malloc(sizeof(int)*nElements);
		c[i] = (int*) malloc(sizeof(int)*nElements);
	}
	for (k = 0; k < itrNum; ++k) {
		for (i = 0; i < nElements; ++i)
			for (j = 0; j < nElements; ++j)
				a[i][j] =rand()%1001 , b[i][j] =rand()%1001;

		t1 = curTime();
//		multiply1();
		(*myfn)();
		t2 = curTime();
		averagetime += (t2-t1);
	}
	averagetime/=itrNum;
	printf("benchmark using a[%d][%d] * b[%d][%d]: average on %d samples = %lld usec\n",
			nElements,nElements,nElements,nElements,itrNum,averagetime);
	return averagetime;
}

Simple Shell

Simple Shell, that was the first assignment of the OS course i’m enrolled in this year.
simply we were required to make a simple Unix shell featuring executing commands (foreground and background -using &- ) using system calls. Handling commands with several arguments like “ls -l”

to keep is simple here is the code you can also find the code on github here

 ============================================================================
 Name        : SimpleShell.c
 Author      : Ashraf Saleh
 Version     : 1.0
 Copyright   : leonardo7 on github or
 Description : Simple Shell on linux environment, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <sys/types.h>
#include <unistd.h>
#include <errno.h>
#include <sys/param.h>

#define MAX_BUFR 300
#define MAX_ARGS 100
char lineBuffer[MAX_BUFR] ;
char* cur_arg;
char* args[MAX_ARGS]; // arguments of a command
int  argc ;// number of arguments
FILE *log_file;
// related to directory handling
char workingDirectory[PATH_MAX];
char oldWorkingDirectory[PATH_MAX];
char default_path[100];
char host_name[HOST_NAME_MAX] = "host" ;
char usr_name[LOGIN_NAME_MAX] = "user";

void parentHandle(pid_t child, int _wait){
    int status;
    if (_wait){
        waitpid(child, &status,0);
        fprintf(log_file,"%d\t terminated \t SIGCHILD \t %d\n",child,status);
        printf("%d\t terminated \t SIGCHILD \t %d\n",child,status);
        fflush(log_file);
    }
}

void childHandle (){
    execvp(args[0],args);
    // if the program arrives here, an error must be happened
    perror("");
    exit(1);
}

void childSignalHandler(int signum){
    pid_t pid;
    // using the while loop to ensure that all terminted process are killed (no zombie)
    int status;
    while ((pid = waitpid(-1, &status, WNOHANG )) > 0){
        fprintf(log_file,"%d\t terminated \t SIGCHILD \t %d\n",pid,status);
        fprintf(stderr,"%d\t terminated \t SIGCHILD \t %d\n",pid,status);
    }
    fflush(log_file);
}

void HandleDirectoryCommands(){
    if (argc == 1)// "cd"
        strcpy(workingDirectory, default_path);

    else //"cd ..", "cd {Directory}" or "cd {absolute path}"
        strcpy(workingDirectory,args[1]);

    int status = chdir(workingDirectory);
    if (status != 0)
        perror("");

    getcwd(workingDirectory,PATH_MAX);
}

int main() {
    // setting the default path to the path where the executable file exists
    getcwd(default_path,100);//setting the default path
    log_file = fopen("log.txt", "w");
    const	char* delimeter = " \t\n";
    const char* exitCommand = "exit";
    int wait_request;

    //register new signal handler for SIGCHILD
    signal(SIGCHLD, childSignalHandler);
    //retrieving the host name and username
    gethostname (host_name,HOST_NAME_MAX);
    getlogin_r(usr_name, LOGIN_NAME_MAX);

    //set working directory
    chdir("/home");
    getcwd(workingDirectory,PATH_MAX);

    while (1){
        printf("%s@%s~%s$ ",usr_name,host_name,workingDirectory);
        fgets(lineBuffer,MAX_BUFR,stdin);

        //tokenizing the lineBuffer
        argc = 0 ;
        args[argc++] = strtok(lineBuffer,delimeter);
        while ((args[argc++] = strtok(NULL,delimeter) ) != NULL && argc<MAX_ARGS);
        argc--;

        //checking if command == "exit"
        if(strcmp(args[0], exitCommand) == 0){
            printf("closing\n");
            fclose(log_file);
            exit(0);
        }
        // changing directory
        else if (strcmp(args[0], "cd") == 0){
            HandleDirectoryCommands();
            continue ;
        }

        // checking the '&'
        wait_request = 1;
        if (strcmp(args[argc-1],"&") == 0){
            args[argc-1] = NULL;
            wait_request = 0;
        }

        // forking new process
        pid_t pid = fork();
        if ( pid > 0 )
            parentHandle(pid, wait_request); //parent process
        else if (pid == 0)
            childHandle(); //child process
        else {
            //failed to fork
            perror("failed to fork a new child\n");
        }
    }

    fclose(log_file);
    return 0;
}