###### tags: `提升程式設計師的面試力`
# 15 Threads and Locks

在微軟、谷歌或亞馬遜的面試中，被要求用線程實現算法的情況並不常見（除非你在一個團隊工作，而這對你來說是一項特別重要的技能）。
然而，對於任何公司的面試官來說，評估你對線程，尤其是你對死鎖的理解。
本章將介紹該主題。

Java中的線程
Java 中的每個線程都是由 java.lang 的唯一對象創建和控制的。 線程類。 運行獨立應用程序時，會自動創建一個用戶線程來執行 main() 方法。 這個線程稱為主線程。
在 Java 中，我們可以通過以下兩種方式之一來實現線程：

Implementing the Runnable Interface

public interface Runnable {
    void run();
} 

public class RunnableThreadExample implements Runnable {
    public int count = 0;
    
    public void run() {
    System.out.println("RunnableThread starting.");
    try {
        while (count< 5) {
            Thread.sleep(500);
            count++;
        }
    } catch (InterruptedException exc) {
        System.out.println("RunnableThread interrupted.");
    }
        System.out.println("RunnableThread terminating.");
    }
}

public static void main(String[] args) {
    RunnableThreadExample instance = new RunnableThreadExample();
    Thread thread= new Thread(instance);
    thread.start();
    /* waits until above thread counts to 5 (slowly) */
    while (instance.count != 5) {
        try {
            Thread.sleep(250);
        } catch (InterruptedException exc) {
            exc.printStackTrace();
        }
    }
}

* 在上面的代碼中，觀察到我們真正需要做的就是讓我們的類實現 run() 方法
（第 4 行）。 然後另一個方法可以將類的實例傳遞給 new Thread (obj)（第 19 - 20 行）和
在線程上調用 start() （第 21 行）。

* 擴展線程類
或者，我們可以通過擴展 Thread 類來創建線程。 這幾乎總是意味著
我們重寫了 run() 方法，子類也可以在其內部顯式調用線程構造函數
構造函數。

public class ThreadExample extends Thread {
    int count = 0;

    public void run() {
        System.out.println("Thread starting.");
        try {
            while (count < 5) {
                Thread.sleep(500);
                System.out.println("In Thread, count is " + count);
            }
            count++;
        } catch (InterruptedException exc) {
            System.out.println("Thread interrupted.");
        }
        System.out.println("Thread terminating.");
    }
}

public class fxampleB {
    public static void main(String args[]) {
     ThreadExample instance = new ThreadExample();
        instance.start();

        while (instance.count != 5) {
            try {
                Thread.sleep(250);
            } catch (InterruptedException exc) {
                exc.printStackTrace();
            }
        }
    }
}

### 此代碼與第一種方法非常相似。 不同之處在於，由於我們正在擴展 Thread
類，而不僅僅是實現一個接口，我們可以在類本身的實例上調用 start()。

### 擴展線程類vs實現可運行接口
* 創建線程時，實現 Runnable 接口可能比擴展 Thread 類更可取的原因有兩個：
1. Java 不支持多重繼承。 因此，擴展 Thread 類意味著子類不能擴展任何其他類。 實現 Runnable 接口的類將能夠擴展另一個類。
2. 一個類可能只對可運行性感興趣，因此，繼承 Thread 類的全部開銷會過多

### Multithreading in Java Explained in 10 Minutes
{%youtube r_MbozD32eo %}

## Synchronization and Locks

* 給定進程中的線程共享相同的內存空間，這既是積極的，也是消極的。 它使線程能夠共享數據，這可能很有價值。 然而，它也為問題創造了機會當兩個線程同時修改一個資源時。 Java提供同步以控制訪問共享資源。

### Synchronized Methods

public class MyClass extends Thread {
    private String name;
    private MyObject myObj;
    
    public MyClass(MyObject obj, String n) {
        name = n;
        myObj = obj;
    }
    
    public void run() {
        myObj.foo(name);
    }
}

public class MyObject {
    public synchronized void foo(String name) {
        try {
            System.out.println("Thread " + name + ".foo(): starting");
            Thread.sleep(3000);
            System.out.println("Thread " + name + ".foo(): ending");
        } catch (InterruptedException exc) {
            System.out.println("Thread " + name + ": interrupted.");
        }
    }
}

當然，我們已經添加了代碼來故意減慢提款和存款的執行速度，因為它
有助於說明可能發生的潛在問題。您可能不會完全像這樣編寫代碼，但是
它所反映的情況非常非常真實。使用鎖將有助於保護共享資源不被修改
意想不到的方式。
### 死鎖和死鎖預防
死鎖是一個線程正在等待另一個線程持有的對象鎖的情況，而這
第二個線程正在等待第一個線程持有的對象鎖（或具有多個
線程）。由於每個線程都在等待另一個線程放棄鎖，所以它們都在等待
永遠。線程被稱為死鎖。
為了發生死鎖，您必須滿足以下所有四個條件：

- 1.互斥：在給定時間只有一個進程可以訪問資源。 （或者，更準確地說，有對資源的訪問受限。如果資源數量有限，也可能發生死鎖。）
- 2. 持有和等待：已經持有資源的進程可以請求額外的資源，而不會放棄它們當前的資源。
- 3. 無搶占：一個進程不能強行移除另一個進程的資源。
- 4. 循環等待：兩個或多個進程形成一個循環鏈，其中每個進程都在等待另一個進程
鏈中的資源。

### Q1 Thread vs. Process: What's the difference between a thread and a process?
* 線程與進程：線程和進程有什麼區別？
### A1
https://totoroliu.medium.com/program-process-thread-%E5%B7%AE%E7%95%B0-4a360c7345e5

進程Processes和線程Thread彼此相關，但本質上是不同的。

進程可以被認為是正在執行的程序的一個實例。
進程是分配系統資源（例如 CPU 時間和內存）的獨立實體。每個進程都在單獨的地址空間中執行，一個進程不能訪問另一個進程的變量和數據結構。如果一個進程希望訪問另一個進程的資源，則必須使用進程間通信。這些包括管道、文件、套接字和其他形式。

線程存在於進程中並共享進程的資源（包括其堆空間）。同一進程中的多個線程將共享相同的堆空間。這與進程有很大不同，進程不能直接訪問另一個進程的內存。每個線程仍然有自己的寄存器和自己的堆棧，但其他線程可以讀取和寫入堆內存。

線程是進程的特定執行路徑。當一個線程修改進程資源時，該更改立即對兄弟線程可見。

### Q2 Context Switch: How would you measure the time spent in a context switch?
* 上下文切換：您如何衡量在上下文切換中花費的時間？
### A2 從缺

### Q3 Dining Philosophers:
* In the famous dining philosophers problem, a bunch of philosophers are sitting around a circular table with one chopstick between each of them. A philosopher needs both chopsticks to eat, and always picks up the left chopstick before the right one. A deadlock could potentially occur if all the philosophers reached for the left chopstick atthe same time. Using threads and locks, implement a simulation of the dining philosophers problem that prevents deadlocks.
* 哲學家進餐：在著名的哲學家進餐問題中，一群哲學家是圍坐在一張圓桌旁，兩人中間夾著一根筷子。 哲學家需要兩者筷子要吃，總是先拿起左邊的筷子再拿起右邊的筷子。 僵局可能如果所有哲學家同時伸手去拿左筷子，就可能發生。 使用線程和鎖，實現防止死鎖的哲學家進餐問題的模擬。？
### A3 [從缺 危機就找維基](https://zh.wikipedia.org/zh-tw/%E5%93%B2%E5%AD%A6%E5%AE%B6%E5%B0%B1%E9%A4%90%E9%97%AE%E9%A2%98)


### Q4 Deadlock-Free Class: Design a class which provides a lock only if there are no possible deadlocks
* 無死鎖類：設計一個僅在沒有可能的死鎖時才提供鎖的類

* https://wangwilly.github.io/willywangkaa/2018/07/10/Operating-System-Deadlock/
* What is Deadlock & How to prevent Deadlock in Java? | Multithreading | Almighty Java
{%youtube 82IYrX0qdWs %}

### A4 從缺

### Q5 Call In Order: Suppose we have the following code:

public class Foo {
public Foo() { ... }
public void first() { ... }
public void second() { ... }
public void third() { ... }
}

* The same instance of Foo will be passed to three different threads. ThreadA will call first threadB will call second, and thread( will call third. Design a mechanism to ensure that first is called before second and second is called before third.
* Foo 的同一個實例將被傳遞給三個不同的線程。 ThreadA 將調用第一個 threadB 將調用第二個，thread( 將調用第三個。設計一種機制以確保在第二個之前調用第一個，在第三個之前調用第二個。
### A5 從缺

### Q6 Synchronized Methods:
* You are given a class with synchronized method A and a normal method B. If you have two threads in one instance of a program, can they both execute A at the same time? Can they execute A and B at the same time?
* 同步方法：給定一個具有同步方法 A 和普通方法 B 的類。如果一個程序的一個實例中有兩個線程，它們可以同時執行 A 嗎？ 他們可以同時執行A和B嗎？
### A6 從缺

### Q7 FizzBuzz:
* In the classic problem FizzBuzz, you are told to print the numbers from 1 to n. However,when the number is divisible by 3, print "Fizz''. When it is divisible by 5, print "Buzz''. When it is divisible by 3 and 5, print"FizzBuzz''. In this problem, you are asked to do this in a multithreaded way.Implement a multithreaded version of FizzBuzz with four threads. One thread checks for divisibility of 3 and prints"Fizz''. Another thread is responsible for divisibility of 5 and prints"Buzz''. A third thread is responsible for divisibility of 3 and 5 and prints "FizzBuzz''. A fourth thread does the numbers.
* 在經典問題 FizzBuzz 中，您被告知打印從 1 到 n 的數字。 但是，當數字可以被 3 整除時，打印“Fizz”。當它可以被 5 整除時，打印“Buzz”。 當它可以被 3 和 5 整除時，打印“FizzBuzz”。在這個問題中，您被要求以多線程方式執行此操作。使用四個線程實現 FizzBuzz 的多線程版本。一個線程檢查 3 的可除性並打印“ Fizz''。 另一個線程負責 5 的整除並打印“Buzz”。第三個線程負責 3 和 5 的整除並打印“FizzBuzz”。 第四個線程處理數字。
### A7 從缺

$n = 100;
for ($i=1; $i <= $n; $i++) { 
    if($i % 15 == 0){
        echo "FizzBuzz";
    }elseif($i % 3 == 0){
        echo "Fizz";
    }elseif($i % 5 == 0){
        echo "Buzz";
    }else{
        echo $i;
    }
}