【王壘-OS】上課筆記 - 排成演算法考試解答
上課範例：FCFS排程演算法→先到的先服務，非強奪式的排程演算法。
小考題目(1)：SJF排程演算法→Job最短者先服務，非強奪式的排程演算法。
小考題目(2)：SRTF排程演算法→與SJF相似，但是是強奪式的排程演算法。
2008-06-03
小考題目(1)：SJF排程演算法→Job最短者先服務，非強奪式的排程演算法。
2007-10-22
【X86組語】作業二-第二版
;;修正第二運算元，第二運算元如果只有一位元，可以選擇按enter鍵即進行運算。
;;前一版請參考http://new-acos.blogspot.com/2007/10/x86_21.html
GETCHAR MACRO char
push ax
mov ah,01h
int 21h
mov char,al
pop ax
ENDM
PUTCHAR MACRO char
push dx
push ax
mov dl,char
mov ah,02h
int 21h
pop ax
pop dx
ENDM
END_PROCESS MACRO
mov ah,4ch
int 21h
ENDM
.MODEL SMALL
.DATA
values db 2 dup(?)
operator db 1 dup(?)
answer db 1 dup(?)
.STACK
.CODE
main_pro proc far
mov dl,3
count_loop: mov si,0
keyin_loop: GETCHAR bl
cmp bl,'+'
je go_1
cmp bl,'-'
jne continue
go_1: cmp si,0
je invalid
mov [operator],bl
jmp keyin_loop
go_2: mov [operator],bl
jmp finish
continue: call check_num
mov cl,bl
GETCHAR bl
cmp bl,'+'
je go_2
cmp bl,'-'
je go_2
cmp bl,0dh
je finish
mov al,10
mul cl
mov cl,al
call check_num
add cl,bl
finish: mov [values+si],cl
inc si
cmp si,2
jne keyin_loop
mov al,[values]
mov bl,[values+1]
mov cl,[operator]
cmp cl,'-'
jne do_add
sub al,bl
mov [answer],al
call print_ans
jmp ok
do_add: add al,bl
mov [answer],al
call print_ans
ok: dec dl
jnz count_loop
END_PROCESS
main_pro endp
check_num proc far
cmp bl,'0'
jl invalid
cmp bl,'9'
jg invalid
sub bl,'0'
ret
check_num endp
print_ans proc far
call cr
xor ax,ax
mov al,[values]
call print_num
PUTCHAR [operator]
xor ax,ax
mov al,[values+1]
call print_num
PUTCHAR '='
xor ax,ax
mov al,[answer]
call print_num
call lf
ret
print_ans endp
print_num proc far
push cx
mov ch,1
cmp al,100
jb ignore_h
xor ch,ch
PUTCHAR '1'
sub al,100
ignore_h: mov cl,10
div cl
cmp al,0
jne go_3
cmp ch,0
jne go_4
go_3: add al,'0'
PUTCHAR al
go_4: add ah,'0'
PUTCHAR ah
pop cx
ret
print_num endp
cr proc near
push ax
push dx
mov ah,2
mov dl,0dh
int 21h
pop dx
pop ax
ret
cr endp
lf proc far
push ax
push dx
call cr
mov ah,2
mov dl,0ah
int 21h
pop dx
pop ax
ret
lf endp
invalid: PUTCHAR '!'
END_PROCESS
END
2007-10-21
【X86組語】作業二
作業二，0~99兩數字加減法
;;;; 程式說明 ;;;;
;; 使用者輸入一算數
GETCHAR MACRO char
push ax
mov ah,01h
int 21h
mov char,al
pop ax
ENDM
PUTCHAR MACRO char
push dx
push ax
mov dl,char
mov ah,02h
int 21h
pop ax
pop dx
ENDM
END_PROCESS MACRO
mov ah,4ch
int 21h
ENDM
.MODEL SMALL
.DATA
values db 2 dup(?)
operator db 1 dup(?)
.STACK
.CODE
main_pro proc far
mov dl,3
count_loop: mov si,0
keyin_loop: GETCHAR bl
cmp bl,'+'
je go_1
cmp bl,'-'
jne continue
go_1: cmp si,0
je invalid
mov [operator],bl
jmp keyin_loop
go_2: mov [operator],bl
jmp finish
continue: call check_num
mov cl,bl
GETCHAR bl
cmp bl,'+'
je go_2
cmp bl,'-'
je go_2
mov al,10
mul cl
mov cl,al
call check_num
add cl,bl
finish: mov [values+si],cl
inc si
cmp si,2
jne keyin_loop
mov al,[values]
mov bl,[values+1]
mov cl,[operator]
cmp cl,'-'
jne do_add
sub al,bl
call print_ans
jmp ok
do_add: add al,bl
call print_ans
ok: dec dl
jnz count_loop
END_PROCESS
main_pro endp
check_num proc far
cmp bl,'0'
jl invalid
cmp bl,'9'
jg invalid
sub bl,'0'
ret
check_num endp
print_ans proc far
PUTCHAR '='
cmp al,100
jb ignore_h
PUTCHAR '1'
sub al,100
ignore_h: mov cl,10
div cl
add al,'0'
add ah,'0'
PUTCHAR al
PUTCHAR ah
call cr_lf
ret
print_ans endp
cr_lf proc far
push ax
push dx
mov ah,2
mov dl,0dh
int 21h
mov dl,0ah
int 21h
pop dx
pop ax
ret
cr_lf endp
invalid: PUTCHAR '!'
END_PROCESS
END
2007-10-15
【X86組語】作業一
作業一
說明：
使用者每次輸入五個數值（五張撲克牌），若輸入錯誤牌值或是輸入'!'字元程式結束。
程式不印中獎名稱，改印中獎編號。
PS. 僅接受01~0d, 11~1d, 21~2d, 31~3d（限小寫）
GETCHAR MACRO char
mov ah,01h
int 21h
mov char,al
ENDM
PUTCHAR MACRO char
mov ah,02h
mov dl,char
int 21h
ENDM
END_PROCESS MACRO
mov ah,4ch
int 21h
ENDM
.MODEL SMALL
.DATA
abc equ 61
cde equ 55
key_temp db 2 dup(?)
card_5 db 5 dup(?)
temp_5 db 5 dup(?)
max_prize db ?
max_num db ?
ceq db ?
prize db ?
_mask db 00001000b,00000100b,00000010b,00000001b
pr_tab db 0,1,1,3,1,2,3,7,1,2,2,6,3,6,7,10
card_tab db 1,2,3,4,5, 1,2,3,4,6, 1,2,3,5,6
db 1,2,4,5,6, 1,3,4,5,6, 2,3,4,5,6
db 1,2,3,4,7, 1,2,3,5,7, 1,2,4,5,7
db 1,3,4,5,7, 2,3,4,5,7, 1,2,3,6,7
db 1,2,4,6,7, 1,3,4,6,7, 2,3,4,6,7
db 1,2,5,6,7, 1,3,5,6,7, 2,3,5,6,7
db 1,4,5,6,7, 2,4,5,6,7, 3,4,5,6,7
card_52 db 01h,02h,03h,04h,05h,06h,07h
db 08h,09h,0ah,0bh,0ch,0dh
db 11h,12h,13h,14h,15h,16h,17h
db 18h,19h,1ah,1bh,1ch,1dh
db 21h,22h,23h,24h,25h,26h,27h
db 28h,29h,2ah,2bh,2ch,2dh
db 31h,32h,33h,34h,35h,36h,37h
db 38h,39h,3ah,3bh,3ch,3dh
mess db '** sorry !! ** $'
db ' ===> 1 $'
db ' ===> 2 $'
db ' ===> 3 $'
db ' ===> 4 $'
db ' ===> 5 $'
db ' ===> 6 $'
db ' ===> 7 $'
db ' ===> 8 $'
db ' ===> 9 $'
db 07h, ' %% error %% $'
;----------------------------------------------------------
.STACK 1000h
.CODE
main proc far
;
mov ax,@data
mov ds,ax
continue: mov di,5
key_round: GETCHAR [key_temp]
cmp [key_temp], '!'
je exit
GETCHAR [key_temp+1]
cmp [key_temp+1], '!'
je exit
PUTCHAR ' '
call transform
dec di
xor di,0
jne key_round
call check_5
;
call far ptr p_result
;
jmp continue
exit: END_PROCESS
main endp
;
transform proc
mov si,2
trans_run: mov ch,[key_temp-1+si]
cmp ch,'0'
jl err
cmp ch,'9'
jle is_num
cmp ch,'a'
jl err
cmp ch,'f'
jg err
sub ch,87
jmp go_f
is_num: sub ch,'0'
go_f: mov [key_temp-1+si],ch
dec si
xor si,0
jnz trans_run
;
mov cl,[key_temp]
mov al,16
mul cl
mov cl,[key_temp+1]
add al,cl
mov [card_5+di-1],al
ret
transform endp
err: PUTCHAR 'E'
PUTCHAR 'R'
PUTCHAR 'R'
PUTCHAR 'O'
PUTCHAR 'R'
PUTCHAR '!'
PUTCHAR '!'
END_PROCESS
;-----------------------------------------------------------------
check_5 proc near
mov [prize],0
mov ah,0fh
call copypure
call sorttemp_5
call compare
cmp [ceq],0
jne setprize
call checkstr
mov ah,30h
call copypure
call compare
cmp [ceq],0fh
jne noflush
cmp1: cmp bh,0
jne cmp2
mov [prize],5
jmp checkexit
cmp2: cmp bh,1
jne cmp3
mov [prize],8
jmp checkexit
cmp3: mov [prize],9
jmp checkexit
noflush: cmp bh,0
je nostraight
mov [prize],4
jmp checkexit
nostraight: mov [ceq],0
setprize: lea bx,pr_tab
mov al,[ceq]
xlat
mov [prize],al
checkexit: ret
check_5 endp
;---------------------------------------------------------------
copypure proc
mov si,5
pureloop: dec si
mov al,[card_5 + si]
and al,ah
mov [temp_5 + si],al
cmp si,0
jne pureloop
ret
copypure endp
;--------------------------------------------------------------
sorttemp_5 proc near
mov si,4
sortloop1: mov al,[ temp_5 + si ]
mov di,0
sortloop2: cmp al,[ temp_5 + di ]
jge sortnext
xchg al,[ temp_5 +di ]
sortnext: inc di
cmp di,si
jne sortloop2
mov [ temp_5 + si ],al
dec si
jnz sortloop1
ret
sorttemp_5 endp
;--------------------------------------------------------------
compare proc
mov [ceq],0
mov si,0
cmploop: mov ah,[temp_5 + si]
xor ah,[temp_5 + si + 1]
jnz cmpnext
mov al,[_mask + si]
or [ceq],al
cmpnext: inc si
cmp si,4
jnz cmploop
ret
compare endp
;--------------------------------------------------------------
checkstr proc near
mov bh,0
mov al,[temp_5 +4]
sub al,[temp_5 +0]
cmp al,4
je addbh
cmp al,12
jne strexit
mov al,[temp_5+1]
cmp al,10
jne strexit
inc bh
addbh: inc bh
strexit: ret
checkstr endp
;----------------------------------------------------
p_result proc far
mov bl,[prize]
mov al,16
mul bl
lea dx,mess
add dx,ax
mov ah,09h
int 21h
cmp bl,0
ret
p_result endp
END main
【X86組語】上課用講義內容
徐泓洋老師上課教學用的程式碼。
功能說明：程式每次執行會自動抓取亂數設定牌值與花色，並且依照亂數產生的牌判斷得到的是one pair、two pair...等獎項或是槓龜...
.MODEL SMALL
.DATA
abc equ 61
cde equ 55
card_7 db 7 dup(?)
card_5 db 5 dup(?)
temp_5 db 5 dup(?)
max_prize db ?
max_num db ?
ceq db ?
prize db ?
_mask db 00001000b,00000100b,00000010b,00000001b
pr_tab db 0,1,1,3,1,2,3,7,1,2,2,6,3,6,7,10
card_tab db 1,2,3,4,5, 1,2,3,4,6, 1,2,3,5,6
db 1,2,4,5,6, 1,3,4,5,6, 2,3,4,5,6
db 1,2,3,4,7, 1,2,3,5,7, 1,2,4,5,7
db 1,3,4,5,7, 2,3,4,5,7, 1,2,3,6,7
db 1,2,4,6,7, 1,3,4,6,7, 2,3,4,6,7
db 1,2,5,6,7, 1,3,5,6,7, 2,3,5,6,7
db 1,4,5,6,7, 2,4,5,6,7, 3,4,5,6,7
card_52 db 01h,02h,03h,04h,05h,06h,07h
db 08h,09h,0ah,0bh,0ch,0dh
db 11h,12h,13h,14h,15h,16h,17h
db 18h,19h,1ah,1bh,1ch,1dh
db 21h,22h,23h,24h,25h,26h,27h
db 28h,29h,2ah,2bh,2ch,2dh
db 31h,32h,33h,34h,35h,36h,37h
db 38h,39h,3ah,3bh,3ch,3dh
mess db ' ** sorry !!! ** $'
db 'one pair $'
db 'two pairs $'
db 'three of a kind $'
db 'straight $'
db 'flush $'
db 'full house $'
db 'four of a kind $'
db 'flush straight $'
db 'flush royal $'
db 07h, '%% data error %% $'
;----------------------------------------------------------
.STACK 1000h
.CODE
main proc far
;
mov ax,@data
mov ds,ax
;
call far ptr cdgen
;
call far ptr check_7
;
call far ptr p_result
;
mov ah,4ch
int 21h
main endp
;
;----------------------------------------------------------
;
check_7 proc far
;
mov [max_prize],0
mov [max_num],0
;
mov cx,21
ckloop1: mov al,05h
mov dl,cl
dec dl
mul dl
mov bx,ax
mov si,5
ckloop2: dec si
mov al,[card_tab + bx + si]
mov di,ax
mov al,[card_7 - 1 + di]
mov [card_5 + si],al
xor si,0
jnz ckloop2
;
call check_5
;
mov ah,[prize]
cmp ah,[max_prize]
jbe nextturn
;
mov [max_prize],ah
mov [max_num],cl
nextturn: loop ckloop1
ret
check_7 endp
;-----------------------------------------------------------------
check_5 proc near
mov [prize],0
mov ah,0fh
call copypure
call sorttemp_5
call compare
cmp [ceq],0
jne setprize
call checkstr
mov ah,30h
call copypure
call compare
cmp [ceq],0fh
jne noflush
cmp1: cmp bh,0
jne cmp2
mov [prize],5
jmp checkexit
cmp2: cmp bh,1
jne cmp3
mov [prize],8
jmp checkexit
cmp3: mov [prize],9
jmp checkexit
noflush: cmp bh,0
je nostraight
mov [prize],4
jmp checkexit
nostraight: mov [ceq],0
setprize: lea bx,pr_tab
mov al,[ceq]
xlat
mov [prize],al
checkexit: ret
check_5 endp
;---------------------------------------------------------------
copypure proc
mov si,5
pureloop: dec si
mov al,[card_5 + si]
and al,ah
mov [temp_5 + si],al
cmp si,0
jne pureloop
ret
copypure endp
;--------------------------------------------------------------
sorttemp_5 proc near
mov si,4
sortloop1: mov al,[ temp_5 + si ]
mov di,0
sortloop2: cmp al,[ temp_5 + di ]
jge sortnext
xchg al,[ temp_5 +di ]
sortnext: inc di
cmp di,si
jne sortloop2
mov [ temp_5 + si ],al
dec si
jnz sortloop1
ret
sorttemp_5 endp
;--------------------------------------------------------------
compare proc
mov [ceq],0
mov si,0
cmploop: mov ah,[temp_5 + si]
xor ah,[temp_5 + si + 1]
jnz cmpnext
mov al,[_mask + si]
or [ceq],al
cmpnext: inc si ;74
cmp si,4
jnz cmploop
ret
compare endp
;--------------------------------------------------------------
checkstr proc near
mov bh,0
mov al,[temp_5 +4]
sub al,[temp_5 +0]
cmp al,4
je addbh
cmp al,12
jne strexit
cmp [temp_5 + si],10
jne strexit
cmp [temp_5 + si],10
jne strexit
inc bh
addbh: inc bh
strexit: ret
checkstr endp
;----------------------------------------------------
p_result proc far
mov bl,[max_prize]
mov al,20
mul bl
lea dx,mess
add dx,ax
mov ah,09h
int 21h
cmp bl,0
je pr_exit
mov bl,[max_num]
dec bl
mov al,05h
mul bl
mov bx,ax
mov ah,02h
mov dl,[card_tab + bx + 0]
or dl,30h
int 21h
mov si,1
prloop: mov dl,","
int 21h
mov dl,[card_tab + bx + si]
or dl,30h
inc si
cmp si,5
jne prloop
pr_exit: ret
p_result endp
;----------------------------------------------------
cdgen proc far
call randomize
mov cx,7
mov dh,52
rndloop: call random
lea bx,card_52
xor ah,ah
add bx,ax
mov ah,[bx]
mov si,cx
mov [card_7 - 1 + si],ah
xchg ah,[card_52 + 44 + si]
mov [bx],ah
dec dh
loop rndloop
ret
cdgen endp
;----------------------------------------------------
randomize proc near
mov ah,2ch
int 21h
shl dh,1
add dl,dh
ret
randomize endp
;----------------------------------------------------
random proc near
mov al,abc
mul dl
add ax,cde
mov dl,al
mul dh
mov al,ah
ret
random endp
END main
2007-09-18
MASM操作說明
- 版本說明：提供下載版本是6.11。目前最新版本有8.0，不過必須搭配Visual C++ 2005 Express Edition，避免麻煩用跟課本一樣的版本就好。
- IBM80X86組合語言實務 施威銘著
- 環境設定說明：
step1) 下載檔案：http://www.box.net/shared/8dnahg31c5
step2) 解壓縮後會產生『MASM611』資料夾
step3) 把資料夾移到C槽下（或移到你想放的路徑，在此以C:\MASM611路徑為示範）
step4) 點選『我的電腦』右鍵→『內容』，選擇『進階』頁面。
step5) 開啟『環境變數』。在下面『系統變數』裡找到『Path』並點選編輯，在跳出的視窗中，於『變數值』欄位新增『;C:\MASM611』
step6) 完成以上設定就可以使用MASM了。 - 操作說明：
step1) 參考課本2-3節的『啟動MASM』，用文字編輯器把程式2-1輸入好並存檔（存檔路徑建議選擇較簡單的路徑：在C槽底下建立新資料夾『ASM』，把檔案存在該路徑底下）。
step2) 點選『開始』→『執行』，輸入『cmd』後按Enter鍵會開啟『命令提示字元』視窗
step3) 輸入指令cd c:\ASM以切換到ASM資料夾（如果你檔案存在其他地方請輸入對應的路徑），此時你可以下指令dir查看目錄內的檔案。
step4) 組譯程式，下指令ml prog2_1.asm，程式就會自動完成編譯動作，詳細的關係可以參考課本2-3節的解說。
step5) 組譯完後會自動產生PROG2_1.EXE與PROG2_1.obj兩個檔案（你可以下dir查看目前資料夾的檔案內容），接著測試程式直接輸入PROG2_1.EXE即可（此時應該會在螢幕上印出字元A）。
2007-06-12
Unix期末作業總整理
作業一：試找knight主機上非使用csh之帳號數
提示：使用grep 指令
輸出：僅有一個數字
限制：
1. 請以一行指令完成
2. 須排除錯誤訊息
> more /etc/passwd | grep -vc /csh
==================================================================================
作業二：試將資工94級學生帳號，複製到新主機。
使用vi編輯器
1. 將帳號前字元 d 改為 cs
2. 將HOME Directory由 /student/stu3/94/cs/dxxxxxx 路徑改為/student/94/csxxxxxx
3. 並將default shell： /bin/csh 改為 /bin/bash
> grep /stu3/94/cs/ /etc/passwd > homework.txt
:1,$ s/d/cs/g
:1,$ s/stu3\/
:1,$ s/csh/bash
==================================================================================
作業一：試找knight主機上學生目錄下core dump檔案數。
提示：使用find 指令
假設與限制：
1. 目標為 /student/stu3/94。
2. 判定方式以 “core”檔名為準。
3. 輸出僅有一個數字。
4. 請以一行指令完成並須排除錯誤訊息。
# find /student/stu3/94 -name core 2>/dev/null | wc -l
==================================================================================
作業二：試寫一shell script，能搜尋並取代所指定檔案中特定字串。
範例：./myreplace d cs file1 file2
假設與要求：共四個參數
1. d, cs 為所欲置換字串。
2. file1 為輸入檔名，以knight主機中密碼檔 (/etc/passwd) 部份內容。
3. file2 為輸出檔名。
#!/bin/bash
`sed -n 's/'$1'/'$2'/gp' $3> $4`
==================================================================================
作業：試寫一具功能選單之shell script。
Design a menu like as:
Current directory is "/student/stu4/93/cs"
1. Sum of online Users
2. List our Classmates
3. Broadcast a message to the idle Users
0. Quit
Enter choice [1]:
說明：
1. 列出目前線上使用者數目
2. 列出本班同學清單與總數
3. 廣播一警訊給idle 時間超過5 minutes的使用者
0. 離開
echo "Current directory is"$PWD
n=1
while [ "$n" -lt 10 ]
do
echo "1. Sum of online Users"
echo "2. List our Classmates"
echo "3. Broadcast a message to the idle Users"
echo "0. Quit"
echo "choice [0]:"
read choice
clear
case $choice in
0) break ;;
1)
echo "Total online number: " `who | wc -l`
;;
2)
echo "Show the online user of our classmates."
echo `who | grep pcroom`
echo "Number:"`who | grep pcroom | wc -l`;;
3) `uname > oo`
who -u | awk '{print $1, $6}' | grep -v [.] | grep -v '[0-4]:[0-9][0-9]' | awk '{print $1}' | awk '{print "`write",$1,"<> tt
`chmod 777 tt`
`./tt`
`rm tt oo`
;;
*) break ;;
esac
echo "========================================"
echo "++++++++++++++++++++++++++++++++++++++++"
echo "========================================"
echo
done
【關鍵字：Unix實務應用、劉嘉政、95-上、期末作業】
2007-06-04
Advanced Linux Programming
上Unix時劉老介紹的網站，正確說法是強迫接受...很讚的東西。「Advanced Linux Programming」是一本書名，其內容名符其實就是介紹Linux上的程式（C/C++）寫作，這本書是一群作者合力完成的，這些作者也很讚...把這本書的所有內容都放上網路了，網頁上註明書本版權是Open Publication License，也就是可以隨意拿去書局「拷貝」！
Link：http://www.advancedlinuxprogramming.com/
2007-03-08
【0309】徐弘洋：計算機結構學
加速比（Speedup）
Amdahl' Law：
the performance improvement to be gained from using some faster mode of execution is limited by the fraction of the time the faster mode can be used.整體Speedup公式：
千萬不要死背，請看懂以下推倒過程：
2007-03-02
【0302】林秀峰：密碼學
Cryptology（密碼技術）
Cryptography（密碼學）：
如何使信息能夠達到秘密性，可鑑定的科學（或藝術）。
Cryptanalysis（破密學）：
破解秘密系統或偽造信息使密碼系統認為其真。
Cryptosystem（秘密通訊系統）：
Plaintext（明文），M
Ciphertext（密文），C
Cryptosystem的要件：
① 秘密性（Secrecy or Privacy）
② 鑑定性（Authenticity）
確定訊息來源的合法性，亦即接收此信息確實發方所傳送而非別人偽造或利用以前信息重送。
③ 完整性（Integrity）
確定信息沒有被惡意或無意中遭到修改、取代、加入或刪除…等。
④ 不可否認性（Nonrepudiation）
發方在事後，不可否認傳送過此信息。
Kerckhoff（1835～1903）提出系統安全的觀點：
密碼系統安全必須僅賴其解密金匙，亦即在密碼系統中，除了解密金匙外，其餘加／解密器等方法，均假設破密者完全知道，在此情況下，破密者無法解此密碼系統，此系統方可稱為安全。
通常破密方式
（1）密文攻擊法（Cyphertext-only attack）
（2）已知明文攻擊法（know plaintext attack）
（3）選擇性攻擊（Chosen-text attack）
A. 選擇密文攻擊（chosen-ciphertext attack）
B. 選擇明文攻擊（chosen-plaintext attack）
訂閱：
文章 (Atom)
