---
title: 期中考古題
---
# List the answer items
### What are the types of OS structures?
- Simple struc.
- MS-DOS、UNIX
- 受限於硬體所提供的內容
- Layered Approach
- 模組化、資訊hiding、debug容易
- Microkernels
- 最精簡化，多餘部分丟到user space
- 擴大可用在分散式系統、縮小可用在嵌入式系統
- user modules間用msg passing方式傳遞信息
> 可跨機傳，但會有time delay的問題
- Modules
- 較layered approach彈性
- lodable, dynamic(Linux)
- object oriented
- 根據系統所需增刪模組，使用API call
- Hybrid Sys.(混合)

### What are the benefits of multithreading programming?
- Responsiveness
- 有別的thread來接替原本工作
- Resource sharing
- economy
- scalability
- Multicore的環境底下concurrency++

### What are the methods explored in the implicit threading?
- Thread Pools
- 用一個Queue(Pool)存固定數量的thread(事先創造)
> 為防止user thread無限制的產生
> 另外，對比"create a new thread"更省資源
- task分段，每段小task去喚醒pool中可用的thread，若當前沒有則須wait

<Note>
Traditonal-multithreading
 - Pop-up To create new thread(Dynamic)
 - Unlimited產生 >> 易有overhead情況產生
     > 換句話說就是沒有斷電機制;user thread可以無限制產生新的thread，kernel thread數量則受限於H/W

- Fork-Join

    flowchart LR
        op1["Main thread"]
        op2["Main thread"]
        op3["Task"]
        op4["Task"]
        op1 -->|fork| op3 -->|join| op2
        op1 -->|fork| op4 -->|join| op2
        
 `
 - OpenMP
 - Grand Central Dispatch
 - Intel Threading Building Blocks

<Note>
Implicit Threading vs Explicit Threading
> 前者對thread的維護、管理、增刪都由compiler的run-time library處理；後者都必須由programmer自己處理

### What are the commonly used thread libraries?
 - POSIX Pthreads (UNIX)
 - Win32 threads (Windows)
 - Java threads

### What are the types of computing environment?
 - Traditional computing
   - Web-based operation
   - PC、Labtop
 - Mobile computing
   - 搭載GPS, Gyroscope(陀螺儀）等
   - AR實現
   - IEEE 802.11 wireless, cellular data
   - 手機、tablet
 - Client-server computing
 - Peer-to-Peer computing
   - Type1. Central Lookup Service
   - Type2. Broadcast via "discovery protocol"
 - Cloud computing
   - Public cloud
   - Private cloud
   - Hybrid cloud
   - Software as a Service (word processor)
   - Platform as a Service (DB server)
   - Infrastructure as a Service (storage for backup)

### What are the challenges of multiprocessor program?
 - Dividing activities
 - Balance
 - Data splitting
 - Data dependency
 - Testing and debugging
 
### What are the types of interprocess communication(IPC)?
 - Shared memory
   - provided by OS
   - 適合大量訊息傳遞
 - Message passing
   - OS要提供空間存儲msg
   - 適合小量訊息傳遞
 - Signal
   - 收送事先約定好信號意義

<Note>
跨機器
- Distributed Shared Memory(DSM)
- 特點:fast、strong consistency(立即同步)
> 反例:不立即同步如google drive、one drive、drop drive...

### What are the types of Client-server communication?
 - Sockets
 - Remote procedure call(RPC)
 - Pipe
 ---
# Explain in detail
### Explain NUMA?
 - CPU can access local memory faster than remote memory, and only low contention over the interconnection among CPUs occurred when accessing remote memory.
### Explain "Convoy effect"(護衛效應)?
 - 因CPU-bound process占用CPU時長過長導致I/O-bound process被延誤只能一直往後排隊等待
### Explain "Schedule Activation"?
 - 在M:M和Two-level models中，維護分配到application之kernel thread數量的機制
### Explain and make comparisons for PROCESS, TASK, and THREAD?
 - Process:系統中的工作單位
 - Task:執行環境中，資源分配的單位
 - Thread:CPU使用的基本單位
program像是設計圖，執行中的process就是把program這個藍圖做出來，過程中有很多thread負責各個部分，當thread運作時會根據工作內容所需去取用task(相當於資源)，task不僅限於data或value，亦有可能是一段code
### Explain and make comparison for Short-term/Medium-term/Long-term scheduler?
 - Short-term: 
     - CPU scheduler
     - 負責將process從ready queue中load到CPU執行
 - Long-term: 
     - 控制放入RAM的process個數，亦可調節使用CPU、I/O的process個數
     - 將process從memory中取出load到ready queue
 - Medium-term: 
     - swap in/out process to/from disk
     - I/O scheduler
     - 負責CPU執行過程中I/O相關的運作排班
![](https://i.imgur.com/5TyO5qf.png)
 
### Explain "Peer-to-Peer Computing"?
 - All nodes are considered peers, each can act as client, server or both, and each node must join P2P network.
### Explain "Blade Server"?
 - A server contains multiple processor boards, I/O boards, network boards...in the same chassis. A processor could be independently booted and run its own OS.
### Explain and make difference between SAN and NAS?
 - SAN是將叢集系統中的storage串接一起的網路，NAS是用網路和host建立連線的storage
### Explain "Dual mode"?
 - 分別為user mode和monitor mode。當OS偵測到有AP用illegal instruction，OS會trap AP，並從user mode轉為monitor mode，以fatal error為由殺掉AP；
### Explain "Copyleft"?
 - Copyleft is a stipulation for distributing software that the user can copy it freely, examine and modify the source code, and redistribute the software to other software passed along with the copyleft stipulation.
### Explain "Up-calls"?
 - An upcall is a mechanism that allows the kernel to execute a function in userspace, and info is returned as a result.
 ---
# Calculating Question
### There's a application that is 65% parallel and 35% serial, compare the speedup.
#### 1. 4 processing cores v.s 1 processing core?
 - 4 cores:  ${1 \over 0.35 + {0.65 \over 4}} \approx 1.95$
 - 1 core:  ${1 \over 0.35 + {0.65 \over 1}} \approx 1$
 $\therefore$ 4 cores run faster than 1 core
#### 2. Unlimited processing cores v.s. 1 processing core? 
 $\because {0.65 \over \infty}\to 0$
   $\therefore$ unlimited processing cores' speedup will be ${1 \over 0.35}\approx 2.86 \gt 1$ (one processing core)
   

 ---
# Write a C program
### Create a child process printing its process ID...
### then create 2 brother processes of the child process and print their own process IDs.

#include <stdio.h> /* printf */
#include <stdlib.h> /* exit(0) */
#include <sys/types.h> /* pid_t */
#include <unistd.h> /* fork(), getpid() */
#include <sys/wait.h> /* wait() */

int main() {
/* Create a child with pid */
if(fork() == 0){
printf("I'm the first child [%d]\n", getpid());
exit(0);
}
wait(NULL);

/* 2 brothers with pids */
for(int i=0; i<2; i++){
if(fork() == 0){
printf("Brother %d [%d]\n", i+1, getpid());
exit(0);
}
}
for(int i=0; i<2; i++) wait(NULL);
return 0;
}

 ---
# 一定考!
### Consider the following 4 processes, with the length of the CPU burst given in milliseconds:
![](https://i.imgur.com/Cc2IiCh.png)
 > AT:到達ready queue的時間點
 > BT:執行的時間長
 > TT:process從進入CPU到完成所需的時間
 > WT:Process在ready queue中的等待時間
#### a. Draw four Gantt chart illustrating the execution of these processes using FCFS, SJF, a nonpreemptive priority(a smaller priority number implies a higher priority), and RR(quantum = 1) scheduling.
![](https://i.imgur.com/SPJ9cCe.jpg)


![](https://i.imgur.com/HiMMktk.jpg)


![](https://i.imgur.com/apEXgD7.jpg)


![](https://i.imgur.com/tEQVqMe.jpg)


#### b. The turnaround time of each process for each of the scheduling algorithms in part a?
> Turnaround time 
> = Burst time + Waiting time
> = Exit time - Arrival time

|      | P1  | P2  | P3  | P4  |
| ---- | --- | --- | --- | --- |
| FCFS | 8   | 11  | 19  | 23  |
| SJF  | 17  |  4  | 24  | 7   |
| NP   | 26  |  9  | 17  | 5   |
| RR   | 24  | 13  | 24  | 16  |

#### c. The waiting time of each process for each of the scheduling algorithms in part a?
> Waiting time = Turnaround time - Burst time

|      | P1  | P2  | P3  | P4  |
| ---- | --- | --- | --- | --- |
| FCFS | 0   | 7   | 10  | 18  |
| SJF  | 9   | 0   | 15  | 2   |
| NP   | 18  | 5   | 8   | 0   |
| RR   | 16  | 9   | 15  | 11  |