Tài liệu Luận văn thạc sĩ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 -42.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 Ch÷ viÕt t¾t Ch÷ ®Çy ®ñ 1 FCFS First Come First Served 2 FIFO First In First Out 3 LIFO Last In First Out 4 MCS Micro Controller System 5 OS 6 RTOS 7 RR Round Robbin 8 SJF Shortest Job First 9 SRT Shortest Remain Time 10 uC Operating System Real Time Operating System Micro Controller -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 -8H×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 -10x· 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 -13chÊ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. -14Trong 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 ®ã. -15Trong 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Þ. -16Ph¸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- Runing Ready New Halt 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: ltem = ...; Type Var Buffer: array [0..n-1] of ltem; In. Out: 0..n-1 Counter: 0..n Begin (TiÕn tr×nh P) Repeat ... -18S¶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). -191.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 P1 vµ P song hµnh sö dông c¸c tµi nguyªn r1 vµ r, ®−îc ®iÒu khiÓn bëi hai ®Ìn hiÖu S1 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 P1 Thêi ®iÓm P2 Wait (S1) t1 Wait (S2) ... t2 ... Wait (S2) t3 ... t4 Wait (S1) NhËn xÐt: T¹i vÞ trÝ trªn, sau thêi ®iÓm t3, tiÕn tr×nh P1 r¬i vµo tr¹ng th¸i chê tµi nguyªn r2 ®ang ®−îc P2 sö dông; Sau thêi ®iÓm t4, tiÕn tr×nh P2 r¬i vµo tr¹ng th¸i chê tµi nguyªn r1 ®ang ®−îc tiÕn tr×nh P1 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