操作系统导论OSTEP 第28章作业答案 锁
问题4生成不同的中断频率，运行结果会不同，仍然存在竞态。问题5程序test-and-set.s.var mutex.var count.main.top.acquire# 获取锁mov$1, %axxchg %ax, mutex# atomic swap of 1 and mutextest $0, %ax# if we get 0 back: lock is free!jne.acquire#
·
问题2
linux.> ./x86.py -p flag.s -M flag,count -R ax,bx -c
ARG seed 0
ARG numthreads 2
ARG program flag.s
ARG interrupt frequency 50
ARG interrupt randomness False
ARG procsched
ARG argv
ARG load address 1000
ARG memsize 128
ARG memtrace flag,count
ARG regtrace ax,bx
ARG cctrace False
ARG printstats False
ARG verbose False
flag count ax bx Thread 0 Thread 1
0 0 0 0
0 0 0 0 1000 mov flag, %ax
0 0 0 0 1001 test $0, %ax
0 0 0 0 1002 jne .acquire
1 0 0 0 1003 mov $1, flag
1 0 0 0 1004 mov count, %ax
1 0 1 0 1005 add $1, %ax
1 1 1 0 1006 mov %ax, count
0 1 1 0 1007 mov $0, flag
0 1 1 -1 1008 sub $1, %bx
0 1 1 -1 1009 test $0, %bx
0 1 1 -1 1010 jgt .top
0 1 1 -1 1011 halt
0 1 0 0 ----- Halt;Switch ----- ----- Halt;Switch -----
0 1 0 0 1000 mov flag, %ax
0 1 0 0 1001 test $0, %ax
0 1 0 0 1002 jne .acquire
1 1 0 0 1003 mov $1, flag
1 1 1 0 1004 mov count, %ax
1 1 2 0 1005 add $1, %ax
1 2 2 0 1006 mov %ax, count
0 2 2 0 1007 mov $0, flag
0 2 2 -1 1008 sub $1, %bx
0 2 2 -1 1009 test $0, %bx
0 2 2 -1 1010 jgt .top
0 2 2 -1 1011 halt
问题4
生成不同的中断频率，运行结果会不同，仍然存在竞态。
问题5
程序test-and-set.s
.var mutex
.var count
.main
.top
.acquire # 获取锁
mov $1, %ax
xchg %ax, mutex # atomic swap of 1 and mutex
test $0, %ax # if we get 0 back: lock is free!
jne .acquire # if not, try again
# critical section
mov count, %ax # get the value at the address
add $1, %ax # increment it
mov %ax, count # store it back
# release lock
mov $0, mutex # 释放锁
# see if we're still looping
sub $1, %bx
test $0, %bx
jgt .top
halt
问题6
linux.> ./x86.py -p test-and-set.s -M mutex,count -R ax,bx -i 1 -c
linux.> ./x86.py -p test-and-set.s -M mutex,count -R ax,bx -i 6 -c
linux.> ./x86.py -p test-and-set.s -M mutex,count -R ax,bx -i 11 -c
linux.> ./x86.py -p test-and-set.s -M mutex,count -R ax,bx -i 16 -c
linux.> ./x86.py -p test-and-set.s -M mutex,count -R ax,bx -i 21 -c
# 上述命令执行结果如下
ARG seed 0
ARG numthreads 2
ARG program test-and-set.s
ARG interrupt frequency 1
ARG interrupt randomness False
ARG procsched
ARG argv
ARG load address 1000
ARG memsize 128
ARG memtrace mutex,count
ARG regtrace ax,bx
ARG cctrace False
ARG printstats False
ARG verbose False
mutex count ax bx Thread 0 Thread 1
0 0 0 0
0 0 1 0 1000 mov $1, %ax
0 0 0 0 ------ Interrupt ------ ------ Interrupt ------
0 0 1 0 1000 mov $1, %ax
0 0 1 0 ------ Interrupt ------ ------ Interrupt ------
1 0 0 0 1001 xchg %ax, mutex
1 0 1 0 ------ Interrupt ------ ------ Interrupt ------
1 0 1 0 1001 xchg %ax, mutex
1 0 0 0 ------ Interrupt ------ ------ Interrupt ------
1 0 0 0 1002 test $0, %ax
1 0 1 0 ------ Interrupt ------ ------ Interrupt ------
1 0 1 0 1002 test $0, %ax
1 0 0 0 ------ Interrupt ------ ------ Interrupt ------
1 0 0 0 1003 jne .acquire
1 0 1 0 ------ Interrupt ------ ------ Interrupt ------
1 0 1 0 1003 jne .acquire
1 0 0 0 ------ Interrupt ------ ------ Interrupt ------
1 0 0 0 1004 mov count, %ax
1 0 1 0 ------ Interrupt ------ ------ Interrupt ------
1 0 1 0 1000 mov $1, %ax
1 0 0 0 ------ Interrupt ------ ------ Interrupt ------
1 0 1 0 1005 add $1, %ax
1 0 1 0 ------ Interrupt ------ ------ Interrupt ------
1 0 1 0 1001 xchg %ax, mutex
1 0 1 0 ------ Interrupt ------ ------ Interrupt ------
1 1 1 0 1006 mov %ax, count
1 1 1 0 ------ Interrupt ------ ------ Interrupt ------
1 1 1 0 1002 test $0, %ax
1 1 1 0 ------ Interrupt ------ ------ Interrupt ------
0 1 1 0 1007 mov $0, mutex
0 1 1 0 ------ Interrupt ------ ------ Interrupt ------
0 1 1 0 1003 jne .acquire
0 1 1 0 ------ Interrupt ------ ------ Interrupt ------
0 1 1 -1 1008 sub $1, %bx
0 1 1 0 ------ Interrupt ------ ------ Interrupt ------
0 1 1 0 1000 mov $1, %ax
0 1 1 -1 ------ Interrupt ------ ------ Interrupt ------
0 1 1 -1 1009 test $0, %bx
0 1 1 0 ------ Interrupt ------ ------ Interrupt ------
1 1 0 0 1001 xchg %ax, mutex
1 1 1 -1 ------ Interrupt ------ ------ Interrupt ------
1 1 1 -1 1010 jgt .top
1 1 0 0 ------ Interrupt ------ ------ Interrupt ------
1 1 0 0 1002 test $0, %ax
1 1 1 -1 ------ Interrupt ------ ------ Interrupt ------
1 1 1 -1 1011 halt
1 1 0 0 ----- Halt;Switch ----- ----- Halt;Switch -----
1 1 0 0 ------ Interrupt ------ ------ Interrupt ------
1 1 0 0 1003 jne .acquire
1 1 0 0 ------ Interrupt ------ ------ Interrupt ------
1 1 1 0 1004 mov count, %ax
1 1 1 0 ------ Interrupt ------ ------ Interrupt ------
1 1 2 0 1005 add $1, %ax
1 1 2 0 ------ Interrupt ------ ------ Interrupt ------
1 2 2 0 1006 mov %ax, count
1 2 2 0 ------ Interrupt ------ ------ Interrupt ------
0 2 2 0 1007 mov $0, mutex
0 2 2 0 ------ Interrupt ------ ------ Interrupt ------
0 2 2 -1 1008 sub $1, %bx
0 2 2 -1 ------ Interrupt ------ ------ Interrupt ------
0 2 2 -1 1009 test $0, %bx
0 2 2 -1 ------ Interrupt ------ ------ Interrupt ------
0 2 2 -1 1010 jgt .top
0 2 2 -1 ------ Interrupt ------ ------ Interrupt ------
0 2 2 -1 1011 halt
ARG seed 0
ARG numthreads 2
ARG program test-and-set.s
ARG interrupt frequency 6
ARG interrupt randomness False
ARG procsched
ARG argv
ARG load address 1000
ARG memsize 128
ARG memtrace mutex,count
ARG regtrace ax,bx
ARG cctrace False
ARG printstats False
ARG verbose False
mutex count ax bx Thread 0 Thread 1
0 0 0 0
0 0 1 0 1000 mov $1, %ax
1 0 0 0 1001 xchg %ax, mutex
1 0 0 0 1002 test $0, %ax
1 0 0 0 1003 jne .acquire
1 0 0 0 1004 mov count, %ax
1 0 1 0 1005 add $1, %ax
1 0 0 0 ------ Interrupt ------ ------ Interrupt ------
1 0 1 0 1000 mov $1, %ax
1 0 1 0 1001 xchg %ax, mutex
1 0 1 0 1002 test $0, %ax
1 0 1 0 1003 jne .acquire
1 0 1 0 1000 mov $1, %ax
1 0 1 0 1001 xchg %ax, mutex
1 0 1 0 ------ Interrupt ------ ------ Interrupt ------
1 1 1 0 1006 mov %ax, count
0 1 1 0 1007 mov $0, mutex
0 1 1 -1 1008 sub $1, %bx
0 1 1 -1 1009 test $0, %bx
0 1 1 -1 1010 jgt .top
0 1 1 -1 1011 halt
0 1 1 0 ----- Halt;Switch ----- ----- Halt;Switch -----
0 1 1 0 ------ Interrupt ------ ------ Interrupt ------
0 1 1 0 1002 test $0, %ax
0 1 1 0 1003 jne .acquire
0 1 1 0 1000 mov $1, %ax
1 1 0 0 1001 xchg %ax, mutex
1 1 0 0 1002 test $0, %ax
1 1 0 0 1003 jne .acquire
1 1 0 0 ------ Interrupt ------ ------ Interrupt ------
1 1 1 0 1004 mov count, %ax
1 1 2 0 1005 add $1, %ax
1 2 2 0 1006 mov %ax, count
0 2 2 0 1007 mov $0, mutex
0 2 2 -1 1008 sub $1, %bx
0 2 2 -1 1009 test $0, %bx
0 2 2 -1 ------ Interrupt ------ ------ Interrupt ------
0 2 2 -1 1010 jgt .top
0 2 2 -1 1011 halt
ARG seed 0
ARG numthreads 2
ARG program test-and-set.s
ARG interrupt frequency 11
ARG interrupt randomness False
ARG procsched
ARG argv
ARG load address 1000
ARG memsize 128
ARG memtrace mutex,count
ARG regtrace ax,bx
ARG cctrace False
ARG printstats False
ARG verbose False
mutex count ax bx Thread 0 Thread 1
0 0 0 0
0 0 1 0 1000 mov $1, %ax
1 0 0 0 1001 xchg %ax, mutex
1 0 0 0 1002 test $0, %ax
1 0 0 0 1003 jne .acquire
1 0 0 0 1004 mov count, %ax
1 0 1 0 1005 add $1, %ax
1 1 1 0 1006 mov %ax, count
0 1 1 0 1007 mov $0, mutex
0 1 1 -1 1008 sub $1, %bx
0 1 1 -1 1009 test $0, %bx
0 1 1 -1 1010 jgt .top
0 1 0 0 ------ Interrupt ------ ------ Interrupt ------
0 1 1 0 1000 mov $1, %ax
1 1 0 0 1001 xchg %ax, mutex
1 1 0 0 1002 test $0, %ax
1 1 0 0 1003 jne .acquire
1 1 1 0 1004 mov count, %ax
1 1 2 0 1005 add $1, %ax
1 2 2 0 1006 mov %ax, count
0 2 2 0 1007 mov $0, mutex
0 2 2 -1 1008 sub $1, %bx
0 2 2 -1 1009 test $0, %bx
0 2 2 -1 1010 jgt .top
0 2 1 -1 ------ Interrupt ------ ------ Interrupt ------
0 2 1 -1 1011 halt
0 2 2 -1 ----- Halt;Switch ----- ----- Halt;Switch -----
0 2 2 -1 1011 halt
ARG seed 0
ARG numthreads 2
ARG program test-and-set.s
ARG interrupt frequency 16
ARG interrupt randomness False
ARG procsched
ARG argv
ARG load address 1000
ARG memsize 128
ARG memtrace mutex,count
ARG regtrace ax,bx
ARG cctrace False
ARG printstats False
ARG verbose False
mutex count ax bx Thread 0 Thread 1
0 0 0 0
0 0 1 0 1000 mov $1, %ax
1 0 0 0 1001 xchg %ax, mutex
1 0 0 0 1002 test $0, %ax
1 0 0 0 1003 jne .acquire
1 0 0 0 1004 mov count, %ax
1 0 1 0 1005 add $1, %ax
1 1 1 0 1006 mov %ax, count
0 1 1 0 1007 mov $0, mutex
0 1 1 -1 1008 sub $1, %bx
0 1 1 -1 1009 test $0, %bx
0 1 1 -1 1010 jgt .top
0 1 1 -1 1011 halt
0 1 0 0 ----- Halt;Switch ----- ----- Halt;Switch -----
0 1 1 0 1000 mov $1, %ax
1 1 0 0 1001 xchg %ax, mutex
1 1 0 0 1002 test $0, %ax
1 1 0 0 1003 jne .acquire
1 1 0 0 ------ Interrupt ------ ------ Interrupt ------
1 1 1 0 1004 mov count, %ax
1 1 2 0 1005 add $1, %ax
1 2 2 0 1006 mov %ax, count
0 2 2 0 1007 mov $0, mutex
0 2 2 -1 1008 sub $1, %bx
0 2 2 -1 1009 test $0, %bx
0 2 2 -1 1010 jgt .top
0 2 2 -1 1011 halt
ARG seed 0
ARG numthreads 2
ARG program test-and-set.s
ARG interrupt frequency 21
ARG interrupt randomness False
ARG procsched
ARG argv
ARG load address 1000
ARG memsize 128
ARG memtrace mutex,count
ARG regtrace ax,bx
ARG cctrace False
ARG printstats False
ARG verbose False
mutex count ax bx Thread 0 Thread 1
0 0 0 0
0 0 1 0 1000 mov $1, %ax
1 0 0 0 1001 xchg %ax, mutex
1 0 0 0 1002 test $0, %ax
1 0 0 0 1003 jne .acquire
1 0 0 0 1004 mov count, %ax
1 0 1 0 1005 add $1, %ax
1 1 1 0 1006 mov %ax, count
0 1 1 0 1007 mov $0, mutex
0 1 1 -1 1008 sub $1, %bx
0 1 1 -1 1009 test $0, %bx
0 1 1 -1 1010 jgt .top
0 1 1 -1 1011 halt
0 1 0 0 ----- Halt;Switch ----- ----- Halt;Switch -----
0 1 1 0 1000 mov $1, %ax
1 1 0 0 1001 xchg %ax, mutex
1 1 0 0 1002 test $0, %ax
1 1 0 0 1003 jne .acquire
1 1 1 0 1004 mov count, %ax
1 1 2 0 1005 add $1, %ax
1 2 2 0 1006 mov %ax, count
0 2 2 0 1007 mov $0, mutex
0 2 2 -1 1008 sub $1, %bx
0 2 2 -1 ------ Interrupt ------ ------ Interrupt ------
0 2 2 -1 1009 test $0, %bx
0 2 2 -1 1010 jgt .top
0 2 2 -1 1011 halt
此时代码总能按预期工作，但有时会导致CPU使用率不高。
问题7
./x86.py -p test-and-set.s -M mutex,count -R ax,bx -a bx=5 -P 1100111000111000111000 -i 10 -c
正确的事发生了。
问题8
linux.> cat peterson.s
# array of 2 integers (each size 4 bytes)
# load address of flag into fx register
# access flag[] with 0(%fx,%index,4)
# where %index is a register holding 0 or 1
# index reg contains 0 -> flag[0], if 1->flag[1]
.var flag 2
# global turn variable
.var turn
# global count
.var count
.main
# put address of flag into fx
lea flag, %fx
# assume thread ID is in bx (0 or 1, scale by 4 to get proper flag address)
mov %bx, %cx # bx: self, now copies to cx
neg %cx # cx: - self
add $1, %cx # cx: 1 - self
.acquire
mov $1, 0(%fx,%bx,4) # flag[self] = 1
mov %cx, turn # turn = 1 - self
.spin1
mov 0(%fx,%cx,4), %ax # flag[1-self]
test $1, %ax
jne .fini # if flag[1-self] != 1, skip past loop to .fini
.spin2 # just labeled for fun, not needed
mov turn, %ax
test %cx, %ax # compare 'turn' and '1 - self'
je .spin1 # if turn==1-self, go back and start spin again
# fall out of spin
.fini
# do critical section now
mov count, %ax
add $1, %ax
mov %ax, count
.release
mov $0, 0(%fx,%bx,4) # flag[self] = 0
# end case: make sure it's other's turn
mov %cx, turn # turn = 1 - self
halt
问题9
只有使用-a给%bx赋初值时锁才有效，否则可能会出现错误结果。
问题14
linux.> cat yield.s
.var mutex
.var count
.main
.top
.acquire
mov $1, %ax
xchg %ax, mutex # atomic swap of 1 and mutex
test $0, %ax # if we get 0 back: lock is free!
je .acquire_done
yield # if not, yield and try again
j .acquire
.acquire_done
# critical section
mov count, %ax # get the value at the address
add $1, %ax # increment it
mov %ax, count # store it back
# release lock
mov $0, mutex
# see if we're still looping
sub $1, %bx
test $0, %bx
jgt .top
halt
分别调用命令：
linux.> ./x86.py -p yield.s -M mutex,count -R ax,bx -a bx=5 -P 1100111000111000111000 -i 10 -c
linux.> ./x86.py -p test-and-set.s -M mutex,count -R ax,bx -a bx=5 -P 1100111000111000111000 -i 10 -c
可以观察到在锁被占用时，yield.s主动放弃CPU，而test-and-set.s会自旋，浪费资源。
问题15
这是一个两阶段锁，其优点参考本章最后一节。
鸿蒙生态一站式服务平台。
更多推荐
1078
0
0- 0
- 分享
所有评论(0)
您需要登录才能发言
查看更多评论
已为社区贡献1条内容
