web pages for usp and its programs
GNU make document
note of activation record

exercise 1: summing numbers in arguments

Figure out the sum of numbers in arguments.
An arguemnt is a number if it is consisted of only digits.

For example:

      $ ./a.out  
      0
      $ ./a.out 1 2 3 
      6
      $ ./a.out 1 2 3 4
      10
      $ ./a.out 1 2 3 klim
      6
      $ ./a.out 1 2 3 klim 3 -1
      8
      $ ./a.out 1 2 3 klim 3 -1 9klim
      8
      $

Due: 2022/Feb/23, 00:05
Put your files under ~/usp-1102/exer1
You may use strtol().

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
      $

Since there are 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: 2022/Mar/02, 00:05
Put your files under ~/usp-1102/exer2

exercise 3: practicing atexit()

Copy stdin to stdout, but when exiting, print
number of lines, number of words, and number of characters.
The three numbers should be the same as the output of 'wc'
and they should be printed to stderr, not stdout.

For example:

      $ gcc ex3-atexit.c
      $
      $ cat k
      this is a test
      Oh! It works.
            1 + 2=3
      $
      $ wc k
       3 10 43 k
      $
      $ ./a.out < k
      this is a test
      Oh! It works.
            1 + 2=3
      3 10 43
      $
      $ cat k-no-newline
      this is a test
      Oh! It works.
            1 + 2=3
      without the trailing newline$
      $
      $ wc k-no-newline
       3 14 71 k-no-newline
      $
      $ ./a.out < k-no-newline
      this is a test
      Oh! It works.
            1 + 2=3
      without the trailing newline3 14 71
      $
      $ ./a.out < k-no-newline > output
      3 14 71
      $ cat output 
      this is a test
      Oh! It works.
            1 + 2=3
      without the trailing newline$ 
      $

You may assume the line length does not exceed 4096.
Beware of the last line. It may be not terminated with a newline.
Due: 2022/Mar/09, 00:05
Put your files under ~/usp-1102/exer3

exercise 4: creating processes with fork()

Write a program which will create a process tree.
The tree is a fully binary tree. The argv[1] denotes the number of internal nodes. The internal nodes form a zig-zag line, first skew left, then right, etc.

For example:

      $ ./a.out 1
      I am external 12312. My parent is 12311.
      I am external 12313. My parent is 12311.
      I am internal 12311. My left and right are 12312 and 12313.
      $ ./a.out 2
      I am external 12320. My parent is 12319.
      I am external 12321. My parent is 12319.
      I am internal 12319. My left and right are 12320 and 12321.
      I am external 12322. My parent is 12318.
      I am internal 12318. My left and right are 12319 and 12322.
      $ ./a.out 3
      I am external 12325. My parent is 12324.
      I am external 12327. My parent is 12326.
      I am external 12328. My parent is 12326.
      I am internal 12326. My left and right are 12327 and 12328.
      I am internal 12324. My left and right are 12325 and 12326.
      I am external 12329. My parent is 12323.
      I am internal 12323. My left and right are 12324 and 12329.
      $

You must insert wait() somewhere in your code to make the messages printed in post-order.
deadline: 2022/Mar/16, 00:05
Put your files under ~/usp-1102/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 correct arguments, such as label, "is it a leaf?", .. etc.
- The second program which is loaded by exec() should do something like:
```
      print a message to show itself label, pid, ...
      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: 2022/Mar/23, 00:05
- Put your files under ~/usp-1102/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, `cat' can not be used to show its content.
      # Instead, 'od' is used. Check the argument of 'od' carefully. 
      # 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: 2022/March/30 00:05
Put your files under ~/usp-1102/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:

      $ gcc 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: 2022 Apr 06 00:05am
Put your file(s) under ~/usp-1102/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 
              read from stdin 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-1 to the clockwise next process
              end loop
              write to the stdout the first number, a
            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 next 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: 2022 Apr 27 00:05am
Put your file(s) under ~/usp-1102/exer8

exercise 9: practicing kill() and sigaction()

You should first pipe(), and then fork() to create a pipe to connect parent and child.

The parent does something like:

        while get a line do 
          if first char is 'q' then 
            break
          endif

          if first char is 'l' then 
            send a signal to child
            read an integer from child (through the pipe)
            print the integer
          endif  
        done
        send a signal to terminate the child

The child does something like:

        setup signal handler
        initialize random generator

        while true; do 
          wait a signal from parent
          generate a number in the range 1..49
          write the number to parent (through the pipe)
        done

When waiting for signal, try to use pause() to avoiding busy waiting.

For example,

      $ ./a.out 
      hello
      do it
      lot of fun
      got 33
      lottery
      got 26
      l
      got 29
      quit
      $

Deadline: 2022 May 04 00:05am
Put your file(s) under ~/usp-1102/exer9

exercise 10: do waiting for a signal and reading simultaneously

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 two signals.
One is for sending fibonacci numbers, and the other is 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 'f' from the the same neighbour.
Third, when initiating generation of a fibonacci number, choose a random number 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.
Consult the manpage of pselect() or ppoll().

For example:

      $ gcc ex10-pselect.c 
      $ ./a.out 4
      I am 28539
      I am 28540
      I am 28541                                   another window
      I am 28542                               +----------------------
      I am 28541, I got   0   1   5 from 28540 | $ kill -USR1 28540
      I am 28542, I got   1   1   4 from 28540 |
      I am 28539, I got   1   2   3 from 28540 |
      I am 28540, I got   2   3   2 from 28540 |
      I am 28541, I got   3   5   1 from 28540 |
      I am 28542, I got   5   8   0 from 28540 |
      I am 28539, I got   5   8   0 from 28540 |
      I am 28540, Fib(5) = 5                   |
      I am 28542, I got   0   1  15 from 28541 | $ kill -USR1 28541
      I am 28539, I got   1   1  14 from 28541 |
      . . . .
      I am 28541, I got  89 144   4 from 28541 |
      I am 28542, I got 144 233   3 from 28541 |
      I am 28539, I got 233 377   2 from 28541 |
      I am 28540, I got 377 610   1 from 28541 |
      I am 28541, Fib(15) = 610                |
      I am 28542, I got   0   1  15 from 28541 | $ kill -USR1 28541 28539
      I am 28540, I got   0   1   1 from 28539 |
      I am 28539, I got   1   1  14 from 28541 |
      I am 28540, I got   1   2  13 from 28541 |
      I am 28541, I got   1   1   0 from 28539 |
      I am 28541, I got   2   3  12 from 28541 |
      I am 28542, I got   1   1   0 from 28539 |
      I am 28542, I got   3   5  11 from 28541 |
      I am 28539, Fib(1) = 1                   |
      I am 28539, I got   5   8  10 from 28541 |
      I am 28540, I got   8  13   9 from 28541 |
      I am 28541, I got  13  21   8 from 28541 |
      I am 28542, I got  21  34   7 from 28541 |
      I am 28539, I got  34  55   6 from 28541 |
      I am 28540, I got  55  89   5 from 28541 |
      I am 28541, I got  89 144   4 from 28541 |
      I am 28542, I got 144 233   3 from 28541 |
      I am 28539, I got 233 377   2 from 28541 |
      I am 28540, I got 377 610   1 from 28541 |
      I am 28541, Fib(15) = 610                |
      $                                        | $ $ kill -INT  28541

Deadline: 2022 May 11 00:05am
Put your file(s) under ~/usp-1102/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.
  This is for explanation. You should set MAX to 49 instead.
  And you are required to show only the final six balls.
```
      $ 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 and consecutive few invocations of the program should give different set of balls.
- Due: 2022/May/25, 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 a random ball,
  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 generate balls. That is, notify the 6 threads.
  The main thread then has to collect the balls and make sure they are distinct. That is, wait for notifying.
  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: 2022/June/01, 00:05