Chương 2 Quản lý tiến trình

CHƯƠNG 2 Quản lý tiến trình 1. TỔNG QUAN VỀ TIẾN TRÌNH  Vì sao muốn xử lý đồng thời nhiều công việc trên máy tính ? IO CPU IOCPU Job 1 CPU Job 1 CPU IO IO CPU IO CPU Job 2 CPU CPU  Xử lý đồng thời để tăng hiệu suất sử dụng CPU 3  Vì sao muốn xử lý đồng thời nhiều công việc trên máy tính ?  Xử lý đồng thời để tăng tốc độ xử lý Job : kq = a*b + c*d; CPU #1 CPU #1 CPU #2 x = a * b y = c * d kq = x+y x = a * b 1 y = c *d 2 kq = x+y 3 Xứ lý tuần tự Xửù lý đồng hành 4 Xử lý đồng hành, những khó khăn ? HĐH : “Giải quyết nhiều công việc đồng thời, đâu có dễ !” - Tài nguyên giới hạn, ứng dụng “vô hạn” - Nhiều hoạt động đan xen ??? Phân chia tài nguyên ? ??? Chia sẻ tài nguyên ? ??? Bảo vệ? Excel Visual C++ CDplayer Winword 5 Giải pháp HĐH: “Ai cũng có phần khi đến lượt mà!” -“Chia để trị”, cô lập các hoạt động. - Mỗi thời điểm chỉ giải quyết 1 yêu cầu. - Aûo hoá tài nguyên: biến ít thành nhiều Winword CDPlayer Visual C ++ Excel 6 1. Tổng quan về tiến trình  Tr¹ng th¸i cđa mét hƯ thèng tÝnh to¸n t¹i mét thêi ®iĨm ®-ỵc hiĨu lµ mét bé th«ng tin cđa tÊt c¶ c¸c thµnh phÇn trong hƯ thèng tÝnh to¸n.  Mét d·y chuyĨn tr¹ng th¸i cđa hƯ thèng tÝnh to¸n ký hiƯu lµ S0, S1,..Sn trong ®ã S0 lµ tr¹ng th¸i ®Çu, Sn lµ tr¹ng th¸i kÕt thĩc th× ta gäi ®ã lµ mét tiÕn tr×nh.  ViƯc chuyĨn tr¹ng th¸i hƯ thèng tÝnh to¸n ph¶i dùa vµo mét sù kiƯn ph¸t sinh trong hƯ thèng gäi lµ hiƯn t-ỵng ng¾t. S0 S1 S2 S3 S4 S5 . . . . Sn-1 Sn Sn+1 . . . . A B 7 Khái niệm tiến trình (process)  Tiến trình là một bộ phận của một chương trình đang thực hiện, đơn vị thực hiện tiến trình là processor.  Tiến trình sở hữu một con trỏ lệnh, một con trỏ stack, một tập các thanh ghi, một khơng gian địa chỉ trong bộ nhớ chính và tất cả các thơng tin cần thiết khác để tiến trình cĩ thể hoạt động được. Vd: Một chương trình Word có thể được chạy 2 lần sẽ tạo ra 2 tiến trình khác nhau:  Microsoft Word – [Bai tap1.doc]  Microsoft Word – [Bai tap2.doc] 8 Khái niệm khác 9  Saltzer: Tiến trình là một chương trình do một processor logic thực hiện.  Horning & Rendell: Tiến trình là một quá trình chuyển từ trạng thái này sang trạng thái khác dưới tác động của hàm hành động, xuất phát từ một trạng thái ban đầu nào đĩ. Các loại tiến trình  Cĩ thể chia thành hai loại: tiến trình tuần tự (MS_DOS) và tiến trình song song (uniprocessor và multiprocessor)  Tiến trình tuần tự là các tiến trình mà điểm khởi tạo của nĩ là điểm kết thúc của tiến trình trước đĩ.  Tiến trình song song là các tiến trình mà điểm khởi tạo của tiến trình này nằm ở thân của các tiến trình khác: BEGIN END t Begin A B 10 11 Ph©n lo¹i tiÕn tr×nh song song A B C Z a b c z A B C Z a b c z I I A B C Z b c z A B C Z a b c z Độc lập Quan hệ thơng tin Phân cấp Đồng mức 12 P1 P2 P3 Time a. Trong hệ thống uniprocessor P1 P2 P3 Time b. Trong hệ thống Multiprocessor Sự thực hiện đồng thời của các tiến trình trong hệ thống uniprocessor (a) và hệ thống multiprocessor (b). Các loại tiến trình Nếu nhìn ở gĩc độ người dùng thì cĩ 2 loại tiến trình:  Tiến trình của hệ điều hành: Được chạy ở chế độ đặc quyền và được truy xuất đến các vùng dữ liệu được bảo vệ của hệ thống.  Tiến trình của chương trình ứng dụng: Chạy ở chế độ khơng đặc quyền và khơng được truy xuất đến các dữ liệu được bảo vệ một cách trực tiếp mà phải thơng qua lời gọi hệ thống. 13 Mơ hình tiến trình  Về nguyên tắc, hệ thống phải cĩ nhiều processor, mỗi processor cĩ nhiệm vụ thực hiện một chương trình.  Tuy nhiên, mong muốn là thực hiện sự đa chương trên các hệ thống chỉ cĩ một processor. Tức là, cĩ thể cĩ nhiều chương trình hoạt động đồng thời (concurrence)  Sử dụng mơ hình tiến trình để tạo ra sự song song giả hay tạo ra các processor logic từ processor vật lý. 14 15  ChÕ ®é ®a ch-¬ng tr×nh ph©n chia thêi gian mçi ng-êi sư dơng cã c¶m gi¸c nh- chØ cã mét m×nh m×nh lµ ng-êi duy nhÊt sư dơng toµn bé hƯ thèng.  TÊt c¶ c¸c hƯ ®iỊu hµnh thùc hiƯn song song ®Ịu do mét processor cđa hƯ thèng – processor vËt lý ®iỊu khiĨn.  Ng-êi sư dơng ®¸nh gi¸ ho¹t ®éng processor trªn c¬ së quan s¸t tiÕn tr×nh cđa m×nh thùc hiƯn -> Processor ng-êi sư dơng quan s¸t vµ ®¸nh gi¸: processor l«gic  Processor logic g¾n víi tiÕn tr×nh. Mơ hình tiến trình 16 Processor l« gÝc vµ Processor vËt lý  ChÕ ®é xư lý kÕ tiÕp ®¬n ch-¬ng tr×nh:  Mét tiÕn tr×nh ®-ỵc thùc hiƯn xong míi khëi t¹o vµ thùc hiƯn tiÕn tr×nh kh¸c -> cã thĨ ®ång nhÊt processor logic víi processor vËt lý.  KÐm hiƯu qu¶ v× tµi nguyªn processor bÞ l·ng phÝ nhiỊu.  N©ng cao hiƯu qu¶ khai th¸c cđa toµn hƯ thèng nãi chung:  Ph©n chia bé nhí  Ph©n phèi thêi gian cđa processor cho nhiỊu tiÕn tr×nh ®ång thêi tån t¹i.  §èi víi mçi tiÕn tr×nh, tèc ®é thùc hiƯn sÏ bÞ gi¶m :  Thêi gian truy nhËp bé nhí t¨ng  Kh«ng ®-ỵc quyỊn sư dơng processor liªn tơc.  §èi víi ng-êi sư dơng: thay ®ỉi t©m lý khai th¸c hƯ thèng. 17 C¸c vÊn ®Ị cÇn ph¶i gi¶i quyÕt ®èi víi c¸c hƯ thèng nhiỊu processor a)Sè l-ỵng processor logic nªn t¹o ra lµ bao nhiªu? b) §é dµi kho¶ng thêi gian g¾n liªn tơc processor vËt lý cho mét processor l«gic lµ bao nhiªu th× hỵp lý? c)Sau khi mét processor l«gic hÕt quyỊn sư dơng processor vËt lý th× cÇn chän tiÕn tr×nh nµo ®Ĩ ph©n phèi processor vËt lý? C¸c c¸ch gi¶i quyÕt kh¸c nhau ba vÊn ®Ị nªu trªn t¹o ra c¸c chiÕn l-ỵc ®iỊu ®é tiÕn tr×nh kh¸c nhau. Mơ hình tiến trình  Hệ điều hành sẽ chia các chương trình thành các tiến trình, khởi tạo, đưa vào hệ thống và cấp phát đầy đủ tài nguyên (trừ processor) cho tiến trình và đưa các tiến trình sang trạng thái sẵn sàng.  Hệ điều hành cấp processor cho một tiến trình trong số các tiến trình ở trạng thái sẵn sàng, sau một khoảng thời gian hệ điều hành thu hồi processor của tiến trình này để cấp cho một tiến trình sẵn sàng khác.  Khoảng thời gian đĩ là rất nhỏ tạo ra cảm giác các tiến trình đều sở hữu processor song song giả 18 Mơ hình tiến trình  Ví dụ: Giả sử trong hệ thống cĩ 3 tiến trình sẵn sàng P1, P2, P3 thì quá trình chuyển processor giữa 3 tiến trình này cĩ thể minh họa như sau: Thời điểm Trạng thái các tiến trình t1 P1: được cấp processor t2 P1: bị thu hồi processor (khi chưa kết thúc) P3: được cấp processor t3 P3: bị thu hồi processor (khi chưa kết thúc) P1: được cấp processor t4 P1: kết thúc và trả lại processor P2: được cấp processor t5 P2: kết thúc và trả lại processor P3: được cấp processor t6 P3: kết thúc và trả lại processor 19 Mơ hình tiến trình  Ví dụ: Hình sau đây minh họa quá trình thực hiện của 3 tiến trình P1, P2, P3 ở trên: P1 P2 P3 Time Sự hoạt động “song song” của các tiến trình P1, P2, P3 uniprocessor t1 t2 t3 t4 t5 t6 20 Mơ hình tiến trình  Ưu điểm: Tiết kiệm được bộ nhớ vì khơng phải nạp tất cả chương trình vào bộ nhớ mà chỉ nạp các tiến trình cần thiết nhất.  Cho phép các chương trình hoạt động song song nên tốc độ xử lý của tồn hệ thống tăng lên và khai thác tối đa thời gian xử lý của processor.  Việc thu hồi processor chuyển cho tiến trình khác là những vấn đề phức tạp. Bộ phận thực hiện chức năng này của hệ điều hành được gọi là bộ điều phối (dispatcher) tiến trình. 21 Mô hình đa tiến trình (MultiProcesses)  Hệ thống là một tập các tiến trình hoạt động đồng thời  Các tiến trình độc lập với nhau => không có sự trao đổi thông tin hiển nhiên… winword Visual C CDplayer Excel OS VD: Giờ thi lý thuyết môn Hệ Điều hành Mỗi sinh viên là một tiến trình : Cùng làm bài => Hoạt động đồng hành Có bài thi , bút, giấy…riêng => Tài nguyên riêng biệt Độc lập => Không trao đổi (về nguyên tắc) 22 Tiểu trình  Mỗi tiến trình cĩ một khơng gian địa chỉ và một dịng xử lý.  Một số ứng dụng cần nhiều dịng xử lý cùng chia sẻ một khơng gian địa chỉ tiến trình, điều này đưa đến một cơ chế thực thi mới, được gọi là tiểu trình.  Tiểu trình là một đơn vị xử lý cơ bản trong hệ thống, nĩ hồn tồn tương tự như tiến trình. Tức là nĩ cũng phải xử lý tuần tự các chỉ thị máy, nĩ cũng sở hữu con trỏ lệnh, một tập các thanh ghi, và một khơng gian stack riêng.  Một tiến trình bao gồm nhiều tiểu trình. 23 Tiểu trình - Thread 25  Tiểu trình là một đơn vị xử lý cơ bản trong hệ thống, nĩ hồn tồn tương tự như tiến trình.  Tức là nĩ cũng phải xử lý tuần tự các chỉ thị máy của nĩ, nĩ cũng sở hữu con trỏ lệnh, một tập các thanh ghi, và một khơng gian stack riêng.  Một tiến trình đơn cĩ thể gồm nhiều tiểu trình. Các tiểu trình trong một tiến trình chia sẻ một khơng gian địa chỉ chung => cĩ thể chia sẻ các biến tồn cục của tiến trình và cĩ thể truy xuất lên các vùng nhớ stack của nhau. Tiểu trình PCB vàTCB trong mô hình multithreads pid Threads list Context (Mem, global ressources…) Scheduling statistic Relatives ( Dad, children) PCB tid State (State, details) Context (IP, local stack…) Thread Control Block TCB 26 Lợi ích của Tiểu trình  Đáp ứng nhanh: Cho phép chương trình tiếp tục thực thi khi một bộ phận bị khóa hoặc một hoạt động dài  Chia sẻ tài nguyên: tiết kiệm không gian nhớ  Kinh tế: tạo và chuyển ngữ cảnh nhanh hơn tiến trình VD: trong Solaris 2, tạo process chậm hơn 30 lần, chuyển chậm hơn 5 lần  Trong multiprocessor: có thể thực hiện song song 27 Ví dụ: Tiểu trình  Thực hành môn Hệ Điều hành Mỗi nhóm 2 sinh viên là một tiến trình : Mỗi sinh viên là một tiểu trình  Cùng làm bài => Hoạt động đồng hành  Cóù bài thực hành chung => Tài nguyên chung  Trao đổi với nhau 28 Tiểu trình vs Tiến trình  Tiểu trình: 1 dòng xử lý  Tiến trình:  1 không gian địa chỉ  1 hoặc nhiều tiểu trình  Các tiến trình là độc lập  Các tiểu trình trong cùng 1 tiến trình không có sự bảo vệ lẫn nhau (cần thiết ? ). P1 int a; T1 T2 T 3 29 Phân chia CPU?  1 CPU vật lý: làm thế nào để tạo ảo giác mỗi tiến trình sở hữu CPU riêng của mình ?  Luân chuyển CPU giữa các tiến trình  2 thành phần đảm nhiệm vai trò điều phối:  Scheduler chọn 1 tiến trình  Dispatcher chuyển CPU (processor) cho tiến trình được chọn CPU 30 Scheduler - Nhiệm vụ  Ra quyết định chọn một tiến trình để cấp phát CPU :  Ứng cử viên = {Các tiến trình ready list}  0 tiến trình : CPU rảnh rỗi (idle)!  1 tiến trình : không cần suy nghĩ nhiều, đúng không ?  >1 : chọn ai bây giờ ?  Cần có thuật toán điều phối 31 Dispatcher - Nhiệm vụ  Nhiệm vụ của Dispatcher: Chuyển đổi ngữ cảnh  Xét ví dụ  Tiến trình A đang dùng CPU 1 chút thì bị HĐH thu hồi CPU  HĐH cấp CPU cho B dùng 1 chút, HĐH thu hồi lại CPU.  HĐH cấp CPU trở lại cho A.  Giá trị các thanh ghi giữa những lần chuyển đổi CPU?  Kịch bản :  Lưu ngữ cảnh tiến trình hiện hành  Nạp ngữ cảnh tiến trình được chọn kế tiếp 32 33 Phân biệt chương trình và tiến trình  Một chương trình là một thực thể thụ động, chứa đựng các chỉ thị điều khiển máy tính để tiến hành một tác vụ nào đĩ.  Khi cho thực hiện các chỉ thị này, chương trình chuyển thành tiến trình, là một thực thể hoạt động, với con trỏ lệnh xác định chỉ thị kế tiếp sẽ thi hành, kèm theo tập các tài nguyên phục vụ cho hoạt động của tiến trình. 2. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.1. Trạng thái tiến trình và sự chuyển trạng thái tiến trình  Trạng thái của tiến trình tại một 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 đĩ.  Nguyên nhân một tiến trình thay đổi trạng thái :  Phải chờ một sự kiện nào đĩ xảy ra  Đợi một thao tác nhập/xuất hồn tất  Buộc phải dừng hoạt động do đã hết thời gian xử lý … 35 36 ready running dispatch interrupt I/O or event completion I/O or event wait new terminated waiting admit exit 37 Các trạng thái của tiến trình  New (Mới tạo): tiến trình đang được tạo lập.  Running (thực hiện): Là trạng thái mà tiến trình đang được sở hữu processor để hoạt động  Blocked hay waiting (khố): Là trạng thái mà tiến trình đang chờ để được cấp phát thêm tài nguyên hay chờ một sự kiện xảy ra .  Ready : là trạng thái của một tiến trình trong hệ thống đã cĩ đủ tài nguyên, đang chờ được cấp processor để bắt đầu thực hiện.  Kết thúc (terminated): tiến trình hồn tất xử lý. Tại một thời điểm, chỉ cĩ một tiến trình cĩ thể nhận trạng thái running trên một bộ xử lý bất kỳ. Trong khi đĩ, nhiều tiến trình cĩ thể ở trạng thái blocked hay ready 2.2. Cấu trúc dữ liệu khối quản lý tiến trình 38 Khối quản lý tiến trình hay Khối điều khiển tiến trình (process control block - PCB).  Quản lý mọi hoạt động của tiến trình  Cấu trúc dữ liệu của khối điều khiển bao gồm:  Định danh tiến trình  Trạng thái của tiến trình  Ngữ cảnh của tiến trình  Thơng tin giao tiếp  Thơng tin thống kê status pid Waiting list CPU-state-rec Processor Main store Resource Created recource Parent Progency Priority CPU time Unit 1 Unit 2 RCB 1 RCB 2 RCB 1 RCB 2 PCB PCB 1 PCB 2 … (3) Ngữ cảnh của trình (4) Thơng tin giao tiếp (5) Thơng tin thống kê (2) Trạng thái trình (1) Định danh trình 39 40 Cấu trúc dữ liệu khối quản lý tiến trình  Định danh của tiến trình (1) : giúp phân biệt các tiến trình  Trạng thái tiến trình (2): xác định hoạt động hiện hành của tiến trình.  Ngữ cảnh của tiến trình (3): mơ tả các tài nguyên tiến trình đang trong quá trình, hoặc để phục vụ cho hoạt động hiện tại, hoặc để làm cơ sở phục hồi hoạt động cho tiến trình, bao gồm các thơng tin về:  Trạng thái CPU: nội dung các thanh ghi, quan trọng nhất là con trỏ lệnh IP lưu trữ địa chỉ câu lệnh kế tiếp tiến trình sẽ xử lý. Các thơng tin này cần được lưu trữ khi xảy ra một ngắt, nhằm cĩ thể cho phép phục hồi hoạt động của tiến trình đúng như trước khi bị ngắt. 41 Ngữ cảnh của tiến trình (3)  Bộ xử lý: dùng cho máy cĩ cấu hình nhiều CPU, xác định số hiệu CPU mà tiến trình đang sử dụng.  Bộ nhớ chính: danh sách các khối nhớ được cấp cho tiến trình.  Tài nguyên sử dụng: danh sách các tài nguyên hệ thống mà tiến trình đang sử dụng.  Tài nguyên tạo lập: danh sách các tài nguyên được tiến trình tạo lập. 42 Cấu trúc dữ liệu khối quản lý tiến trình  Thơng tin giao tiếp (4): phản ánh các thơng tin về quan hệ của tiến trình với các tiến trình khác trong hệ thống :  Tiến trình cha: tiến trình tạo lập tiến trình này .  Tiến trình con: các tiến trình do tiến trình này tạo lập .  Độ ưu tiên : giúp bộ điều phối cĩ thơng tin để lựa chọn tiến trình được cấp CPU.  Thơng tin thống kê (5): thống kê về hoạt động của tiến trình  Thời gian đã sử dụng CPU  Thời gian chờ.  Các thơng tin này cĩ thể cĩ ích cho cơng việc đánh giá tình hình hệ thống và dự đốn các tình huống tương lai. Lưu đồ chuyển CPU từ tiến trình này sang tiến trình khác 43 44 Process table 45 Process table  Hệ điều hành lưu con trỏ tới từng PCB của mỗi tiến trình trong một bảng tiến trình của tồn hệ thống hoặc từng người dùng.  Truy cập nhanh tới các PCB  Khi một tiến trình bị dừng, hệ điều hành loại bỏ tiến trình khỏi bảng tiến trình và giải phĩng tất cả các tài nguyên của tiến trình 46 2.3. Thao tác trên tiến trình  Tạo lập tiến trình (create)  Kết thúc tiến trình (destroy)  Tạm dừng tiến trình (suspend)  Tái kích hoạt tiến trình (resume)  Thay đổi độ ưu tiên tiến trình 3. TÀI NGUYÊN GĂNG VÀ ĐIỀU ĐỘ TIẾN TRÌNH 3.1. Tài nguyên găng (Critical Resource)  Trong mơi trường đa nhiệm dẫn đến dùng chung tài nguyên -> cạnh tranh.  Xung đột được thể hiện: Hai tiến trÌnh hoạt động đồng thời cùng ghi vào một khơng gian nhớ chung (một biến chung) trên bộ nhớ hay hai cùng ghi dữ liệu vào một file chia sẻ.  Những tài nguyên được hệ điều hành chia sẻ cho nhiều tiến trÌnh hoạt động đồng thời dùng chung, mà cĩ nguy cơ dẫn đến sự tranh chấp được gọi là tài nguyên găng.  Tài nguyên găng cĩ thể là tài nguyên phần cứng hoặc tài nguyên phần mềm, cĩ thể là tài nguyên phân chia được hoặc khơng phân chia được. 48 Tài nguyên găng (Critical Resource) Ví dụ: bài tốn rút tiền ngân hàng từ tài khoản dùng chung If (tài khoản – tiền rút >=0) tài khoản:=tài khoản – tiền rút Else Thơng báo lỗi endif 49 3.2 Đoạn găng (Critical Section)  Các đoạn code trong các chương trình dùng để truy cập đến tài nguyên găng được gọi là đoạn găng  Để hạn chế lỗi cĩ thể xảy ra do sử dụng tài nguyên găng, tại 1 thời điểm HĐH chỉ cho 1 tiến trình nằm trong đoạn găng  HĐH cĩ cơ chế điều độ tiến trình qua đoạn găng 50 51  Trong kho¶ng thêi gian tiÕn tr×nh sư dơng tµi nguyªn g¨ng th× ta gäi ®ã lµ tiÕn tr×nh g¨ng.  Mét tiÕn tr×nh cã thĨ chia lµm 2 ®o¹n : ®o¹n g¨ng vµ ®o¹n cßn l¹i. 2.3 Yêu cầu của cơng tác điều độ tiến trình qua đoạn găng  Tại 1 thời điểm chỉ cho phép 1 tiến trình nằm trong đoạn găng, các tiến trình khác cĩ nhu cầu vào đoạn găng phải chờ  Tiến trình chờ ngồi đoạn găng khơng được ngăn cản các tiến trình khác vào đoạn găng  Khơng cĩ tiến trình nào phải chờ lâu để được vào đoạn găng  Đánh thức các tiến trình trong hàng đợi để tạo điều kiện cho nĩ vào đoạn găng khi tài nguyên găng được giải phĩng 52 53 Điều độ tiến trình qua đoạn găng Cã 2 møc ®é ®iỊu ®é s¬ cÊp vµ cao cÊp.  ë møc s¬ cÊp  c¸c lƯnh ®iỊu ®é ®-ỵc ®Ỉt ngay trong ch-¬ng tr×nh ng-êi dïng: Kü thuËt khãa trong (®Ìn hiƯu), Kü thuËt kiĨm tra vµ x¸c lËp, Kü thuËt semaphore  §iỊu ®é cao cÊp  lƯnh ®iỊu ®é ®Ỉt trong thµnh phÇn hƯ ®iỊu hµnh.  ch-¬ng tr×nh ®iỊu phèi c«ng viƯc vµ ®iỊu phèi chÝnh  Ng-êi sư dơng kh«ng biÕt tµi nguyªn g× vµ khi nµo thuéc lo¹i g¨ng => HƯ thèng ph¶i cã tr¸ch nhiƯm kiĨm tra. nhËn biÕt vµ ®iỊu ®é: Dïng ch-¬ng tr×nh monitor (th- ký) ®Ĩ ®iỊu ®é 4. TẮC NGHẼN VÀ CHỐNG TẮC NGHẼN 4.1 Tắc nghẽn (Deadlock)  Tắc nghẽn: Hiện tượng bắt nguồn từ sự xung đột về tài nguyên của hai hoặc nhiều tiến trình đang hoạt động đồng thời trên hệ thống. 55 56 57 4.2. §iỊu kiƯn x¶y ra Tắc nghẽn 4 điều kiện cần cĩ thể làm xuất hiện tắc nghẽn:  Cĩ sử dụng tài nguyên khơng thể chia sẻ (Mutual exclusion): Mỗi thời điểm, một tài nguyên khơng thể chia sẻ được hệ thống cấp phát chỉ cho một tiến trình, khi tiến trình sử dụng xong tài nguyên này, hệ thống mới thu hồi và cấp phát tài nguyên cho tiến trình khác. 58  Sự chiếm giữ và yêu cầu thêm tài nguyên (Wait for): Các tiến trình tiếp tục chiếm giữ các tài nguyên đã cấp phát cho nĩ trong khi chờ được cấp phát thêm một số tài nguyên mới.  Khơng thu hồi tài nguyên từ tiến trình đang giữ chúng: Tài nguyên khơng thể được thu hồi từ tiến trình đang chiếm giữ chúng trước khi tiến trình này sủ dụng chúng xong. 59  Tồn tại một chu kỳ trong đồ thị cấp phát tài nguyên (Circular wait): cĩ ít nhất hai tiến trình chờ đợi lẫn nhau: tiến trình này chờ được cấp phát tài nguyên đang bị tiến trình kia chiếm giữ và ngược lại (Đợi vịng trịn). => Khi cĩ đủ 4 điều kiện này, thì tắc nghẽn xảy ra. 4.3. Các mức phịng tránh tắc nghẽn  Ngăn ngừa  Dự báo và tránh tắc nghẽn  Nhận biết và khắc phục 60 61 Các phương pháp xử lý tắc nghẽn 3 hướng tiếp cận để xử lý tắc nghẽn :  Sử dụng một quy tắc (protocol) để bảo đảm rằng hệ thống khơng bao giờ xảy ra tắc nghẽn.  Cho phép xảy ra tắc nghẽn và tìm cách sữa chữa tắc nghẽn.  Hồn tồn bỏ qua việc xử lý tắc nghẽn, xem như hệ thống khơng bao giờ xảy ra tắc nghẽn. 5. ĐIỀU PHỐI TIẾN TRÌNH 63  Trong mơi trường hệ điều hành đa nhiệm, bộ phận điều phối tiến trình cĩ nhiệm vụ xem xét và quyết định khi nào thì dừng tiến trình hiện tại để thu hồi processor và chuyển processor cho tiến trình khác, và khi đã cĩ được processor thì chọn tiến trình nào trong số các tiến