Japan Advanced Institute of Science and Technology
JAIST Repository
https://dspace.jaist.ac.jp/
Title Robust and Cryptographically Secure Pseudo‑Random Bit Generation
Author(s) Mpho, Tjabane Citation
Issue Date 2003‑03
Type Thesis or Dissertation Text version author
URL http://hdl.handle.net/10119/1703 Rights
Description Supervisor:Hong Shen, 情報科学研究科, 修士
!
"
!# $
%&&'
())&&*&+
!
"
!# $
!# $
!# $
!# , - .
/ %&&' (+
!
" #
!" ! #
!$
% & & !
! $ # & !
'
'((
( )!
*
*
*(
& $
! & !
$ & &
! !
Æ
!! !
+ , ! * -.
!
!
/0,1 ! 2 ! % 3! !
! /0,1 ! !
45,1 !!$,$0# #
!&! ! %
% !6 3 2
!6 3 % !6 !2
! /0,1 /, ! 6
3#! !
/0,1 /, !
(
%
(
Æ ! 7! 6 6
!!!
(( ! 8 (
((( 7 ! 8 (
(( /!! ! 8
( $6 9
( 7$ 8
(. 8
(.( :
(. ; %
(. 6 .
( $8 <
(( / &/!! <
( 9 -
8 ,! =
( , > ?
8 (
. ! ! ((
.( ,!"/ ((
. 9 (
. 8 (
< 7 / (
( 0 9 (<
(( $ 3 (=
( ! (=
( /6 (=
(. 9 (?
(< ! (?
9 ! (?
) ! (@
.( 8 $ (
.(( 9 8 $
.( A% Æ
. %0 .
. 0 / & ! <
.. ,!" -
.< 8 =
!"#$ #$ %
<( 4 , @
<(( / ) @
< ,!
< $9 =
<. 8 ?
& '$ (
-( .
- / / ! .(
-( / .
- B 9 $,$0 .<
-. " .?
-.( / .?
-. .?
-< 4 !& / ! .@
) '# !"#
=( C <(
= 0 <
= ! <
*
#$"
<( / % 3
<
-( .(
- / ! .
- !&% .@
=( ; <
( / ((
(
/ $ (
. / (.
< % (.
( $ ! (-
! (-
9 ! (@
. / !Æ
$ %&'
$ (
) *
)
+ ,
,
-
% .
/ (
. 0
% 1
*1, ' 2
34
3 !D E 958!6%
F F ! F F !! GHI !
! !!
! ! 6
6 ! 6 !
/F 6 ! , !
3 ! !
! !
5 3 ! 958F
&! 3
# 3
3 ! %!
&! 3 ! !
B!!# % 3
! ! C&
! 9 !
3 % ! !
# % Æ!
3 & &! &
& ! !!
&!
! >C 7 (@.@H(=I
*
'
!! ! ! !
&! !! %!
6
J ; H<I !
7 ! & !" 3
*
'
'
*
'
'
'
C K "6H(?I H(I & % ; F 6 6 !!
! & ! !
!
6 D 6
3 A !!
!
,
! & &
% !
(
6 ! ! B!
! 109 ! !!
$ ! 6 3! ! !!
3! 3 ! ! ; ; !6
! H(I 6 6
! 5! 6
6 !!! !6 6 !! Æ
66 6
" #
$ # !
* '
$ !"
*
! !
&! !! ! !$ !
D
! 6
!!
( Æ !!
'
''
((
& !!
$
! & !
!
8& 3 *
*
L
" #!! 3 3
L , % HI ! HI
% 1 3 , :
C& KH(=I : &
!
!&
C ! 3 !!
, & 3 *
*
!
!3
*
! A !
! &
'-
$ 9
HI , & !
*
'
½
*
'
*
'
6 & , !!
!! !! ( !! !6 , !
!6 & % #!
109
B 3 E 6G 3 8&
3
* (
*
3
# 3
¼
½
, 3
E G E +G ! 3
6! 3 ! !
!!
! 6 &
*
'
*
'
, # !6 ,
# !6 #!
109 F 6! !
/6& 6
! !
! F !
&! !
! !!!!
!/4 $
6 ! ! !
! @- ! !
, " !! !
! (
! 6 & 6 !!
! ! % ! !
$ ! &! !
! ! !
!! # ! 6 !
& ! $ !
!!! & !
!! %
!! ! 0 !!
!!
*.+ !! ( !
*(
(
& ! & ##!8$
& ! ! & !
'
'( $
'
'(
'
'(
'
'(
! !! & "
(
! %
& !
!&!
L
F 6! & ! 6
'
'(
& ; H?I
0 !! $ &
! #
* '
(
!! !"
* '
!"
!
*
'
, !" !!
!
! ! ! ,7/
! !! 6#(- -. BF
, !! 3 ( !!
&!
½
%
!
& & &!
& L !
! B 3 & )!&
! & !
.= & !!
*
.
*D.-
! ; &
! !D
*
<
! &!
!!! &!
! ! .='< *
!
*
-
C !
! & !!
$ F !
*
( =
C &! ( !
! .('*( F !
.(!!
*
?
!
! & !
B ! D
*
< @
& &! < !<' !
3 !
!&
*
(
! "# $
B !! 6 !" ! & !
&! % !!
! = ,,
? (-
D =!=--.--<<"
$ ! &! & .= * (<.
(?? ? &
!! ! &
!
!
(@ !&
. ! # & &
* =!=--.--<<"=!=--.--<<"
=!=--.--<<"=!=--.--<<"
=!=--.--<<"=!=--.--<<"
=!=--.--<<"=!=--.--<<"
=!=--.--<<"=!=--.--<<"
=!=--.--<<"=!=--.--<<
=!=--.--<<"=!=--.--<<"
=!=--.--<<"=!=--.--<<"
=!=--.--<<"=!=--.--<<"
=!=--.--<<"=!=--.--<<"
=!=--.--<<"=!=--.--<<"
=!=--.--<<"=!=--.
) ! ! ! %!
?
/ 3 < &
* -.--<<"=!=--.--<<"=!=-
-.--<<"=!=--.--<<"=!=-
-.--<<"=!=--.--<<"=!=-
-.--<<"=!=--.--<<"=!=-
-.--<<"=!=--.--<<"=!=-
-.--<-.--<<"=!=--.--<
-.--<<"=!=--.--<<"=!=-
-.--<<"=!=--.--<<"=!=-
-.--<<"=!=--.--<<"=!=-
-.--<<"=!=--.--<<"=!=-
-.--<<"=!=--.--<<"=!=-
-.--<<"=!=--.--<
; 3- # !
* <-<!<"<"-(.(.(.
@-=-=((!(!(!.=(".=(???
="!==?<!??<
<??".-.-.-@@@@"<?.?
"=?@"(<(<=-.(@!!!<
=<<("<."@-@@-<(-?.-
.=(!=-"?@=<-"??@?(=!
!!=""(<--<?=@?"(!.@
?(!"!@@"..@<!!(.-
-=@<(-@(?<.!<"".
?..=.!=="..?(-@=-
-!"-(@?-?"=(
; 3= ? # !
* --<((.!<!=@<?--<@<
?!!@="..(<((@.?!""!
""<<@=<..?(@(.?!(-
<-.=@(.!(?.@-<""@@
!@?=@-."?@@-.=(?<@@
?=?"="-<[email protected]"!@.=
?.!(@.-<=-!-!(=.
@<.<<."(?"!!(!-
<.@.""(".?(=-@."=
(@".("(!!"==!<<@?<-
@.-""
! 3 @ ( &
* --?@<!@<("----.?=
@.<@!<<=?<?!(!.".?=<
!<<-!@-?@(-="=
=@.<((.=!@.<"!".!<@""
=?@<-@(@<=<(<""--(.
"@<<.(@@-=?@-=<.(=
@(==!!@"<-=(((!".
"!?.=--?<=??@"?@?<<
..=@-<.@@("@"=
"
9 !
# & $
$ $
!
3 .-2
3
# .2
3
. $
$
$
3
$
*
((
$ * (
$
*
(
! !!
!
&! !"
3 (( ( &
&!! ! !
!!
! (D /
; !! < $ & ! !
6 ! & ! !
3 ! < E, !
! G
$
3&& ! M
B 3 &
! ! 6
B!! ! &
! 3 B6
! !! %
0 ! ! D ,!" 9
B !!!"
"%
! ! & &
!
2
* !
&
%?'( ! B
! & & & ! !
&! !
'
&
&
&
*'&
&
&
&
!%
! !
! 3- ?
( B !
3
! ! ! 6
(
( ('
HI
'(
(
!
HI(
! D
, 3 &
%& ! , ! &&
& &# , # 6' # 3
0 # 3 " !!
) !
!
)*
'
'(' '' #
!#
) *
'
'(
' '' #
; % !
) *'
#
C " 6 !
$ ! ! ! 3
! '( 7 ! & #
) &
) * '' #' #
¾
3(( ( ! ! !
! 109 $ ! !
6 ! !!& !%
'
#
! ! & ! #
6 ! !! 3
'' #' #
109 !!6 '
& #
, !! 6 7 $ & !
'
'( & %!
( !
B ! *
*
( *
&! )! ! !
! *
$ /
* '
(
* '
.=(
*
'
==@(
! D / $
$ &!
*.=.(< !
*
! !&! 4
!
*#
3 (( ( &
! !
&! *
% ! &!!!
! !
$ ( *
* (
(
(
#% !
* * (
(
( $
/
*
*
*
*
*
*
*
*
*
! .D /
%
(<(
(
( <(
=( =?(
! <D %
% &! !
!!!
&!! < # &
!$ $
! ! !
Æ
" '
$ %
Æ #
D
!!!
&
! 3
& 6 6 !!!! %
&
, !!+ ! !
3 ! 3!
% $ ! & !!! & !
3 $
B &! ! ( 3 (( ( (
#! !! + #&
D
$ 3
!
/6
9
!
& ! #
& !& # 3
& 3 !! ! /
& Æ 3
!! !
;
;?AA- >?=A=?> --$@>>
?-;?;>$ @A$;;> ;=?$
=.<?.=< @><$= AA$$@
;A$<<A( =@>$ =AA;<@
;?(?= @;;@>@ =A<$(
?$-$=A ---A? ;.;=>=(
>(<> ??;;= >->(=(<
A;A;@@ >@@?= ??<.>
<;.A<? .?>$$>>( ;@--$A
;..;@(;. >>.<> $.(>$
(.(@$A $?>-;; -@>@@A
=$.= >-$$. <$;@=A@
?;>- >=@$. >;=@$A;
! (D $ !
!
$
$
$
>>-.( =.<<-. =@A@;?-
;A<==; .;=;--< @A<A>.
?-.>>; (<$-@A @<(=A=
<.= (A<<-;( A;=;=$
;?A.A$ AA.?; (?<.-<
>?@=; @(>$A$; ;?>(@
AA;>( .-.>$( A@<;
<=-$( ;>A-?= -$<?$-
@?<<>= =?(;=(? (=.<>>@
;.@A= .;=- =@;$$$A
! D !
0 ! !
!6 A ! @-
@- !6
((((((((((((((((((((((((((((((((((((((
! ! #
&' !
F (F 3 %!
! 3
*
F(F &!*
'
&
%!!! +
( ( $
3 !
*.=.
*.?@ # !&! ,*<
!
*<@
*(<
!
( ( ((
3 ! 3 %! !
3 3
F
(F 3 &! $ !
( ( (( 3 3 !!
& !
'
'
'
*(
* .
(
'
'
'
'
'(
%!!!+
(
$ !
* =
* =
* (
* =.2
* .=.
* .?- # !&! , *< ! &!
*===?
*-.
!
&
<
2! *
3 ! %!
3 ! % 3
*
!! +
( $
! * < *(@
* ((= # !&! , * <
! &!
*.?(@
*=<
½
!
& !
3 % 3 %
F (F 3 ! -
*('%
,
# ! ! -
< ! !
!6 &!! 3
(
*
-
-
'
-
-
!! +
$ !
3 # !&! , * < ! &!
* (=<.<
*((?=
( ) !
! 6 ! 3 !
& 7 #% ( %
!3 3! *
109 $
*
%
!! ! ( $ !
3 # !&! , * < !
* @<
*=.
"
A%
! !!
& +
& >0$
% ! ! " !! ! &
$ !! # !&! ,*< $
! &! ! &!
&!
* ,
&! ! ! ! $ !
3
! !
¾
% & '& &'& & () *)+
)! ! >0$ 0
. <@ ( /
-. ===? /
=< .? ( /
((?= (=<< ? /
=. @< /
! D 9 !
$ !! ! 3#
# ! ! !!
3
& # 3
"" (
, & &
! & #! & 3
# Æ B &!
&!
! &! ! B
& ! &! ! , 3 ! !
! !! !2 !! ! 8&
*
*
!Æ
& 3
*
* (
* (
& &! !
! Æ D
, ! *
!! (
5 !& ! "
& !
& !!& ! L
!" B & !
#! ! !
&
! Æ
-- -. .# ..-
.# ..- .# ..-
.# ..- .# ..-
! .D / ! Æ
Æ &! ! !
! & 3 !
! !" L&
& & $
! ! ! !
#! &
"#$
$
, $
* '
* '
*
'
&! , !
6! !
8& 3
*
3 #
*
*
'
'
'
!! ! 3 !&
! !
!"#$ %"#$
34 & , &' , !"#$ ( &%"#$
'
*,
'&
2
34 #"# !"#$%"#$
'
*
'
'
''
'
2
34 $
!"#$' '
'
*
/(
/2
('
*(''
'*
! !! ;!
* &
#
* '
& & %
*
; ( 3
*
'
'
''
'
3
*
$ 3
*
; 6 &
(
*
'
'
'
'
'
'
$ !!.=
* !
(
*
'
'
'
'
'
! & !
*
(
.(
&!
! !
(
3
!
!! !!
0 0
0
0
'
'
''
*
*
0
'
0
''
0
)
*
1*
(
.
F ! ! !
&
2*
(
.
! ! !!
3
&! !!
+ Æ
; !( ! ! 3
*
0
'
0
'' 0 ..
0
F 3 (
* ,
5 !! 3
0
F
! & ! !% & ! !!
F ! Æ
% Æ % !
* (
3
*( .<
8" & *
.( .< !
* (
3
(
.-
8" & *
8"
! & !! (
,
3 .. .- !&!
3
; ! !!
3
* (
3
(
.=
* (
3
(
.?
&! $ ! 3 !!! 3
3 ; !! .- .?
& 2 !% & &! #
%
% ! 3 ..
.-2 %& 3
6 !!
.=
*
N
.=N.=N (
! ! &! & ,
6 !! !&! &
(
! ! , * .= *
! !!
((
, 6 & <O !! !
& 6 /4 (
(4( /4!!#6( N
%& ! !!!
$ )* '
, %& $
! ! !
! !
4 ! ! #
& D
+ , !" !
&
! &
* + ; ! ! ! ! !
! & ! !
&! & L &!
76 &!
L &! &
+ ; $
6 ! #!
& !% !
0 ! !
* & !
*
*
*
* & !
*
*
*
4 & & & !%
! 6
! !
$" ' + ,
0 + '
(%
; !! & ! &
' '( '
'(
'
'( ! & !!
,6 ! # &
!! ! !" !
& % &! !
! ! !
! !" ! !
& & & ! % ! !
; &!!
! !
' '(
!
'
'(
&! !! 6 36 !! &!
# !!& ( N
! ! !! !!"!
% !! ! ,
! !&! 3 6%
!!&! & L &!
!! &! ; L !"
!! & $ ! ! !" Æ
$$ ,)" %-
! !" %
L 6!
B
! , ! $ ! ><
6 ! (? C(!
6 (- 9,/A>(- !
6 ! (- !
!
!"! !
& !# ! ,
!"! D
188 & #% !
& & ! !
$ !! !F # !" !
)5 .6*/
6
/
6
/
6
/
6
.@
/
#
&
!!
'
'( & 6
& 6
3
6
*/
/
6
/ * . .(
*/
! 6
& & !
#
'
'( .7 *(.
& !
*
**
*..
!
*
**
*(
&!
!! ! ! !&!
%
18
! !
6
*/
/
/
/
6
.((
B !
% & 3 .(( !"
.( ! 6 ! 6
#!
! & 6
! !6! !
!! ! 6 6 &
$&
! ! &
3 , !
! .( B
3
& $ .
!
& & ! ! !
&
!
! !
! !! !
6 $ 3 ((
# &
$
*
!
& !
! ! !&
$ * ' ' ' ' ' .(
.( - 6!
Æ! 7 K" 3 # 3 .(
8*
$
.(
3.( .(&
8*
'
'
'
'
'
.(.
, ! ! 3 & !
Æ! !& !!
&! $
!
$
* (
3
8
*( .(<
!! ! ! 6 6
!"! $ ,!"
5" $
$
3 !!%
5*
'
'
'
'
'
.(-
9*
'
'
'
'
'
.(=
$ ! 3 ! ! $ 3
%
! &!!
6 .(< !
, !! !
!! L %& ! +
& E6 G &
Æ !6
&
! &
! $ .( M ! 3 %
& ! ! ! !
! !
0 <= ,; ,1 &
45,1 M& !! 6 45,1 & !
! #!
C& 2
L ! >Æ!
! ! !!
! ! ! # !
!" $ !
$ !& !
& . %!
( ,* * -
3
& 6 ! !
, &
A& 6 ,, ! %
! A
&
B 3 .&
!! $ .= 0 !
& .=*(<.
(?? ! # ?
seed vector
init state A
init state B
init state C
recurrence A recurrence B recurrence C
rec A output rec B output rec C output
1st_generator 2nd_generator 3rd_generator
Serial Component
Parallel Component
Password
User Interface
$ <(D / % 3
!
* . ! ! (@ >!
!66 !! ! !!!
&! 0! ! !&!
!
! "
# $
% & ' ((
)
* + ##
,
B 3 ?
9:5 $
,, %! & &
# !"! 9:5.
B .? .
!
& &
-./ 0
1.(
)2-./321.(3
4
&
* + -./ ##
* + 1.( ##
% 4 + &
)2323 24##3
,5 666 5
,
A ) A F ,, !
& = !
# .( !! &
77
203
* + 0 ##
9
8 5
# :
8
,
#
,
, 5 666 5
,
A # ! !
& %!
? %! !
; !! 6 !& !
0 ? ? ? ? ? ? ? 0 ? ? ? ? ? ? ? 0 ? ? ? ? ? ? ? 0 ? ? ? ? ? ? ?
32 bits
$ <D
*
'
'
''
! !
77
*
! 0
& & 2 !3
)2;3 6666, 5 & !5
* + ; ##
#
66666666
* + ! ##
23
,
,5 6665
,
!" &
; ? !&
& !! !
! & (@ ,,
$ &
66 6!6 ,, !<-
! ! , ? (? !
6 %& !!& 6
(?
?
*
(?N
(??N?N
(.(
, <-,, ! %&
6
<-
?
*
<-N
<-?N?N
.((
, !! (@ .? 6
%& !
<-
(@
*
<-N
<-(@N(@N
(@(
! 6 ! !
& F &
& %
& !
$ &
!&!
! D ! !" !
3 ! &
&& , 3
& H I
! D
& L # &!
L ! # &
! ! !
! 0 !
L #
; !
7 & !
! 9 *
* 9 ##
* + !5" ##
&7<23 *
*
,
7<2=$3 0
23 23 ++ $
,
7 !=$
,
,
,
! !
!
!! !
7 &
& 4
4 *>"*
* + : " ##
4 4 99 $
2 5"3 2 5"3 ? 4
,
#
6 ! L !! (
8 !
&7 &
& 4
4 *>"*
* + : " ##
4 4 99 $
4 < 2 5"3 4 A $ B *
,
&
6 #
( 4 !! !
%
! 6 , !! !! .C #
&% ; #!
! ! # $
DEFG7$ 0
& & 7 77$ & &
& & *
& & 7$2DEFG7$3
7$
+ DEFG7$ ?? 9 DEFG7$
>$
,
7 DEFG7$ ; *
* + DEFG7$ ##
: .C # 7$23 : .C : .C
7$23
,
7$
,
! 3 - 6 &
! ! ,
& 6 ;
.='< * 6 !
!
' * '
>! !!!
2! !
. & , ! ! $
DEFG7 $
& & 7 77 & & 7$
& & *
& & 72DEFG73
7 7$
+ DEFG7 ?? 9 DEFG7
>$
,
7 DEFG7 ; $
* + DEFG7 ##
: .C # 723 : .C : .C
723
,
,
7
,
6 ! #
.(' & !.(.- &
! ! .( & !
6 $ !
!7; ;H
& & 7 77; & & 7
& & *
& & 7;2DEFG7;3
7; 7
+ DEFG7; ?? 9 DEFG7;
>$
,
7 DEFG7; ; H
* + DEFG7$ ##
: .C # 7;23 : .C : .C
7;23
,
,
7;
,
! !3(
& < . <'
%
&"
3 ( ! ! ! $
! ! !
+ ! 1H(I 1HI 1H I !! &!
&! * * ! 3
* '
(.(.
* (2 / *.7- *
* (2 / * .7- *
& !!$
!
(EDIDEFG
JK(JL
E(JL
&7$ & &
& & 2(EDIDEFG3
* (EDIDEFG + (EDIDEFG ## ==
23 #
,
JK(JL E(JL
%$
# # : .C # # : .C: .C
#
= $
* JK(JL,
= $
* JK(JL,
,
,
A%! ! ! ( 3 !(??
(-. (. &!
&$
3(((!& 6
$ #
6 !
! # #
!
& %$7& & & $ & &
& & ;
& & %$ J7* J7$ M 1
J7* $ : .C
J7$ # $ : .C
M : .C
1 ; : .C
%$ J7* M # J7$ N 1
%$
&! $
&! $ @-
!
!! + % D
( ##$
&!6 !% , !
!! ! !% ,
!!& ! !
! / !!
# &! & !
+
M& D 3! !!! ,
% 3 ! % !
! 3! & ! !!
!!! &
! 0 !!! !
675 !!!
!! %! 6
/ !!! !!
L /4 / !!! 0 6
!!! 3
!! ! ! !!
! & ! $
!
!% !!
% ! %
$ ! !
/
! < #
3 A 6&!
$ ! # &!
! ! !!# 3 &!
, !! #!
! - !
#! &! ! , ! & &
!! 6 !
# -( &!
, !! &
WORD1 WORD2 WORD3
A[k] A[k+1] B[l] B[l+1] C[m] C[m+1]
$ -(D
! $( $ $ # &
3! ! &6
! !!
&! &!
!! ! $
! $ !!
6 !
/
! # -( " !D !
L $ - # & -( !
- ! ,
$ !
!!
,/
$ ! # - ,/ $,$0 #
# ! 45,1
½
./01* 2 3% 4+ + 5
+ 0$ & $ (&$ 6 78(&$
'& "& & 4+ % + " "
,/ ! $,$0 ! !%
& M ! $,$0 ,/
Fibonacci recurrence Thread 1
Fibonacci recurrence Thread 2
Fibonacci recurrence Thread 3
FIFO 1
FIFO 2
FIFO 3
Combination generator Thread 1
Combination generator Thread 2
Combination generator Thread 3
write() read()
write()
write() read()
$ -D / !
4
!4% $,$0
$,$0 ! ! #
$,$0
OEO.$ PP556$QQ
OEO.$ O7.R =$
4OEO.$ OE(G7 .CG
' *
PP : SQQ OEO.$
>GKEI7OJE(-G
,
,
4OEO.$
,
$ 0K # " %
#!!!$,$0( $,7A 0>A # !!#
#! 6 4 !! & $,$0
0 $,$0 % #!
"34#
#! !! $,$0 556$ M
0 ! $,$0 !
# $ &!$,$0
! !% . /-.(T &
6
. * * !*
!!45,1 & ! !
! ,
! 3! 6
# ! 3 6 !
& ! ! ! , ! ! !!
! ! !
#!
/0,1
/
# ! !
!6 " !!
A $ &
%
/0,1 ! !
5 5
+69
$ ;
7 $ ;
5 & 5
$ 7<$ (( 77$ $
¾
$ ' *
PPU $ QQ
>GKEI7OJE(-G
,
7< (( 77 $
$ ' *
PPU QQ
>GKEI7OJE(-G
,
; 7<; (( 77; $
$ ' *
PPU ; QQ
>GKEI7OJE(-G
,
> *
# & !
# # ! !
! % 5477
#! ! % !!
B &
!! $,$0$,$0
, $,$0 !!
! $
B !
!!
A 6
#
# #!
& & $
& &
& & ;
,
%$ % %;
7 $ ;
7&
%$ 7< $ (( %7$7&
%$ ' *
PP1 $ QQ
>GKEI7OJE(-G
,
% 7< (( %77&
% ' *
PP1 QQ
>GKEI7OJE(-G
%; 7< ; (( %7;7&
%; ' *
PP1 ; QQ
>GKEI7OJE(-G
,
!! !
5477
" &
! ! %
/" 0 % '
% & L
$,$0
!! * -C.(T . /-.(T 0 505;70K M , $,$0
D
. -C.(T !! !
$,$0
. -C.(T ? . .M(.1R !!
! & $,$0
. /-.(T !! !
$,$0
. /-.(T ? . .M(.1R
! $,$0 ( !!
$ ! ! $,$0
!! ! !&! " !! 3 B
$,$0 . /-.(T !
!!% !!! 3
( # $,$0&
$,$0 & !!
$,$0
$,$0 !
OEO.
MOOG-7DEFG
GLJ
& & 7
7
)7 *
& & 2MOOG-7DEFG3
7 OEO. .7/-.(T
7 ' $
% ) 7 + GLJ
%7 MOOG-7DEFG
=$
PP/ QQ
>GKEI7OJE(-G
,
) 7 #
,
7
,
>GKEI7OJE(-G
,
* .M(.1R M !! !!
6 " / !!
&! L % ! "
3 ;
" !6 L
A $,$0 . -C.(T
. .M(.1R !! ! L
! !
OEO.$
OEO.
CGOEG OEO.;
& & $2MOOG-7DEFG3
& & 2MOOG-7DEFG3
& & ;2MOOG-7DEFG3
7
7$ 7 7;
$ ;
) 7 *
$ * !$
* !
; * !;
7$ OEO.$ .7-C.(T
7 OEO. .7-C.(T
7; OEO.; .7-C.(T
7$ ' =$ << 7 ' =$ << 7; ' $
$ 7$ MOOG-7DEFG
) 7 #
7 MOOG-7DEFG
) 7 #
$ 7; ; MOOG-7DEFG
) 7; # ;
, % $ 9 * << 9 * << ; 9 *
7$
7
7;
,
>GKEI7OJE(-G
,
666
& !! $,$0
9 5> # !! !!
! !!& L % !6
!6 & !
% !! % & %!&
A %!& $,$0 ,
!! !6 % & !
L !! L !!
& ! !
/$ -
. *
% & ! ;
3 " $
& ! /0,1 ! !!/,D
% >
&
L !
$ L
; & !
!! % # % L
F % F
% $ % ! !!D
( /
76 %
6 L !
! L , ! & !
!! 6 B
.> & ! % !6
. / L F % L
L
< , 3!
! & & ! , ! !6
! !6
- 4!6 %
$ %! !!D
( 76 %
6 "
, &! " % !! !
. % !6 ! ! !!
& & !
< ; % !6 %
- B %
.
A 3 $,$0 !
!!!6 ! !
Thread 1
Thread 2
Thread 3
time
Blocked Active
time slice
expires thread 1 resumes
$ -D !& %
/ !6 3
!!D
( 76 %
C! L
/ !
. 9! % !6
!! !
! & !& #! %
% ! %
/& .+
!
! #
D ( !
% !6 3 0
! # 3
6 !
% ! (
! % !6 !! 3
! ! !6 3
3 !6 !6 !
!6 ! !6 ! 3
!6 , /0,1 /,
& !6 !
8& 3 % !6 !
/0,1F ! ! !& !
/0,1 ! & ! !
! # ! & /4
!6 #!
!
!! ! !! !& !
6 !! !6 !!
! ! ! ! ! "
($ &
F &
! ! L
! ! F ! 6 !
!& D
C !
0 !
! !
$ !! !! !
! 3 # ! / 45,1 6
; !!45,1
-. ! ! ! !
1 2
&! 6 &
4! /9,, ! &/0BA9,,
,1 ! !
! .
! & $ =(
! L $
!! ! #7; & ! !
$ # ; & !
! 0 - #
$
& L !L !
#
! 6
! ! , %
#
$
address A address A+1 address A+1 address A
MSB LSB
high-order byte low-order byte
high-order byte low-order byte
increasing memory address increasing memory address
little-endian byte order
big-endian byte order 32-bit value
$ =(D ;
%7$7& & & $ & &
& & ;
77 ((
7 &
% ! - ! !% $ &
7&
& & $
& &
& & ;
,
0 /9,,-< C" /0BA,, .<C" -. C&
& " &
! !
! !
! !
1 '
0 /9 ,, ! )9 . / /
& & 4
9 % ! D /0,1 ! 0P B
5 )9 . ! /0,1 !
! ! ,1 /0,1 ! !
/, ! /0,1 & L
!& ! !
/0,1 $ ! !
! /, ) !!
! !! & ! ! %
/0,1 ! )! ! B
& +
& &! $
# - !
! CA> $,$0 CA> 99 CA> $,$0#
# # ! A
$,$0 3 !
3 & & 3
! % &!!
CA> 99 ! # ! !
! ! CA> $,$0 !% 3
& 3
6 ! 3
B $,$0 " ;
! $,$0 !
#! 0! <(
,1 =-? ; # /0,1 /,/A ;4$
<( /,/A ;4$ $,$0
0 B9057Q !! !!
! ! /0,1 & !! ! & /,
Æ! ! !
! !! B B 1/
! /0,1 /,
1"
! &! 5, !
854 ! ; ! &!! ! !!
&!!,1 !& ,0, !0
" " ! # ! >
$ 5, ! ! # ( $ 854 !
!! ! !
7
7
! /0,1 1P0 $
! 10/A5 049A # ! #!
# & ! #!
! 1P0 , !
" ! (- -. ,
! & !
$ -. !
% & &
! ,0P,A @?@@ (@@ / 7 ! #
#$ " ! ! & & #!!
; 5, 854 !
,7/ !
-/. *-/#*-/.-
5, 854 ! F !
,7/ ! %
-.
7! & & ,,
! & ! %!3&
! ! 3
" F &! ! "
? << % &! ! & !
% 3 &
! ,, ((=
% ! &
! (= & &!
+
! $
*.+ ! &!
, # L &! &! & !
&! !! B&!
& ! *
! *
*(
*.+ 3
+!!!
& ! 1
!3
*
$ & ! &! ,
*
/
..
*.+ /
!!
*.+ !*
3
*(, !! , !
& ! 1
! *
*.+ & !1 4
;
! #
/* (
;
3 -
´ µ
¾
¾
¾
B 4 * ;
* ( & ! 1 &
7 , ! !
3! ,
*,
;! ! ! ! !
«
Ü
!
*
*.+ & ! 1 +
! #
/*
¾
-
R
+
! ;!!! !
+
«
Ú
½
:! Ê
½
Ø ½
Ü
$ ;
H(I 5 !E0- 0 1 * !G ,J ,
0/4 &!@ (@??
HI 9 J E2 &3 !G K4 7& B 6
! ) ! (@@<
HI 7 E1
G , 9& (@@
H.I ;!!E% ! 4-
1 0G, J &! ((@?.
H<I J ; E+ 4 4-1 * !G
J &! -( (@?@
H-I 8; /; !E& /G/ C!! , (@@-
H=I 9 / ; E2 4 2 !# & 1G 0
&! -5 = J!(@@.
H?I 9/; 7 &!/S E/&/+
5G 9 /989( / 9 8
>
H@I B8 E21614GK47&
B 6 ! ) !(@@<
H(I > C K "6 Q E !G &
! 9Q/0 F@ 75 & ==
H((I > 8!!B 8 E - 7 / G ,AAA
J ! &!= (@?@
H(I B8!E 1 G / 6 / (@-=
H(I J C E 1-
G/ (= !
(@?<
H(.I $ J E/ G /
&( (@@
H(<I K!>;! E4 %18/G/
) ! (@@-
H(-I >AKE/ 4-/G&!
( B! 7(@@=
H(=I >AKE/ 4-/G&!
B! 7(@@?
H(?I C K "6E% 4 !G & !
9Q/0 F?@/ ) ! (@@
H(@I ; 7 > J ; E%18/ 41+681 - / ! 6 4-
G / & ! (@@-
HI 8 ! E/ 1 * !G
D , 7;!! A!& (@?<
H(I J "" / & 0 ) E% 2 / -
9 / (@@-
HI C B7 E4-1 0 G A!
>& 5& (@=
HI 0 8 E 9*+: ,G) (@@=
H.I 09E4/ &&G,J &!
@ (@?
H<I ; E/ GJ B!T , (@@-
H-I B 9 & E9*+: *8;213 412!1/66+*! - + -
G)! A / C!! , ! , (@@@
H=I 9 5 E0 4G A B % /
7 ;
H?I J ) 8 8 E0 G B! / !
H@I A JB E4 4 " 5$G & (@-
HI 5 S ! E2 4 G, ! (@-?
H(I 5S ! E44 6 8G,
