Question

In: Computer Science

How could we use Pthreads to find the minimum value in an array without mutex locks?...

How could we use Pthreads to find the minimum value in an array without mutex locks? Would this version be slower? If so, why?

Solutions

Expert Solution

What are PThreads?

  1. POSIX Threads, or Pthreads, is a POSIX standard for threads. The standard, POSIX.1c, Threads extensions (IEEE Std 1003.1c-1995), defines an API for creating and manipulating threads.

The Pthread API: Pthreads API can be grouped into four->

  1. Thread management: Routines that work directly on threads.
  2. Mutexes: Routines that deal with synchronization, called a "mutex".
  3. Condition variables: Routines that address communications between threads that share a mutex.
  4. Synchronization: Routines that manage read/write locks and barriers.

Creating Threads:

  1. Our main() program is a single, default thread. All other threads must be explicitly created by the programmer.
  2. pthread_create creates a new thread and makes it executable. This routine can be called any number of times from anywhere within our code.
  3. pthread_create (pthread_t *thread, pthread_attr_t *attr, void *(*start_routine)(void *), void *arg)
  4. The return value from the pthread_create() call will be zero if it's successful, otherwise, it returns an error.

Code for finding the minimum value in an array using pthreads:

# include <stdio.h>
# include <pthread.h>
# define N 10

struct StructMin{
    int iMax;
    int iMin;
};

int arr[N];

void *thread_search_min(void *para){
    struct StructMin *st;
    st=(struct StructMin*)malloc(sizeof(struct StructMin));
    int i;
    st->iMin=arr[N/2];
    for(i=N/2 + 1;i<N;i++){
        if(arr[i] < st->iMin){
            st->iMin=arr[i];
        }
    }
    pthread_exit((void*)st);        
}

int main(){
    pthread_t tid;
    struct StructMin *st_main,*st_th;
    int RetVal, i;
    st_main=(struct StructMin*)malloc(sizeof(struct StructMin));
    for(i=0;i<N;i++){
        printf("Enter Value of arr[%d] :",i);
        scanf("%d",&arr[i]);
    }        
    pthread_create(&tid,NULL,thread_search_min,NULL);
    st_main->iMin=arr[0];
    for(i=1;i<N/2;i++){
        if(arr[i] < st_main->iMin){
            st_main->iMin=arr[i];
        }
    }
    pthread_join(tid,(void**)&st_th);            
    if(st_main->iMin <=st_th->iMin){
        RetVal=st_main->iMin;
    }
    else{
        RetVal=st_th->iMin;
    }
    printf("Final Min : %d \n",RetVal);
    return 0;
}

Algorithm:

  • Let us define array size as Sz.
  • Create n threads
  • Each thread will process (Sz/n) array elements and will find a minimum element from it.
  • Finally, compute the minimum from the minimum value reported by each thread

Mutex Lock: A mutex lock is a mechanism that can be acquired by only one thread at a time. For other threads to get the same mutex, they must wait until it is released by the current owner of the mutex.

Would this version be slower and why?

I can say that It basically depends on the user or programmer ->

If you are using one lock per thread, so that's why when you use all the mutexes you don't see an increase in the execution time.

If all the threads are working on the same file, all they should be accessing it using the same lock (otherwise you will have incorrect results: all the threads trying to modify the file at the same time).

If you use just one global lock, and this is the worst-case scenario that many threads always trying to lock the same mutex may result in performance worse than a single thread serving all requests.

The most vital point is the waiting time. Your threads should spend only a fraction of their time waiting on mutexes. If they are waiting too often, then you are losing concurrency. The overhead costs of a mutex relate to the test-and-set operation and the system call that implements a mutex

Conclusion: A program without using mutex locks would be faster than using them. Besides, Implementing a program using mutex locks is much more secure if you have some functions which you shouldn't get access easily. And implementing using mutex locks in a proper way, like keeping them in same directory etcc. will increase execution time a very little bit and that can neglible if porperly implemented witout losing concurrency.


Related Solutions

Write a Pthreads program 'Dining-Philosophers.c' to implement the classical 'Dining-Philosophers'problem by using Pthreads mutex locks and...
Write a Pthreads program 'Dining-Philosophers.c' to implement the classical 'Dining-Philosophers'problem by using Pthreads mutex locks and condition variables. To implement the program, please followthe hints below. (a) The detailed 'Dining-Philosophers' problem statement: Refer to Page 71 ~ Page 72 in 'Lecture-08.pptx'    (b) The introduction to Pthreads mutex locks and condition variables: Refer to Page 17 ~ Page 39 in'Lecture-08.pptx'    (c) Creating five philosophers, each of which will run as a separate thread. Philosophers alternatebetween thinking and eating: The activities...
Find the second minimum of an integer array? //this is the template we follow. Answer must...
Find the second minimum of an integer array? //this is the template we follow. Answer must run in linear time (i.e. no nested loops). package findsecondminimumtest; import java.util.Arrays; import java.util.NoSuchElementException; public class FindSecondMinimumTest { /** * Find the second minimum of an integer array * * @param a is the array * @return the second minimum if array has at least two elements and it * indeed has a second minimum. If array length is less than two, it throws...
Find the median (middle value) of an array of numbers, which we will assume are all...
Find the median (middle value) of an array of numbers, which we will assume are all distinct. For example, if there are 27 elements, then you must return the 14th smallest (which is also the 14th largest). The strategy used to solve this problem is somewhat like the quicksort algorithm, but has some important differences. Consider choosing a pivot element and partitioning the input so that the elements less than the pivot are to its left, and those larger than...
Given a minimum unimodal array of integers, run the binary search algorithm to find the minimum...
Given a minimum unimodal array of integers, run the binary search algorithm to find the minimum element. You need to show the initial and the iteration-level values of the left index, right index and middle index as well as your decisions to reduce the search space in each iteration. 42 39 2 6 9 16 20 28 31 34
Use any C program without using PTHREADS calculate time taken to execute program. Write same program...
Use any C program without using PTHREADS calculate time taken to execute program. Write same program of question 1 using PTHREADS. Calculate time taken to execute program.(1 mark) Identify data races in above program and explain why this situation occurred with an example (1 mark) Rewrite the code to avoid data races should use any of the THREE techniques.(1.5 marks) please I need the c code.. critical section mutex solution semaphore functions Barriers Read-Write Locks Run program using 1, 2,...
Divide and conquer approach to find the minimum absolute difference in array A[lo..hi] Input an array...
Divide and conquer approach to find the minimum absolute difference in array A[lo..hi] Input an array A[lo..hi] of n real numbers. Requirement: Shouldn't use a sorting algorithm. Complexity O(nlgn)
implement in LEGV8 find the smallest value in an array.
implement in LEGV8 find the smallest value in an array.
Write a c++program using queue to find the minimum value in a queue. Use the above...
Write a c++program using queue to find the minimum value in a queue. Use the above program for implementing queue. You must use dequeue function to read values from queue.  
how to use routh array find out the number of poles on the rhp, lhp and...
how to use routh array find out the number of poles on the rhp, lhp and jω-axis?
(in java) Find the maximum value and minimum value in milesTracker. Assign the maximum value to...
(in java) Find the maximum value and minimum value in milesTracker. Assign the maximum value to maxMiles, and the minimum value to minMiles. Sample output for the given program: Min miles: -10 Max miles: 40 given code below (please bold the solution, thank you!) import java.util.Scanner; public class ArraysKeyValue { public static void main (String [] args) { Scanner scnr = new Scanner(System.in); final int NUM_ROWS = 2; final int NUM_COLS = 2; int [][] milesTracker = new int[NUM_ROWS][NUM_COLS]; int...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT