# 2020_mid
**Answers could be wrong!!**
**Contact me for discussion**
:email: : [e-mail]
:::spoiler Table of Content
[toc]
:::
:::spoiler Abbreviations
* IVT : Interrupt Vector Table
* IC : Interrupt Controller
* OS : Operating System
* ISR : Interrupt Service Routine
* CXT-SW : Context Switch
* SW : software
* HW : hardware
* PC : Program Counter
* CFS : Completely Fair Scheduler
* SJF : Shortest Job First
* TAS : test and set/swap
:::

## Problem 1.-Done
* Question:
* Regarding IO operations
1. What is the diff. between sync. IO and async. IO?
2. Is `fread()` async. or sync. by default? And `fwrite()`?
* Answer:
* Sync: blocking IO, control returns to program upon IO completion(wait until IO complete).
* Async.: non blocking IO, control returns to program without waiting for IO completion. Program will be signalized upon IO completion.

## Problem 2.-Done
* Question:
* Describe the procedure of handling a timer interrupt, from that timer generates an interrupt signal to the resumption of the interrupted program. The answer must involve: IVT, PC, ISR.
* Answer:
* 

## Problem 3. :star:
* Question:
* Consider a user program that prompts the user for an input string, saves the string in a disk file, and terminates itself. List 5 diff. system calls that the program uses and explain why it uses these calls.
* Answer:
1. read()
2. fwrite()
3. fopen()
4. fclose()
5. exit()
## Problem 4.-Done
* Question:
* Regarding Microkernel OS
1. They are considered more secure than monolithic kernels. Why?
2. They suffer from poor performance for IO intensive app. Why?
* Answer:
1. Microkernel moves as much kernel services to user space, so the size of kernel becomes smaller. Since the kernel is smaller(=less accessibility to HW), the OS has better security.
2. Accessing HW could require several kernel services, since Microkernel might require several InterProcess Communication, causing large overheads

* 
* 

## Problem 5.-Done
* Question:
* What's the next state of the prcoess if (the process is currently running)
1. the process is preempted
2. the process initiates a sync. IO and is then blocked.
* Answer:
* Ready
* Waiting
* 

## Problem 6.-Done
* Question:
* Why CXT-SW is implemented as an interrupt rather than standard procedure call.
* Answer:
* It's controlled by OS timer -> interrupt.
* We don't let program call CXT-SW itself because a malicious program will take over the system if it doesn't yield its resource to other.
## Problem 7.-Done
* Question:
* Why it's necessary for concurrent threads to have their own stacks.
* Answer:
* Function arguments are passed to thread and they are stored in stacks
## Problem 8.-Done :star:
* Question:
* You are writing a CPU-bound program which can be perfectly parallelized. The thread library is M:M. Let the # of kernel-level threads be K and # of CPU Cores be C. Let the process contain U user-level threads.
* Discuss possible performance implications(in terms of the utilization of CPU cores) for the following cases:
1. U = K > C
2. U < K > C
* Answer:
* 1 Core serves for one kernel thread.
* A kernel thread require one CPU core (!= CPU) to execute process.
* Based on previously mentioned,
1. U user threads map to K kernel threads, and C CPU cores choose from K kernel threads to execute. Since C < K, CPU core could jump to another kernel thread to execute. In fact, the speed is bottlenecked by C CPU cores.
2. Same as 1. But now U < K, so the speed now depends on whether C > U or not. If C > U, the user threads could be executed parallel. Otherwise the kernel thread used = U and C still have to choose from U kernel-thread to execute
* [Reference1: difference-between-kernel-threads-and-user-threads-in-a-multi-core-cpu](https://stackoverflow.com/questions/59598468/difference-between-kernel-threads-and-user-threads-in-a-multi-core-cpu)
* [Reference2: What-is-the-difference-between-cores-and-threads-of-a-processor](https://www.quora.com/What-is-the-difference-between-cores-and-threads-of-a-processor)
## Problem 9.-Done
* Question:
* CPU scheduling algorithms.
1. Why SJF is not a good choice for real systems. Give 2 reasons
2. What's the problem when the time slice for Round-Robin is too small?
3. With Multilevel feedback queue, IO bound gradully promoted to upper-level queues. Explain the rationale of this design.
4. Many real-time OS implement Rate-Monotonic scheduling algorithm but not Earliest-Deadling First Scheduling. Explain Why.
5. Process migration is necessary for load balancing among CPUs. However, it is always desirable to reduce the frequency of process migration. Explain why.
6. Why the virtual runtime approach in Linux CPU scheduling is free from starvation?
* Answer:
1. 1)CPU burst time is not deterministic; 2)Could lead to starvation.
2. CXT-SW overhead too large because it's needed every time the time slice expired.
3. IO bound uses CPU for less time, and therefore higher priority. In this way, we could ensure its responsiveness
4. RM assigns a fixed priority to processes while ED's priority might change. So RM is simpler. Also when there are problems, RM is easier to fix due to fixed priority.
5. Migration requires memory moving, which is expensive.
6. Programs vruntime increases as it executes on CPU, so it will eventually exceed those who haven't execute on CPU. CPU will allocate resources to them when their vruntime is surpassed.

## Problem 10.-Done
* Question:
* Why do modern OS use spinlocks as a synchronization mechanism only on multiprocessor systems and not on single processor systems?
* Answer:
* It wastes CPU cycles waiting on single processor systems.
* Another core could still run even one of the computer's CPU core is busy waiting.
## Problem 11.-Done
* Question:
* What's the potential problem of the following "solution" to hte bounded-buffer problem? How can it be corrected?
* 

* Answer:
* Consumer wait(mutex) -> mutex = 0
* Consumer wait(full) -> full = -1 (block)
* Producer wait(mutex) -> mutex = -1 (block)
* full can only be signaled by producer but it's blocked by Consumer
* !!Deadlock!!
* Solution:
* move the `wait(mutex)` and `signal(mutex)` into `wait(empty/full)` and `signal(full/empty)`

## Problem 12.-Done
* Question:
* In the Linux CFS algorithm. The virtual runtime of a CPU-bound process increases faster than other processes. Explain why.
* Answer:
* vruntime increase as it executes, holds the same value as it waits
* so vruntime of a running process will eventually exceed those of waiting processes and lead to preemption

## Problem 13.-Done
* Question:
* There is only one restroom on the first floor of our building. The restroom is shared by all students, but it is made uni-sex with the following rules:
1. Females and males cannot appear in the restroom at the same time, and
2. there cannot be more than 3 people using the resttoom
* Write programs for males and females to solve this problem. Use as many semaphores as you wish. You don't have to worry about starvation.
* Answer:
* Like Reader-Writer Problem, but now writer becomes readers too.
* Do Mutex between Female and Male.
* Count how many people are in the restroom.
* The first to join should Lock the room for same gender
* The last to leave shold unlock

mutex=1, R=1, Count=0;
M(){
    while(1){
        wait(mutex);
        Count++;
        if(Count == 1) wait(R);
        else if(Count >= 3){
            signal(mutex);
            // use restroom
            wait(mutex);
            Count--;
            if(Count == 0) signal(R);
            signal(mutex);
        }
        else{
            signal(mutex);
        }
    }
}
// Female is the same

###### tags: `Introduction to Operating System`