文章目录
- 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.