System Programming- Homework 3: Context Switch Simulation Solved

1. Goal
 Understand and simulate the concept of context switch.
Understand and learn some system calls about signals.
Understand and learn to use setjmp(), longjmp().
Enjoy the journal in system programming.
 2. Problem Description
 In this programming assignment, we are going to simulate a user-thread library by using setjmp(), longjmp(), etc. For the simplicity, we use a function to represent a single thread. In other words, you are required to do "context switch" between functions. To do this, you need to do non-local jumps between functions, which is arranged by a scheduler(): each time a function needs to context switch to another, it needs to jump back to scheduler(), and scheduler() will schedule next function to be executed and jump to it. Since non-local jump will not store local variables, we define a data structure, TCB_NODE, for each function to store data needed for computing. All of the TCB_NODEs will formulate a circular linked-list. As scheduler() schedules functions, it also needs to make sure Current pointer points to correct TCB_NODE for functions to output correct execution result.

 You are expected to complete the following tasks:

 Complete the user-thread library threadtools.h.
Complete the functions required in scheduler.c.
Implement three functions: ReduceInteger(), MountainClimbing(), and OperationCount() in simulatedThreads.c.
 3. main.c
 You DON'T have to change any code in main.c. But, it's better for you to understand the workflow in main.c. You should complete all your homework WITHOUT changing any variables or inserting any code segement in main.c.

 4. threadtools.h
 Here, we define the data structure of TCB_NODE and all global variables needed for scheduler.c and simulatedThreads.c. Moreover, you are required to complete some macro functions in this file. Please refer to the comments in threadtools.h.

 5. scheduler.c
 You need to implement sighandler() and scheduler() in scheduler.c. The sighandler is the requirement as a signal handler in system call sigaction(). Please refer to the comments in scheduler.c. (To learn more: https://pubs.opengroup.org/onlinepubs/007904875/functions/sigaction.html)

 6. Rules of "context switch"
 We introduce the rule of "context switch" in detail:

 "Context switch" means that function jumps back to scheduler(), the scheduler() schedules next function in the circular linked-list to be executed.
"Context switch" may occur in two different scenarios:After each iteration in a function. (Please refer to the spec in next section.)
Signal caught (we only consider SIGTSTP), timeslice reached.
If you're doing context switch after each iteration, you should change the function you're executing at the end of each iteration.
If you're doing context switch on signal caught or timeslice reached, you should check the pending signals at the end of each iteration. Once you get the pending signal(s), you should do "context switch".
Timeslice is the time that a function can execute between context switch, which is implemented by alarm() system call. Typically the timeslice is set to 3.
If multiple signals are pending after one iteration, SIGTSTP has the top priority.
 7. simulatedThreads.c
 Function name refers to ReduceInteger, MountainClimbing, or OperationCount.
You are required the three functions with O(n) time complexity.
You are required to solve all functions via iterative method, instead of recursion.
Functions should at least print an output line during its timeslice.
Functions only context switch at the end of each iteration.
You can refer to the code section down below.
The details of each functions and corresponding steps you need to follow are down below.
 ReduceInteger(): Given a positive integer n: if n is even, replace n with n/2; otherwise, you can replace n with either n + 1 or n - 1. Please find the minimum number of replacements needed for n to become 1. The function stops when the calculation is done.
MountainClimbing(): Imagine you are climbing a mountain. Each step you can either climb 1 or 2 units of height. Please compute how many distinct ways you climb to the top? The function stops when the calculation is done.
OperationCount(): Given an array arr of length n where arr[idx] = (2*idx)+323 for all valid indices, 0 <= idx < n. In each operation, you are allowed choose two indices p and q where 0 <= p, q < n and subtract 1 from arr[p] and add 1 to arr[q] (i.e. arr[p] -= 1 & arr[q] += 1). The goal is to make all the elements of the array equal. We promised that all the numbers of an array can be made equal using this operations. Please calculate the minimum number of operations needed to make all the elements of array equal with given integer n, the length of the array. The function stops when the calculation is done.
 In each timeslice, function should outputs its current result as below:
 printf("FunctionName: %d\n", your_output);

 [Hint] Basically, when the function thread starts, you should do some initialization, ThreadInit. And in each iteration, do the context switch, ThreadYield. When the end of execution is triggerd, just complete the function thread, ThreadExit.
 function_name(parameters){
    ThreadInit();
    for(...){
        sleep(1);
        /* function work */
        ThreadYield();
    } 
    ThreadExit();
}

 8. Execution
 Below are argument explainations:

 ri_int = The number for ReduceInteger to process
mc_heights = The mountain height for MountainClimbing to process
oc_arrlen = The array length for OperationCount to process
timeslice = time limit for a function to process until next context switch
switchmode = 0 for context switch after each iteration; 1 for context switch due to signal caught and timeslice reached

 The homework will only be executed by the following command:

 $ ./main {ri_int} {mc_heights} {oc_arrlen} {timeslice} {switchmode}

 Sample execution 1

 $ ./main 8 10 6 3 0
Reduce Integer: 1
Mountain Climbing: 2
Operation Count: 1
Reduce Integer: 2
Mountain Climbing: 3
Operation Count: 4
Reduce Integer: 3
Mountain Climbing: 5
Operation Count: 9
Mountain Climbing: 8
Mountain Climbing: 13
Mountain Climbing: 21
Mountain Climbing: 34
Mountain Climbing: 55
Mountain Climbing: 89

 Sample execution 2

 $ ./main 8 10 6 3 1
Reduce Integer: 1
Reduce Integer: 2
Reduce Integer: 3
ALRM signal caught!
Mountain Climbing: 2
Mountain Climbing: 3
Mountain Climbing: 5
ALRM signal caught!
Operation Count: 1
Operation Count: 4
Operation Count: 9
ALRM signal caught!
Mountain Climbing: 8
Mountain Climbing: 13
Mountain Climbing: 21
ALRM signal caught!
Mountain Climbing: 34
Mountain Climbing: 55
Mountain Climbing: 89
ALRM signal caught!

 Sample execution 3

 $ ./main 8 10 6 3 1
Reduce Integer: 1
Reduce Integer: 2
^ZReduce Integer: 3
TSTP signal caught!
Mountain Climbing: 2
ALRM signal caught!
Operation Count: 1
Operation Count: 4
^ZOperation Count: 9
TSTP signal caught!
Mountain Climbing: 3
ALRM signal caught!
Mountain Climbing: 5
^ZMountain Climbing: 8
TSTP signal caught!
Mountain Climbing: 13
ALRM signal caught!
Mountain Climbing: 21
Mountain Climbing: 34
Mountain Climbing: 55
ALRM signal caught!
Mountain Climbing: 89

 Note: ^Z is where SIGTSTP delivered to process, it is not output by process itself.