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 strings from stdin and if a string is consisted of digits, it is treated as a number. Sum all the numbers and write sum to stdout.
- The reading is terminated by end of file, that is, a ctrl-D.
- The length of each string does not exceed 16.
- You may assume the numbers and the sum can be handled with int.
- For converting a string to a number, you may consult strtol().
- For example:
```
        $ gcc ex1-sum-stdin.c 
        $ ./a.out 
        I have 1000
        You have 200
        I give you 50
        Now You have 250.       <---- ctrl-D pressed
        1250                    <---- only 1000, 200, 50 are summed
        $ ./a.out 
        100 + 23 = 123
        $100 - 23 = 77.         <---- ctrl-D pressed
        269                     <---- 100, 23, 123, 23 are summed
        $ 
      
```
- Due: 2021/Mar/03, 00:05
  You have to put your program under ~/usp-1092/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[33]: INFOPATH=/usr/info:/usr/share/texmf/info
        environ[34]: G_BROKEN_FILENAMES=1
        environ[35]: _=./a.out
        environ[36]: OLDPWD=/home/klim/course/usp-1092
        
        argc      is resided at 0x7ffdddad11fc
        argv      is resided at 0x7ffdddad11f0
        environ   is resided at 0x601040
        argv[]    is resided at 0x7ffdddad12f8
        environ[] is resided at 0x7ffdddad1328
        value of argv[ 0] is 0x7ffdddad24c3
        value of argv[ 1] is 0x7ffdddad24cb
        value of argv[ 2] is 0x7ffdddad24d0
        value of argv[ 3] is 0x7ffdddad24d3
        value of argv[ 4] is 0x7ffdddad24d7
        value of argv[ 5] is (nil)
        value of env [ 0] is 0x7ffdddad24dc
        value of env [ 1] is 0x7ffdddad2505
        value of env [ 2] is 0x7ffdddad2521
        value of env [ 3] is 0x7ffdddad2575
        ..........
        value of env [33] is 0x7ffdddad2f86
        value of env [34] is 0x7ffdddad2faf
        value of env [35] is 0x7ffdddad2fc4
        value of env [36] is 0x7ffdddad2fce
        $

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 hello=ohio ./a.out see you again
        argc is 4
        argv[0]: ./a.out
        argv[1]: see
        argv[2]: you
        argv[3]: again
        environ[0]: A=1
        environ[1]: hello=ohio
        
        argc      is resided at 0x7fff4b9083dc
        argv      is resided at 0x7fff4b9083d0
        environ   is resided at 0x601040
        argv[]    is resided at 0x7fff4b9084d8
        environ[] is resided at 0x7fff4b908500
        value of argv[ 0] is 0x7fff4b908fcb
        value of argv[ 1] is 0x7fff4b908fd3
        value of argv[ 2] is 0x7fff4b908fd7
        value of argv[ 3] is 0x7fff4b908fdb
        value of argv[ 4] is (nil)
        value of env [ 0] is 0x7fff4b908fe1
        value of env [ 1] is 0x7fff4b908fe5
        $

deadline: 2021/Mar/10, 00:05
Put your files under ~/usp-1092/exer2

exercise 3: practicing strtok_r()
- Write a program to figure out
  number of lines, number of tokes, and number of fields.
- A line is terminated by '\n' or just end of file.
- A toke is separated by ' '(space) or '\t'(tab).
- A field is inside a token and is separated by ':' or '/'.
- A token without ':' or '/' is also a field.
- You MUST use strtok_r() to complete your program.
- For example:
```
        $ cat IN-3
        this is ok.
        10/31   2019::::10/31
        dec/12 koala
        $ ./a.out < IN-3 
        number of line  is 3
        number of token is 7
        number of field is 11
        $
      
```
- deadline: 2021/Mar/17, 00:05
- Put your files under ~/usp-1092/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 id, pid and ppid.

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

      $ echo $$
      5009                                #  pid of the shell
      $ ./a.out                           #
      a, my pid = 6001, my ppid = 5009    #  only one process
      $ ./a.out 3                         #  
      b, my pid = 6009, my ppid = 6008    #          a
      c, my pid = 6010, my ppid = 6008    #       /  |  \   <----- 3
      d, my pid = 6011, my ppid = 6008    #      b   c   d
      a, my pid = 6008, my ppid = 5009    #
      $ ./a.out 1 1                       #           a
      c, my pid = 6021, my ppid = 6020    #           |     <------ 1
      b, my pid = 6020, my ppid = 6019    #           b
      a, my pid = 6019, my ppid = 5009    #           |     <------ 1
      $ ./a.out 3 2                       #           c
      b, my pid = 6037, my ppid = 6036    #      a
      c, my pid = 6038, my ppid = 6036    #    / | \        <------ 3
      e, my pid = 6040, my ppid = 6039    #   b  c  d
      f, my pid = 6041, my ppid = 6039    #        / \      <------ 2
      d, my pid = 6039, my ppid = 6036    #       e   f
      a, my pid = 6036, my ppid = 5009    #
      $                                   #

deadline: 2021/Mar/24, 00:05
Put your files under ~/usp-1092/exer4

exercise 5: practicing exec() and wait()
- Refer to the description of exercise 2 (usp-982) for explanation of the code .
- You have to write two programs. One is to create a process tree and invoke exec(). Another is loaded by exec() and executes wait()
- The one which invokes exec() should accept arguments like the previous demo program and after creating the process tree, it should just exec() the second program.
  Note 1: The first program should not print anything. The message should be printed by the second one.
  Note 2: You have to remove the wait(NULL) in the demo program.
  Note 3: To exec() another program, you have to pass it with correct arguments, such as label, "is it a leaf?", .. etc.
- The second program which is loaded by exec() should first print a a message, and do something 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:
```
      $ gcc -o wait ex5-wait.c   # the executable is named as ``wait''.
      $ gcc ex5-exec.c           
      $ ./a.out ddudduduuduu abcdef                 #
      I'am a, mypid is 21790, and my ppid is 18796  #         a
      I'am f, mypid is 21793, and my ppid is 21790  #       / | \
      I'am c, mypid is 21792, and my ppid is 21790  #      b  c  f
      I'am b, mypid is 21791, and my ppid is 21790  #        / \
      I'am e, mypid is 21795, and my ppid is 21792  #       d   e
      I'am d, mypid is 21794, and my ppid is 21792  #
      child 21791 signaled with signal 1            # $ kill -1 21791    kill b
      child 21794 signaled with signal 2            # $ kill -2 21794    kill d
      child 21795 signaled with signal 3            # $ kill -3 21795    kill e
      child 21792 exited with value 5               #                    c exit
      child 21793 signaled with signal 2            # $ kill -2 21793    kill f
      $ echo $?                                     #                    a exit
      8                                             # 
      $ 
      
```
- deadline: 2021/Mar/31, 00:05
- Put your files under ~/usp-1092/exer5

exercise 6: sort an array and remove the duplicates

Write a program to manipulate an array in a file
First the array is read in.
Second the array is sorted.
Third, the duplicates are removed.
And finally the array is written to a file.
The integers are stored in big-endian format. So when you read a number from a file, you MAY have to convert its endian in memory. Similarly, you MAY also have to convert the endian of a number before it is written out to a file.
When stored in a file, the number of the array is stored as the first integer, followed by the content of the array.
Only the functions mentioned in textbook are allowed. Do NOT use fprintf(), fopen(), fread(), fwrite, ....

For example:

      #
      # Since 'A' is a binary file, you can not just use `cat' to show its content.
      # Check the argument of 'od'. 
      # File 'A' contains 13 integer. First is the count, 
      # others are values of the array.
      #
      $ od -A none --endian=big -t d4  A     
                12           9         101           3
                 4          78         119           4
                 3         119          78          78
                 9
      $
      #
      # Run and check the result.
      #
      $ ./a.out A B
      $
      $ od -A none --endian=big -t d4  B
                 6           3           4           9
                78         101         119
      $ 
      $ cat A | ./a.out - B 
      $
      $ od -A none --endian=big -t d4  B
                 6           3           4           9
                78         101         119
      $
      $ cat A | ./a.out - - | od -A none --endian=big -t d4
                 6           3           4           9
                78         101         119
      $

Due: 2021/Apr/7 00:05
Put your files under ~/usp-1092/exer6

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 two pipes are created between a parent and each one of its children.
One pipe is for parent's sending to child, the other is for child's sending to the parent.
When the process tree is created, the root will read from stdin and others will read from a pipe.
When root gets a character, it sends this character to its children which also send to their children recursively.
Each process will do some operation according to this character.
If it is a 'p' (lowercase), each process will print a line in preorder.
If it is a 'P' (uppercase), each process will print a line in postorder.
If it is a 'q' (lowercase), each process will exit. But the parent has to wait its children before exit.

For example:

      $ backup ex7-pre-post.c 
      $ ./a.out ddududduduuduu abcdefg
      p                                          .__a___.
      I'm a, my pid=26986, and my ppid=26014    /  /  \  \
      I'm b, my pid=26987, and my ppid=26986   b  c    d  g
      I'm c, my pid=26988, and my ppid=26986          / \
      I'm d, my pid=26989, and my ppid=26986         e   f
      I'm e, my pid=26991, and my ppid=26989
      I'm f, my pid=26992, and my ppid=26989
      I'm g, my pid=26990, and my ppid=26986
      P
      I'm b, my pid=26987, and my ppid=26986
      I'm c, my pid=26988, and my ppid=26986
      I'm e, my pid=26991, and my ppid=26989
      I'm f, my pid=26992, and my ppid=26989
      I'm d, my pid=26989, and my ppid=26986
      I'm g, my pid=26990, and my ppid=26986
      I'm a, my pid=26986, and my ppid=26014
      p
      I'm a, my pid=26986, and my ppid=26014
      I'm b, my pid=26987, and my ppid=26986
      I'm c, my pid=26988, and my ppid=26986
      I'm d, my pid=26989, and my ppid=26986
      I'm e, my pid=26991, and my ppid=26989
      I'm f, my pid=26992, and my ppid=26989
      I'm g, my pid=26990, and my ppid=26986
      q
      $

Deadline: 2021 Apr 14 00:05am
Put your file(s) under ~/usp-1092/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

For example,

      $ gcc ex8-poll-fib.c 
      $ ./a.out 6
      f 10
      I am  8815, I got   0   1  10
      I am  8816, I got   1   1   9
      I am  8817, I got   1   2   8
      I am  8818, I got   2   3   7
      I am  8819, I got   3   5   6
      I am  root, I got   5   8   5
      I am  8815, I got   8  13   4
      I am  8816, I got  13  21   3
      I am  8817, I got  21  34   2
      I am  8818, I got  34  55   1
      I am  8819, I got  55  89   0
      I am  root, I got  55  89   0
      I am  root. Fib(10) = 55
      f 2
      I am  8815, I got   0   1   2
      I am  8816, I got   1   1   1
      I am  8817, I got   1   2   0
      I am  8818, I got   1   2   0
      I am  8819, I got   1   2   0
      I am  root, I got   1   2   0
      I am  root. Fib(2) = 1
      p
      I am  8819
      I am  8818
      I am  8817
      I am  8816
      I am  8815
      I am  8814, the root
      q
      $

Deadline: 2021 May 05 00:05am
Put your file(s) under ~/usp-1092/exer8

exercise 9: practicing sigsuspend()

Your program first generates two children, called left and right.
Also a pipe should be created between the parent and each of the children.
The pipe is for parent's sending to child.

After the pipes and children processes are setup, the parent

        initialize signal handling
        loop 
            read a number from stdin 
            send it to two children through the pipes
            waiting signals generated by children
            show the waited result
        end loop

Each child does something like:

        initialize random seed
        loop
          read a number, N, from the pipe
          generate a random number, R
          use R to determine the read number N if good or not 
          if good then send SIGNAL-1 to parent
          send SIGNAL-2 to parent
        end loop

For example, if left child (child 0)
uses SIGINT for SIGNAL-1 and SIGUSR1 for SIGNAL-2, while right child (child 1)
uses SIGTERM for SIGNAL-1 and SIGUSR2 for SIGNAL-2,
and left child thinks N is good, right child thinks N is not good,
the parent will got SIGINT, SIGUSR1, SIGUSR2.

      $ ./a.out 
      190
      child 0 does not approve 190
      child 1 does not approve 190
      190
      child 0 does approve 190
      child 1 does approve 190
      190
      child 0 does approve 190
      child 1 does not approve 190
      121
      child 0 does not approve 121
      child 1 does not approve 121
      121
      child 0 does not approve 121
      child 1 does not approve 121
      1223232323
      child 0 does approve 1223232323
      child 1 does not approve 1223232323
      1223232323
      child 0 does not approve 1223232323
      child 1 does not approve 1223232323
      $

Use sigsuspend() to wait signals.
For random number manipulation, see `man random', or `man drand48'.
Deadline: 2021 May 19 00:05am
Put your file(s) under ~/usp-1092/exer9

exercise 10: practicing pselect() or ppoll()

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.
Although only reading from a file, the process still has to wait for signals. So ppoll() and pselect() are functions you should consider to use.
Check 'man pselect' for details.
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(12) while another process initiates generation of fib(8). In order to handle this case, your messages flowing in the ring may contain the original sender's pid.

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 simultaneou
sly
       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 
       $

Deadline: 2021 May 26 00:05am
Put your file(s) under ~/usp-1092/exer10

exercise 11: 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 ex11-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: 2021/June/09, 00:05

exercise 12: 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: 2021/June/16, 00:05