Luận văn Nghiên cứu, thiết kế hệ điều hành trên bộ vi điều khiển 8 bít

bé gi¸o dôc vµ ®µo t¹o

tr−êng ®¹i häc b¸ch khoa hµ néi

-----------------------------------------

luËn v¨n th¹c sü khoa häc

Nghiªn cøu, thiÕt kÕ hÖ ®iÒu hµnh trªn

bé vi ®iÒu khiÓn 8 bÝt

ngµnh: xö lý th«ng tin vµ truyÒn th«ng

M∙ sè:

vò trung kiªn

Ng−êi h−íng dÉn khoa häc: TS. NguyÔn Linh Giang

hµ néi 2006

-2-

Lêi cam ®oan

T«i xin cam ®oan b¶n luËn v¨n nµy lµ kÕt qu¶ nghiªn cøu cña b¶n th©n d−íi

sù h−íng dÉn cña TS. NguyÔn Linh Giang. NÕu cã g× sai ph¹m, t«i xin hoµn toµn

chÞu tr¸ch nhiÖm.

Ng−êi lµm cam ®oan

Vò Trung Kiªn

-3-

Môc lôc

Lêi cam ®oan.....................................................................................................2

Danh môc c¸c ký hiÖu, c¸c ch÷ viÕt t¾t ..........................................................5

Danh môc c¸c b¶ng ..........................................................................................6

Danh môc c¸c h×nh vÏ, ®å thÞ..........................................................................7

Lêi nãi ®Çu ........................................................................................................9

Ch−¬ng 1 - Tæng quan vÒ hÖ ®iÒu hµnh......................11

1.1. Kh¸i niÖm vÒ hÖ ®iÒu hµnh (OS-Operating System)................................. 11

1.1.1. Kh¸i niÖm................................................................................................. 11

1.1.2. Chøc n¨ng cña hÖ ®iÒu hµnh. ................................................................... 11

1.1.3. C¸c thµnh phÇn cña hÖ ®iÒu hµnh............................................................. 13

1.2. Qu¶n lý tiÕn tr×nh......................................................................................... 16

1.2.1. C¸c tr¹ng th¸i cña mét tiÕn tr×nh.............................................................. 16

1.2.2. Kh¸i niÖm vÒ tµi nguyªn “g¨ng” vµ ®o¹n tíi h¹n .................................... 17

1.2.3. HiÖn t−îng bÕ t¾c..................................................................................... 19

1.3. LËp lÞch cho CPU......................................................................................... 20

1.3.1. Kh¸i niÖm giê CPU.................................................................................. 20

1.3.2. C¸c tr¹ng th¸i cña tiÕn tr×nh liªn quan ®Õn giê CPU................................ 20

1.3.3. LËp lÞch cho CPU..................................................................................... 22

1.4. Qu¶n lý bé nhí............................................................................................. 25

1.4.1. Yªu cÇu ph¶i qu¶n lý bé nhí ................................................................... 25

1.4.2. C¸c s¬ ®å qu¶n lý bé nhí......................................................................... 26

Ch−¬ng 2 - Vi ®iÒu khiÓn vµ ng«n ng÷ lËp tr×nh

cho vi ®iÒu khiÓn ......................................................................28

2.1. Vi ®iÒu khiÓn........................................................................................28

2.1.1. Vi xö lý vµ vi ®iÒu khiÓn.......................................................................... 28

2.1.2. Tæ chøc bé nhí cña vi ®iÒu khiÓn............................................................ 30

2.1.3. C¸c bé ®Þnh thêi....................................................................................... 35

2.1.4. Bé xö lý ng¾t............................................................................................ 37

2.2. Ng«n ng÷ lËp tr×nh cho vi ®iÒu khiÓn......................................................... 39

-4-

2.2.1. Tæng quan vÒ c¸c ng«n ng÷ lËp tr×nh cho vi ®iÒu khiÓn. ......................... 39

2.2.2. Nh÷ng vÊn ®Ò víi ng«n ng÷ C viÕt cho c¸c bé vi ®iÒu khiÓn................... 42

Ch−¬ng 3 - thiÕt kÕ hÖ vi ®iÒu khiÓn............................49

3.1. X¸c ®Þnh yªu cÇu thiÕt kÕ. ........................................................................... 50

3.2. Lùa chän cÊu h×nh cho hÖ thèng................................................................. 51

3.2.1. Lùa chän bé ®iÒu khiÓn trung t©m........................................................... 51

3.2.2. Giao diÖn ng−êi sö dông.......................................................................... 52

3.2.3. C¸c thiÕt bÞ m« pháng qu¸ tr×nh ho¹t ®éng cña tiÕn tr×nh. ...................... 53

3.3. ThiÕt kÕ m¹ch ®iÖn....................................................................................... 58

3.4. §o thö vµ kiÓm tra lçi.................................................................................. 59

Ch−¬ng 4 - ThiÕt kÕ hÖ ®iÒu hµnh.....................................60

4.1.1. Môc ®Ých vµ yªu cÇu thiÕt kÕ. .................................................................. 60

4.1.2. Môc ®Ých. ................................................................................................. 60

4.1.2. Yªu cÇu .................................................................................................... 63

4.2. Tr×nh tù thiÕt kÕ hÖ ®iÒu hµnh.................................................................... 64

4.3. X©y dùng c¸c tiÕn tr×nh. .............................................................................. 65

4.3.1. X©y dùng c¸c t¸c vô t−¬ng øng c¸c tiÕn tr×nh.......................................... 65

4.3.2. Gi¶i quyÕt bµi to¸n tµi nguyªn g¨ng ........................................................ 69

4.4. LËp lÞch cho CPU. ........................................................................................ 71

4.4.1. Sù kiÖn vµ chuyÓn tr¹ng th¸i gi÷a c¸c tiÕn tr×nh. ..................................... 71

4.4.2. LËp lÞch cho CPU..................................................................................... 80

4.5. Qu¶n lý bé nhí............................................................................................. 83

KÕt luËn vµ kiÕn nghÞ.....................................................................................86

Tµi liÖu tham kh¶o .........................................................................................87

-5-

Danh môc c¸c ký hiÖu, c¸c ch÷ viÕt t¾t

STT

1

Ch÷ viÕt t¾t

FCFS

FIFO

LIFO

MCS

OS

Ch÷ ®Çy ®ñ

First Come First Served

First In First Out

2

3

Last In First Out

4

Micro Controller System

Operating System

5

6

RTOS

RR

Real Time Operating System

Round Robbin

7

8

SJF

Shortest Job First

9

SRT

Shortest Remain Time

Micro Controller

10

uC

-6-

Danh môc c¸c b¶ng

B¶ng 1.1. Tr¹ng th¸i cña c¸c tiÕn tr×nh............................................................... 19

B¶ng 1.2. Thêi gian thùc hiÖn cña c¸c tiÕn tr×nh................................................ 25

B¶ng 1.3. Thêi gian chê cña c¸c tiÕn tr×nh......................................................... 25

B¶ng 2.1. Bé nhí d÷ liÖu trªn chÝp cña AT89S52 .............................................. 33

-7-

Danh môc c¸c h×nh vÏ, ®å thÞ

H×nh 1.1. C¸c tr¹ng th¸i cña mét tiÕn tr×nh........................................................ 17

H×nh 1.2. C¸c tr¹ng th¸i cña tiÕn tr×nh liªn quan ®Õn giê CPU.......................... 20

H×nh 1.3. S¬ ®å thùc hiÖn tiÕn tr×nh ................................................................... 21

H×nh 1.4. S¬ ®å tæ chøc hµng ®îi c¸c tiÕn tr×nh ................................................. 22

H×nh 1.5. S¬ ®å Grant......................................................................................... 25

H×nh 2.1. S¬ ®å khèi cña bé vi ®iÒu khiÓn AT89S52......................................... 29

H×nh 2.2. Tæ chøc bé nhí cña vi ®iÒu khiÓn ...................................................... 30

H×nh 2.3. S¬ ®å ghÐp nèi AT89S52 víi EPROM............................................... 31

H×nh 2.4. S¬ ®å ghÐp nèi AT89S52 víi RAM .................................................. 34

H×nh 2.5. Gi¶i m· ®Þa chØ cho c¸c vi m¹ch nhí ................................................. 34

H×nh 2.6. Bé nhí d÷ liÖu ®äc nh− bé nhí ch−¬ng tr×nh..................................... 35

H×nh 2.7. Ho¹t ®éng cña Timer0 vµ Timer1 ë chÕ ®é 1..................................... 36

H×nh 2.8. C¸c nguån ng¾t cña AT89S52............................................................ 38

H×nh 3.1. Tr×nh tù thiÕt kÕ phÇn cøng cho hÖ thèng.......................................... 49

H×nh 3.2. S¬ ®å khèi cña hÖ vi ®iÒu khiÓn ......................................................... 51

H×nh 3.3. GhÐp nèi vi ®iÒu khiÓn víi RAM ngoµi. ............................................ 52

H×nh 3.4. Giao diÖn ng−êi sö dông trªn hÖ vi ®iÒu khiÓn................................... 53

H×nh 3.5. HiÓn thÞ trªn LED 7 ®o¹n b»ng kü thuËt quÐt .................................... 54

H×nh 3.6. GhÐp nèi ma trËn LED trªn hÖ vi ®iÒu khiÓn ..................................... 57

H×nh 3.7. Nguyªn t¾c xÕp ch÷ trªn ma trËn LED............................................... 58

H×nh 4.1. C¸c t¸c vô ®−îc thùc hiÖn ®ång thêi (song song) .............................. 62

H×nh 4.2. C¸c t¸c vô ®−îc thùc hiÖn lu©n phiªn liªn tôc.................................... 62

H×nh 4.3. Gi¶n ®å xung trªn P1.......................................................................... 69

H×nh 4.4. Chèt l¹i gi¸ trÞ cña P1......................................................................... 70

-8-

H×nh 4.5. C¸c tiÕn tr×nh ®−îc ph©n bæ thêi gian CPU b»ng nhau...................... 71

H×nh 4.6. ChuyÓn gi÷a c¸c tiÕn tr×nh b»ng sù kiÖn time out.............................. 73

H×nh 4.7. C¸c tiÕn tr×nh ®−îc ph©n bæ thêi gian CPU kh¸c nhau ...................... 74

H×nh 4.8. Ng−êi sö dông ra lÖnh vµo c¸c thêi ®iÓm kh¸c nhau ......................... 75

H×nh 4.9. ChuyÓn gi÷a c¸ tiÕn tr×nh b»ng sù kiÖn interrupt ............................... 76

H×nh 4.9. M« t¶ tr¹ng th¸i cña c¸c tµi nguyªn cña tiÕn tr×nh............................. 77

H×nh 4.10. C¸c tµi nguyªn cÇn l−u khi dõng mét tiÕn tr×nh............................... 78

H×nh 4.11. Ph©n bæ ng¨n xÕp cho c¸c tiÕn tr×nh ................................................ 79

H×nh 4.12. LËp lÞch cho 8 tiÕn tr×nh thùc hiÖn quÐt ch÷ trªn ma trËn LED ....... 81

H×nh 4.13. LËp lÞch cho 4 tiÕn tr×nh quÐt c¸c sè trªn 4 LED 7 ®o¹n ................. 81

H×nh 4.14. LËp lÞch cho tiÕn tr×nh ®iÒu khiÓn LCD........................................... 82

H×nh 4.15. LËp lÞch cho tiÕn tr×nh thêi gian thùc.............................................. 82

H×nh 4.16. Tæ chøc bé nhí ROM cña hÖ vi ®iÒu khiÓn ..................................... 83

H×nh 4.17. Thay ®æi vÞ trÝ ®Æt c¸c ch−¬ng tr×nh con phôc vô ng¾t..................... 84

H×nh 4.18. Ph©n bæ bé nhí ROM....................................................................... 85

H×nh 4.19. Ph©n bæ bé nhí RAM....................................................................... 85

-9-

Lêi nãi ®Çu

Cïng víi sù ph¸t triÓn cña khoa häc kü thuËt, côm tõ “tù ®éng ho¸” ®· trë

nªn hÕt søc phæ th«ng. Tõ c¸c m¸y mãc tù ®éng trong c¸c nhµ m¸y xÝ nghiÖp

thay thÕ cho søc lao ®éng cña c«ng nh©n, tõ c¸c ®å gia dông tù ®éng trong gia

®×nh gióp Ých cho ng−êi néi trî...nãi chung c¸c thiÕt bÞ cã kh¶ n¨ng tù ®éng ho¸

xuÊt hiÖn ë kh¾p mäi n¬i. Mét c©u hái ®Æt ra víi kh¸ nhiÒu ng−êi lµ nhê ®©u mµ

c¸c thiÕt bÞ cã kh¶ n¨ng tù ®éng ®−îc? §Ó tr¶ lêi c©u hái nµy chóng ta cÇn ph¶i ®i

tõ khi cã côm tõ “tù ®éng ho¸” ra ®êi.

Tr−íc kia, khi ch−a cã c«ng nghÖ b¸n dÉn, c¸c phÇn tö cã tiÕp ®iÓm nÕu

®−îc ®Çu nèi víi nhau theo mét m¹ch logic nµo ®ã th× vÉn cã thÓ t¹o ra mét hÖ

thèng tù ®éng, tuy nhiªn kh¶ n¨ng ®¸p øng vµ tÝnh tù ®éng c¶ hÖ thèng nµy

kh«ng cao. C«ng nghÖ b¸n dÉn ra ®êi, nã gi¶i quyÕt ®−îc h¹n chÕ vÒ ®¸p øng (tèc

®é) cña c¸c phÇn tö cã tiÕp ®iÓm tuy nhiªn còng ph¶i chê ®Õn khi cã sù xuÊt hiÖn

cña c¸c bé vi xö lý, c¸c hÖ thèng cã tÝnh tù ®éng ho¸ cao míi ra ®êi. §Æc tr−ng

cña c¸c hÖ thèng nµy ®−îc m« t¶ b»ng mét c«ng thøc ®¬n gi¶n: PhÇn cøng +

PhÇn mÒm = øng dông. Theo c«ng thøc nµy th× khi tuú biÕn mét trong 2 thµnh

phÇn lµ phÇn cøng hoÆc phÇn mÒm th× sÏ cho ra øng dông kh¸c. Th«ng th−êng

phÇn mÒm lµ thµnh phÇn ®−îc tuú biÕn.

Mét hÖ thèng víi c¸c bé vi xö lý cã thÓ gi¶ c¸c suy nghÜ vµ hµnh ®éng cña

con ng−êi v× lý do ®¬n gi¶n lµ chóng ho¹t ®éng theo mét ch−¬ng tr×nh cña ng−êi

thiÕt kÕ ®−a vµo mµ ch−¬ng tr×nh chÝnh lµ c¸c thuËt to¸n lµ ý nghÜ cña ng−êi lËp

tr×nh. Nh− vËy ®Ó mét hÖ thèng cã tÝnh th«ng minh, tù ®éng ho¸ cao th× phÇn

mÒm viÕt cho nã lµ vÊn ®Ò hÕt søc quan träng.

Mét hÖ thèng víi cïng mét phÇn cøng nh−ng nÕu nã ®−îc viÕt hÖ ®iÒu hµnh

th× kh¶ n¨ng cña nã sÏ trë nªn m¹nh h¬n rÊt nhiÒu so víi mét hÖ thèng chØ cã

mét ch−¬ng tr×nh tuÇn tù. Víi môc ®Ých kh«ng ngõng ®¸p øng c¸c nhu cÇu cña

-10-

x· héi, hiÖn nay c¸c m«n häc vÒ hÖ nhóng ®· vµ ®ang ®−îc ®−a vµo gi¶ng d¹y t¹i

c¸c tr−êng Cao ®¼ng vµ §¹i häc. Tuy nhiªn ®Ó cã mét hiÖu qña gi¶ng d¹y tèt

nhÊt th× cÇn cã mét ph−¬ng ph¸p nghiªn cøu vµ thiÕt kÕ ®óng chÝnh t¾c vµ còng

cÇn ph¶i cã mét thiÕt bÞ phôc vô qua tr×nh thÝ nghiÖm.

Tr−êng §¹i häc C«ng nghiÖp Hµ néi lµ mét tr−êng ®µo t¹o c¸c cö nh©n vµ

c¸c kü s− thùc hµnh. Trong ch−¬ng tr×nh ®µo t¹o còng ®· cã m«n kü thuËt vi ®iÒu

khiÓn, ®©y cã thÓ coi lµ nÒn t¶ng ®Ó tiÕp cËn víi c¸c hÖ thèng nhóng sö dông vi

®iÒu khiÓn cã hÖ ®iÒu hµnh. ViÖc nghiªn cøu ®Ó ®−a vµo gi¶ng d¹y m«n thiÕt kÕ

hÖ ®iÒu hµnh cho c¸c hÖ vi ®iÒu khiÓn lµ phï hîp víi yªu cÇu hiÖn t¹i.

Víi sù h−íng dÉn cña TS NguyÔn Linh Giang, trong khu«n khæ luËn v¨n

nµy, t«i m¹nh d¹n nghiªn cøu vÒ c¸c nguyªn t¾c c¬ b¶n khi thiÕt kÕ mét hÖ ®iÒu

hµnh trªn hÖ vi ®iÒu khiÓn.

Néi dung cña luËn v¨n bao gåm 4 ch−¬ng, trong ®ã:

Ch−¬ng 1: Giíi thiÖu tæng quan hÖ ®iÒu hµnh.

Ch−¬ng 2: Giíi thiÖu bé vi ®iÒu khiÓn ®−îc sö dông ®Ó viÕt hÖ ®iÒu hµnh vµ

ng«n ng÷ lËp tr×nh cho vi ®iÒu khiÓn.

Ch−¬ng 3. ThiÕt kÕ phÇn cøng hÖ vi ®iÒu khiÓn.

Ch−¬ng 4. ThiÕt kÕ hÖ ®iÒu hµnh cho hÖ vi ®iÒu khiÓn

Do thêi gian vµ kh¶ n¨ng cã h¹n nªn luËn v¨n nµy sÏ cßn nhiÒu thiÕu sãt.

RÊt mong ®−îc sù gãp ý vµ th«ng c¶m cña c¸c thÇy gi¸o, c« gi¸o.

Hµ néi, ngµy 30 th¸ng 10 n¨m 2006

Häc viªn

Vò Trung Kiªn

-11-

Ch−¬ng 1 - Tæng quan vÒ hÖ ®iÒu hµnh

1.1. Kh¸i niÖm vÒ hÖ ®iÒu hµnh (OS-Operating System)

1.1.1. Kh¸i niÖm

Khã cã mét kh¸i niÖm hay ®Þnh nghÜa chÝnh x¸c vÒ hÖ ®iÒu hµnh, v× hÖ ®iÒu

hµnh lµ mét bé phËn ®−îc nhiÒu ®èi t−îng khai th¸c nhÊt, hä cã thÓ lµ ng−êi sö

dông th«ng th−êng, cã thÓ lµ lËp tr×nh viªn, cã thÓ lµ ng−êi qu¶n lý hÖ thèng vµ

tuú theo møc ®é khai thøc hÖ ®iÒu hµnh mµ hä cã thÓ ®−a ra nh÷ng kh¸i niÖm

kh¸c nhau.

Kh¸i niÖm 1: HÖ ®iÒu hµnh lµ hÖ thèng ch−¬ng tr×nh víi c¸c chøc n¨ng gi¸m

s¸t ®iÒu khiÓn viÖc thùc hiÖn c¸c ch−¬ng tr×nh cña ng−êi sö dông qu¶n lý vµ ph©n

chia tµi nguyªn cho nhiÒu ch−¬ng tr×nh ng−êi sö dông ®ång thêi sao cho viÖc

khai th¸c chøc n¨ng cña hÖ thèng m¸y tÝnh cña ng−êi sö dông lµ thuËn lîi vµ hiÖu

qu¶ nhÊt.

Kh¸i niÖm 2: HÖ ®iÒu hµnh lµ mét ch−¬ng tr×nh ®ãng vai trß nh− giao diÖn

gi÷a ng−êi sö dông vµ phÇn cøng m¸y tÝnh nã qu¶n lý vµ ®iÒu khiÓn phÇn cøng

còng nh− sù thùc hiÖn cña tÊt c¶ c¸c ch−¬ng tr×nh.

Kh¸i niÖm thø hai rÊt gÇn víi c¸c hÖ ®iÒu hµnh ®ang sö dông trªn c¸c m¸y

tÝnh hiÖn nay trong khi kh¸i niÖm thø nhÊt l¹i gÇn víi c¸c hÖ thèng ®o l−êng ®iÒu

khiÓn trong c«ng nghiÖp sö dông c¸c bé ®iÒu khiÓn kh¶ tr×nh (VÝ dô nh− vi ®iÒu

khiÓn).

1.1.2. Chøc n¨ng cña hÖ ®iÒu hµnh.

Cã thÓ nãi hÖ ®iÒu hµnh lµ 1 hÖ thèng c¸c ch−¬ng tr×nh ®ãng vai trß trung

gian gi÷a ng−êi sö dông vµ phÇn cøng. NhiÖm vô chÝnh cña nã lµ cung cÊp mét

m«i tr−êng thuËn lîi ®Ó ng−êi sö dông dÔ dµng thùc hiÖn c¸c ch−¬ng tr×nh øng

dông cña hä trªn m¸y tÝnh vµ khai th¸c triÖt ®Ó c¸c chøc n¨ng cña phÇn cøng.

-12-

§Ó ®¹t ®−îc môc tiªu trªn hÖ ®iÒu hµnh ph¶i thùc hiÖn 2 chøc n¨ng chÝnh

sau ®©y:

- T¹o ra mét hÖ th«ng më réng bao gåm c¸c thµnh phÇn vËt lý vµ c¸c thµnh

phÇn logic:

Nh− chóng ta biÕt, mét hÖ thèng kh¶ tr×nh (vÝ dô nh− m¸y tÝnh) gåm c¸c bé

phËn chÝnh nh−: Processor, Memory, I/O Device, Bus, vv, do ®ã ®Ó ®èi tho¹i

hoÆc khai th¸c m¸y tÝnh ng−êi sö dông ph¶i hiÓu ®−îc c¬ chÕ ho¹t ®éng cña c¸c

bé phËn nµy vµ ph¶i t¸c ®éng trùc tiÕp vµo nã tÊt nhiªn lµ b»ng nh÷ng con sè 0,1

(ng«n ng÷ m¸y). §iÒu nµy lµ qu¸ khã ®èi víi ng−êi sö dông hÖ ®iÒu hµnh ph¶i

che ®Ëy c¸c chi tiÕt phÇn cøng m¸y tÝnh bëi mét m¸y tÝnh më réng, m¸y tÝnh më

réng nµy cã ®Çy ®ñ c¸c chøc n¨ng cña mét m¸y tÝnh thùc nh−ng ®¬n gi¶n vµ dÔ

sö dông h¬n. Theo ®ã khi cÇn t¸c ®éng vµo m¸y tÝnh thùc ng−êi sö dông chØ cÇn

t¸c ®éng vµo m¸y tÝnh më réng mäi sù chuyÓn ®æi th«ng tin ®iÒu khiÓn tõ m¸y

tÝnh. Môc ®Ých cña chøc n¨ng nµy kµ: Gióp ng−êi sö dông khai thøc c¸c chøc

n¨ng cña phÇn cøng m¸y tÝnh dÔ dµng vµ hiÖu qu¶ h¬n.

- Qu¶n lý tµi nguyªn cña hÖ thèng:

Tµi nguyªn hÖ thèng cã thÓ lµ: prrocessor, Memory, I/O Device..., ®©y lµ

nh÷ng tµi nguyªn mµ hÖ ®iÒu hµnh dïng ®Ó cÊp ph¸t cho c¸c tiÕn tr×nh, ch−¬ng

tr×nh trong qu¸ tr×nh ®iÒu khiÓn sù ho¹t ®éng cña hÖ thèng. Khi ng−êi sö dông

cÇn thùc hiÖn mét ch−¬ng tr×nh hay mét ch−¬ng tr×nh cÇn n¹p thªm mét tiÕn

tr×nh míi vµo bé nhí th× hÖ ®iÒu hµnh ph¶i cÊp ph¸t kh«ng gian nhí cho ch−¬ng

tr×nh, tiÕn tr×nh ®ã ®Ó ch−¬ng tr×nh, tÝªn tr×nh ®ã n¹p ®−îc vµo bé nhí vµ ho¹t

®éng ®−îc. Trong m«i tr−êng hÖ ®iÒu hµnh ®a nhiÖm cã thÓ cã nhiÒu ch−¬ng

tr×nh, tiÕn tr×nh ®ång thêi cÇn ®−îc n¹p vµo bé nhí nh−ng kh«ng gian l−u tr÷ cñ©

bé nhí cã giíi h¹n do ®ã hÖ ®iÒu hµnh ph¶i tæ chøc cÊp ph¸t bé nhí sao cho hîp

lý ®Ó ®¶m b¶o tÊt c¶ c¸c ch−¬ng tr×nh tiÕn tr×nh khi cÇn ®Ó ®−îc n¹p vµo bé nhí

®Ó ho¹t ®éng. Ngoµi ra hÖ ®iÒu hµnh cßn ph¶i tæ chøc b¶o vÖ c¸c kh«ng gian nhí

®· cÊp cho c¸c ch−¬ng tr×nh tiÕn tr×nh ®Ó tr¸nh sù truy cËp bÊt hîp lÖ vµ sù tranh

-13-

chÊp bé nhí gi÷a c¸c ch−¬ng tr×nh, tiÕn tr×nh, ®Æc biÖt lµ c¸c tiÕn tr×nh ®ång thêi

ho¹t ®éng trªn hÖ thèng. §©y lµ mét trong nh÷ng nhiÖm vô quan träng cña hÖ

®iÒu hµnh.

Trong qu¸ tr×nh ho¹t ®éng cña hÖ thèng ®Æc bÖt lµ c¸c hÖ thèng ®a ng−êi

dïng ®a ch−¬ng tr×nh, ®a tiÕn tr×nh. Cßn xuÊt hiÖn mét hiÖn t−îng kh¸c, ®ã lµ

nhiÒu ch−¬ng tr×nh, tiÕn tr×nh ®ång thêi sö dông mét kh«ng gian nhí hau mét tËp

tin (d÷ liÖu, ch−¬ng tr×nh) nµo ®ã. Trong tr−êng hîp nµy hÖ ®iÒu hµnh ph¶i tæ

chøc viÖc chia sÎ vµ gi¸m s¸t viÖc truy xuÊt ®ång thêi trªn c¸c tµi nguyªn nãi

trªn sao cho viÖc sö dông tµi nguyªn cã hiÖu qu¶ nh−ng tr¸nh ®−îc sù mÊt m¸t d÷

liÖu vµ lµm háng c¸c tËp tin.

Hai dÉn chøng ®iÓn h×nh gióp chóng ra thÊy vai trß cña hÖ ®iÒu hµnh trong

viÖc qu¶n lý tµi nguyªn hÖ thèng sau nµy chóng ra sÏ thÊy viÖc cÊp ph¸t, chia sÎ,

b¶o vÖ tµi nguyªn cña hÖ ®iÒu hµnh lµ mét trong nh÷ng c«ng viÖc khã kh¨n vµ

phøc t¹p nhÊt. HÖ ®iÒu hµnh ®· chi phÝ nhiÒu cho c«ng viÖc nãi trªn ®Ó ®¸t ®−îc

môc tiªu: Trong mäi tr−êng hîp tÊt c¶ c¸c ch−¬ng tr×nh, tiÕn tr×nh nÕu cÇn ®−îc

cÊp ph¸t tµi nguyªn ®Ó ho¹t ®éng th× sím muén nã ®Òu ®−îc cÊp ph¸t vµ ®−îc

®−a vµo tr¹ng th¸i ho¹t ®éng.

1.1.3. C¸c thµnh phÇn cña hÖ ®iÒu hµnh

1.1.3.1. Thµnh phÇn qu¶n lý tiÕn tr×nh.

HÖ ®iÒu hµnh ph¶i cã nhiÖm vô t¹o lËp tiÕn tr×nh vµ ®−a nã vµo danh s¸ch

qu¶n lý tÝªn tr×nh cña hÖ thèng. Khi tiÕn tr×nh kÕt thóc hÖ ®iÒu hµnh ph¶i lo¹i bá

tiÕn tr×nh ra lhái danh s¸c qu¶n lý tiÕn tr×nh cña hÖ thèng.

HÖ ®iÒu hµnh ph¶i cung cÊp ®Çy ®ñ tµi nguyªn ®Ó tiÕn tr×nh ®i vµo ho¹t ®éng

vµ ph¶i ®¶m b¶o ®ñ tµi nguyªn ®Ó duy tr× sù ho¹t ®éng cña tiÕn tr×nh cho ®Õn khi

tiÕn tr×nh kÕt thóc. Khi tiÕn tr×nh kÕt thóc hÖ ®iÒu hµnh ph¶i thu håi nh÷ng tµi

nguyªn mµ hÖ ®iÒu hµnh ®· cÊp cho tiÕn tr×nh.

-14-

Trong qu¸ tr×nh ho¹t ®éng nÕu v× mét lý do nµo ®ã tiÕn tr×nh kh«ng thÓ tiÕp

rôc ho¹t ®éng ®−îc th× hÖ ®iÒu hµnh ph¶i t¹m dõng tiÕn tr×nh thu håi tµi nguyªn

mµ tiÕn tr×nh ®ang chiÕm gi÷, sau ®ã nÕu diÒu kiÖn thuËn lîi th× hÖ ®iÒu hµnh

ph¶i t¸i kÝch ho¹t tiÕn tr×nh ®Ó tiÕn tr×nh tiÕp tôc ho¹t ®éng cho ®Õn khi kÕt thóc.

Trong c¸c hÖ thèng cã nhiÒu tiÕn tr×nh ho¹t ®éng song song hÖ ®iÒu hµnh

ph¶i gi¶i quyÕt vÊn ®Ò tranh chÊp tµi nguyªn gi÷a c¸c tiÕn tr×nh, ®Òu phèi

processor cho c¸c tiÕn tr×nh, gióp c¸c tiÕn tr×nh trao ®æi th«ng tin vµ ho¹t ®éng

®ång bé víi nhau, ®¶m b¶o nguyªn t¾c tÊt c¶ c¸c tiÕn tr×nh ®· ®−îc khëi t¹o ph¶i

®−îc thùc hiÖn vµ kÕt thóc ®−îc.

Tãm l¹i, bé phËn qu¶n lý tiÕn tr×nh cña hÖ ®iÒu hµnh ph¶i thùc hiÖn nhøng

nhiÖm vô sau ®©y:

T¹o lËp, huû bá tiÕn tr×nh.

T¹m dõng, t¸i kÝch ho¹t ®éng tiÕn tr×nh.

T¹o c¬ chÕ th«ng tin liªn l¹c gi÷a c¸c tiÕn tr×nh.

T¹o c¬ chÕ ®ång bé ho¸ gi÷a c¸c tiÕn tr×nh.

1.1.3.2. Thµnh phÇn qu¶n lý bé nhí.

Bé nhí chÝnh lµ mét trong nh÷ng tµi nguyªn quan träng cña hÖ thèng, ®©y lµ

thiÕt bÞ l−u tr÷ duy nhÊt mµ CPU cã thÓ truy xuÊt trùc tiÕp ®−îc.

C¸c ch−¬ng tr×nh cña ng−êi sö dông muèn thùc hiÖn ®−îc bëi CPU th×

trwocs hÕt nã ph¶i ®−îc hÖ ®iÒu hµnh n¹p vµo bé nhí chÝnh, chuyÓn ®æi c¸c ®Þa

chØ sö dông trong ch−¬ng tr×nh thµnh nh÷ng ®Þa chØ mµ CPU cã thÓ truy xuÊt

®−îc.

Khi ch−¬ng tr×nh, tiÕn tr×nh cã yªu cÇu ®−îc n¹p vµo bé nhí th× hÖ ®iÒu

hµnh ph¶i cÊp ph¸t kh«ng gian nhí cho nã. Khi ch−¬ng tr×nh, tiÕn tr×nh kÕt thóc

th× hÖ ®iÒu hµnh ph¶i thi håi l¹i kh«ng gian nhí ®· cÊp ph¸t cho ch−¬ng tr×nh,

tiÕn tr×nh tr−íc ®ã.

-15-

Trong c¸c hÖ thèng ®a ch−¬ng hay ®a tiÕn tr×nh, trong bé nhí tån t¹i nhiÒu

ch−¬ng tr×nh/ nhiÒu tiÕn tr×nh, hÖ ®iÒu hµnh ph¶i thùc hiÖn nhiÖm vô b¶o vÖ c¸c

vïng nhí ®· cÊp ph¸t cho c¸c ch−¬ng tr×nh/tiÕn tr×nh, tr¸nh sù vi ph¹m trªn c¸c

vïng nhí cña nhau.

Tãm l¹i, bé phËn qu¶n lý bé nhí chÝnh cña hÖ ®iÒu hµnh thùc hiÖn nh÷ng

nhiÖm vô sau:

CÊp ph¸t, thu håi vïng nhí.

Chi nhËn tr¹ng th¸i bé nhí.

B¶o vÖ bé nhí.

QuyÕt ®Þnh tiÕn tr×nh nµo ®−îc n¹p vµo bé nhí.

1.1.3.3. Thµnh phÇn qu¶n lý vµo ra.

Mét trong nh÷ng môc tiªu cña hÖ ®iÒu hµnh lµ gióp ng−êi sö dông khai thøc

hÖ thèng m¸y tÝnh dÔ dµng vµ hiÖu qu¶, do ®ã c¸c thao t¸c trao ®æi th«ng tin trªn

thiÕt bÞ xuÊt / nhËp ph¶i trong suèt ®èi víi ng−êi sö dông.

§Ó thùc hiÖn ®−îc ®iÒu nµy hÖ ®iÒu hµnh ph¶i tån t¹i mét bé phËn ®iÒu

khiÓn thiÕt bÞ, bé phËn nµy phèi hîp cïng CPU ®Ó qu¶n lý sù ho¹t ®éng vµ trao

®æi th«ng tin gi÷a hÖ thãng, ch−¬ng tr×nh ng−êi sö dông vµ ng−êi sö dông víi c¸c

thiÕt bÞ xu©ts/nhËp.

Bé phËn ®iÒu khiÓn thiÕt bÞ thùc hiÖn nh÷ng nhiÖm vô sau:

Gëi m· lÖnh ®iÒu khiÓn ®Õn thiÕt bÞ: HÖ ®iÒu hµnh ®iÒu khiÓn c¸c thiÕt bÞ

b»ng c¸c m· ®iÒu khiÓn, do ®ã tr−íc khi b¾t ®Çu mét qu¸ tr×nh trao ®æi d÷ liÖu

víi thiÕt bÞ th× hÖ ®iÒu hµnh ph¶i gëi m· ®iÓu khiÓn ®Õn thiÕt bÞ.

TiÕp nhËn yªu cÇn ng¾t (Interrupt) tõ c¸c thiÕt bÞ khi cÇn trao ®æi víi hÖ

thèng khi nã ph¸t ra mét tÝn hiÖu yªu cÇu ng¾t, hÖ ®iÒu hµnh tiÕp nhËn yªu cÇu

ng¾t tõ c¸c thiÕt bÞ, xem xÕt vµ thùc hiÖn mét thñ tôc ®Ó ®¸p øng yªu cÇu c¸c

thiÕt bÞ.

-16-

Ph¸t hiÖn vµ xö lý lçi: qu¸ tr×nh trao ®æi d÷ liÖu th−êng x¶y ra c¸c lçi nh−:

thiÕt bÞ vµo/ra ch−a s½n sµng, ®−êng truyÒn háng, vv, do ®ã hÖ ®iÒu hµnh ph¶i t¹o

ra c¸c c¬ chÕ thÝch hîp ®Ó ph¸t hiÖn lçi sím nhÊt vµ kh»c phôc c¸c lçi võa x¶y ra

nÕu cã thÓ.

1.2. Qu¶n lý tiÕn tr×nh

TiÕn tr×nh lµ mét ch−¬ng tr×nh ®ang xö lý, nã së h÷u mét con trá lÖnh, lËp

c¸c thanh ghi vµ c¸c biÕn. §Ó hoµn thµnh nhiÖm vô cña m×nh, c¸c tiÕn tr×nh cã

thÓ cßn yªu cÇu mét sè tµi nguyªn hÖ thèng nh−: CPU, bé nhí vµ c¸c thiÕt bÞ.

1.2.1. C¸c tr¹ng th¸i cña mét tiÕn tr×nh

Tr¹ng th¸i cña tiÕn tr×nh t¹i mçi thêi ®iÓm ®−îc x¸c ®Þnh bëi ho¹t ®éng

hiÖn thêi cña tiÕn tr×nh t¹i thêi ®iÓm ®ã. Trong suèt kho¶ng thêi gian tån t¹i trong

hÖ thèng, mét tiÕn tr×nh cã thÓ thay ®æi tr¹ng th¸i do rÊt nhiÒu nguyªn nh©n nh−:

Chê ®îi sù kiÖn nµo ®ã x¶y ra, ®îi mét thao t¸c vµo/ra hoµn tÊt, hÕt thêi gian xö

lý...

T¹i mçi thêi ®iÓm, tiÕn tr×nh cã thÓ nhËn mét trong c¸c tr¹ng th¸i sau:

- Khëi t¹o (new): TiÕn tr×nh ®ang ®−îc t¹o lËp.

- S½n sµng (ready): TiÕn tr×nh chê ®−îc cÊp ph¸t CPU ®Ó xö lý.

- Thùc hiÖn (runing): TiÕn tr×nh ®−îc xö lý.

- §îi (waiting): TiÕn tr×nh ph¶i dõng v× thiÕu tµi nguyªn hoÆc chê mét sù

kiÖn nµo ®ã.

- KÕt thóc (halt): TiÕn tr×nh ®· hoµn tÊt c«ng viÖc xö lý.

C¸c tr¹ng th¸i cña tiÕn tr×nh cã thÓ ®−îc biÓu diÔn qua s¬ ®å (h×nh 1.1)

-17-

Halt

Runing

Ready

New

Waiting

H×nh 1.1. C¸c tr¹ng th¸i cña mét tiÕn tr×nh

HÖ ®iÒu hµnh qu¶n lý ho¹t ®éng cña c¸c tiÕn tr×nh trong hÖ thèng th«ng

qua khèi m« t¶ tiÕn tr×nh (process control block - PCB). Khèi m« t¶ tiÕn tr×nh bao

gåm c¸c thµnh phÇn:

- Sè thø tù cña tiÕn tr×nh

- Con trá tr¹ng th¸i cña tiÕn tr×nh (cho biÕt tr¹ng th¸i hiÖn t¹i cña tiÕn

tr×nh).

- Vïng nhí l−u tr÷ gi¸ trÞ c¸c thanh ghi mµ tiÕn tr×nh ®ang sö dông.

- Th«ng tin vÒ tµi nguyªn tiÕn tr×nh ®ang sö dông hoÆc ®−îc phÐp sö dông.

1.2.2. Kh¸i niÖm vÒ tµi nguyªn “g¨ng” vµ ®o¹n tíi h¹n

Chóng ta cïng xem thuËt to¸n sau:

Type ltem = ...;

Var Buffer: array [0..n-1] of ltem;

In. Out: 0..n-1

Counter: 0..n

Begin

(TiÕn tr×nh P)

Repeat

...

-18-

S¶n xuÊt th«ng tin vµ chøa trong NextP;

...

While Counter = n do Skip;

Buffer [In]:=NextP;

In:= In + 1 mod n;

Until false;

(TiÕn tr×nh C)

Repeat

While Counter = 0 do Skip;

NextC:= Buffer [Out];

Out:= Out + 1 mod n;

...

LÊy th«ng tin trong chøa trong NextC

...

Until false;

End;

NhËn xÐt: V× hai tiÕn tr×nh P vµ C song hµnh nªn cã thÓ x¶y ra tr−êng hîp

trong cïng 1 thêi ®iÓm, tiÕn tr×nh P t¨ng biÕn Counter lªn 1 (Counter:= Counter

+ 1) cßn tiÕn tr×nh C l¹i gi¶m biÕn Counter ®i 1 (Counter:= Counter – 1) dÉn tíi

kÕt qu¶ sai. Nh− vËy biÕn Counter trong tr−êng hîp nµy ®−îc gäi lµ tµi nguyªn

“g¨ng”. §o¹n tr×nh sö dông biÕn Counter gäi lµ ®o¹n tíi h¹n.

§Þnh nghÜa:

- C¸c tµi nguyªn logic vµ vËt lý ph©n bæ cho c¸c tiÕn tr×nh song hµnh lµ tµi

nguyªn “g¨ng”.

C¸c ®o¹n tr×nh sö dông tµi nguyªn g¨ng gäi lµ ®o¹n tíi h¹n (Critical

Section).

-19-

1.2.3. HiÖn t−îng bÕ t¾c

1.2.3.1. Kh¸i niÖm vÒ bÕ t¾c

Gi¶ sö cã hai tiÕn tr×nh P₁vµ P song hµnh sö dông c¸c tµi nguyªn r₁vµ r,

®−îc ®iÒu khiÓn bëi hai ®Ìn hiÖu S₁vµ S. T¹i mçi thêi ®iÓm, mçi tµi nguyªn chØ

phôc vô cho sù ho¹t ®éng cña mét tiÕn tr×nh. XÐt tr¹ng th¸i:

B¶ng 1.1. Tr¹ng th¸i cña c¸c tiÕn tr×nh

P₁

Thêi ®iÓm

P₂

Wait (S₂)

...

Wait (S₁)

...

t₁

t₂

t₃

t₄

Wait (S₂)

...

Wait (S₁)

NhËn xÐt: T¹i vÞ trÝ trªn, sau thêi ®iÓm t₃, tiÕn tr×nh P₁r¬i vµo tr¹ng th¸i

chê tµi nguyªn r₂®ang ®−îc P₂sö dông; Sau thêi ®iÓm t₄, tiÕn tr×nh P₂r¬i vµo

tr¹ng th¸i chê tµi nguyªn r₁®ang ®−îc tiÕn tr×nh P₁sö dông vµ b¾t ®Çu tõ ®©y, c¶

hai tiÕn tr×nh r¬i vµo tr¹ng th¸i chê ®îi v« h¹n vÒ hÖ thèng gÆp bÕ t¾c.

Nh− vËy bÕ t¾c lµ tr¹ng th¸i khi hai hoÆc nhiÒu tiÕn tr×nh cïng chê ®îi mét

sè sù kiÖn nµo ®ã vµ nÕu kh«ng cã t¸c ®éng ®Æc biÖt tõ bªn ngoµi th× sù chê ®îi

®ã lµ v« h¹n.

1.2.3.2. §iÒu kiÖn x¶y ra bÕ t¾c trong hÖ thèng.

HiÖn t−îng bÕ t¾c x¶y ra khi vµ chØ khi trong hÖ thèng tån t¹i 4 ®iÒu kiÖn:

- Cã tµi nguyªn g¨ng

- Cã hiÖn t−îng gi÷ vµ ®îi, cã mét tiÕn tr×nh ®ang gi÷ mét sè tµi nguyªn vµ

®îi tµi nguyªn bæ sung ®ang ®−îc gi÷ bëi c¸c tiÕn tr×nh kh¸c.

- Kh«ng cã hÖ thèng ph©n phèi l¹i tµi nguyªn: ViÖc sö dông tµi nguyªn

kh«ng bÞ ng¾t.

-20-

- Cã hiÖn t−îng chê ®îi vßng trßn.

1.2.3.3. C¸c møc phßng tr¸nh bÕ t¾c

§Ó tr¸nh hiÖn t−îng bÕ t¾c, th«ng th−êng hÖ thèng ¸p dông ba møc:

- Ng¨n chÆn: ¸p dông c¸c biÖn ph¸p ®Ó hÖ thèng r¬i vµo tr¹ng th¸i bÕ t¾c.

- Dù b¸o vµ tr¸nh bÕ t¾c: ¸p dông c¸c biÖn ph¸p ®Ó kiÓm tra c¸c tiÕn tr×nh

xem cã bÞ r¬i vµo tr¹ng th¸i bÕ t¾c hay kh«ng. NÕu cã th× th«ng b¸o tr−íc khi bÕ

t¾c x¶y ra.

- NhËn biÕt vµ kh¾c phôc: T×m c¸ch ph¸t hiÖn vµ gi¶i quyÕt.

1.3. LËp lÞch cho CPU

1.3.1. Kh¸i niÖm giê CPU

CPU lµ mét lo¹i tµi nguyªn quan träng cña m¸y tÝnh. Mäi tiÕn tr×nh muèn

ho¹t ®éng ®−îc ®Òu ph¶i cã sù phôc vô cña CPU (®Ó xö lý, tÝnh to¸n...). Thêi gian

mµ CPU phôc vô cho tiÕn tr×nh ho¹t ®éng ®−îc gäi lµ giê CPU.

T¹i mçi thêi ®iÓm nhÊt ®Þnh, chØ cã mét tiÕn tr×nh ®−îc ph©n phèi giê CPU

®Ó ho¹t ®éng (thùc hiÖn c¸c lÖnh cña m×nh).

1.3.2. C¸c tr¹ng th¸i cña tiÕn tr×nh liªn quan ®Õn giê CPU

Trong chÕ ®é ®a ch−¬ng tr×nh, cã ba tr¹ng th¸i cña tiÕn tr×nh liªn quan mËt

thiÕt ®Õn giê CPU bao gåm:

Runing

Ready

Waiting

H×nh 1.2. C¸c tr¹ng th¸i cña tiÕn tr×nh liªn quan ®Õn giê CPU

-21-

- S½n sµng (ready): Lµ tr¹ng th¸i mµ tiÕn tr×nh ®−îc ph©n phèi ®Çy ®ñ mäi

tµi nguyªn cÇn thiÕt vµ ®ang chê giê CPU.

- Thùc hiÖn (running): Lµ tr¹ng th¸i mµ tiÕn tr×nh ®−îc ph©n phèi ®Çy ®ñ

mäi tµi nguyªn cÇn thiÕt vµ giê CPU.

- §îi (waiting): Lµ tr¹ng th¸i tiÕn tr×nh kh«ng thùc hiÖn ®−îc v× thiÕu mét

vµi ®iÒu kiÖn nµo ®ã (®îi d÷ liÖu vµo/ra, ®îi tµi nguyªn bæ sung...). Khi sù kiÖn

mµ nã chê ®îi xuÊt hiÖn, tiÕn tr×nh sÏ quay trë l¹i tr¹ng th¸i s½n sµng.

Nh− vËy, trong suèt thêi gian tån t¹i cña m×nh, c¸c tiÕn tr×nh sÏ tu©n thñ

theo s¬ ®å thùc hiÖn sau:

Sö dông CPU

KÕt thóc

Sö dông CPU

B¾t ®Çu

§îi I/O

H×nh 1.3. S¬ ®å thùc hiÖn tiÕn tr×nh

Mét tiÕn tr×nh ®ang trong tr¹ng th¸i thùc hiÖn, nã cã thÓ rêi khái tr¹ng th¸i

bëi mét trong ba lý do:

- TiÕn tr×nh ®· hoµn thµnh c«ng viÖc vµ chuyÓn sang tr¹ng th¸i kÕt thóc, nã

tr¶ l¹i giê CPU cho hÖ thèng.

- TiÕn tr×nh tù ng¾t: Khi tiÕn tr×nh chê ®îi mét sù kiÖn nµo ®ã, tiÕn tr×nh sÏ

®−îc chuyÓn sang tr¹ng th¸i thùc hiÖn khi xuÊt hiÖn sù kiÖn nã ®ang chê.

- TiÕn tr×nh sö dông hÕt giê CPU dµnh cho nã, khi ®ã nã sÏ ®−îc chuyÓn

sang tr¹ng th¸i s½n sµng.

ViÖc chuyÓn tiÕn tr×nh sang tr¹ng th¸i s½n sµng vÒ b¶n chÊt lµ thùc hiÖn

viÖc ph©n phèi l¹i giê CPU.

-22-

1.3.3. LËp lÞch cho CPU

1.3.3.1. Kh¸i niÖm

§Ó ®iÒu khiÓn tiÕn tr×nh ë nhiÒu tr¹ng th¸i kh¸c, hÖ thèng th−êng tæ chøc

c¸c tõ tr¹ng th¸i (thùc chÊt lµ c¸c khèi ®iÒu khiÓn tiÕn tr×nh) ®Ó ghi nhËn t×nh

tr¹ng sö dông tµi nguyªn vµ tr¹ng th¸i tiÕn tr×nh. C¸c tõ tr¹ng th¸i ®−îc tæ chøc

theo kiÓu ®îi nh− sau:

Ready queue

CPU

I/O queue

I/O

I/O queue

M

I/O queue

I/O

H×nh 1.4. S¬ ®å tæ chøc hµng ®îi c¸c tiÕn tr×nh

Nh− vËy, lËp lÞch cho CPU cã nghÜa lµ tæ chøc mét hµng ®îi c¸c tiÕn tr×nh

s½n sµng ®Ó ph©n phèi giê CPU cho chóng dùa trªn ®é −u tiªn cña c¸c tiÕn tr×nh

sao cho hiÖu suÊt sö dông CPU lµ tèi −u nhÊt.

Mçi tiÕn tr×nh ë tr¹ng th¸i s½n sµng ®−îc g¾n víi mét thø tù −u tiªn. Thø tù

−u tiªn nµy ®−îc x¸c ®Þnh dùa vµo c¸c yÕu tè nh−: Thêi ®iÓm h×nh thµnh tiÕn

tr×nh, thêi gian thùc hiÖn tiÕn tr×nh, thêi gian kÕt thóc tiÕn tr×nh...

-23-

1.3.3.2. Mét sè thuËt to¸n lËp lÞch cho CPU

1. First Come First Served (FCFS)

Trong thuËt to¸n nµy, ®é −u tiªn phôc vô tiÕn tr×nh c¨n cø vµo thêi ®iÓm

h×nh thµnh tiÕn tr×nh. Hµng ®îi c¸c tiÕn tr×nh ®−îc tæ chøc theo kiÓu FIFO. Mäi

tiÕn tr×nh ®Òu ®−îc phôc vô theo tr×nh tù xuÊt hiÖn cho ®Õn khi kÕt thóc hoÆc bÞ

ng¾t.

2. Shortest Job First (SJF).

ThuËt to¸n SJF x¸c ®Þnh thø tù −u tiªn thùc hiÖn tiÕn tr×nh dùa vµo tæng

thêi gian thùc hiÖn tiÕn tr×nh. TiÕn tr×nh nµo cã tæng thêi gian thùc hiÖn ng¾n sÏ

®−îc −u tiªn phôc vô tr−íc.

3. Shortest Remain Time (SRT)

T−¬ng tù nh− SJF nh−ng trong thuËt to¸n nµy, ®é −u tiªn thùc hiÖn c¸c tiÕn

tr×nh dùa vµo thêi gian cÇn thiÕt ®Ó thùc hiÖn nèt tiÕn tr×nh (b»ng tæng thêi gian =

thêi gian ®· thùc hiÖn). Nh− vËy trong thuËt to¸n nµy cÇn ph¶i th−êng xuyªn cËp

giê CPU còng ph¶i ®−îc ¸p dông nÕu kh«ng sÏ lµm mÊt tÝnh −u viÖt cña thuËt

to¸n.

4. Round Robin (RR)

Trong thuËt to¸n nµy, hÖ thèng quy ®Þnh mét l−îng tö thêi gian (time

tr×nh ch−a kÕt thóc hoÆc kh«ng r¬i vµo tr¹ng th¸i ®îi th× nã ®−îc chuyÓn vÒ cuèi

hµng ®îi.

Hµng ®îi c¸c tiÕn tr×nh ®−îc tæ chøc theo kiÓu vßng trßn vµ c¸c tiÕn tr×nh

lu«n lu«n ®¶m b¶o ®−îc phôc vô. Khi cã tiÕn tr×nh míi ph¸t sinh, nã sÏ ®−îc ®−a

-24-

vµo hµng ®îi vßng trßn vµ ®−îc ®Æt ë vÞ trÝ phôc vô ngay. C¸c tiÕn tr×nh dï ng¾n

hay dµi ®Òu cã ®é −u tiªn phôc vô nh− nhau.

Trªn thùc tÕ, ®Ó ®¶m b¶o ®é −u tiªn cho c¸c tiÕn tr×nh dµi, hÖ thèng sÏ

phôc vô tiÕn tr×nh t¹i mçi líp kh¸c nhau (gi¶ sö ë líp thø i, tiÕn tr×nh ®−îc phôc

vô k lÇn vµ mçi lÇn víi thêi gian q_i).

hoÆc kh«ng bÞ ng¾t th× nã ®−îc chuyÓn sang líp thø i+1 (víi k_i+1vµ q_i+1lín h¬n).

L−îng tõ thêi gian sÏ t¨ng dÇn cho ®Õn khi tiÕn tr×nh r¬i vµo líp ngoµi cïng (líp

m). ë ®ã nã sÏ ®−îc phôc vô víi l−îng tö q_mkh«ng ®æi. Nh− vËy thø tù −u tiªn

cña c¸c tiÕn tr×nh sÏ t¨ng dÇn theo thêi gian xÕp hµng ®îi.

¦u ®iÓm cña ph−¬ng ph¸p phôc vô ®ång møc theo líp sÏ cho phÐp hÖ

lín cho c¸c tiÕn tr×nh dµi.

chê ®îi trung b×nh cña Round Robin cã thÓ lín h¬n so víi FCFS.

quantum) thÝch hîp. NÕu chän gi¸ trÞ time quantum lín th× viÖc bæ sung tiÕn tr×nh

míi hoÆc kÝch ho¹t tiÕn tr×nh bÞ ng¾t sÏ lµm t¨ng thêi gian chê ®îi trung b×nh

nh−ng ng−îc l¹i nÕu chän gi¸ trÞ time quantum nhá th× nã sÏ lµm cho c¸c tiÕn

tr×nh ph¶i liªn tôc chuyÓn tr¹ng th¸i dÉn ®Õn gi¶m hÖ sè h÷u Ých cña CPU.

Th«ng th−êng gi¸ trÞ time quantum ®−îc chän theo c«ng thøc: q = t/n hoÆc

q=t/n – s. Trong ®ã: t lµ thêi gian khèng chÕ tr−íc; n lµ sè tiÕn tr×nh; s thêi gian

chuyÓn tõ tiÕn tr×nh nµy sang tiÕn tr×nh kh¸c.

VÝ dô: Cho d·y tiÕn tr×nh víi thêi gian thùc hiÖn t−¬ng øng theo b¶ng 1.2

vµ time quantum cã gi¸ trÞ q= 4

-25-

B¶ng 1.2. Thêi gian thùc hiÖn cña c¸c tiÕn tr×nh

TiÕn tr×nh

T thùc hiÖn

P1

P2

P3

24

3

S¬ ®å Grant biÓu thÞ thø tù thùc hiÖn c¸c tiÕn tr×nh nh− h×nh 1.5.

P1 P2 P3 P1 P1 P1 P1

P1

0

4

7

10

14

18

22

26

30

H×nh 1.5. S¬ ®å Grant

Theo s¬ ®å nµy chóng ta thÊy thêi chê ®îi cña c¸c tiÕn tr×nh nh− b¶ng 1.2.

B¶ng 1.3. Thêi gian chê cña c¸c tiÕn tr×nh

Processes

P1

T thùc hiÖn

T ®îi

24

3

6

1

P3

P1

3

7

Tæng

30

17

DÉn ®Õn thêi gian chê ®îi trung b×nh cña c¸c tiÕn tr×nh lµ 17/3 = 5.66

1.4. Qu¶n lý bé nhí

1.4.1. Yªu cÇu ph¶i qu¶n lý bé nhí

Bé nhí lµ thiÕt bÞ l−u tr÷ duy nhÊt mµ th«ng qua ®ã CPU cã thÓ trao ®æi

th«ng tin víi m«i tr−êng bªn ngoµi. Do vËy, nhu cÇu tæ chøc, qu¶n lý bé nhí lµ

mét trong nh÷ng nhiÖm vô c¬ b¶n hµng ®Çu cña hÖ ®iÒu hµnh. Bé nhí ®−îc tæ

chøc nh− m¶ng mét chiÒu c¸c tõ nhí (word), mçi tõ nhí cã mét ®Þa chØ. ViÖc

trao ®æi th«ng tin víi m«i tr−êng bªn ngoµi ®−îc thùc hiÖn th«ng qua c¸c thao t¸c

®äc/ghi d÷ liÖu vµo mét ®Þa chØ cô thÓ nµo ®ã trong bé nhí.

-26-

HÖ ®iÒu hµnh chÞu tr¸ch nhiÖm cÊp ph¸t kh«ng gian nhí cho c¸c tiÕn tr×nh

khi cã yªu cÇu. §Ó thùc hiÖn tèt nhiÖm vô nµy, hÖ ®iÒu hµnh cÇn ph¶i xem xÐt

mét sè khÝa c¹nh sau:

- Sù t−¬ng øng gi÷a ®Þa chØ logic vµ ®Þa chØ vËt lý: Lµm thÕ nµo ®Ó chuyÓn

®æi mét ®Þa chØ logic thµnh mét ®Þa chØ vËt lý.

tr×nh ho¹t ®éng, thu håi kh«ng gian nhí khi tiÕn tr×nh kÕt thóc, qu¶n lý ®−îc

kh«ng gian nhí tù do.

- Chia sÎ th«ng tin: Cho phÐp c¸c tiÕn tr×nh ®ang ho¹t ®éng trong bé nhí

cã thÓ chia sÎ th«ng tin víi nhau.

cÊp ph¸t cho c¸c tiÕn tr×nh kh¸c.

1.4.2. C¸c s¬ ®å qu¶n lý bé nhí

Bé nhí ®−îc chia thµnh n phÇn kh«ng nhÊt thiÕt ph¶i b»ng nhau vµ mçi phÇn

thÓ n¹p ®−îc mét ch−¬ng tr×nh vµ tæ chøc thùc hiÖn mét c¸ch ®ång thêi. Nh− vËy

hiÖn mét c¸ch ®ång thêi (n ®−îc gäi lµ hÖ sè song song cña hÖ thèng).

Trong s¬ ®å nµy, bé nhí cã mét b¶ng qu¶n lý kh«ng gian nhí tù do thèng

nhÊt. Khi thùc hiÖn ch−¬ng tr×nh, hÖ thèng dùa vµo kÝch th−íc ch−¬ng tr×nh ®Ó

qu¶n lý riªng. Khi c¸c ch−¬ng tr×nh kÕt thóc, bé nhí giµnh cho nã sÏ bÞ thu håi.

-27-

1.4.2.3. S¬ ®å ho¸n ®æi (swapping)

S¬ ®å ho¸n ®æi dùa trªn nguyªn t¾c néi dung ch−¬ng tr×nh ë tr¹ng th¸i chê

®îi trong mét kho¶ng thêi gian dµi sÏ ®−îc t¹m thêi chuyÓn ra bé nhí ngoµi

(swap out) ®Ó gi¶i phãng vïng nhí cÊp ph¸t cho ch−¬ng tr×nh kh¸c ho¹t ®éng.

Khi ch−¬ng tr×nh kÕt thóc tr¹ng th¸i chê nã sÏ ®−îc n¹p trë l¹i bé nhí trong

(swap in) ®Ó tiÕp tôc thùc hiÖn.

-28-

Ch−¬ng 2 - Vi ®iÒu khiÓn vµ ng«n ng÷ lËp tr×nh

cho vi ®iÒu khiÓn

2.1. Vi ®iÒu khiÓn

2.1.1. Vi xö lý vµ vi ®iÒu khiÓn.

Bé vi xö lý ®· cã lÞch sö ra ®êi tõ 1971 khi Intel giíi thiÖu bé 8080 dïng

cho m¸y tÝnh ®¬n board. KÓ tõ khi ra ®êi, qua nhiÒu thÕ hÖ, cã nhiÒu c¶i tiÕn

nh−ng lÜnh vùc cña c¸c bé vi xö lý vÉn lµ c¸c hÖ thèng m¸y tÝnh. Trong hÖ thèng

m¸y tÝnh, bé vi xö lý cïng víi bé nhí, c¸c thiÕt bÞ vµo/ra...,hîp thµnh mét hÖ

thèng cã kh¶ n¨ng xö lý, ®iÒu khiÓn, l−u tr÷... cùc m¹nh.

Mét hÖ thèng m¸y tÝnh nÕu dïng cho mét øng dông lín yªu cÇu xö lý

nhanh, l−u tr÷ lín... th× kh«ng cã vÊn ®Ó g× ®Ó bµn. Tuy nhiªn nÕu mang hÖ thèng

nµy vµo dïng cho c¸c øng dông nhá th× l¹i trë thµnh l·ng phÝ. Tõ thùc tÕ nµy c¸c

nhµ s¶n xuÊt ®· nghiªn cøu vµ ®−a ra c¸c hÖ m¸y tÝnh nhá víi mét bé xö lý nhá,

mét bé nhí ch−¬ng tr×nh vµ d÷ liÖu nhá, mét sè c¸c thµnh phÇn vµo ra c¬ b¶n.

®iÒu khiÓn.

xem xÐt trªn 2 ph−¬ng diÖn: KiÕn tróc phÇn cøng vµ lÜnh vùc øng dông. PhÇn

cøng cña mét bé vi ®iÒu khiÓn lµ mét bé vi xö lý, bé nhí, c¸c thiÕt bÞ vµo/ra. Vi

®iÒu khiÓn cã ®ñ nh÷ng thµnh phÇn c¬ b¶n cña mét hÖ m¸y tÝnh nªn bé vi ®iÒu

khiÓn cã thÓ ho¹t ®éng ®éc lËp ®−îc cßn vi xö lý th× kh«ng. XuÊt ph¸t tõ nh÷ng

®Æc tr−ng võa nªu nªn bé vi ®iÒu khiÓn ®−îc t×m thÊy trong c¸c øng dông nhá cßn

vi xö lý n»m trong c¸c hÖ thèng m¸y tÝnh.

AT89S52 lµ bé vi ®iÒu khiÓn 8 bit, ®−îc chÕ t¹o bëi h·ng ATMEL theo kiÕn

tróc cña 8051.

-29-

Intermal Devices

Oscilla-

tior

Memory

I/O devices

Timer0

Timer1

Timer2

(16 bit)

RAM

256

byte

ROM

8Kb

UART

Interrupt

Controller

CPU

System Bus

Memory

I/O devices

....

ROM

64Kb

RAM

64Kb

....

...

Extermal Devices

H×nh 2.1. S¬ ®å khèi cña bé vi ®iÒu khiÓn AT89S52

Trªn h×nh 2.1 lµ s¬ ®å khèi cña bé vi ®iÒu khiÓn nµy, theo ®ã bé vi ®iÒu

khiÓn cã ®Çy ®ñ c¸c phÇn cøng cÇn thiÕt cho mét hÖ ®iÒu hµnh thêi gian thùc nh−

thùc hiÖn chuyÓn m¹ch gi÷a c¸c tiÕn tr×nh, khèi vµo ra ®Ó thùc hiÖn c¸c thao t¸c

trong c¸c tiÕn tr×nh...Nh− vËy chØ cÇn mét bé vi ®iÒu khiÓn AT89S52víi gi¸ thµnh

còng chÝnh lµ lý do ®Ó t¸c gi¶ ®Ò tµi chän nghiªn cøu vi ®iÒu khiÓn vµ øng dông

vµo hÖ thèng thêi gian thùc.

-30-

2.1.2. Tæ chøc bé nhí cña vi ®iÒu khiÓn.

AT89S52 coù boä nhôù theo caáu truùc Harvard: coù nhöõng vuøng cho boä nhôù

rieâng bieät cho chöông trình vaø döõ lieäu. Nhö ñaõ noùi ôû treân, caû boä nhôù chöông

trình vaø döõ lieäu coù saün ôû treân chip tuy nhieân dung löôïng cuûa caùc boä nhôù treân

chip laø haïn cheá. Khi thieát keá caùc öùng duïng ñoøi hoûi boä nhôù lôùn ngöôøi ta coù theå

duøng boä nhôù ngoaøi vôùi dung löôïng leân tôùi 64 Kbytes cho boä nhôù chöông trình

vaø cho 64 Kbytes boä nhôù döõ lieäu (hình 2.2).

FFFFH

Boä nhôù

chöông

trình

Boä nhôù

döõ lieäu

(64Kb)

1FFFH

(64Kb)

Boä nhôù

chöông

trình

00FFH

0000H

(8Kb)

256

bytes

Boä nhôù trong

Boä nhôù ngoaøi

H×nh 2.2. Tæ chøc bé nhí cña vi ®iÒu khiÓn

2.1.2.1. Bé nhí ch−¬ng tr×nh.

møc logic cao (+5V), bé vi ®iÒu khiÓn sÏ thùc hiÖn ch−¬ng tr×nh trong Rom néi

b¾t dÇu tõ ®Þa chØ 0000H. Sè lÇn lËp tr×nh (ghi) cho bé nhí nµy lµ kho¶ng 1000

lÇn.

ch−¬ng tr×nh ë bé nhí ch−¬ng tr×nh ngoµi (EPPOM ngoµi), tuy nhiªn ®Ó cã ®−îc