文章目錄
- Q1
- i
- ii
- Q2
- i
- ii
- Q5
- (a) Our most basic synchronization primitive is a lock. When would we use a lock? When we use a lock, what concurrency bug are we trying to prevent?
- b) Deadlock is an important concurrency bug that can be hard to spot. What are the four necessary and sufficient conditions for deadlock?
- (c) As we considered advanced synchronization techniques, we considered situations where we might want to acquire multiple locks. As we know, acquiring multiple locks can be a dangerous requirement, and so we studied conservative two-phase locking. What condition of deadlock does conservative two-phase locking break? Explain how.
- (d) Consider the following code. Is it susceptible to deadlock? If so, fix the code so it is not. If not, explain why.
這兩道題主要考察的是程序和線程中，對于全局變量的了解。
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
int global = 0;
void foo(int a) {
global += 1;
a += 3;
printf("Thread, global= %d, a= %d\n", global, a);
}
int main() {
int a = 5;
int child = fork();
global += 5;
if (child == 0) {
global += 1;
printf("child 1, global = %d, pid = %d \n", global, getpid());//6
}
else {
child = fork();
if (child == 0) {
foo(a);
printf("child 2, a = %d, pid = %d \n", a, getpid());//5
}
else {
global += 2;
printf("parent, global = %d, pid = %d \n", global, getpid());//7
}
}
return 0;
} Q1
i
運作代碼如上：
則結果可能為：
parent, global = 7
Thread, global= 6， a=8
child 2, a = 5
child 1, global = 可能的輸出順序，總共有432*1 = 24種，這4種輸出排列組合，順序不一樣，則輸出不一樣。
ii
會發生變化：
parent, global = 7
Thread, global= 6， a=8
child 2, a = 8 ## 隻有這裡發生變化
child 1, global = child 2中的值會變成8。因為a是全局變量，則函數對它的修改會在child 2這個程序中造成影響。其他沒有影響。
Q2
global_x = 0;
foo (int a) {
global_x += 1;
a += 3;
printf (" Thread: global_x=%d, a=%din", global_x, a)
}
int main () {
int a= 10;
thread_create(foo, a);// 建立線程，去執行了。
a = a + 1;// 此時的a，還是10 + 1，因為是局部變量
thread_create(foo, a);// 建立線程，去執行了。
global_x += 5;// 此時的global，不一定是0，因為上面有兩個線程，是以在這裡有三種情況：
1. 兩個線程都沒執行，5
2. 執行了1個，那就是6
3. 執行了2個，那就是7
printf (" Checkpoint1: global_x=%d, a=%d\n", global_x, a);
// 是以這裡的輸出有三種可能：5, 11 6, 11, 7,11
// 在這裡阻塞，等待兩個線程完成
thread_join();thread_join();
// 執行到這裡，兩個線程都執行完畢了。是以這裡global一定是7，a局部變量，就是11
printf ("Checkpoint2: global_x=%d, a=%d1n", global_x, a);
} i
三種輸出可能：
Checkpoint1: global_x=5, a=11
Thread: global_x=6, a=12
Thread: global_x=7, a=12
Checkpoint2: global_x=7, a=11 Thread: global_x=1, a=12
Checkpoint1: global_x=6, a=11
Thread: global_x=7, a=12
Checkpoint2: global_x=7, a=11 Thread: global_x=6, a=12
Thread: global_x=7, a=12
Checkpoint1: global_x=7, a=11
Checkpoint2: global_x=7, a=11 ii
沒看懂題意說這個使用者核心線程是想幹啥。
Q5
- Deadlock
(a) Our most basic synchronization primitive is a lock. When would we use a lock? When we use a lock, what concurrency bug are we trying to prevent?
Locks are used to guard a shared data variable, like the account balance shown here. If all accesses to a data variable are guarded (surrounded by a synchronized block) by the same lock object, then those accesses will be guaranteed to be atomic — uninterrupted by other threads.
Deadlock occurs when a set of threads is waiting on an event that can only be
generated by another thread in the set.
Race conditions occur when results change based on scheduling due to a failure to protect shared data.
上面是标準答案，其實就是死鎖bug和非死鎖bug
Two types of bugs – Deadlocks: threads cannot execute any further
and wait for each other – Non-deadlock bugs: non deadlock but incorrect
results when threads execute
Non deadlock and deadlock bugs.
Of the non-deadlock bugs, the main types are:
Atomicity Violation Bugs ： atomicity assumptions madeby programmer are violated during executionof concurrent threads。fix : Always use locks when accessing shared data
Order Violation Bugs:desired order of memory accesses is flipped during concurrent
execution – Fix: condition variables
b) Deadlock is an important concurrency bug that can be hard to spot. What are the four necessary and sufficient conditions for deadlock?
死鎖的四個必要條件 ：
Mutual exclusion
Hold-and-wait: They hold the lock while waiting for other resources
No preemption: Resources cannot be forcible removed from threads that hold them.
Circular wait: There is a circular chain of threads s.t. each holds one or more resources that are being requested by the next thread in the chain.
fix : destory one conditions.
© As we considered advanced synchronization techniques, we considered situations where we might want to acquire multiple locks. As we know, acquiring multiple locks can be a dangerous requirement, and so we studied conservative two-phase locking. What condition of deadlock does conservative two-phase locking break? Explain how.
兩階段鎖 two-phase locking
Conservative two-phased locking
Requires you to gather all locks before beginning your operations, and, if you
can’t, you must release any you have acquired. Breaks hold and wait.
也就是說，如果有兩把鎖，隻有擷取兩把鎖才去操作資源，否則要放開鎖。破壞了四個條件中的hold and wait.
Conservative Two-Phase Locking
• A thread must:
– Acquire all locks it will need
• If all locks cannot be acquired, release any already acquired
and begin again
– Make necessary changes, commit, and release locks
• Thus B cannot see any of A’s changes until A
commits and releases the lock
• Provides serializability
• Prevents deadlock
(d) Consider the following code. Is it susceptible to deadlock? If so, fix the code so it is not. If not, explain why.
不會出現死鎖。主要是因為這兩個線程不會出現互相等待資源的情況。總共2個資源，都是按照順序鎖1和2的，如果一個先鎖1後鎖2，另一個先鎖2後鎖1，這種情況就會死鎖了。
下面是一些相關知識點
首先shared 鎖是讀鎖，excude 鎖是寫鎖。
A transaction is said to follow the Two-Phase Locking protocol if Locking and Unlocking can be done in two phases.
Growing Phase: New locks on data items may be acquired but none can be released.
Shrinking Phase: Existing locks may be released but no new locks can be acquired.