Chapter 4

B10415053 四資工三 陳柏宏

一.
xv6運行在有多個獨立運行cpu的電腦上，而這些cpu共同操作在RAM上，也share其中的data structures，為了防止這些cpu互相干擾，而有了lock的概念。
Lock提供了mutual exclusion，讓一個時間點內只有一個cpu擁有lock，如此一來，我們稱這個lock protects the data item。

二.

三.

//初始化lock

1561 void
1562 initlock(struct spinlock *lk, char *name)
1563 {
1564 lk−>name = name;
1565 lk−>locked = 0;
1566 lk−>cpu = 0;
1567 }

//拿lock
//一個cpu佔據lock太長時間，可能會導致其他cpu浪費許多等待拿lock的時間

1573 void
1574 acquire(struct spinlock *lk)
1575 {
1576 pushcli(); //禁用interrupts 以防deadlock
1577 if(holding(lk))
1578 panic(“acquire”);
1579
1580 // The xchg is atomic.
1581 while(xchg(&lk−>locked, 1) != 0)
1582 ;
1583

//告訴compiler和processor不要store或remove這個點，確保在lock release之前，這個critical section對於其他cores是visible

1587 __sync_synchronize();
1588
1589 // 紀錄lock執行debugging之後的info
1590 lk−>cpu = mycpu();
1591 getcallerpcs(&lk, lk−>pcs);
1592 }

1600 //把lock release掉
1601 void
1602 release(struct spinlock *lk)
1603 {
1604 if(!holding(lk))
1605 panic(“release”);
1606
1607 lk−>pcs[0] = 0;
1608 lk−>cpu = 0;
1609

//告訴compiler和processor不要store或remove這個點，確保在lock release之前，這個critical section對於其他cores是visible

1615 __sync_synchronize();
1616

//把lock release，相當於lk->locked=0;

1620 asm volatile(“movl $0, %0” : “+m” (lk−>locked) : );
1621
1622 popcli();
1623 }

//藉由%ebp chain來記錄當前的call stack(pcs[])

1626 void
1627 getcallerpcs(void v, uint pcs[])
1628 {
1629 uint ebp;
1630 int i;
1631
1632 ebp = (uint)v − 2;
1633 for(i = 0; i < 10; i++){
1634 if(ebp == 0 || ebp < (uint)KERNBASE || ebp == (uint*)0xffffffff)
1635 break;
1636 pcs[i] = ebp[1]; // saved %eip
1637 ebp = (uint*)ebp[0]; // saved %ebp
1638 }
1639 for(; i < 10; i++)
1640 pcs[i] = 0;
1641 }

//確認這個cpu是否擁有lock

1644 int
1645 holding(struct spinlock *lock)
1646 {
1647 return lock−>locked && lock−>cpu == mycpu();
1648 }
1649

//Pushcli/popcli與cli/sti類似(中斷遮蔽/解除中斷遮蔽)，但pushcli和popcli需要matched，也就是要2個pushcli才能解除2個popcli。除此之外，若interrupts解除了，pushcli和popcli也會自行解除

1653
1654 void
1655 pushcli(void)
1656 {
1657 int eflags;
1658
1659 eflags = readeflags();
1660 cli();
1661 if(mycpu()−>ncli == 0)
1662 mycpu()−>intena = eflags & FL_IF;
1663 mycpu()−>ncli += 1;
1664 }
1665

1666 void
1667 popcli(void)
1668 {
1669 if(readeflags()&FL_IF)
1670 panic(“popcli − interruptible”);
1671 if(−−mycpu()−>ncli < 0)
1672 panic(“popcli”);
1673 if(mycpu()−>ncli == 0 && mycpu()−>intena)
1674 sti();
1675 }

四.

var markdown = $(".markdown-body");
//smooth all hash trigger scrolling
function smoothHashScroll() {
var hashElements = $(“a[href^=’#’]”).toArray();
for (var i = 0; i < hashElements.length; i++) {
var element = hashElements[i];
var $element = $(element);
var hash = element.hash;
if (hash) {
$element.on('click', function (e) { // store hash var hash = this.hash; if ($(hash).length <= 0) return;
// prevent default anchor click behavior
e.preventDefault();
// animate
$(‘body, html’).stop(true, true).animate({
scrollTop: $(hash).offset().top
}, 100, “linear”, function () {
// when done, add hash to url
// (default click behaviour)
window.location.hash = hash;
});
});
}
}
}
smoothHashScroll();
var toc = $(’.ui-toc’);
var tocAffix = $(’.ui-affix-toc’);
var tocDropdown = $(’.ui-toc-dropdown’);
//toc
tocDropdown.click(function (e) {
e.stopPropagation();
});
var enoughForAffixToc = true;
function generateScrollspy() {
$(document.body).scrollspy({
target: ‘’
});
$(document.body).scrollspy(‘refresh’);
if (enoughForAffixToc) {
toc.hide();
tocAffix.show();
} else {
tocAffix.hide();
toc.show();
}
$(document.body).scroll(); } function windowResize() { //toc right var paddingRight = parseFloat(markdown.css('padding-right')); var right = ($(window).width() - (markdown.offset().left + markdown.outerWidth() - paddingRight));
toc.css(‘right’, right + ‘px’);
//affix toc left
var newbool;
var rightMargin = (markdown.parent().outerWidth() - markdown.outerWidth()) / 2;
//for ipad or wider device
if (rightMargin >= 133) {
newbool = true;
var affixLeftMargin = (tocAffix.outerWidth() - tocAffix.width()) / 2;
var left = markdown.offset().left + markdown.outerWidth() - affixLeftMargin;
tocAffix.css(‘left’, left + ‘px’);
} else {
newbool = false;
}
if (newbool != enoughForAffixToc) {
enoughForAffixToc = newbool;
generateScrollspy();
}
}
$(window).resize(function () {
windowResize();
});
$(document).ready(function () {
windowResize();
generateScrollspy();
});
//remove hash
function removeHash() {
window.location.hash = ‘’;
}
var backtotop = $(’.back-to-top’);
var gotobottom = $(’.go-to-bottom’);
backtotop.click(function (e) {
e.preventDefault();
e.stopPropagation();
if (scrollToTop)
scrollToTop();
removeHash();
});
gotobottom.click(function (e) {
e.preventDefault();
e.stopPropagation();
if (scrollToBottom)
scrollToBottom();
removeHash();
});
var toggle = $(’.expand-toggle’);
var tocExpand = false;
checkExpandToggle();
toggle.click(function (e) {
e.preventDefault();
e.stopPropagation();
tocExpand = !tocExpand;
checkExpandToggle();
})
function checkExpandToggle () {
var toc = $(’.ui-toc-dropdown .toc’);
var toggle = $(’.expand-toggle’);
if (!tocExpand) {
toc.removeClass(‘expand’);
toggle.text(‘Expand all’);
} else {
toc.addClass(‘expand’);
toggle.text(‘Collapse all’);
}
}
function scrollToTop() {
$(‘body, html’).stop(true, true).animate({
scrollTop: 0
}, 100, “linear”);
}
function scrollToBottom() {
$(‘body, html’).stop(true, true).animate({
scrollTop: $(document.body)[0].scrollHeight
}, 100, “linear”);
}