[Solved] SystemProgramming HW 1

# 1. Goal1. Understand and simulate the concept of context switch.2. Understand and learn some system calls about signals.3. Understand and learn to use `setjmp()`, `longjmp()`.4. Enjoy the journal in system programming.

## 2. Problem DescriptionIn this programming assignment, we are going to simulate a user-thread libraryby using `setjmp()`, `longjmp()`, etc. For the simplicity, we use a functionto represent a single thread. In other words, you are required to docontext switch between functions. To do this, you need to do non-local jumpsbetween functions, which is arranged by a `scheduler()`: each time a functionneeds 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_NODE`s will formulate a circular linked-list. As `scheduler()` schedulesfunctions, 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:

1. Complete the user-thread library `threadtools.h`.2. Complete the functions required in `scheduler.c`.3. Implement three functions: `ReduceInteger()`, `MountainClimbing()`, and `OperationCount()` in `simulatedThreads.c`.

## 3. main.cYou **DONT** have to change any code in `main.c`. But, itsbetter for you to understand the workflow in `main.c`. Youshould complete all your homework **WITHOUT** changing anyvariables or inserting any code segement in `main.c`.

## 4. threadtools.hHere, 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.cYou need to implement `sighandler()` and `scheduler()` in `scheduler.c`. The `sighandler` is therequirement 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 switchWe introduce the rule of context switch in detail:1. Context switch means that function jumps back to `scheduler()`, the `scheduler()`schedules next function in the circular linked-list to be executed.2. 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.2. If youre doing context switch after each iteration, you should change the functionyoure executing at the end of each iteration.3. If youre doing context switch on signal caught or timeslice reached, you shouldcheck the pending signals at the end of each iteration. Once you get the pending signal(s),you should do context switch.4. 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.5. If multiple signals are pending after one iteration, `SIGTSTP` has the top priority.

## 7. simulatedThreads.c1. Function name refers to ReduceInteger, MountainClimbing, or OperationCount.2. You are required the three functions with **`O(n)`** time complexity.3. You are required to solve all functions via iterative method, instead of recursion.4. Functions should at least print an output line during its timeslice.5. Functions only context switch at the end of each iteration.6. You can refer to the code section down below.7. 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 replacementsneeded 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 1or 2 units of height. Please compute how many distinct ways you climb to the top? The functionstops when the calculation is done.

`OperationCount()`: Given an array `arr` of length n where `arr[idx] = (2*idx)+323` for allvalid indices, 0 <= idx < n. In each operation, you are allowed choose two indices p and qwhere `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 ofarray equal with given integer n, the length of the array. The function stops when the calculation is done.8. In each timeslice, function should outputs its current result as below:`Cprintf(FunctionName: %d
, your_output);`9. [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. ExecutionBelow are argument explainations:`ri_int = The number for ReduceInteger to processmc_heights = The mountain height for MountainClimbing to processoc_arrlen = The array length for OperationCount to processtimeslice = time limit for a function to process until next context switchswitchmode = 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 0Reduce Integer: 1Mountain Climbing: 2Operation Count: 1Reduce Integer: 2Mountain Climbing: 3Operation Count: 4Reduce Integer: 3Mountain Climbing: 5Operation Count: 9Mountain Climbing: 8Mountain Climbing: 13Mountain Climbing: 21Mountain Climbing: 34Mountain Climbing: 55Mountain Climbing: 89`

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

Sample execution 3`$ ./main 8 10 6 3 1Reduce Integer: 1Reduce Integer: 2^ZReduce Integer: 3TSTP signal caught!Mountain Climbing: 2ALRM signal caught!Operation Count: 1Operation Count: 4^ZOperation Count: 9TSTP signal caught!Mountain Climbing: 3ALRM signal caught!Mountain Climbing: 5^ZMountain Climbing: 8TSTP signal caught!Mountain Climbing: 13ALRM signal caught!Mountain Climbing: 21Mountain Climbing: 34Mountain Climbing: 55ALRM signal caught!Mountain Climbing: 89`Note: ^Z is where `SIGTSTP` delivered to process,it is not output by process itself.