Home CS439

CS439: Principles of Computer Systems

Homework 2, Part 1

Due in Section on Friday, February 5, 2016

Part 1 of the homeworks must be completed before section and brought to section. Please refer to the homework turnin instructions.

  1. Run the following command in your command line (it generates 10k random integers less than 100 and stores them in the num.txt file.):
    $ for i in {1..10000}; do echo $(($RANDOM % 100)); done > nums.txt
    
    How many 12s are in num.txt? How many 10s? How many 87s?
    What command did you use to answer this question?

    Hint: You don't even need to open the file to answer this question. You may find grep and wc useful.

  2. How much more expensive is a system call than a procedure call? Write a simple test program to compare the cost of a simple procedure call to a simple system call ("getuid()" is a good candidate on UNIX; see the man page.) (Note: be careful to prevent the optimizing compiler from "optimizing out" your procedure calls. Do not compile with optimization on.)
    • Explain the difference (if any) between the time required by your simple procedure call and simple system call by discussing what work each call must do (be specific). [Note: Do not provide the source code for your program, just the results].

    Hint: You should use system calls such as gethrtime() or gettimeofday() for time measurements. Design your code such that the measurement overhead is negligible. Also, be aware that timer values in some systems have limited resolution (e.g., millisecond resolution).

  3. Given the following piece of code:
       main(int argc, char** argv)
       {
          forkThem(5);
       }
    
       void forkThem(int n)
       {
          if(n>0)
          {
             fork();
             forkThem(n-1);
          }
       }
    

    How many processes are created if the above piece of code is run?

  4. Consider a system using a multilevel feedback queue scheduler. Its scheduler is configured to have four queues, which are, in order of highest priority to lowest priority: Q1, Q2, Q3, and Q4. The queues have quantums sized 5s, 10s, 20s, and 40s, respectively.

    For each of the following three processes, determine which queue it is in when it begins its final quantum.

    • Process A, runtime 40s, blocks every 2s.
    • Process B, runtime 32s, never blocks.
    • Process C, runtime 70s, blocks at 7s, 11s, 25s, 42s, 48s, where those times are points in its execution.

  5. In the code below, indicate where each variable is stored (e.g., stack, heap, static data segment), and whether that variable would be shared by the threads in a multi-threaded program. If applicable, indicate where the space that variable points to is allocated.

    int i;   
    char * j; 
    
    void foo(int a){
    
       int b; 
       static float c;
    
       /*do stuff*/
    }
    
    int main(int argc, char**argv){
    
       int * m; 
       int g;   
       double z;
    
       j = malloc(MAXBUF*sizeof(char)); 
    
       createThread(0, foo(), 2);
       createThread(1, foo(), 4);
    
       /*do stuff*/
    }