Deadlock的問題

面試很愛的問題之ㄧ~
之前都不會回答 , 實在是沒什麼感覺 :P

直到前幾天, 我可愛的minix 一值hang在某各位置, 看assembly發現它schedule到idle,
這表示qeueue裡面沒有東西可以跑了, 表示大家都跑去睡覺了........表示Deadlock了!!

pg->tty->pg(睡覺中).....tty也去睡覺....然後deadlock....

performance update

100000 times fork(241):
15.68 1.00 7.93
15.41 1.35 7.78
15.51 1.06 8.08
15.63 1.16 7.95
15.75 1.33 7.85
==============================
重新安裝minix,全部重測
(3.1.2a):
fork:
10.26 real 0.11 user 8.38 sys 33.45 0.43 27.63
10.30 real 0.20 user 8.40 sys 33.40 0.46 27.70
10.28 real 0.13 user 8.53 sys 33.46 0.53 27.66
10.30 real 0.13 user 8.56 sys 33.28 0.75 26.96
10.31 real 0.13 user 8.45 sys 33.28 0.48 27.98
10.30 real 0.15 user 8.28 sys
10.31 real 0.13 user 8.48 sys
matrix:
33.43 real 33.33 user 0.10 sys
33.41 real 33.40 user 0.01 sys
33.66 real 33.60 user 0.06 sys
33.65 real 33.61 user 0.03 sys
(v170 3.1.2ar0):
fork:
11.33 real 0.26 user 8.81 sys 38.46 0.83 31.26
11.31 real 0.21 user 9.00 sys 38.61 0.68 31.21
11.28 real 0.26 user 8.86 sys 38.36 0.68 30.98
11.28 real 0.18 user 9.13 sys 38.40 0.95 31.11
11.31 real 0.16 user 8.98 sys 38.40 0.63 31.56
matrix:
33.58 real 33.55 user 0.03 sys
33.56 real 33.55 user 0.01 sys
33.56 real 33.53 user 0.03 sys
(v182 3.1.2ar1)
fork:
12.73 real 0.45 user 10.36 sys 42.40 1.61 34.31
12.73 real 0.40 user 10.18 sys 42.41 1.31 34.31
12.75 real 0.36 user 10.25 sys 42.45 1.75 34.35
12.75 real 0.40 user 10.33 sys 42.46 1.26 35.40
12.76 real 0.38 user 10.18 sys 42.51 1.13 34.75
matrix
33.35 real 33.35
33.36 33.36
33.41 33.41
(nophys 3.1.2ar2) (nophys 3.1.2ar216)
fork: 100000 times:
4.63 real 0.30 user 2.48 sys
4.65 real 0.30 user 2.30 sys
4.66 real 0.26 user 2.45 sys
4.56 real 0.33 user 2.28 sys
4.65 real 0.30 user 2.06 sys
matrix
33.86 real 33.75 user 0.11 sys
33.86 real 33.81 user 0.05 sys
33.86 real 33.76 user 0.10 sys

==========================================================
今天發現wbinvd跟page內部的cache disable在我的程式中都是不必要的存在><"
拿掉wbinvd(release/3.1.2ar88 ,把大部分copy都交給pg做....)
30000 times fork()
real user sys
4.91 0.36 2.51
5.00 0.40 2.60
4.90 0.25 2.75
4.91 0.38 2.38
4.93 0.25 2.56
matrix
real user sys
33.35 33.18 0.15
33.43 33.36 0.06
33.45 33.40 0.05
33.51 33.26 025

===================================================
30000 times fork
pager+MM server:
1:17.76 5.81 41.81

matrix
36.03 34.03 1.96

svn上版本好亂...><"

svn://server170/test170 -->沒有page, 只有把mm移出來的stable版本
svn://server170/test174 version 182-->有page 的stable版本
svn://server170/test174 version 192-->加了linear copy 的stable版本, 但stack加大仍會爛的版本

matrix execution time

256x256 matrix multiplication run 1 times
MM server+ pager:(release/3.1.2ar12)
real usr sys
3.66 3.36 0.30
3.66 3.36 0.30
3.66 3.36 0.30
3.68 3.36 0.28
MM server:(release/3.1.2ar11)
real usr sys
3.36 3.35 0.01
3.36 3.35 0.01
3.36 3.35 0.01
3.38 3.36 0.01
original:(release/3.1.2a)
real usr sys
3.40 3.38 0.01
3.38 3.38 0.00
3.36 3.36 0.01
3.38 3.38 0.00
256x256 matrix multiplication run 10 times
MM server+ pager:(release/3.1.2ar12)
real usr sys
33.58 33.50 0.08
33.61 33.50 0.11
33.66 33.55 0.08
33.70 33.60 0.10
33.73 33.63 0.08
33.85 33.75 0.08
33.85 33.75 0.08
33.85 33.75 0.08
33.85 33.75 0.10

MM server:(release/3.1.2ar11)
real usr sys
33.46 33.45 0.00
33.48 33.48 0.00
33.53 33.51 0.01
33.56 33.56 0.00
33.60 33.56 0.03
33.61 33.61 0.00
33.65 33.63 0.01
33.66 33.66 0.00
33.70 33.65 0.01

original:(release/3.1.2a)
real usr sys
33.46 33.45 0.00
33.46 33.46 0.00
33.50 33.50 0.00
33.51 33.50 0.01
33.53 33.51 0.01

如何設定minix 3的環境

1. install all binary packge
1)insert the minix cd
2)enter 'packman'
3)choose what u want to install
2.setup net
1)create and edit /etc/rc.net
2)write down "ifconfig ...." directly in rc.net
3)or it will setup dhcp automaticallyss
3.recompile minix image
1)cd /usr/src/tools
2)enter 'make' can tell u options it has
3)u can change image in boot monitor by type 'image=boot/image/...'
4)then boot
4.how to setup openssh
1)/usr/local/etc/rc.d/sshd start

提升performace的方式 Jan.05

1. 利用page table entry內的global bit, 此需cr4的PGE被enable, 但minix 的assembler不認得cr4

2. 用memory mapping 方式更改page entry的值

3. 用 hardware-support的task switch 方式(TSS)

測試結果 Jan.05

original version(release/3.1.2a) :
real user sys
100000 31.16 0.53 26.20
10000 3.13 0.06 2.73
30000 9.33 0.18 7.90

only add a new server(release/3.1.2ar11) :
30000 1:09.33 5.63 41.86
1:09.26 6.31 41.63
1:09.30 6.08 41.10

a new server & a new pager(release/3.1.2ar12) :
30000 8:54.26 10.16 7:16.05
8:54.06 10.70 7:15.75
8:53.95 9.45 7:15.91

(改sys_abscopy -> phys_memcpy)
7:33.26 10.01 4:51.21
(改memset-> pg_memset)
5:26.25 10.06 3:02.61
5:26.31 9.96 3:03.48

日誌 Jan. 3 4 about minix 3

lib/ansi :
clock- determine the processor time used
在userspace叫times ,會先送給PM, 在送到kernel ,最後由clock task接手

posix定了一些標準 ：在 lib/posix內
getpriority ,times都是

開完機後還在跑的程式：
idle
clock
system
kernel
pm
fs
rs
mem
log
tty
ds
init
/bin/pci
/bin/floppy
/bin/at_wini
/sbin/is
/sbin/cmos
getty*4

系統時間：
主機板上有一元件存系統時間，可透過BIOS取得資訊，吃主機板上電池的電維持。
在minix 3 上，每60分之一秒一個tick，定義為HZ
每次counter數到0，即產生一個tick，好像是IRQ 0，由Interrupt handler處理，minix 3 上由
clock task處理，clock task有一個global variable --- realtime 每次tick來都加1，因此realtime實際上就是開機的時間。
當每次call time()這個system call時，實際上是去跟PM要時間，而PM內部存的時間是以boottime+uptime/HZ回傳。
Minix 3在開完機後，會up cmos driver(早期稱cmos意指bios)，cmos driver 起來之後會去要系統時間，並且去設定PM裡boottime的值。

相關command的source code在以下位置：
commands/ibm/readclock.c
commands/simple/date

日誌 Jan. 2

以前都沒有寫紀錄的習慣，但是實在是太容易忘了，所以還是記下來吧！！
目前stable的版本是 svn://server/branch/minix3v4 @ 174

1. 針對開機的問題，把/etc/rc裡的 Futrther initialization那欄都 mark 掉
越多程式 bug就越多
2.針對很多程式會在j位址 0x672fc4 page fault，解決方式為map給每個程式8M

如此一來，可順利的開完機並使用基本指令:P

接下來做分析，再者就是自動增大stack的大小
如要有malloc功能可能需要改到compiler
===分析===
1.先了解minix 3 有什麼方式可以拿出時間
2.參考rhealstone benchmark先拿出花在context switch的時間

minix 3 的 scripts

/usr/etc/rc:開啟開機的某些services,如random及 network drivers...
只要放在/usr/local/etc/rc.d/下的script開機都會執行. ex: sshd