同步互斥(lec 17) spoc 思考题

• 有"spoc"标记的题是要求拿清华学分的同学要在实体课上完成，并按时提交到学生对应的ucore_code和os_exercises的git repo上。

个人思考题

背景

• 请给出程序正确性的定义或解释。
• 在一个新运行环境中程序行为与原来的预期不一致，是错误吗？
• 程序并发执行有什么好处和障碍？
• 什么是原子操作？

现实生活中的同步问题

• 家庭采购中的同步问题与操作系统中进程同步有什么区别？
• 如何通过枚举和分类方法检查同步算法的正确性？
• 尝试描述方案四的正确性。
• 互斥、死锁和饥饿的定义是什么？

临界区和禁用硬件中断同步方法

• 什么是临界区？
• 临界区的访问规则是什么？
• 禁用中断是如何实现对临界区的访问控制的？有什么优缺点？

基于软件的同步方法

• 尝试通过枚举和分类方法检查Peterson算法的正确性。
• 尝试准确描述Eisenberg同步算法，并通过枚举和分类方法检查其正确性。

高级抽象的同步方法

• 如何证明TS指令和交换指令的等价性？
• 为什么硬件原子操作指令能简化同步算法的实现？

小组思考题

1. （spoc）阅读简化x86计算机模拟器的使用说明，理解基于简化x86计算机的汇编代码。

2. （spoc)了解race condition. 进入race-condition代码目录。

   • 执行 ./x86.py -p loop.s -t 1 -i 100 -R dx， 请问dx的值是什么？
   • 执行 ./x86.py -p loop.s -t 2 -i 100 -a dx=3,dx=3 -R dx ， 请问dx的值是什么？
   • 执行 ./x86.py -p loop.s -t 2 -i 3 -r -a dx=3,dx=3 -R dx， 请问dx的值是什么？
   • 变量x的内存地址为2000, ./x86.py -p looping-race-nolock.s -t 1 -M 2000, 请问变量x的值是什么？
   • 变量x的内存地址为2000, ./x86.py -p looping-race-nolock.s -t 2 -a bx=3 -M 2000, 请问变量x的值是什么？为何每个线程要循环3次？
   • 变量x的内存地址为2000, ./x86.py -p looping-race-nolock.s -t 2 -M 2000 -i 4 -r -s 0， 请问变量x的值是什么？
   • 变量x的内存地址为2000, ./x86.py -p looping-race-nolock.s -t 2 -M 2000 -i 4 -r -s 1， 请问变量x的值是什么？
   • 变量x的内存地址为2000, ./x86.py -p looping-race-nolock.s -t 2 -M 2000 -i 4 -r -s 2， 请问变量x的值是什么？
   • 变量x的内存地址为2000, ./x86.py -p looping-race-nolock.s -a bx=1 -t 2 -M 2000 -i 1， 请问变量x的值是什么？

3. （spoc） 了解software-based lock, hardware-based lock, software-hardware-lock代码目录

   • 理解flag.s,peterson.s,test-and-set.s,ticket.s,test-and-test-and-set.s 请通过x86.py分析这些代码是否实现了锁机制？请给出你的实验过程和结论说明。能否设计新的硬件原子操作指令Compare-And-Swap,Fetch-And-Add？ ``` Compare-And-Swap

int CompareAndSwap(int ptr, int expected, int new) { int actual = ptr; if (actual == expected) *ptr = new; return actual; }

Fetch-And-Add

int FetchAndAdd(int ptr) { int old = ptr; *ptr = old + 1; return old; } ```