Giáo trình Kiến trúc hệ điều hành: Phần 1

Chia sẻ: Codon_03 Codon_03 | Ngày: | Loại File: PDF | Số trang:44

Thêm vào BST

Báo xấu

149
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mời các bạn cùng tìm hiểu khái niệm tiến trình; các process song song không đồng bộ; Deadlock - Treo;... được trình bày cụ thể trong "Giáo trình Kiến trúc hệ điều hành: Phần 1". Cùng tìm hiểu để nắm bắt nội dung thông tin tài liệu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Kiến trúc hệ điều hành: Phần 1

GIÁO TRÌNH KIẾN TRÚC HỆ ĐIỀU HÀNH NHÀ XUẤT BẢN KHOA HỌC VÀ KỸ THUẬT HÀ NỘI - 2010
Phần II Chương 3 Khái niệ m Tiế n trình (Process) 3.1 Mởđầu Trong chương này chúng ta sẽxem xét khái niệ m process, một khái niệm quan trọng nhấtđểhình dung vềcông việ c của máy tính ngày nay. Chúng ta sẽtìm hiểu khái niệm vềcác trạ ng thái (rời rạ c) của process và cũng như cách mà process chuyể n từtrạ ng thái này sang trạ ng thái khác cùng với các thao tác cơbản trên process. Khái niệm process lần đầu tiên được các kỹsưthiết kếhệthống MULTICS vào những năm 60. Trong thời kỳđầ u tiên, process được hiể u trong nhiề u trường hợp đồng nghĩ a nhưlà chương trình, bài toán (task) hay là đối tượng được bộxửlý phục vụ,.. Người ta thường dùng đị nh nghĩ a process nhưlà chương trình trong lúc chạ y. 3.2 Trạng thái của p ro cess Trong thời gian tồn tạ i của mình, process tồn tạ i trong các trang thái tách biệ t (rời rạc). Sựđổi từtrạng thái này sang trạng thái khác có thểxảy ra bởi các sựkiệ n khác nhau. Nói rằng process ởtrạ ng thái hoạ t động (running state) nế u nó đang được BXL phục vụ.Còn nế u process đã sẵn sàng đểđược BXL phục vụnhưng đang chờđế n lượt thì proces ởtrạng thái sẵn sàng – ready state. Nói rằ ng process ởtrạng thái bị cản, chặn – blocked state nế u nhưnó đang chờmộtsựkiệ n nào đó (ví dụkế t thúc tác vụvào/ra) đểcó thểtiếp tục hoạ t động. Ngoài 3 trạng thái nói trên còn một số trạng thái khác nhưng tạm thời chúng ta chỉxem xét quan hệgiữa 3 trạ ng thái trên. Đểđơn giả n chúng ta xem xét trường hợp máy tính chỉcó một BXL. Trong hệ thống một BXL, tạ i một thời điểm chỉcó thểcó một process được thực hiện, còn một sốprocess nằm trong trạ ng thái sẵ n sàng (ready) và một sốkhác trong trạ ng thái bịchặ n (blocked). Do đó chúng ta có thểlập một danh sách chứa các process ở trạng thái ready và một danh sách các blocked process. Mỗi ready process nằm trong list thứnhấ t sẽcó mức độưu tiên riêng (priority) của mình- tức là các process đó được sắ p xếp theo thứtựvà process nằm ởđầu danh sách sẽlà process có độưu tiên cao nhấ t và sẽđược BXL thực hiệ n tiế p theo (có nhiề u tiêu chuẩn để gán priority và thay đổi priority). Còn danh sách các blocked process nói chung
không có thứtựvì blocked process sẽđược giả i phóng (unblock) bởi các sựkiệ n mà nó đang chờ. 3.3 Sựchuyển trạng thái của p ro cess Khi có một chương trình – task bắ t đầu được thực hiệ n, hệthống sinh ra một process tương ứng và process đó được đưa vào danh sách các ready process, đơn giản nhấ t là đưa vào cuối danh sách – tức là có mức ưu tiên priority thấp nhất. Process này sẽdị ch chuyển dần lên phía đầu list bởi vì các process trước nó dầ n dần được BXL phục vụ. Khi process nằ m ởđầ u list và BXL được giả i phóng thì process này được BXL phục vụvà lúc đó xả y ra sựthay đổi trạ ng thái của process – chuyển từtrạ ng thái ready sang running. Việ c trao quyề n sửdụng BXL cho process đầ u tiên trong danh sách các ready processes gọi là quá trình dispatching, điều đó được thực hiện bởimodule chương trình nằ m trong OS gọi là dispatcher. Quá trình đổitrạng thái đó có thểbiể u diễ n bằ ng ký hiệ u: dispatch(process name): ready  running Process đang sửdụng BXL được gọi là process đang được thực hiện Running blocking Dispatch Over time Ready Blocked waik up H×nh 3.1 Đểngă n chặn trường hợp vô tình hoặc cốý độc quyền chiế m tài nguyên hệthống của process, hệđiều hành sinh ra một ngắ t cứng đặc biệ t – timer interrupt (ngắt thời gian), xác định khoả ng thời gian lớn nhấ t mà một process được sửdụng BXL liên tục. Nếu nhưsau khoảng thời gian đó, process không tựgiả i phóng BXL thì hệ thống sẽsinh ngắ t, theo đó quyề n điề u khiển được chuyể n lại cho HĐH. Lúc đó HĐH sẽchuyể n process đang được thực hiệ n từtrạng thái running vềtrạng thái, đưa nó vào danh sách các ready process, sau đó đưa process đầ u tiên trong danh sách (process có mức ưu tiên cao nhấ t) vào thực hiện (running state). Các sựbiế n đổinày có thểbiể u diễ n bằng hai thao tác: interval gone (process name): running  ready dispatch (process name) : ready  running
Nế u nhưmộtprocess đang sửdụng BXL (running state) trong quá trình hoạt động của mình thực hiện tác vụvào/ra (I/O) thì nó sẽtựmình giả i phóng BXL (tựmình chuyển vào trạng thái blocked đểchờtác vụvào/ra kếtthúc). Sựchuyển trạng thái này có thểbiểu diễn: blocking (process name): running  blocked. Còn một quá trình thay đổi trạng thái cuối cùng, đó là khi kết thúc tác vụvào/ra (hay nói chung xảy ra một sựkiệ n mà blocked process đang chờ) lúc đó process chuyển từtrạ ng thái blocked sang trạng thái ready – sẵn sàng đểthực hiện tiế p. Quá trình này có thểbiểu diễ n: waikup(npocess name): blocked  ready. Với 3 trạng thái cơbả n trên, chúng ta có 4 khảnă n trạ ng chuyể ng thái của một process đó là: dispatch (process name): ready  running interval gone(process name): running  ready blocking (process name): running  blocked waikup (process name): blocked  ready Chú ý rằng trong 4 khảnăng trên, chỉcó khảnă ng thứ3 là có thểsinh ra bởi chính chương trình người sửdụng, còn lạ i các khảnă ng khác đề u do các đối tượng khác ởbên ngoài process gây ra. 3.4 Process control Block (PCB)- kh ối điều kh iển ti ến trình Đại diệ n cho một process trong HĐH là khối điề u khiển process (PCB). PCB là một cấ u trúc dữliệu chứa những thông tin quan trọng vềprocess và có thểkhác nhau trong các hệthống khác nhau, trong đó thường có:  trạng thái hiệ n tạ i của process  ID (identifier) duy nhấ t cho process  độưu tiên (priority) của process  thông tin vềbộnhớ  thông tin vềcác tài nguyên process đang sửdụng  vùng đểcho các thanh ghi PCB là đối tượng quan trọng, nhờnó HĐH có thểcó được toàn bộthông tin cơbả n nhấ t vềmột process. Khi HĐH chuyển (switch) BXL từđang phục vụprocess này sang phục vụprocess khác, nó dùng vùng cho các thanh ghi trong PCB lưu thông tin giá trịcác thanh ghi của hệthống đểcó thểtiế p tục thực hiện process mỗi khi process đế n lượt được sửdụng BXL.
Tóm lại, PCB là đốitượng chính đạ i diện cho process đối với HĐH. Vì HĐH phải có khảnăng thực hiệ n các thao tác với các PCB khác nhau một cách nhanh chóng, trong nhiều hệthống có những thanh ghi đặ c biệt luôn chỉtới PCB của running process. Và cũng có những lệ nh cài đặt ngay trong phần cứng đểđả m bảo nhanh chóng ghi thông tin trạng thái vào PCB và tiế p theo là nhanh chóng đọc các thông tin đó. 3.5 Các th ao tác với process Hệthống điề u khiển process cầ n có khảnăng thực hiệ n các thao tác với process, trong đó có:  tạo process (create)  huỷprocess (free, destroy)  thay đổiđộưu tiên priority  dừng – block process  kích hoạ t – waikup process  thực hiện process (dispatch) o mộtprocess gồm nhiề Quá trình tạ u thao tác nhỏ:  gán tên cho process  đưa tên process vào danh sách các process của hệthống  xác đị nh mức ưu tiên priority ban đầ u cho process  tạo, nạ p thông tin PCB  phân chia tài nguyên khởiđầu cho process Một process có thểtạ o ra process mới. Process đầ u tiên là parent còn process mới được tạo ra là child process. Đểtạ o process chỉcần một process tức là mỗi child process chỉcó mộtparent còn một parent có thểcó nhiề u child. Các quan hệđó tạo n trúc process ra kiế A B C D E F H×nh 3.2
Xoá một process là loạ i bỏnó khỏihệthống. Khi đó các tài nguyên được phân chia cho process sẽđược giải phóng, trảlạ i cho HĐH, tên của process được xoá khỏitất cảcác danh sách của hệthống, còn PCB cũng được giảiphóng. Một suspended process (bịhoãn, dừng) là process không tiếp tục được thực hiệ n đế n khi có một process khác kích hoạ t nó. Suspending (tạm dừng) là một thao tác quan trọng được sửdụng trong nhiều hệthống với các cách cài đặ t, thực hiệ n khác nhau. Suspending thường chỉdiễ n ra trong khoả ng thời gian ngắn. Ví dụHĐH phải suspend một sốprocess (không phải luôn là tấ t cả) trong thời gian ngắn khi hệ thống quá tả i,.. Trong trường hợp process bịdừng trong thời gian dài hơn thì các tài nguyên của nó phả i được giải phóng trảlại cho HĐH. Việ c một loạ i tài nguyên có cầ n giải phóng hay không còn phụthuộc vào kiể u của nó. Ví dụbộnhớcầ n được giả i phóng ngay, còn thiết bịvào ra có thểvẫ n thuộc quyề n sửdụng process trong trường hợp process bịsuspend trong thời gian ngắ n còn sẽđược giải phóng khi thờigian suspend dài hay không xác đị nh. t là thao tác chuẩn bịđểprocess có thểtiế Quá trình activate – kích hoạ p tục thực hiện từđúng trạng thái mà nó bịdừng trước đó. Quá trình huỷbỏmột process sẽkhá phức tạ p nếu nó là parent process. Trong một sốhệthống thì các children process sẽtựđộng bịhuỷbỏtheo, còn trong một sốhệ thống khác thì children process vẫ n tồn tạ i (độc lập vớiparent process). Sựthay đổi priority process thường đơn giả n là thay đổi giá trịpriority trong PCB bởi HĐH. 3.6 Suspend ing and Activating - d ừn g và kích h oạt Chúng ta đã biế t các khái niệ m suspend and activate. Các thao tác này khá quan trọng do các lý do:  nếu hệthống hoạt động không ổn đị nh có dấu hiệ u trục trặc thì các process đang diễ n ra cầ n suspend đểlạiđược activate sau khi sửa lỗi.  Người sửdụng (lậ p trình viên) có thểcầ n tạ m dừng (không phả i huỷbỏ) process đểkiể m tra kếtquảtrung gian xem chương trình có hoạ t động đúng hay không.  Mộtsốprocess có thểbịsuspend trong khoả ng thời gian ngắ n khi hệthống quá tả i và sau đó lại được activate khi có đủtài nguyên (hệthống trởvề trạng thái bình thường).
event terminated Ready Dispatch Blocked Over waik up time Suspend Activate Running Suspend Activate ACTIVE STATE Suspend SUSPENDED STATE Ready Blocked suspend suspend event terminated H×nh 3.3 So vớimục trước- có thêm hai trạ ng thái ứng vớicác thao tác suspend và activate. Tác nhân dừng có thểlà chính bản thân process hay là process khác. Trong hệcó một BXL thì process chỉcó thểdừng chính bả n thân nó vì không có proces khác nào đang chạ y đồng thời vớinó. Còn trong hệcó nhiề u BXL thì một process có thể bịdừng bởiprocess khác đang chạy trên BXL khác. Một process ởtrạ ng thái ready chỉcó thểbịdừng bởi process khác, lúc đó xả y ra sựchuyển trạng thái: suspend (process name): ready  suspended-ready Process đang ởtrạ ng thái suspended-ready có thểchuyển vềtrạ ng thái ready bởi process khác; quá trình chuyển trạ ng thái đó có thểbiểu diễ n bởi activate (process name): suspend-ready  ready Process đang ởtrạ ng thái blocked có thểchuyể n sang trạ ng thái suspend bởi một process khác, khi đó diễn ra sựđổitrạng thái suspend (process name): blocked  suspend-blocked Và ngược lạ i, prrocess ởtrạng thái suspended blocked có thểđược kích hoạ t bởi một process khác activate (process name): suspended-blocked  blocked Chúng ta có thểđặ t vấn đềtạisao không thay vì suspend một process ởtrạ ng thái blocked, ta vẫn chờđế n khi có sựkiện (kế t thúc I/O) mà process đợi xả y ra để process chuyển vềtrạng thái ready. Tuy nhiên tác vụI/O hay sựkiện process chờ có thểkhông xả y ra hay không biết khi nào mới xảy ra. Nhưthế , các nhà thiết kế cần phải chọn lựa: hoặ c suspend một blocked process (đưa về trạ ng thái suspended-blocked) hoặc phải sinh ra cơchếcho phép đưa process từtrạng thái blocked sang trạng thái ready và sau đó chuyể n thành trạ ng thái suspened-ready khi kết thúc I/O hay diễ n ra sự kiệ n process đang chờ. Mặt khác thao tác
suspending thường có mức ưu tiên cao và cần thực hiệ n ngay, do đó phầ n lớn các hệthống sửdụng cách thứnhấ t. Khi sựkiệ n process đang chờxảy ra (nếu nhưnó xảy ra), trạ ng thái của process sẽchuyể n từsuspended-blocked sang trạ ng thái suspended-ready: Incommingevent (process name): suspended-blocked  suspended-ready 3.7 Xửl ý ngắt Trong thực tếcó nhiề u trường hợp tương tựngắ t trong máy tính. Trong kỹthuậ t máy tính, ngắ t (interupt) là sựkiệ n làm thay đổi trình tựthực hiệ n lệnh bình thường của BXL. Tín hiệ u ngắt được xửlý bởi phần cứng. Khi xảy ra ngắt, trình tựthực hiện nhưsau:  Điề u khiể n chuyển cho HĐH  HĐH lưu lạ i trạng thái của process bịngắ t. Trong nhiều hệthống thì thông tin đó được lưu trong PCB của process bịngắ t.  i ngắ HĐH phân tích loạ t và chuyể n điề u khiể n cho chương trình xửlý ngắt tương ứng. Tác nhân gây ra ngắ t có thểlà chính bả n thân process đang chạ y, hay là một sự kiện có thểliên quan hoặ c không liên quan đến process đó. 3.7.1 Các dạng ngắt ng ngắttrong các hệthống máy lớn của IBM: Chúng ta xem xét các dạ  SVC- interrupt: ngắt này do process đang chạy sinh ra. SVC do chương trình ứng dụng sinh ra đểyêu cầu một dịch vụnào đó của hệthống, ví dụ thực hiện tác vụvào/ra, cấ p phát bộnhớ... CơchếSVC giúp bả o vệHĐH, người sửdụng không được tựdo xâm nhậ p OS mà anh ta phảiyêu cầ u dịch vụthông qua lệnh SVC. Do đó HĐH luôn kiể m soát được các thao tác vượt quá giớihạn ứng dụng và hoàn toàn có thểtừchốiyêu cầ u.  Ngắ t vào/ra: do các thiế t bịvào/ra sinh ra. Các ngắt này thông báo cho BXL vềsựthay đổi trạng thái nào đó ví dụkế t thúc tác vụin, máy in hết giấy,...  External interrupt: ngắt này có thểdo nhiề u nguyên nhân sinh ra, trong đó có ngắt thời gian overtime, ngắ t bàn phím, ngắt từcác BXL khác trong hệ thống đa BXL, ...  Restart interrupt: sinh ra khi người điề u kiể n cầ n khởi động lạ i hệthống, hay lệnh restart SIGP của một processor (BXL) khác trong hệthống đa BXL.
 t sinh ra do lỗihoạt động của chương trình ví Program check interrupt: ngắ dụlệnh chi cho 0, ...  Machine check interrupt: sinh ra do lỗi phầ n cứng trong hệthống. 3.8.2 Context switching - Đổingữcảnh Đểxửlý các loại ngắt, trong HĐH có chương trình chuyên biệt gọi là interrupt handler. Nhưtrên đã nói, trong hệthống có 6 loạ i ngắt, nhưthếtrong HĐH có 6 IH (interrupt handler) đểxửlý 6 loạ i ngắt khác nhau. Khi có ngắ t thì HĐH ghi lại trạng thái của process bịngắ t và chuyể n điều khiển cho chương trình xửlý ngắt tương ứng. Điề u đó được thực hiện bởiphương pháp gọi là “chuyể n đổingữcảnh” (context switching). Trong phương pháp này sử dụng các thanh ghi trạ ng thái chương trình PSW (program status word), trong đó chứa thứtựthực hiện lệ nh và các thông tin khác nhau liên quan đến trạng thái của process. Có 3 loạ i PSW: PSW hiệ n thời (current), PSW mới (new) và PSW cũ(old) Đị a chỉcủa lệnh tiế p theo (sẽđược thực hiện) được chứa trong current PSW, trong current PSW cũng chứa thông tin vềnhững loạ i interrupt nào hiện đang bịcấm (disable) hay được phép (enable). BXL chỉphản ứng với những loạiinterrupt được phép, còn các interrupt đang bịcấ m sẽđược xửlý sau hoặ c bỏqua. Có một số interupt không bao giờbịcấ m: SVC, restart,.. Trong hệcó một BXL thì chỉcó một current PSW, nhưng có 6 new PSW (tương ứng cho mỗi loại ngắt) và 6 old PSW tương ứng. New PSW của mộtloạingắ t chứa địa chỉcủa chương trình xửlý ngắ t (interupt handler) loạ i đó. New PSWs Old PSWs SVC SVC I/O I/O External current PSW External Restart Restart Program check Program check Machine check Machine check H×nh 3.5 Khi xả y ra ngắt (nếu loại ngắt đó không bịcấ m) lúc đó sẽtựđộng (do phầ n cứng thực hiện) xảy ra quá trình chuyển đổiPSW nhưsau:  current PSW trởthành old PSW của loạ i ngắ t tương ứng
 new PSW của loạ i ngắtđó trởthành current PSW Nhưthế , sau khi chuyển đổi thì current PSW chứa đị a chỉcủa chương trình xửlý ngắ t và sau đó chương trình xửlý ngắt sẽđược thực hiện. Khi kế t thúc chương trình xửlý ngắ t, BXL lại hoạt động bình thường, BXL sẽtiế p tục phục vụprocess bịngắ t hoặ c có thểmột process khác trong danh sách các ready process. Trong trường hợp process không cho phép giải phóng (nhường) quyền sửdụng BXL thì nó sẽtiếp tục được BXL phục vụ, còn nếu nó cho phép thì nó tiếp tục được sử dụng BXL khi không có ready process nào. Trong các hệthống, có nhiề u mô hình xửlý ngắ t khác nhau không hoàn toàn như mô hình trên. 3.8 Hạt nhân của OS Tất cảcác thao tác liên quan đế n process, thực hiệ n bởi một phần HĐH gọi là hạt nhân – kernel. Kernel chỉlà một phần không lớn (vềkích thước code) của HĐH nhưng nó là một trong sốnhững thành phầ n được sửdụng nhiề u nhất trong HĐH. Do đó kernel thường luôn được nạp vào bộnhớ, trong khi các thành phầ n khác có thểnằm ởbộnhớngoài và chỉđược nạ p vào khi cần. Một trong những chức năng quan trọng nhất trong kernel là xửlý ngắt. Trong các hệlớn nhiều thành phầ n (component) thường xuyên có dòng lớn (nhiề u) ngắt. Do đó xửlý ngắt nhanh đóng vai trò quan trọng trên quan điể m sửdụng tài nguyên hệ thống và đảm bả o thời gian phản ứng với các yêu cầ u của người dùng một cách nhanh chóng. Khi kernel xửlý ngắ t, nó cấm các ngắ t khác và chỉcho phép tiế p tục xửlý ngắtsau khi xửlý xong ngắ t hiện thời. Trong trường hợp có dòng liên tục các ngắt thì có thểxuấ t hiệ n tình huống các ngắ t bịchặ n trong thời gian tương đối lớn tức là hệ thống không phả n ứng kị p thời với các sựkiệ n. Do đó kernel thường được thiế t kế sao cho nó chỉthực hiệ n việ c tiề n xửlý tốithiể u và chuyển việ c xửlý tiếp theo cho process hệthống (system process) tương ứng và có thểcho phép xửlý các ngắt tiếp theo. Theo đó các ngắ t bịcấ m trong khoảng thời gian nhỏhơn do đó tốc độ phả n ứng của hệthống tăng đáng kể . 3.8.1 Các chức năng chính của kernel Kernel thường gồm các chương trình thực hiện các chức nă ng sau:  xửlý ngắ t  tạo và xoá các process  đổitrạ ng thái của process  dispatching
 suspend and activate process  đồng bộ(synchronize) các process  xửlý, tổchức mối quan hệgiữa các process  điều khiể n PCBs  n lý bộnhớ quả  hỗtrợlàm việ c hệthống file 3.8.2 Cho phép (enable) và cấm (diasable) ngắt Xâm nhậ p kernel thường được thực hiệ n thông qua ngắ t, khi kernel phản ứng với ngắt nào đó thì nó cấm các ngắt khác. Sau khi phân tích nó chuyển việ c xửlý cho một system process chuyên làm việ c vớiloạ i ngắtđó. Trong mộtsốhệthống mỗi ngắ t đề u đươc xửlý bởi cảHĐH cồng kề nh, do đó các ngắt thường bịcấm trong phầ n lớn thời gian nhưng vềnguyên tắc HĐH lạ i đơn giản hơn. Cách này thường áp dụng cho các máy nhỏ,làm việc với ít process. Còn với các hệthống phức tạp, thường có mộtphần HĐH chuyên xửlý ngắt cho phép nâng cao các chỉsốcủa cảhệthống. 3.8.3 Kiế n trúc phân cấp của hệthống Trong việ c thiế t kếHĐH, phương pháp xây dựng HĐH phân cấ p thành nhiề u khối có nhiều ưu điể m. Tầ ng thấ p nhấtcủa kiế n trúc thường là phần cứng, ởcác lớp tiế p theo thường là các module với các chức nă ng khác nhau của HĐH. Tổng hợp các module của kernel ta có máy tính mởrộng (extended machine), nhờđó hệthống cung cấ p nhiề u dị ch vụkhác nhau cho người dùng. Các chức nă ng mởrộng đó (do kernel cung cấ p) được gọilà các primitive. Phía trên kernel là các system process của HĐH đểphục vụcho các process của người dùng. Còn trên cùng là các user process. Kinh nghiệ m cho thấ y kiến trúc lớp làm cho công việc thiế t kế, sửa đổi, test dễ dàng hơn. Trong hệthống mà kernel gồm nhiề u lớp, thì cầ n xem xét cẩn thận chức năng nào nằ m ởlớp nào. Trong các hệđó thường người ta hạ n chếcho phép truy xuấ t từtrên xuống tức là tạ i mỗi lớp chỉcó thểthâm nhậ p đế n lớp dưới kếtiế p mà thôi. 3.8.4 Thực hiệ n kernel với microcode Xu hướng: thiế t kếnhiề u chức năng với microcode đó là cách hiệu quảbả o vệ kernel ngoài ra viết microprogram tốt có thểnâng cao tốc độcủa cảhệthống. Tất nhiên đổilạiviệc thiế t kếphức tạp hơn rấtnhiều.
Chương 4: Các process song song không đồ ng bộ asynchronous concurent process 4.1 Mởđầu Các process gọi là song song nế u các process đó tồn tại đồng thời. Các process song song (concurent process) có thểhoạ t động hoàn toàn độc lập với nhau hoặc song song không đồng bộ– asynchronous, tức là theo chu kỳchúng cầ n đồng bộ và tương tác với nhau. Asynchronism – song song không đồng bộlà một vấ n đề phức tạp. Chúng ta sẽxem xét một sốvấ n đềliên quan đến điều khiể n các quá trình song song không đồng bộ– asynchronous concurent process. Các ví dụđược đưa ra với ngôn ngữgiảpascal. Một sốví dụvềngôn ngữcho phép lậ p trình song song là ngôn ngữModula (Nicolar Witt), ngôn ngữAda. 4.2 Xửlý son g son g Theo sựphát triể n của máy tính chúng ta có thấ y sựphổbiến củ a các hệthống đa BXL (multiprocessor) và cùng với nó là sựphổbiế n của xửlý song song. Nếu như một quá trình logic có thểxửlý song song logic thì các hệthống mới có thểxửlý chúng song song thực sựvà có thểcông việ c được phân chia giữa các BXL khác nhau. Xửlý song song là vấ n đềđược quan tâm và có nhiều khó khăn do một loạt nguyên nhân khác nhau. Con người theo tựnhiên có xu hướng chỉchú ý đến một công việ c tạ i mỗi thời điể m hơn là nghĩđến nhiều việ c khác nhau cúng một lúc. Thông thường khó mà xác đị nh những thao tác nào có thểthực hiện song song. Và theo dõi mộtchương trình song song khó hơn nhiều so với chương trình xửlý tuần tự. Các asynchronous process cầ n tương tác qua lại lẫn nhau theo chu kỳthời gian và tương tác này có thểkhá phức tạp. Cuối cùng, việ c chứng tỏsựđúng đắ n cho các chương trình song song khó hơn nhiều so với trường hợp chương trình tuầ n tự. Và chúng ta cũng đến phương pháp hiệu quảđểchứng minh tính đúng đắ n của chương trình, có nhưthếchúng ta mới có thểxây dựng các hệthống có tính ổn đị nh cao. 4.3 Các l ện h chỉthịxửlý song song : parbegin và parend Trong nhiều ngôn ngữlậ p trình đã có các chỉthịyêu cầu xửlý song song(như trong Ada, Modula,...) các chỉthịnày thường đi theo cặ p:
 Chỉthịđầu tiên chỉra rằ ng bắ t đầu từsau lệnh đó, chương trình được tách thành mộtsốdòng điều khiển (thread control) thực hiệ n song song.  Chỉthịthứhai chỉra rằng từđó chương trình lạ i được xửlý tuầ n tự. Có nhiề u tên khác nhau nhưng người ta thường dùng cặ p parbegin/parend (Dijktra – cooperating sequenical process). Nói chung đoạ n mã chương trình được thực hiện song song có dạng parbegin operator 1 operator 2 ...... operator n parend Việ c thực hiện đoạ n chương trình song song có thểhình dung nhưsau. Chương trình được thực hiện theo một luồng điều khiển tuần tự, đến khi gặp lệnh parbegin, luồng xửlý sẽđược chia thành n quá trình xửlý độc lậ p, mỗi quá trình sẽxửlý một thao tác tương ứng từoperator 1, ... đế n operator n. Thao tác này có thểlà các lệnh đơn, lời gọi hàm, khốicác lệnh tuần tựnằ m giữa begin/end hay là tổhợp các thao tác đó. Các quá trình xửlý sẽdần thực hiện đến lệnh parend lúc đó luồng điề u khiể n lại hợp nhấtthành mộtluồng xửlý các lệnh tiếp theo mộtcách tuần tự. Ví dụxét biể u thức: x:= ( -b + ( b2 - 4*a*c ) * 5 ) / (2*a) u quá trình xửlý là hoàn toàn tuầ nế n tựchúng ta có thểlàm theo các bước sau: 2 1. b 2. 4*a 3. (4*a)*c 2 4. b - (4*a*c) 2 5. (b - (4*a*c))*5 6. -b 2 7. -b + ((b - (4*a*c))*5) 8. 2*a 2 9. (-b + ((b - (4*a*c))*5)) / (2*a) Các bước xửlý trên theo đúng trình tựquy tắ c thực hiệ n phép toán. Vớihệthống hỗtrợxửlý song song chúng ta có thểlàm nhưsau:
1. parbegin temp1 := -b 2 temp2 := b temp3 := 4*a temp4 := 2*a parend 2. temp5 := temp3*c 3. temp5 := temp2 - temp5 4. temp5 := temp5 * 5 5. temp5 := temp1 + temp5 6. x := temp5 / temp4 Ta thấy nế u thực hiện xửlý song song thì thời gian tính toán giả m đi đáng kểso với khi tính tuầ n tự. 4.4 Mutu al exclu si on (loại trừn hau) Xét trường hợp hệthống phục vụtrong chếđộphân chia thời gian cho nhiề u thiết bịđầ u cuối – terminal. Giảsửkhi người sửdụng đánh hết một dòng và gõ Enter, cần tính sốdòng của tấtcảcác người sửdụng đã gõ từtấ t cảcác terminal. Đểthực hiện điều đó, mỗi khi một người sửdụng nào đó gõ enter thì process của người dùng đó sẽtăng thêm 1 đơn vịcho một biế n toàn cục (global) totalLine. Vì hệ thống là đa xửlý và đa người dùng, do đó hoàn toàn có khảnă ng là hai người dùng khác nhau gõ enter gần nhưđồng thời, khi đó 2 process điều khiển ứng với 2 người dùng đó sẽđồng thời muốn truy nhậ p đến biến toàn cục totalLine. Đểtăng biến đó giảsửmỗiprocess ứng dụng đề u dùng các lệnh sau: 1- load totalline 2- totalline := totalline + 1 3- store totalline Giảsửtạ i mộtthời điểm, totalline có giá trị62829 Bây giờnế u mớiprocess 1 thực hiệ n được 2 lệ nh đầ u tiên: load totalline (đọc giá trịhiện thời của biế n) và tă ng 1 cho giá trịbiế n totalline := totalline + 1 khi đó trong mộtthanh ghi (ví dụAx) chứa giá trịmới62830 của biế n totalline. Sau đó process 1 không được quyề n sửdụng BXL nữa (ví dụdo ngắ t thời gian) và đến lượt process 2 được thực hiệ n. Giảsửprocess 2 kịp thực hiệ n cả3 lệ nh trên,
khi đó giá trịcủa biế n totalline sau khi thực hiện xong sẽcó giá trị62830. Sau đó điều khiển được trảlạ i cho HĐH và đế n lượt process 1 được tiếp tục, nó thực hiệ n nốt lệnh thứ3 tức là ghi lại giá trị62830 vào biế n totalline. Chúng ta thấy do sự điều khiển truy xuất không đúng mà chương trình hoạ t động không đúng. Ta thấy rằng vấn đềnày có thểkhắc phục nế u mỗiprocess có quyền truy nhập duy nhất đến biến totalline, tức là khi một process đang truy nhập đế n biến totalline thì các process khác phả i đợi đến khi process đầu tiên kế t thúc truy nhập. Nhưthế , khi một process truy nhập đến dữliệu chung thì cần cấm tấ t cảcác process khác truy nhập đến cùng dữliệu vào thời điể m đó. Điề u đó gọi là mutual exclusion (loạitrừlẫn nhau) 4.5 Khoảng tới hạn Criti cal regi on Loạitrừlẫ n nhau chỉcầ n thiế t trong trường hợp khi các process cùng truy nhập đến dữliệ u chung, hay khi chúng thực hiện các thao tác có thểdẫn tới tranh chấ p (conflic) dữliệ u nói chung, còn khi chúng thực hiệ n các thao tác operation không dẫ n tới tranh chấp thì hoàn toàn có thểthực hiện song song đồng thời. Khi process truy nhập đế n dữliệ u chung thì người ta nói rằng lúc đó process nằm trong khoả ng tới hạ n – critical region. Rõ ràng là đểgiả i quyết tranh chấ p thì khi có một process nằm trong khoả ng tới hạn, cần phải không cho phép process khác (ít nhấ t là các process truy nhập đế n cùng một dữliệu) được vào khoảng tới hạn (tấ t nhiên chúng vẫ n có thểthực hiệ n các thao tác khác ngoài khoả ng thới hạ n). Còn khi proces ra khỏi khoảng tới hạ n thì một trong sốcác process đang chờvào khoả ng tới hạn phải được tiế p tục vào khoả ng tới hạn. Đảm bả o 'loại trừlẫn nhau' là một trong những vấ n đềmấ u chốt của lập trình xửlý song song. Có nhiề u phương pháp được đềxuấ t từthực hiệ n hoàn toàn bằng phầ n mề m đế n thực hiệ n bằ ng phần cứng, từmức thấ p đến mức cao, có những phương pháp cho phép loạ i trừlẫ n nhau trong điề u kiện tương đối thoảimái, còn có những phương pháp thì bắtbuộc phả i có thêm các điều kiện chặt chẽ. Khi một process nằ m trong khoả ng tới hạ n thì có nhiều vấn đềcầ n quan tâm. Trong chếđộnày nó có toàn quyề n truy nhập dữliệu chung còn các process khác phải chờ.Do đó các process cầ n ra khỏichếđộnày càng nhanh càng tốt, trong chế độnày nó không được chuyể n sang trạng thái blocked, do đó các khoảng tới hạn cần thiết kế,kiểm tra cẩ n thậ n (đểví dụkhông cho phép xảy ra vòng lặ p chờtrong khoả ng tớihạn...) Khi process kết thúc (ra khỏi) khoả ng tới hạ n (bình thường hoặc ngay cảkhi có lỗi) thì HĐH phải kiểm soát được đểhuỷbỏchếđộtới hạn, nhờthếcác process khác có thểđến lượtvào khoả ng tới hạn.
4.6 Mutu al exclu si on Pri mi tive Chương trình song song dưới đây đảm bả o bài toán trong mục 4.4 hoạt động đúng. Từđây trởđi chúng ta xét trường hợp chỉcó hai process song song, cầ n phải nói ng trường hợp có n process (n>2) thì bài toán phức tạ rằ p hơn rấ t nhiề u. Trong chương trình 4.2 chúng ta dùng hai chỉthị : enterMutualExclusion và exitMutualExclusion trong mỗi process ởđoạ n code truy nhập đế n dữliệu chung (biến toàn cục totalLine), hai chỉthịnày bao hai đầu khoả ng tới hạ n. Đôi khi các chỉthịnày được gọilà mutual exclusion primitive Chương trình 4.2 Program MutualExclusionSample var totalLine: integer; procedure process1 begin while true do begin get line {readln} enterMutualExclusion; totalLine := totalLine +1; exitMutualExclusion; processing line ... end; end; procedure process2 begin while true do begin get line {readln} enterMutualExclusion; totalLine := totalLine +1; exitMutualExclusion; processing line ... end; end; begin
totalLine := 0; parbegin process1; process2; parend; end. Trong trường hợp có hai process, các lệnh primitive làm việc nhưsau: khi process 1 thực hiệ n chỉthịenterMutualExclusion (và lúc đó process 2 ởngoài khoả ng tới hạ n) thì nó được vào khoảng tới hạ n, thực hiệ n các lệnh trong khoả ng tới hạn và đế n khi thực hiện lệ nh exitMutualExclusion là lúc báo hiệ u nó ra khỏi khoả ng tới hạ n. Còn nế u khi process1 muốn vào khoả ng thới hạ n, trong lúc đó process 2 đã ở trong khoả ng tới hạn thì process1 nó phả i chờđế n khi process2 ra khỏi khoảng tới hạ n đểcó thểtiếp tục vào khoả ng tới hạ n. Nế u cảhai process thực hiện enterMutualExclusion cùng một lúc thì một trong hai process sẽđược phép vào khoảng tới hạ n còn process kia sẽphải chờ,có thểsựlựa chọn là ngẫu nhiên. 4.7 Th ực h iện mutu al exclu si on primitive Chúng ta sẽtìm cách thực hiệ n các primitive enter và exit vớicác hạn chếsau:  Vấ n đềgiải quyết hoàn toàn bằng chương trình (phần mềm) trên hệthống không có lệ nh chuyên cho mutual exclusion. Mỗi lệnh được thực hiện trọn vẹ n không bịngắ t giữa chừng. Khi có nhiều process cùng muốn truy nhậ p đế n dữliệu chung thì tranh chấ p được giảiquyếtbằ ng phầ n cứng, một cách tình cờsẽcó mộtprocess được chọn.  Không có bất cứgiảsửgì vềtốc độtương đối của các asynchronous parallel process  Các process nằ m ngoài khoảng tới hạ n không thểcấ m các process khác vào khoảng tớihạn.  Không được đểprocess chờvô hạ n đểvào khoả ng tới hạ n. Cơchếthực hiện loạ i trừlẫn nhau bằ ng chương trình được nhà toán học Hà lan Dekker đềra đầu tiên. Chúng ta sẽxem xét các version của thuậ t toán Dekker do Dijkstra thực hiệ n.
4.8 Th uật toán Dekker Đầ u tiên, chúng ta xem xét version đầ u tiên Có thểcoi mỗi process nhưlà một vòng lặp vô tậ n với nhiề u lần lặp vào chếđộ mutual exclusion. Trong version này primitive enter mutual exclusion được thực hiện nhịp vòng lặp while chờđế n khi biến processno bằng sốcủa process, còn primitive exit mutual exclusion thực hiện nhưmột lệnh đặ t biến processno bằng số của process khác. Chương trình 4.3 Program Version1 var processNo: integer; procedure process1 begin while true do begin .... while processNo = 2 do ; {critical region} processNo := 2; .... end; end; procedure process2 begin while true do begin .... while processNo = 1 do ; {critical region} processNo := 1; .... end; end; begin processNo := 1;
parbegin process1; process2; parend; end. Hoạt động: cảhai process cùng thực hiện. Vì đầ u tiên biến processNo gán bằ ng 1 do đó chỉprocess1 được vào critical region. Process 2 khi muốn vào critical region kiểm tra thấy biến processno có giá trị1 do đó nó phả i chờbằ ng vòng lặp rỗng, nó chờ đế n khi processNo=2 tức là khi process 1 ra khỏi critical region và đặt processNo :=2. Vậy chương trình đã đả m bảo loại trừlẫ n nhau (mutual exclusion). Version1 có nhiều nhược điể m, process 1 phảivào critical region trước tiên (tức là dù process 2 sẵ n sàng trước thì nó vẫn phảichờ) và các process lần lượtvào critical region theo thứtựcốđị nh (do đó nế u mộtprocess thực hiệ n các lệnh trong critical region thường xuyên hơn thì nó phả i làm việ c với tốc độchậm hơn nhiề u). Chương trình này đả m bả o không rơi vào tình trạ ng deadlock vì khi cảhai process cùng muốn vào critical region thì có ít nhấ t một process tiế p tục. Còn khi một process kế t thúc thì sau đó process còn lại cũng kế t thúc. Trong version 1 việ c thực hiệ n mutual exclusion chỉbằ ng một biến do đó có vấ n đềcác process vào khoả ng tới hạ n theo thứtựcốđị nh. Đểcảitiế n, trong version 2 sửdụng hai biế n logic: flag1 và flag2, chúng nhậ n giá trịtrue khi process tương ứng nằm trong critical region. Trong version này process 1 chủđộng chờ(active wait) trong khi biến flag2 vẫ n là true. Khi process 2 ra khỏi khoả ng tới hạn, nó đặ t lại flag2 := false và do đó process1 ra khỏi vòng chờwhile, đặ t biến flag1 = true và vào khoả ng tới hạn. Khi flag1 còn là true thì process 2 không thểvào khoả ng tớihạn. Chương trình 4.4 Program Version2 var flag1, flag2: boonlean; procedure process1 begin while true do begin ....
while flag2 = true do ; flag1 := true; {critical region} flag1 := false; .... end; end; procedure process2 begin while true do begin .... while flag1 = true do ; flag2 := true; {critical region} flag2 := false; .... end; end; begin flag1 := false; flag2 := false; parbegin process1; process2; parend; end. Nhưng lạ i xuất hiện một sốvấn đềliên quan đế n lập trình song song. Vì process 1 và process 2 là song song do đó chúng có thểđồng thời thửvào critical region. Đầ u tiên các biến flag1 và flag2 có giá trịfalse. Process 1 kiể m tra biến flag2 thấy flag2=false và thoát khỏi vòng lặp chờ, trước khi nó kị p đặt flag1 thành true bằ ng lệnh flag1:= true thì đế n lượt process 2 được chiế m BXL, process2 cũng có thể kiểm tra thấ y flag1 là false (vì lúc đó process1 chưa kị p đặ t)- lúc đó process 2 đặt