# 4.8
> Provide two programming examples in which multithreading does not provide better performance than a single-threaded solution.
>
> 中文翻譯:提供兩個程式例子，在多執行序下不會比單執行序有更好的效率
## 答案
1. 串行操作爲主的程序，例如:圖像進行處理的各個步驟之間通常是無法並行的
2. 大量需要同步等待資源的程式
# 4.10
> Which of the following components of program state are shared across threads in a multithreaded process?
>
> 中文翻譯:在多線程過程中，以下哪些程序狀態組件在線程之間共享？
## 答案
- [ ] a. Register values(寄存器/CPU)
- [x] b. Heap memory(動態配置變數)
- [x] c. Global variables(全域變數)
- [ ] d. Stack memory(區域變數)
### 解釋
stack：區域變數
堆疊區段（stack segment）用於儲存函數的區域變數，以及各種函數呼叫時需要儲存的資訊（例如函數返回的記憶體位址還有呼叫者函數的狀態等），每一次的函數呼叫就會在堆疊區段建立一個 stack frame，儲存該次呼叫的所有變數與狀態，這樣一來同一個函數重複被呼叫時就會有不同的 stack frame，不會互相干擾，遞迴函數就是透過這樣的機制來執行的。

heap：動態配置變數
heap 區段的記憶體空間用於儲存動態配置的變數，例如 C 語言的 malloc 以及 C++ 的 new 所建立的變數都是儲存於此。
堆疊區段一般的狀況會從高記憶體位址往低記憶體位址成長，而 heap 剛好從對面以相反的方向成長。
### example code

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>

#define NUM_THREADS 5

// Heap過去共享資料型態
struct SharedData {
    int value;
};

// Global variables
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

// Pthread function
void *thread_function(void *arg) {
    struct SharedData *data = (struct SharedData *)arg;

    for (int i = 0; i < 3; i++) {
        pthread_mutex_lock(&mutex); // Lock
        printf("Thread: Reading shared value = %d\n", data->value);
        data->value++;
        printf("Thread: Modifying shared value to %d\n", data->value);
        pthread_mutex_unlock(&mutex); // UnLock
    }
    pthread_exit(NULL);
}

int main() {
    pthread_t threads[NUM_THREADS];
    // malloc 就是去heap memory 拿記憶體
    struct SharedData *shared_data = (struct SharedData *)malloc(sizeof(struct SharedData));

    shared_data->value = 0;

    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_create(&threads[i], NULL, thread_function, (void *)shared_data);
    }

    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }

    printf("Final value of shared variable: %d\n", shared_data->value);

    free(shared_data);

    return 0;
}

The threads of a multithreaded process share heap memory and global variables. Each thread has its separate set of register values and a separate stack.
# 4.16
>A system with two dual-core processors has four processors available for
scheduling. A CPU-intensive application (e.g., a program that spends most of its time on
computation, not I/O or memory accesses) is running on this system. All input is performed
at program start-up, when a single file must be opened and read sequentially. Similarly, all
output is performed just before the program terminates, when the program results must be
written sequentially to a single file. Between startup and termination, the program is entirely
CPU-bound (e.g., only executing instructions). Your task is to improve the performance of
this application by multithreading it. Specifically, you must determine:
>
> 中文翻譯:一個擁有兩個雙核處理器的系統，有四個處理器可供排程使用。正在此系統上運行一個CPU密集型應用程序（例如，一個大部分時間用於計算而非I/O或內存訪問的程序）。所有輸入均在程序啟動時進行，需要打開並按順序讀取單個文件。同樣，所有輸出都在程序結束前進行，需要將程序結果按順序寫入單個文件。在啟動和終止之間，程序完全依賴於CPU（例如，僅執行指令）。您的任務是通過將其多線程化來改善此應用程序的性能。具體來說，您必須確定：
## P1
> How many threads will you create to handle input and output? Briefly explain.
>
> 中文翻譯:
您將創建多少個線程來處理輸入和輸出？簡要解釋一下
## 答案
Since the file must be accessed sequentially, the work of reading and writing it cannot
reasonably be parallelized, and only a single thread should be used for each of these tasks.
## P1
> How many threads will you create for the CPU-bound portion of the
application? Briefly explain.
## 答案
4個 題目有說 **four processors**
# 5.14
> Most scheduling algorithms maintain a run queue, which lists processes eligible to run on a processor. On multicore systems, there are two general options:
(1) each processing core has its own run queue, or
(2) a single run queue is shared by all processing cores.
What are the advantages and disadvantages of each of these approaches?
>
> 中文翻譯:大多數調度算法都維護一個運行隊列，其中列出了可在處理器上運行的進程。在多核系統上，有兩個常見的選擇：
（1）每個處理核心都有自己的運行隊列，或者
（2）所有處理核心共享一個單一的運行隊列。
這兩種方法各有什麼優缺點？

## 答案
1. 第一種的優點在，任務不會互相干擾，也不需要等待資源，但需要更多管理以及同步，以避免資源競爭
2. 第二種的優點在簡單方便有效率的使用系統資源，而且較好管理，但必須管控資源開銷，同步問題，可能會造成效率不佳
# 5.18
> The following processes are being scheduled using a preemptive, priority-based, round-robin scheduling algorithm.
Each process is assigned a numerical priority, with a higher number indicating a higher relative priority.
For processes with the same priority, a round-robin scheduler will be used with a time quantum of 10 units.
If a process is preempted by a higher-priority process, the preempted process is placed at the end of the queue.
(a) Show the scheduling order of the processes using a Gantt chart.
(b) What is the turnaround time for each process?
(c) What is the waiting time for each process?

| Thread | Priority | Burst | Arrival |
| --- | -------- | -------- | -------- |
| P1 | 8 | 15 | 0 |
| P2 | 3 | 20 | 0 |
| P3 | 4 | 20 | 20 |
| P4 | 4 | 20 | 25 |
| P5 | 6 | 5 | 45 |
| P6 | 6 | 15 | 55 |

gantt
    title Process Scheduling
    dateFormat  m
    axisFormat %M
    section Processes
    P1:undone, after 0m, 15m
    P2:undone, after 0m, 20m
    P3:undone, after 20m, 20m
    P4:undone, after 25m, 20m
    P5:undone, after 45m, 5m
    P6:undone, after 55m, 15m

## 答案
### A

gantt
    title Process Scheduling
    dateFormat  m
    axisFormat %H:%M
    section Scheduling
        P1:P1, 0, 15m
        P2-1:P2-1, after P1, 5m
        P3-1:P3-1, after P2-1, 5m
        section round-robin
            P3-2:P3-2, after P3-1, 10m
            P4-1:P4-1, after P3-2, 10m
            P5:P5, after P4-1, 5m
            P6:P6, after P5, 15m    
            P4-2:P4-2, after P6, 10m
            P3-3:P3-3, after P4-2, 10m
            P2-2:P2-2, after P3-3, 10m

### B

| Process | Time Start | Time End | Total |
| ------- | ---------- | -------- |:----- |
| P1 | 0 | 15 | 15 |
| P2 | 15 | 95 | 80 |
| P3 | 20 | 85 | 65 |
| P4 | 35 | 75 | 40 |
| P5 | 45 | 50 | 5 |
| P6 | 50 | 65 | 15 |
### C
| Process | Time Start | Time End | Wait |
| ------- | ---------- | -------- |:----- |
| P1 | 0 | 15 | 0 |
| P2 | 15 | 95 | 60 |
| P3 | 20 | 85 | 45 |
| P4 | 35 | 75 | 20 |
| P5 | 45 | 50 | 0 |
| P6 | 50 | 65 | 0 |

# 5.22
> Consider a system running ten I/O-bound tasks and one CPU-bound task.
Assume that the I/O-bound tasks issue an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete.
Also assume that the context-switching overhead is 0.1 millisecond and that all processes are long-running tasks.
Describe the CPU utilization for a round-robin scheduler when:
(a) The time quantum is 1 millisecond
(b) The time quantum is 10 millisecond

## 答案
### A
$\frac{1.0ms}{1.0ms+0.1ms(context-switching)}=0.909%$
### B
$\frac{20ms}{(10ms*1.1)+10.1ms(context-switching)}=0.94$
# 5.25
> Explain the differences in how much the following scheduling algorithms discriminate in favor of short processes:(a) FCFS(b) RR(c) Multilevel feedback queues
## 答案
a 先來先服務（FCFS）：這種排程算法不太偏向於**短進程**，因為它按照進程到達的順序進行調度。如果有長進程在短進程之前到達，那麼短進程需要等待長進程執行完畢才能被執行，這可能導致**短進程的等待時間變長**。
b 輪轉（RR）：這種排程算法傾向於短進程，因為它使用固定的時間片來輪流執行進程。**當一個時間片用完時，如果進程還沒有執行完，它會被放回隊列的末尾**，而短進程通常可以在一個時間片內完成執行，因此有更多的機會被執行
c 多級反饋隊列：多級反饋隊列排程算法也傾向於短進程，因為它將進程按照優先級分成多個隊列，並且對於短進程使用較短的時間片，對於**長進程使用較長的時間片**。**這意味著短進程有更高的機會被執行**，因為它們會在較短的時間內完成，並且會經常被提升到較高優先級的隊列中。
# 6.7
> The pseudocode of Figure 6.15 illustrates the basic push() and pop() operations of an array-based stack. Assuming that this algorithm could be used in a concurrent environment, answer the following questions:
(a) What data have a race condition?
(b) How could the race condition be fixed?

## 答案
### A
push跟POP都會影響top數據會在過程中被修改，而導致is_empty有時候調用會有競爭
### B
在所有修改操作之前加上互斥鎖（mutex），以避免對堆疊頂部（top）的競爭條件。
# 6.15
> Explain why implementing synchronization primitives by disabling interrupts is not appropriate in a single-processor system if the synchronization primitives are to be used in user-level programs.
> 中文翻譯:解釋為什麼如果要在使用者層級程式中使用同步原語，則透過停用中斷來實現同步原語在單處理器系統中不合適。
## 答案
如果要在用戶級程序中使用同步原语，通過禁用中斷來實現同步原语在單處理器系統中是不合適的。如果一個用戶級程序被賦予禁用中斷的能力，那麼它可以禁用計時器中斷並阻止上下文切換發生，從而允許它使用處理器而不讓其他進程執行。
# 6.18
The implementation of mutex locks provided in Section 6.5 suffers from busy waiting.
Describe what changes would be necessary so that a process waiting to acquire a mutex lock would be blocked and placed into a waiting queue until the lock became available.
## 答案

push(item, mutex) { 
    wait(mutex); // Block and wait for mutex
    if (top < SIZE) {
        stack[top] = top++;
        signal(mutex); // Release mutex
    } else {
        signal(mutex); // Release mutex
        ERROR;
    }
} 

pop(mutex) { 
    wait(mutex); // Block and wait for mutex
    if (!is_empty()) { 
        top--;
        int item = stack[top];
        signal(mutex); // Release mutex
        return item; 
    } else {
        signal(mutex); // Release mutex
        ERROR;
    }
} 

is_empty(mutex) { 
    wait(mutex); // Block and wait for mutex
    if (top == 0) {
        signal(mutex); // Release mutex
        return true; 
    } else {
        signal(mutex); // Release mutex
        return false; 
    }
}