IC221: Systems Programming (SP17)


Home Policy Calendar Units Assignments Resources

HW 13: Threading

Instructions

  • You must turn in a sheet of paper that is neatly typed or written answering the questions below. (You are strongly encouraged to type your homework.)
  • This homework is graded out of 100 points. Point values are associated to each question.

Questions

  1. (15 points) For each of the statements, indicate if the statement is true or false. You must add a brief statement to support your claim.
    1. Threads are created just like processes by calling fork() except instead of checking the return value of fork() a specific function is used.
    2. Threads are scheduled just like other processes because POSIX threads are treated like individual processes by the OS.
    3. Like multiple processes, threads provide resource isolation. Two threads from the same program do not share memory or other resources.
    4. It's not possible for two threads of the same process to run simultaneously.
    5. When any of the threads terminates, such as a call to exit(), all threads terminate.
  2. (5 points) What are the equivalent thread command for the following system calls:
    1. fork()
    2. wait()
  3. (15 points) Match the following terms, identifiers, functions to the descriptions below.

    tid, pid, pid_t, pthread_t, syscall(SYS_getttid), getpid(), pthread_self()

    1. Retrieve the POSIX thread identifier for the calling thread
    2. The process identifier, shared by all threads of a multi-threaded program.
    3. Retrieve the UNIX OS thread identifier of the calling thread
    4. Retrieve the UNIX OS process identifier of the calling process
    5. The type of a POSIX thread identifier
    6. The type of the UNIX OS thread identfier
    7. The thread identifier, unique to each thread and equal to the pid of the main thread
  4. (5 points) Complete the following program below. The thread should print the command line argument passed to it:

    void * startup( void * args){
      char * str; //varible to reference string to print
    
    
    
      printf( );
      return NULL;
    }
    int main(int argc, char * argv[]){
    
      pthread_t thread; //POSIX thread identifier
    
    
      //create a thread to run startup with argument argv[1]
      pthread_create(&thread, NULL, startup, argv[1]);
    
    
    
    
      return 0;
    }
    
  5. Answer the following questions about the program below. You could assume this would be run on a lab machine, if you wanted to run it to answer the questions (hint!).

    #include <stdio.h>
    #include <stdlib.h>
    #include <pthread.h>
    
    void * foo(void * args){
      pthread_t thread;
    
      if(args == NULL){
        pthread_create(&thread, NULL,
                       foo, (void *) 1);
      }
    
      while(1);
    }
    
    int main(int argc, char * argv[]){
      pthread_t threads[4];
      int i;
    
      for(i=0;i<4;i++){
        pthread_create(&threads[i], NULL,
                       foo, NULL);
      }
    
      while(1);
    }
    
    1. (5 points) Based on the code, what are the two possible values for the argument to foo()?
    2. (5 points) When you run this program, how many threads are running. You could use ps -L to count.
    3. (5 points) According to top what percent CPU does the program consume? Explain.
  6. (5 points) Explain why the following code snippet is not atomic?

    balance = balance+1
    
  7. (5 points) For the code below, what is the expected output? Would you always get what you expect? Explain.

    int shared = 0;
    
    void * fun(void * args){
      int i;
      for(i=0;i<100;i++){
        shared++;
      }
      return NULL;
    }
    
    int main(){
      pthread_t t1,t2;
      pthread_create(&t1, NULL, fun, NULL);
      pthread_create(&t2, NULL, fun, NULL);
    
      pthread_join(t1, NULL);
      pthread_join(t2, NULL);
    
      printf("shared: %d\n", shared);
    
    }
    
  8. (5 points) For the code in the previous question, identify the critical section. What makes this section critical?
  9. (5 points) Consider the naive locking solution below. Does this prove proper locking? Explain why or why not.

    int shared;
    int lock;
    
    void * fun(void * args){
      int i;
    
      for(i=0;i<100;i++){
        while(lock > 0);//spin
    
        lock = 1; //set lock
    
        shared++; //increment
    
        lock = 0; //unlock
      }
    
      return NULL;
    }
    
  10. (5 points) Explain why using a mutex avoids issues of a lack of atomicity in lock acquisition?
  11. (10 points) The cod below uses a course locking strategy, rewrite it to use fine locking.

    pthread_mutext_t lock;
    
    int avail = MAX_FUNDS;
    int local_1 = 0;
    int local_2 = 0;
    
    void * fun(void * args){
      int v,i;
    
      for(i=0; i < 100; i++){
        v = random() % 100;
    
        pthread_mutext_lock(&lock);
    
        if(avail - v > 0){
          avail -= v;
        }
    
        if(random() % 2){
          local_1 += v;
        }else{
          local_2 += v;
        }
    
        pthread_mutext_unlock(&lock);
    
      }
    
      return NULL;
    
    }
    
  12. (5 points) What is deadlock? Provide a small, (pseudo-) code example of how deadlock can arise.
  13. (5 points) Explain a strategy for avoiding deadlock.