ebook

Size: px

Start display at page:

Download "ebook"

誉施冯
9 years ago
Views:

1 3

2 ( ) 90

3 B e r n s t e i n P ( i ) R ( i ) W ( i P ( i P ( j ) 1) R( i) W( j)=φ 2) W( i) R( j)=φ 3) W( i) W( j)=φ ( p r o c e s s ) 91

4 Wi n d o w s Process Control Bl o c k P C B U N I X (/ p r o c ) 4 (process ID) (user ID) (process group) P C P S W P C B ) ( R u n n i n g ) 2) ( R e a d y ) I / O 3) ( B l o c k e d ) I / O 92

5 3 3-1 ( ) 4) ( N e w ) 5) ( E x i t ) 1) 2) (Admit, ) 3) ( D i s p a t c h ) 4) ( R e l e a s e ) ( E x i t ) ( a b o r t ) I / O 5) Ti m e o u t 6) Event Wa i t I / O 7) Event Occurs

6 Wi n d o w s 3-2 ( ) ( )

7 ) ( r e a d y ) 2) ( b l o c k e d ) 3) blocked, suspend 4) r e a d y, suspend 1) s u s p e n d 95

8 Wi n d o w s 2) a c t i v a t e 3) event occur 4) ( a d m i t ) f o r k s p a w n e x e c 3-1 f o r k 96 s p a w n e x e c

9 3 C e x i t ( ) I / O U N I X ( s l e e p ) ( p a u s e ) ( w a i t ) ( k i l l ) 1) sleep s e c o n d s unsigned sleep(unsigned s e c o n d s ) ; 2) pause int pause(void); 3) wait w a i t pid_t wait(int * s t a t _ l o c ); I D 4) kill s i g p i d int kill(pid_t pid, int sig); / u s r / u c b i n c l u d e / s y s / s i g n a l. h k i l l kill S I G K I L L I D 1 00 Windows NT Windows 2000/XP S u s p e n d T h r e a d R e s u m e T h r e a d suspend count ) Windows NT S u s p e n d T h r e a d DWORD SuspendThread( HANDLE hthread // ); 2) Windows NT R e s u m e T h r e a d DWORD ResumeThread( HANDLE hthread // ); 97

10 Wi n d o w s Windows 2000/XP Windows 2000/XP Windows ( h a n d l e ) ( s e r v i c e s ) ( P I D (Access To k e n ) (Base Priority) (Processor Aff i n i t y ) Wi n 32 O S / 2 PO S I X Windows 2000/XP PO S I X PO S I X 3-6 Windows NT Windows 2000/XP Wi n 3 2 Wi n 32 PO S I X O S / 2 Wi n 32 Windows 2000/XP Wi n 32 POSIX POSIX Win32 fork( ) CreateProcess( ) Windows Windows 2000/XP 3-7 Windows 2000/XP Wi n 32 ( E P R O C E S S ) (Virtual Address space Descriptor, VAD) Windows 2000/XP Wi n 32 C r e a t e P r o c e s s E x i t P r o c e s s Te r m i n a t e P r o c e s s C r e a t e P r o c e s s E x i t P r o c e s s Te r m i n a t e P r o c e s s 1) CreateProcess Wi n 32 D L L 2) ExitProcess Te r m i n a t e P r o c e s s

11 3 E x i t P r o c e s s Te r m i n a t e P r o c e s s VAD VAD VAD 3-7 Windows 2000/XP Wi n 32 Windows 2000/XP d e b u g g e r t a rg e t DEBUG_ PROCESS D e b u g A c t i v e P r o c e s s D L L Wa i t F o r D e b u g E v e n t C o n t i n u e D e b u g E v e n t Wa i t F o r D e b u g E v e n t C o n t i n u e D e b u g E v e n t R e a d P r o c e s s M e m o r y () WriteProcessMemory()

12 Wi n d o w s ( T h r e a d ) (kernel-level thread) I / O Windows NT Windows 2000/XP ( u s e r-level thread)

13 3 In f o r m i x Aldus PageMaker / ( L i g h t Weight Process) Windows 2000/XP Windows 2000/XP 101

14 Wi n d o w s Windows 2000/XP Windows 2000/XP 1) ( r e a d y ) 2) ( s t a n d b y ) 3) ( r u n n i n g ) 4) ( w a i t i n g ) 5) ( t r a n s i t i o n ) 6) ( t e r m i n a t e d )

15 3 7) ( I n i t i a l i z e d ) Windows 2000/XP C r e a t e T h r e a d E x i t T h r e a d S u s p e n d T h r e a d R e s u m e T h r e a d (mutual exclusion) ( d e a d l o c k ) ( s t a r v a t i o n ) 3-2 ( ( c o m p e t i t i o n ) ) ( ) ( ) 103

16 Wi n d o w s 3-11 (entry section) (critical section) (exit section) (remainder section) 1. (1) 1 while (turn! = i); P i P j t u r n turn = j; t u r n t u r n i P i t u r n P i t u r n P j j 3-12 P i 1 P i P j P i while (flag[j]); <a> (2) 2 flag[i] = TRUE; 1 flag[ ] flag [i] = FALSE; FA L S E P i

17 P i P j P i <a> P j <a> P i P j P i P j f l a g f l a g (3) 3 flag[i] = TRUE; 2 while (flag[j]); <a> flag[i] = FALSE; 3 2 f l a g [ i ] P i i 3-14 P i 3 P i P j P i P j P i <a> P j < a > f l a g f l a g (4) f l a g [ i ] P i t u r n t u r n f l a g t u r n t u r n flag[i] = TRUE; turn = j; while (flag[j] && turn == j); 3-15 P i 4 flag[i] = FALSE; T S S w a p (1) TS (Te s t - a n d - S e t ) 3 T S T R U E T 105

18 Wi n d o w s boolean TS(boolean *lock) { } boolean old; old = *lock; return old; 106 *lock = TRUE; T S l o c k T R U E FA L S E FA L S E T S l o c k 3-16 while TS (&lock); (2) Swap E x c h a n g e S w a p lock = FALSE; S w a p void SWAP(int *a, int *b) { int temp; 3-16 T S } temp = *a; *a = *b; *b = temp; do S w a p { l o c k FA L S E SWAP (&lock, &key); k e y l o c k S w a p } while (key); l o c k k e y k e y 3-17 lock = FALSE; 3-17 S w a p ( s e m a p h o r e ) key = TRUE;

19 3 1. P V D i j k s t r a P V t e s t ( p r o b e r e n ) i n c r e m e n t ( v e r h o g e n ) s s. c o u n t s. q u e u e P V P V P w a i t ( s ) w a i t ( s ) { -- s. c o u n t ; // ; if (s.count <0) // ; { s. q u e u e ; ; } } V s i g n a l ( s ) s i g n a l ( s ) { + + s. c o u n t ; / / if (s.count <= 0) } { / / s. q u e u e P ; P ; } 3-18 m u t e x ( M U Tual Exclusion) 1 P (mutex); P ( m u t e x ) V ( m u t e x ) P V V (mutex); P V P V

20 Wi n d o w s P 1 P 2 C 1 C 2 C 1 C 2 C 1 P(S 12 ); S 12 0 P 1 V ( S 12 ) P 2 P ( S 12 ) 2. (1) AND A N D A N D A N P Swait (Simultaneous Wa i t ) V Ssignal (Simultaneous Signal) S w a i t S w a i t S s i g n a l S w a i t ( S 1, S 2,..., Sn) { while (TRUE) { e l s e } / / P if (S 1 >=1 && S 2 >= 1 &&... && n S>= 1) } { / / for (i = 1; i <= n; ++i) i; --S // w a i t 1 } b r e a k ; { / / 1 Sj. q u e u e ; ; } P 1 V(S 12 ); P C 2 S s i g n a l ( S 1, S 2,..., S n ) / / { for (i = 1; i <= n; ++i) { S i ; / / for (each process P waiting in S i. q u e u e )

21 3 } } { / / S i. q u e u e P ; if ( P S w a i t ) // s i g n a l { // P ; } e l s e } { / / P } (2) n n w a i t n A N D S i t i >= t i t i d i S i S i = S i d i P V S w a i t ( S 1, t 1, d 1 ;...; S n, t n, d n ) ; S s i g n a l ( S 1, d 1 ;...; S n, d n ) ; 1) Swait(S, d, d) d d 2) Swait(S, 1, 1) 3) Swait(S, 1, 0) S 1 S = 0 S w a i t S s i g n a l P V 109

22 Wi n d o w s 1. ( p r o d u c e r-consumer problem) ( ) ( ) n M N 3-20 n f u l l e m p t y m u t e x f u l l 0 e m p t y n m u t e x 1 f u l l e m p t y f u l l + empty == n P A N D S w a i t ( e m p t y, mutex) Ssignal(full, mutex) 2. (readers-writers problem) 110

23 3 W m u t e x R m u t e x R c o u n t W m u t e x 1 R c o u n t 0 R m u t e x R c o u n t R W m u t e x R c o u n t W m u t e x 1 R c o u n t R

24 Wi n d o w s P V H o a r e H a n s o n ( m o n i t o r ) Windows 2000/XP Windows 2000/XP 112

25 3 ( M u t e x ) A P I C r e a t e M u t e x O p e n M u t e x R e l e a s e M u t e x C r e a t e M u t e x O p e n M u t e x R e l e a s e M u t e ( S e m a p h o r e ) 0 A P I C r e a t e S e m a p h o r e O p e n S e m a p h o r e R e l e a s e S e m a p h o r e C r e a t e S e m a p h o r e O p e n S e m a p h o r e R e l e a s e S e m a p h o r ( E v e n t ) A P I C r e a t e E v e n t O p e n E v e n t S e t E v e n t R e s e t E v e n t P u l s e E v e n t C r e a t e E v e n t O p e n E v e n t S e t E v e n P u l s e E v e n t R e s e t E v e n t Windows 2000/XP Wa i t F o r S i n g l e O b j e c t Wa i t F o r M u l t i p l e O b j e c t s Wa i t F o r S i n g l e O b j e c t Wa i t F o r M u l t i p l e O b j e c t s A P I DWORD WaitForSingleObject( HANDLE hhandle, // DWORD dwmilliseconds ); DWORD WaitForMultipleObjects( DWORD ncount, / / CONST HANDLE *lphandles, // // BOOL bwaitall, // T R U E F A L S E DWORD dwmilliseconds // ) ; Windows 2000/XP A P I (Critical Section) C R I T I C A L _ S E C T I O N A P I I n i t i a l i z e C r i t i c a l S e c t i o n E n t e r C r i t i c a l S e c t i o n Tr y E n t e r C r i t i c a l S e c t i o n L e a v e C r i t i c a l S e c t i o n D e l e t e C r i t i c a l S e c t i o n I n i t i a l i z e C r i t i c a l S e c t i o n E n t e r C r i t i c a l S e c t i o n Tr y E n t e r C r i t i c a l S e c t i o n 0 L e a v e C r i t i c a l S e c t i o D e l e t e C r i t i c a l S e c t i o n 113

26 Wi n d o w s A P I A P I I n t e r l o c k e d E x c h a n g e I n t e r l o c k e d C o m p a r e E x c h a n g e I n t e r l o c k e d E x c h a n g e A d d I n t e r l o c k e d D e c r e m e n t I n t e r l o c k e d I n c r e m e n t I n t e r l o c k e d E x c h a n g e 3 2 I n t e r l o c k e d C o m p a r e E x c h a n g e I n t e r l o c k e d E x c h a n g e A d d I n t e r l o c k e d D e c r e m e n t 1 I n t e r l o c k e d I n c r e m e n t ( I n t e r-process Communication, IPC) / / Windows 2000/XP ( s i g n a l ) Windows 2000/XP 1. SetConsoleCtrlHandler G e n e r a t e C o n s o l e C t r l E v e n t S e t C o n s o l e C t r l H a n d l e r ( H a n d l e r R o u t i n e ) C T R L + C S e t C o n s o l e C t r l 114

27 3 H a n d l e r C T R L + C G e n e r a t e C o n s o l e C t r l E v e n t C T R L _ C _ E V E N T C T R L _ B R E A K _ E V E N T C T R L _ C L O S E _ E V E N T C T R L _ L O G O F F _ E V E N T C T R L _ S H U T D O W N _ E V E N T C T R L + C C T R L + B R E A K 2. signal r a i s e s i g n a l r a i s e U N I X 5 Windows 2000/XP 3-4 S I G A B RT S I G F P E S I G I L L S I G I N T S I G S E G V S I G T E R M C T R L + C ( Wi n 32 ) Windows 2000/XP (shared memory) Windows 2000/XP (file mapping) C r e a t e F i l e M a p p i n g O p e n F i l e M a p p i n g M a p Vi e w O f F i l e F l u s h Vi e w O f F i l e U n m a p Vi e w O f F i l e C l o s e H a n d l e 115

28 Wi n d o w s Windows 2000/XP ( p i p e ) K B Windows 2000/XP Windows U N I X U N I C r e a t e P i p e R e a d F i l e Wr i t e F i l e C r e a t e P i p e BOOL CreatePipe( PHANDLE hreadpipe, // PHANDLE hwritepipe, // LPSECURITY_ATTRIBUTES lppipeattributes, // DWORD nsize ); 116 // Windows 2000/XP ( ) \\.\ p i p e \ P i p e N a m e \\ s e r v e r N a m e \ p i p e \ p i p e n a m e C r e a t e N a m e d P i p e C o n n e c t N a m e d P i p C a l l N a m e d P i p e R e a d F i l e Wr i t e F i l e R e a d F i l e E x Wr i t e F i l e E x Windows 2000/XP Windows 2000/XP ( m a i l s l o t ) \\.\ m a i l s l o t \[ p a t h ] n a m e \\ r a n g e \ m a i l s l o t \[ p a t h ] n a m e r a n g e C r e a t e M a i l s l o t G e t M a i l s l o t I n f o S e t M a i l s l o t I n f o R e a d F i l e C r e a t e F i l Wr i t e F i l e

29 ( s o c k e t ) / T C P / I P U N I X B S D T C P / I P s e n d s e n d t o r e c v r e c v f r o m Windows 2000/XP Wi n s o c k " B S D Wi n S o c k 2. 2 s e n d s e n d t o r e c v r e c v f r o m W S A S e n d W S A S e n d t o W S A R e c v W S A R e c v f r o m 3.6 ( d e a d l o c k ) (reusable resource) I / O A B 3-24 P1<a> P2<a> P1 P2 3-24 (consumable resource) 117

30 Wi n d o w s 3-25 P1<a> P2<a> ) 2) 3) 4) ( P r e v e n t i o n ) < 2 > < 3 > < 4 > ( Av o i d a n c e ) ( D e t e c t i o n )

31 (resource allocation graph) G R P R P P R P R 3.6.4

32 Wi n d o w s T 120

33 / I / O

34 Wi n d o w s ( d i s p a t c h e r ) A A B B (First Come First Service, FCFS) F C F S I / O F C F S F C F S I / O (Shortest Job First, SJF) (Shortest Process Next, SPN) F C F S S J F S J F F C F S S J F S J F ( S h o r t e s t Remaining Time, SRT ) S J F (Highest Response Ratio Next, HRRN) ( + ) / F C F S S J F 122

35 (Round Robin) F C F S m s m F C F S (Multiple-level Queue) (Priority Scheduling) 123

36 Wi n d o w s (Round Robin with Multiple Feedback) I / O I / O 1 1 F C F S 1 2 F C F S I / O I / O I / O I / O I / O I / O I / O 3.9 Windows 2000/XP Windows 2000/XP Windows 2000/XP Wi n d o w s 2000 / X P Windows 2000/XP Wi n 32 Windows 2000/XP Windows 2000/XP Windows 2000/XP Windows 2000/XP Wi n

37 3 ( q u a n t u m ) Windows 2000/XP Windows Windows 2000 Windows 2000 Windows 2000/XP Windows 2000/XP ( k e r n e l s dispatcher) D P C / 1) 2) 3) Windows 2000/XP 4) Windows 2000/XP Wi n d o w s / X P Windows 2000/XP A 1 0 B / 12 Windows 2000/XP A B Windows 2000/XP Wi n Win32 API Win A P I S u s p e n d / R e s u m e T h r e a d G e t / S e t P r i o r i t y C l a s s G e t / S e t T h r e a d P r i o r i t y ( ) 125

38 Wi n d o w s A P I G e t / S e t P r o c e s s A ff i n i t y M a s k S e t T h r e a d A ff i n i t y M a s k G e t / S e t T h r e a d P r i o r i t y B o o s t S e t T h r e a d I d e a l P r o c e s s o r G e t / S e t P r o c e s s P r i o r i t y B o o s t S w i t c h To T h r e a d S l e e p S l e e p E x ( ) Windows 2000/XP ( ) 0 I / O A P C Windows 2000/XP ) ) ) 0 Wi n 3 2 Windows 2000/XP Wi n Wi n Wi n 32 Windows 2000/XP 3-28 Task Manager Wi n 32 S e t P r i o r i t y C l a s s Windows 2000/XP 126

39 8 8 Windows 2000/XP Wi n Wi n 3 2 Windows 2000/XP Windows 2000/XP Win32 Windows 2000/XP ( ) 127

40 Wi n d o w s Windows 2000/XP Windows 2000/XP n DPC/dispatch 1 APC 0 31 D P C / ( K i D i s p a t c h e r L o c k ) Windows 2000/XP Windows 2000/XP (quantum unit) 1. Windows Windows 2000/XP 36 Wi n d o w s / X P ( 3 ) Windows Windows 2000/XP 12 D P C / ( D P C ) 128

41 3 x x Wi n 32 G e t S y s t e m Ti m e A d j u s t m e n t w w w. s y s i n t e r n a l s. c o m C l o c k r e s I / O I / O ( I n t e r r u p t s / s e c ) x / 100 = x / = ( Wa i t F o r S i n g l e O b j e c t Wa i t F o r M u l t i p l e O b j e c t s ) H K L M \ S Y S T E M \ C u r r e n t C o n t r o l S e t \ C o n t r o l \ P r i o r i t y C o n t r o l \ Wi n 32 P r i o r i t y S e p a r a t i o n ( ) Wi n 32 P r i o r i t y S e p a r a t i o n (Short vs. Long) ( Windows 2000 Windows 2000 ) ( Variable vs. Fixed) ( Windows 2000 Windows 2000 ) 129

42 Wi n d o w s (Foreground Quantum Boost) ( 3 2 ) P s P r i o r i t y S e p a r a t i o n Wi n 32 Wi n P r i o r i t y S e p a r a t i o n 3 P s p F o r e g r o u n d Q u a n t u m Wi n 32 P r i o r i t y S e p a r a t i o n P s p F o r e g r o u n d Q u a n t u m Windows 2000/XP ( ) start /abovenormal start /high Wi n 32 P r i o r i t y S e p a r a t i o n 3 (Performance Options) 2 Windows 2000 Windows 2000 Windows Windows 2000 ( Terminal Services)

43 3 ( K i D i s p a t c h e r R e a d y L i s t H e a d ) Windows 2000/XP ( K i R e a d y S u m m a r y ) 3 2 B 0 0 B 1 1 Windows 2000/XP ( K i I d l e S u m m a r y ) 3 2 D P C / ( K i D i s p a t c h e r L o c k ) K i D i s p a t c h e r L o c k K e N u m b e r P r o c e s s o r s K e A c t i v e P r o c e s s o r s 3 2 K i I d l e S u m m a r y 3 2 K i R e a d y S u m m a r y 3 2 K i D i s p a t c h e r R e a d y L i s t H e a d

44 Wi n d o w s Windows 2000/XP Windows 2000/XP 1. Wi n 32 ( Wa i t F o r S i n g l e O b j e c t Wa i t F o r M u l t i p l e O b j e c t s ) I / O ( ) 3-32 Windows 2000/XP ( ) /

45 3 1) 2) Windows 2000/XP Windows 2000/XP Windows 2000/XP 133

46 Wi n d o w s 134 Windows 2000/XP ( ) E x i t T h r e a d Te r m i n a t e T h r e a Windows 2000/XP 1) I/O 15 2) 3) 4) 5) ( ) Windows 2000/XP ( ) Windows 2000/XP I/O I / O Windows 2000/XP I / O I / O

47 I / O 1 D D K I / O W d m. h N t d d k. h #define IO 3-9 I / O I o C o m p l e t e R e q u e s t 3-9 I / O I / O 3-35 ( ) S e t E v e n t P u l s e E v e n t R e l e a s e S e m a p h o r e 135

48 Wi n d o w s D D K E V E N T _ I N C R E M E N T S E M A P H O R E _ I N C R E M E N T I / O I / O K i U n w a i t T h r e a d ( ) P s P r i o r i t y S e p a r a t i o n P s P r i o r i t y S e p a r a t i o n Windows 2000 Windows 2000 Wi n 3 2 S e t T h r e a d P r i o r i t y B o o s t 4. ( ) 2 ( Wi n 32 k. s y s ) K e S e t E v e n t K e S e t E v e n Windows 2000/XP (balance set manager)

49 ( ) Wi n d o w s 2000 / X P Wi n d o w s / X P 1. ( ) S e t P r o c e s s A ff i n i t y M a s k S e t T h r e a d A ff i n i t y M a s k 2. 1) 2) Windows 2000/XP S e t T h r e a d I d e a l P r o c e s s o r 3. Windows 2000/XP ( ) Windows 2000/XP Windows 2000/XP Windows 2000/XP 137

50 Wi n d o w s ( ) Windows 2000/XP Windows 2000/XP 4. ( ) Windows 2000/XP Windows 2000/XP Windows 2000/XP 1) 2) 3) 2 4) 24 Wi n d o w s / X P 5. Windows 2000/XP Windows 2000/XP

51 3 8 Windows 2000/XP Windows 2000/XP Windows 2000/XP 0 1) 2) D P C D P 3) 4) Windows 2000/XP Windows Windows C t r l - C 5 C t r l - C A k k B n A ( 1 2 k ) k B n 3.12 T T T

52 Wi n d o w s 3.13 Windows Windows Windows Windows Windows 2000 I / O 3.19 Windows Windows David A. Solomon, Mark E. Russinovich. Inside Microsoft Windows rd Edition. Microsoft Press, Gary Nutt. Operating System Project Using Windows NT. Addison-We s l e y 3. The July 2000 release of the MSDN Library 4. William Stallings. Operating Systems.3rd edition., Uresh Vahalia. UNIX

投影片 1

投影片 1 9 1 9-1 Windows XP Windows Server 2003 Mac OS Linux, 都 (OS, Operating System ) 2 3 , 來, 行 3 理行 4 ,, (UI, User Interface), 滑, 令列 (CLI, Command-Line Interface) (GUI, Graphical User Interface) 2 5 令列,