web pages for usp and its programs
GNU make document
note of activation record
exercise 1: a simple C program
- Write a C program which reads characters from stdin and writes them to stdout. It is like 'cat' without arguments but with the following exceptions.
  When the character is
  - an uppercase character, converted it to lowercase
  - a lowercase character, converted it to uppercase
  - a digit, i.e. '0'..'9', converted it to '9'.
- For example:
```
       $ cat IN 
       this is KLIM.
       I have $1024.
       $ cat IN | ./a.out 
       THIS IS klim.
       i HAVE $9999.
       $
       
```
- Due: 2020/Mar/04, 00:05
  You have to put your program under ~/usp-1082/exer1.

exercise 2: probing argv[] and environ[]

Write a program which prints the values of argc, argv[], and environ[]. Also their addresses are printed. Based on the printed information, you can figure out the memory layout of argc, argv[], and environ[].

For example:

     $ ./a.out klim is not milk
     argc is 5
     argv[0]: ./a.out
     argv[1]: klim
     argv[2]: is
     argv[3]: not
     argv[4]: milk
     environ[0]: CPLUS_INCLUDE_PATH=/usr/lib64/qt/include
     environ[1]: NNTPSERVER=news.ncnu.edu.tw
     environ[2]: MANPATH=/home/klim/man:/usr/local/info:/usr/local/man:/usr/man:/usr/share/texmf/man
     environ[3]: HOSTNAME=lilina.csie.ncnu.edu.tw
     .....
     environ[34]: G_BROKEN_FILENAMES=1
     environ[35]: _=./a.out
     environ[36]: OLDPWD=/home/klim/course/usp-1072/my-try
     
     argc      is resided at 0x7ffdc3b2dbbc
     argv      is resided at 0x7ffdc3b2dbb0
     environ   is resided at 0x601040
     argv[]    is resided at 0x7ffdc3b2dcb8
     environ[] is resided at 0x7ffdc3b2dce8
     value of argv[ 0] is 0x7ffdc3b2f4ba
     value of argv[ 1] is 0x7ffdc3b2f4c2
     value of argv[ 2] is 0x7ffdc3b2f4c7
     value of argv[ 3] is 0x7ffdc3b2f4ca
     value of argv[ 4] is 0x7ffdc3b2f4ce
     value of argv[ 5] is (nil)
     value of env [ 0] is 0x7ffdc3b2f4d3
     value of env [ 1] is 0x7ffdc3b2f4fc
     ......
     value of env [35] is 0x7ffdc3b2ffbd
     value of env [36] is 0x7ffdc3b2ffc7
     $

If there are too many environment strings to display, you can try to use ``env'' to get a cleaner environment. For example:

     $ env -i A=1 B=ohio ./a.out hello
     argc is 2
     argv[0]: ./a.out
     argv[1]: hello
     environ[0]: A=1
     environ[1]: B=ohio

     argc      is resided at 0x7fff487472ec
     argv      is resided at 0x7fff487472e0
     environ   is resided at 0x601040
     argv[]    is resided at 0x7fff487473e8
     environ[] is resided at 0x7fff48747400
     value of argv[ 0] is 0x7fff48748fd7
     value of argv[ 1] is 0x7fff48748fdf
     value of argv[ 2] is (nil)
     value of env [ 0] is 0x7fff48748fe5
     value of env [ 1] is 0x7fff48748fe9
     $

deadline: 2020/Mar/11, 00:05
Put your files under ~/usp-1082/exer2

exercise 3: simulating env
- Refer to section 2.12.
- You have to support at least the following four usages.
```
       $ env                  
       $ env cmd arg1 arg2 ....
       $ env -i
       $ env -i e1=v1 e2=v2 .... cmd arg1 arg2 ....
       
```
- Note that there may be more than one environment string and there may be more than one argument for the cmd. To invoke system(), you have to combine `cmd' and all the `arg1 arg2 ....' to form a single string, which is then passed to system().
- deadline: 2020/Mar/18
- Put your files under ~/usp-1082/exer3

exercise 4: creating processes with fork()

Write a program which will create a process tree.
Each process will print a line to show its pid and ppid.

Use wait() to ensure the lines be printed in post-order.

      $ echo $$
      29554                               # pid of the shell
      $ ./a.out                           #
      I'm 30027, my parent is 29554       # only one process
      $ ./a.out 2                         #
      I'm 30041, my parent is 30040       #    30040
      I'm 30042, my parent is 30040       #     / \
      I'm 30040, my parent is 29554       # 30041  30042 
      $ ./a.out 1 1 1                     #              30049 
      I'm 30052, my parent is 30051       #                | 
      I'm 30051, my parent is 30050       #              30050 
      I'm 30050, my parent is 30049       #                | 
      I'm 30049, my parent is 29554       #              30051 
      $ ./a.out 2 3 2                     #                |
      I'm 30058, my parent is 30057       #     30057    30052
      I'm 30060, my parent is 30059       #     /    \
      I'm 30061, my parent is 30059       # 30058   30059
      I'm 30063, my parent is 30062       #        /  |  \
      I'm 30064, my parent is 30062       #   30060 30061 30062
      I'm 30062, my parent is 30059       #               /  \
      I'm 30059, my parent is 30057       #            30063 30064
      I'm 30057, my parent is 29554       #
      $

deadline: 2020/Mar/25, 00:05
Put your files under ~/usp-1082/exer4

exercise 5: practicing wait()

Refer to the description of exercise 2 (usp-982) for explanation of the code .
Remove the wait(NULL) in the loop. After the line of printing a message to stderr, you should insert code like:
If the process is a leaf,
```
        while(1) pause();
      
```
else (the process is an internal node)
```
        while there are children alive do 
          waiting..
        exit(...);   
      
```
The internal node should wait for all children, and for each child, when waited, reports the signal number if it was terminated by a signal, or the value returned if it exited though exit(). In either case, a number is gained from the child. Those numbers from children are summed and the sum is used as the argument of exit(). This is to say the sum is the return value of this process.
Refer to example 3.22 for the usage of wait().
To test your program, you have to open another window through which you can kill a process with the command `kill'.
For example, to kill a process which pid is 12011 with signal 15, you can type 'kill -15 12011'.

For example:

      $ ./a.out ddduuduu abcd                      a
      I'm c, my pid=3590, and my ppid=3589        / \
      I'm b, my pid=3589, and my ppid=3588       b   d
      I'm d, my pid=3591, and my ppid=3588       |
      I'm a, my pid=3588, and my ppid=3295       c
      Child 3590 is terminated with signal 3.       $ kill -3 3590
      Child 3589 exits with value 3.
      Child 3591 is terminated with signal 2.       $ kill -2 3591
      $ echo $?                            # Check the return value of root.
      5                                    # It is the sum of 2 and 3.
      $ ./a.out ddduuduu abcd              # Run it agagin.
      I'm c, my pid=3594, and my ppid=3593 # This time we try to kill the 
      I'm b, my pid=3593, and my ppid=3592 # internal node. The leaf node will
      I'm d, my pid=3595, and my ppid=3592 # be an orphan and be adopted by init
.
      I'm a, my pid=3592, and my ppid=3295 
      Child 3593 is terminated with signal 4.       $ kill -4 3593
      Child 3595 is terminated with signal 15.      $ kill -15 3595
      $ echo $?
      19
      $ ps -ef | grep a.out                # Find the orphan. Check its ppid.
      klim      3594     1  0 13:39 pts/0    00:00:00 ./a.out ddduuduu abcd
      klim      3597  3295  0 13:40 pts/0    00:00:00 grep a.out
      $

deadline: 2020/Apr/01, 00:05
Put your files under ~/usp-1082/exer5

exercise 6: matrix multiplication

Write a program to do matrix multiplication. For example,
```
 $ ./mul matrix-a matrix-b matrix-c 
```
The program will multiply matrix-a with matrix-b and store the result into matrix-c. The format of a matrix file is:
First 8 bytes stores two integers, m and n, which denote the number of row and the number of column of this matrix.
Following 4*m*n bytes store the elements of the matrix. They are all floating numbers and stored in row major.
The integers, m and n, and the floating numbers are all stored in big-endian.
Only the functions mentioned in textbook are allowed. Do NOT use fprintf(), fopen(), fread(), fwrite, ....
Due: 2020/Apr/8 00:05

For example:

      $ od -A none -N 8 --endian=big -t d4 m23   # show first two integers
                 2           3
      $ od -A none -j 8 --endian=big -t f4 m23   # show remaining elements
                   1.2             0.8               0             0.1
                   0.2            11.8
      $ od -A none -N 8 --endian=big -t d4 m34
                 3           4
      $ od -A none -j 8 --endian=big -t f4 m34
                     1               2               3               4
                     5               6               7               8
                     0               1               0               1
      $
      $ ./mul m23 m34 k24
      $
      $ od -A none -N 8 --endian=big -t d4 k24
                 2           4
      $ od -A none -j 8 --endian=big -t f4 k24 
                   5.2       7.2000003             9.2       11.200001
                   1.1       13.200001             1.7            13.8
      $

exercise 7: practicing pipe()

Refer to the description of exercise 2 (usp-982) for explanation of code .
Use the code shown above to build a process tree, but between a parent and each of its children you have to create two pipes. One pipe is for parent's sending to child, the other is for child's sending to the parent.

After created, each process will do something as follows.

      loop
        if root then  ch = get a char from stdin
                else  ch = get a char from parent
      
        if ch==label then ch=PRE
        if ch==PRE   then show this process's info
        for each child  do
          send ch to child
          get ack from child 

        if not root then send ack to parent
        if ch='q' then break
      forever

For example:

    $ ./a.out ddduduuddudduuuu abcdefgh            #          a
    I'm a, my pid=1734572720, and my ppid=24973    #       /     \
    I'm e, my pid=1734572720, and my ppid=25546    #      b       e
    I'm b, my pid=1734572720, and my ppid=25546    #     /  \    /  \
    I'm g, my pid=1734572720, and my ppid=25548    #    c    d  f    g
    I'm f, my pid=1734572720, and my ppid=25548    #                 |
    I'm d, my pid=1734572720, and my ppid=25547    #                 h
    I'm c, my pid=1734572720, and my ppid=25547    #
    I'm h, my pid=1734572720, and my ppid=25550    #
    a
    I'm a, my pid=25546, and my ppid=24973
    I'm b, my pid=25547, and my ppid=25546
    I'm c, my pid=25551, and my ppid=25547
    I'm d, my pid=25552, and my ppid=25547
    I'm e, my pid=25548, and my ppid=25546
    I'm f, my pid=25549, and my ppid=25548
    I'm g, my pid=25550, and my ppid=25548
    I'm h, my pid=25553, and my ppid=25550
    b
    I'm b, my pid=25547, and my ppid=25546
    I'm c, my pid=25551, and my ppid=25547
    I'm d, my pid=25552, and my ppid=25547
    e
    I'm e, my pid=25548, and my ppid=25546
    I'm f, my pid=25549, and my ppid=25548
    I'm g, my pid=25550, and my ppid=25548
    I'm h, my pid=25553, and my ppid=25550
    g
    I'm g, my pid=25550, and my ppid=25548
    I'm h, my pid=25553, and my ppid=25550
    d
    I'm d, my pid=25552, and my ppid=25547
    q
    $

Deadline: 2020 Apr 15 00:05am
Put your file(s) under ~/usp-1082/exer7

exercise 8: practicing select() or poll()

Generate a bidirectional ring. Refer to program 7.1. The argv[1] specified the number of processes.

After the ring is setup, the root process then does something like:

        loop
            read from stdin 
            if got 'f' then 
              got a number, n
              send 0 1 n to the clockwise next process
              loop 
                read three numbers, a,b,n  from clockwise previous process
                if n is zero, then break
                write b, a+b,n n-1 to the clockwise next process
              end loop
              write first number, a,  out
            if got 'p' then 
              write a token to the anti-clockwise next process
              read a token from anti-clockwise previous process
              show pid
            if got 'q' then 
              write a token to the anti-clockwise next process
              read a token from anti-clockwise previous process
              exit
        end loop

Each child does something like:

        loop
           monitor two inputs simultaneously 
           (one clockwise and another anti-clockwise)
           if clockwise input is ready then 
             read three numbers, a,b,n, from clockwise previous process
             show them
             if n > 0 then write b (a+b) n-1  to clockwise next process
                      else write a b     0    to clockwise next process
                     
           if anti-clockwise input is ready then
             read  a token from anti-clockwise previous process
             write a token to anti-clockwise previous process
             if this token means 'p' then show pid
             if this token means 'q' then exit
        end loop

Due: 2020/Apr/29 00:05

For example:

       $ ./a.out 5
       f 7
       I am  4020, I got   0   1   7
       I am  4021, I got   1   1   6
       I am  4022, I got   1   2   5
       I am  4023, I got   2   3   4
       I am  root, I got   3   5   3
       I am  4020, I got   5   8   2
       I am  4021, I got   8  13   1
       I am  4022, I got  13  21   0
       I am  4023, I got  13  21   0
       I am  root, I got  13  21   0
       I am  root. Fib(7) = 13
       p
       I am  4023
       I am  4022
       I am  4021
       I am  4020
       I am  4019, the root
       f 8
       I am  4020, I got   0   1   8
       I am  4021, I got   1   1   7
       I am  4022, I got   1   2   6
       I am  4023, I got   2   3   5
       I am  root, I got   3   5   4
       I am  4020, I got   5   8   3
       I am  4021, I got   8  13   2
       I am  4022, I got  13  21   1
       I am  4023, I got  21  34   0
       I am  root, I got  21  34   0
       I am  root. Fib(8) = 21
       q
       $

exercise 9: practicing sigaction

Similar to exercise 8, but the ring is uni-directional. So just refer to program 7.1 for instruction.
The argv[1] specified the number of processes.
After the ring is setup, each process will wait for three signals. One is for sending fibonacci numbers, one for printing my pid, and the last one for `quit'. These operations are just the same as those in exercise 8 but there are three differences.
First, these operations are initiated from any process which receives a signal.
Second, there is only one ring. So each process may receive messages for 'p' or 'q' or 'f' from the the same neighbour.
Third, when initiating generation of a fibonacci number, choose a number randomly between 0 .. 20.
It is possible two operations may run simultaneously on the ring. For example, one process initiates generation of fib(20) while another process initiates generation of fib(12). In order to handle this case, your messages flowing in the ring may contain the original sender's pid.
Due: 2020/May/13, 00:05

For example:

       $ ./a.out 6
       I am 22756
       I am 22757
       I am 22758
       I am 22759
       I am 22760                                        another window
       I am 22761
                                                  +----------------------
       I am 22761, source:22760                   | $ kill -USR2 22760
       I am 22756, source:22760                   |
       I am 22757, source:22760                   |
       I am 22758, source:22760                   |
       I am 22759, source:22760                   |
       I am 22760, source:22760                   |
                                                  | # two operations simultaneously
       I am 22759, source:22758                   | $ kill -USR2 22760 22758
       I am 22761, source:22760                   |
       I am 22756, source:22760                   |
       I am 22757, source:22760                   |
       I am 22758, source:22760                   |
       I am 22759, source:22760                   |
       I am 22760, source:22758                   |
       I am 22760, source:22760                   |
       I am 22761, source:22758                   |
       I am 22756, source:22758                   |
       I am 22757, source:22758                   |
       I am 22758, source:22758                   |
                                                  | # generating a random fib 
       I am 22760, I got   0   1   9 from 22759   | $ kill -USR1 22759
       I am 22761, I got   1   1   8 from 22759   |
       ......                                     |
       I am 22757, I got  34  55   0 from 22759   |
       I am 22758, I got  34  55   0 from 22759   |
       I am 22759, Fib(9) = 34                    |
       I am 22760, I got   0   1  14 from 22759   | $ kill -USR1 22759
       I am 22761, I got   1   1  13 from 22759   |
       .......                                    |
       I am 22756, I got 377 610   0 from 22759   |
       I am 22757, I got 377 610   0 from 22759   |
       I am 22758, I got 377 610   0 from 22759   |
       I am 22759, Fib(14) = 377                  |
       I am 22756, I got   0   1  11 from 22761   | $ kill -USR1 22759 22761
       I am 22760, I got   0   1  20 from 22759   |
       I am 22757, I got   1   1  10 from 22761   |
       .....                                      |
       I am 22760, I got  55  89   1 from 22761   |
       I am 22760, I got 144 233   8 from 22759   |
       I am 22761, Fib(11) = 89                   |
       I am 22761, I got 233 377   7 from 22759   |
       I am 22756, I got 377 610   6 from 22759   |
       .....                                      |
       I am 22758, I got 6765 10946   0 from 22759|
       I am 22759, Fib(20) = 6765                 | $ kill -INT 22759 
       $

exercise 10: practicing pthread

The main thread first sets balls[] = {0, 1, 2, 3, 4, 5}.
Then permute the balls[].
Initialize permutations for balls as
perm[0] = {0, 1, 2, .... 48}
......
perm[5] = {0, 1, 2, .... 48}
Then generate 6 threads, denoted as t_0, t_1, ....t_5.
Thread t_i will permute perm[ balls[i] ].
The main thread then join all threads.
Then beginning with balls[], after applied permutations, 6 balls are gotton as the answer. The method is :
for i in 0..5 do balls[i] = perm[0][ balls[i] ];
repeat the previous step for perm[1], .... perm[5].

The following shows an example where the MAX is set to 18. (You should use 49 instead. And the final line is the only required output).

      $ gcc ex10-thread-ball.c -lpthread
      $ ./a.out 
      The ball's initial setting:   0  1  3  2  4  5
      
      The permuations for balls:
        0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
      ------------------------------------------------------
       13  4 15 10  3  7  1 11 12  6  8  5  9  0 16 14  2 17
       16  0 15  1  5 11 12  7  4 10  3  6 14 13 17  8  9  2
        7  6 15  5 14 13 11 17  8 10  4  1  3  0  9 12 16  2
        0  9 14 12 17  7  4 11  8 13 10  2 16  1  5  6 15  3
       16  6  8  1 11 14 10  7  2 17  0 15  9  3 12  4  5 13
        5 12  8  3 17 16 14  1  2  6  0  7 10  9 13 11 15  4
      ------------------------------------------------------
      
      After permutations applied, balls are:  15 14  1  8  7 12
      So the answer is:                       16 15  2  9  8 13
      $

You should use thread-safe random functions, such as erand48(), or nrand48().
Each thread should use different seed.
Due: 2020/June/03, 00:05

exercise 11: pthread synchronizing(mutex and cond)
- Refer to Chapter 13.
- Similar to previous exercise, but after initialization,
  each of t_0, t_1, ...t_5 will wait for notification from main thread,
  generate the permutations,
  and acknowledge main thread that it has done.
  And repeat the above operation forever.
- The main thread after creating 6 threads will read from stdin.
  When it reads a 'l', it will ask each of the six threads to permute.
  When permutations are all done, the main thread figures out the balls.
  The main thread continues until it reads a 'q'.
- Each thread should use different seeds and you should use thread-safe random functions, such as erand48() or nrand48().
- For example,
```
      $ gcc ex12-thread-mutex.c -lpthread
      $ ./a.out   
      l
      the balls are:   6 28 33 13 29 32
      l
      the balls are:  24 17 40 49 26 41
      l
      the balls are:  37  5 23 45 17 10
      l
      the balls are:  34 42 29 35 19 46
      q
      $  
      
```
- Due: 2020/Jun/10, 00:05