Vì sao đối với sơ đồ tiến trình 5 trạng thái phải thiết kế 2 trạng thái suspend?

TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘIKHOA CÔNG NGHỆ THÔNG TIN________________________________________BÀI TẬP LỚNNGUYÊN LÝ HỆ ĐIỀU HÀNHĐỀ TÀINghiên cứu tìm hiểu về quản lí tiến trình trongHệ điều hành Windows- - - - - - - - - - - - - - - - - - - Giáo viên hướng dẫn : ThS. Nguyễn Thanh HảiNhóm số: xMã lớp: IT6025Hà Nội, 2020 TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘIKHOA CÔNG NGHỆ THÔNG TIN________________________________________BÀI TẬP LỚNNGUYÊN LÝ HỆ ĐIỀU HÀNHĐỀ TÀINghiên cứu tìm hiểu về quản lí tiến trình trongHệ điều hành Windows- - - - - - - - - - - - - - - - - - - Giáo viên hướng dẫn : ThS. Nguyễn Thanh HảiMã lớp: IT6025Sinh viên thực hiện :-A-B-C-DHà Nội, 2020 MỤC LỤCLỜI NÓI ĐẦU .................................................................................................................1CHƯƠNG 1: TỔNG QUAN VỀ TIẾN TRÌNH .............................................................21.1. Tiến trình?.............................................................................................................21.2. Các trạng thái của một tiến trình ..........................................................................31.3. Quan hệ giữa các tiến trình .................................................................................101.4. Ví dụ về tiến trình song hành và Bài tốn sản xuất người tiêu dùng [Producer/Consumer Problem] ...................................................................................................10CHƯƠNG 2: TÀI NGUYÊN GĂNG VÀ ĐOẠN TỚI HẠN .......................................132.1. Tài nguyên “găng” và đoạn tới hạn ....................................................................132.2. Các phương pháp giải quyết bài toán đoạn tới hạn ............................................17CHƯƠNG 3: HIỆN TƯỢNG BẾ TẮC .........................................................................243.1. KHÁI NIỆM .......................................................................................................243.2. ĐIỀU KIỆN XẢY RA BẾ TẮC .........................................................................243.3. CÁC MỨC PHÒNG TRÁNH BẾ TẮC .............................................................253.4. CÁC BIỆN PHÁP PHỊNG TRÁNH BẾ TẮC..................................................25CHƯƠNG 4: ĐIỀU PHỐI TIẾN TRÌNH .....................................................................304.1. MỤC TIÊU ĐIỀU PHỐI ....................................................................................304.2. TỔ CHỨC ĐIỀU PHỐI TIẾN TRÌNH ..............................................................334.3. CHIẾN LƯỢC ĐIỀU PHỐI ...............................................................................36CHƯƠNG 5: QUẢN LÝ TIẾN TRÌNH TRÊN WINDOWS .......................................405.1. Tiến trình trong Windows NT ............................................................................405.2. Quản lý tiến trình trên Windows 10 ...................................................................44 DANH MỤC ẢNHẢnh 1.1: Mô tả chuyển trạng thái của tiến trình .......................................................4Ảnh 1.2: Sơ đồ chuyển trạng thái tiến trình ..............................................................5Ảnh 1.3: Sơ đồ chuyển tiến trình vào hàng đợi ........................................................5Ảnh 1.4: Sơ đồ chuyển trạng thái tiến trình ..............................................................6Ảnh 1.5: Sơ đồ chuyển tiến trình vào các hàng đợi ..................................................7Ảnh 1.6: Sơ đồ chuyển trạng thái tiến trình có suspend ...........................................8Ảnh 1.7: Sơ đồ chuyển trạng thái tiến trình với 2 suspend .......................................9Ảnh 4.1: Các danh sách điều phối ..........................................................................34Ảnh 4.2: Sơ đồ chuyển đổi giữa các danh sách điều phối ......................................34Ảnh 4.3: Cấp độ điều phối trung gian .....................................................................36Ảnh 4.4: Minh họa FCFS ........................................................................................36Ảnh 4.5: Minh họa SJF ...........................................................................................37Ảnh 4.6: Minh họa RR ............................................................................................38Ảnh 5.1: Tiến trình và các tài nguyên của nó .........................................................41Ảnh 5.2: Task Manager trên Windows 10 ..............................................................44Ảnh 5.3: Chế độ đơn giản Task Manager ...............................................................45Ảnh 5.4: Tab Processes trong Task Manager .........................................................48Ảnh 5.5: Tab Performance quản lý tài nguyên hệ thống trong Task Manager .......49Ảnh 5.6: Tab Start-up hiển thị các tiến trình sẽ được khởi động cùng Windows ..50Ảnh 5.7: Tab Users trong Task Manager ................................................................51Ảnh 5.8: Tab Details trong Task Manager .............................................................51Ảnh 5.9: Tab Services trong Task Manager ...........................................................53Ảnh 5.10: Khởi tạo tiến trình và chạy tiến trình mới ..............................................53Ảnh 5.11: Analyse wait chain .................................................................................54Ảnh 5.12: Trình quản lý tác vụ Process Explorer ...................................................55 LỜI NĨI ĐẦUTrong những máy tính thế hệ đầu tiên, tại một thời điểm cụ thể chỉ có duy nhấtmột chương trình được phép chạy và sử dụng tồn bộ tài nguyên hệ thống. Các hệ thốngmáy tính hiện đại đều cho phép tải nhiều chương trình vào bộ nhớ trong để thực thi đồngthời. Như vậy, cần có cơ chế đan xen hoạt động của các chương trình khác nhau. Nhucầu này dẫn đến sự xuất hiện khái niệm “tiến trình” – là chương trình đang trong quátrình thực thi. Tiến trình là đơn vị thực thi cơ sở trong hệ thống chia sẻ thời gian thực.Trong hệ điều hành đa chương tại một thời điểm luôn tồn tại nhiều tiến trình nhưng nólại có những tài ngun hữu hạn. Vì vậy hệ điều hành phải có cơ chế cấp phát tài nguyêncho tiến trình theo cơ chế định trước và cơ chế cho phép tiến trình trao đổi thơng tin vớinhau. Như vậy, hệ điều hành phải có cơ chế quản lý các tiến trình để hạn chế tối đa xungđột và bế tắc xảy ra cũng như tận dụng tối đa khả năng của CPU.Để giúp hiểu rõ hơn về cơ chế quản lý tiến trình của hệ điều hành, nhất là hệ điềuhành phổ biến trên máy tính cá nhân như Windows, nhóm chúng em xin được trình bàysơ lược về quản lý tiến trình trong hệ điều hành Windows. Tài liệu gồm những nội dungchính sau:Chương 1: Nội dung của chương trình bày cơ bản về tiến trình, trạng thái cảu tiếntrình, quan hệ giữa các tiến trình.Chương 2: Tài nguyên “găng” và các phương pháp sử dụng tài nguyên găng hợplý.Chương 3: Hiện tượng bế tắc và giải quyết bế tắc.Chương 4: Cơ chế để hệ điều hành có thể điều phối các tiến trình giữa các hàngđợi để phân bổ tài nguyên CPU cho hợp lý.Chương 5: Quản lý tiến trình trên Windows NT và cơng cụ quản lý tiến trìnhTask Manager trên Windows 10.Bài tập lớn được hoàn thành bằng sự cộng tác của các thành viên nhóm cùng sựhướng dẫn của thầy Nguyễn Thanh Hải. Nội dung bài tập không tránh khỏi thiếu xótmong nhận thêm phản ánh và góp ý từ phía thầy và q bạn đọc.Thân ái!Nhóm sinh viên thực hiện1 CHƯƠNG 1: TỔNG QUAN VỀ TIẾN TRÌNH1.1. Tiến trình?1.1.1. Khái niệm tiến trìnhĐể hỗ trợ hoạt động đa nhiệm, hệ thống máy tính cần phải có khả năng thực hiệnnhiều tác vụ xử lí đồng thời nhưng việc điều khiển hoạt động song hành ở cấp dộ phầncứng là rất khó khắn. Vì vậy, các nhà thiết kế hệ điều hành đề xuất một mơ hình songhành giả lập bằng cách chuyển đổi bộ xử lý qua lại giữa các chương trình để duy trì hoạyđộng của nhiều chương trình tại cùng một thời điểm. Trong mơ hình này, các hệ thốngđược tổ chức thành các tiến trình [process].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ựchiện, đơn vị thực hiện tiến trình là processer. Ở đây chúng tơi nhấn mạnh thêm rằng: Vìtiến trình là một bộ phận của chương trình nên tương tự như chương trình tiến trình cũngsở 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 địachỉ 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.Khái niệm trên đây mang tính trực quan, để thấy được bản chất của tiến trình cácchuyên gia về hệ điều hành đã đưa ra nhiều định nghĩa khác nhau về tiến trình. Địnhnghĩa của Saltzer: Tiến trình là một chương trình do một processor logic thực hiện. Địnhnghĩa của Horning & Rendell: Tiến trình là một quá trình chuyển từ trạng thái này sangtrạ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 đầunào đó.Cần phân biệt rõ hai khái niệm chương trình và tiến trình. Chương trình là mộtthực thể thụ động chứa đựng các chỉ thị điều khiển máy tính thi hành một tác vụ cụ thểnào đó. Khi cho thực hiện các chỉ thị này, với con trỏ lệnh xác định chỉ thị kế tiếp sẽ thihành kèm theo các tập tài nguyên phục vụ cho hoạt động của tiến trình.1.1.2. Phân loại tiến trìnhCác loại tiến trình: Các tiến trình trong hệ thống có thể chia thành hai loại: tiếntrình tuần tự và tiến trình song song. Tiến trình tuần tự là các tiến trình mà điểm khởitạ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ìnhmà đ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, tức là có thể2 khởi tạo một tiến trình mới khi các tiến trình trước đó chưa kết thúc. Tiến trình songsong được chia thành nhiều loại:• Tiến trình song song độc lập: là các tiến trình hoạt động song song nhưngkhơng có quan hệ thông tin với nhau, trong trường hợp này hệ điều hành phải thiết lậpcơ chế bảo vệ dữ liệu của các tiến trình, và cấp phát tài nguyên cho các tiến trình mộtcách hợp lý.• Tiến trình song song có quan hệ thơng tin: trong q trình hoạt động các tiếntrình thường trao đổi thơng tin với nhau, trong một số trường hợp tiến trình gởi thơngbáo cần phải nhận được tín hiệu từ tiến trình nhận để tiếp tục, điều này dễ dẫn đến bếtắc khi tiến trình nhận tín hiệu khơng ở trong trạng thái nhận hay tiến trình gởi khơngở trong trạng thái nhận thơng báo trả lời.• Tiến trình song song phân cấp: Trong qua trình hoạt động một tiến trình cóthể khởi tạo các tiến trình khác hoạt động song song với nó, tiến trình khởi tạo đượcgọi là tiến trình cha, tiến trình được tạo gọi là tiến trình con. Trong mơ hình này hệđiều hành phải giải quyết vấn đề cấp phát tài nguyên cho các tiến trình con. Tiến trìnhcon nhận tài nguyên ở đâu, từ tiến trình cha hay từ hệ thống. Để giải quyết vấn đề nàyhệ điều hành đưa ra 2 mơ hình quản lý tài ngun: Thứ nhất, mơ hình tập trung, trongmơ hình này hệ điều hành chịu trách nhiệm phân phối tài nguyên cho tất cả các tiếntrình trong hệ thống. Thứ hai, mơ hình phân tán, trong mơ hình này hệ điều hành chophép tiến trình con nhận tài nguyên từ tiến trình cha, tức là tiến trình khởi tạo có nhiệmvụ nhận tài nguyên từ hệ điều hành để cấp phát cho các tiến trình mà nó tạo ra, và nócó nhiệm vụ thu hồi lại tài nguyên đã cấp phát trả về cho hệ điều hành trước khi kếtthúc.• Tiến trình song song đồng mức: là các tiến trình hoạt động song song sử dụngchung tài nguyên theo nguyên tắc lần lượt, mỗi tiến trình sau một khoảng thời gianchiếm giữ tài nguyên phải tự động trả lại tài nguyên cho tiến trình kia.1.2. Các trạng thái của một tiến trìnhTừ khi được đưa vào hệ thống cho đến khi kết thúc tiến trình tồn tại ở các trạngthái khác nhau. 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 độnghiện thời của tiến trình tại thời điểm đó.3 Là một thưc thể động, tiến trình có thể thuộc những trạng thái khác nhau.Có nhiều cách phân biệt trạng thái tiến trình. Theo cách đơn giản nhất. Tiến trìnhthuộc một trong hai trạng thái: chạy và không chạy. Chạy là khi các lệnh của tiến trìnhđược CPU thực hiện và khơng chạy là trường hợp ngược lại, ví dụ khi CPU đang đượcphân phối cho tiến trình khác hoặc khi tiến trình phải dừng để chờ kết quả vào/ra.Cách sử dụng hai trạng thái tiến trình là quá đơn giản và không đủ để phản ánhđầy đủ thông tin về trạng thái tiến trình. Trên thưc tế, hệ điều hành thường phân biệtnăm trạng thái khác nhau của tiến trình. Ý nghĩa cụ thể năm trạng thái như sau:- Trạng thái khởi tạo [New]: tiến trình đang được tạo lập.- Trạng thái sẵn sàng; [Ready]: tiến trình chờ được cấp phát CPU để xử lý.- Trạng thái thưc hiện [Running]: tiến trình được xử lý.- Trạng thái đợi [Waiting]: tiến trình phải dừng vì thiếu tài nguyên hoặc chờ 1 sựkiện nào đó.- Trạng thái kết thúc [Halt]: tiến trình đã hồn tất cơng việc xử lý.Ảnh 1.1: Mơ tả chuyển trạng thái của tiến trình➢Tiến trình hai trạng thái: Một số ít hệ điều hành chỉ cho phép tiến trình tồn tạiở một trong hai trạng thái: Not Running và Running. Khi hệ điều hành tạo ra một tiếntrình mới, hệ điều hành đưa tiến trình đó vào hệ thống ở trạng thái Not Running, tiếntrình ở trạng thái này để chờ được chuyển sang trạng thái Running. Vì một lý do nào đó,4 tiến trình đang thực hiện bị ngắt thì bộ điều phối tiến trình của hệ điều hành sẽ thu hồilại processor của tiến trình này và chọn một tiến trình ở trạng thái Not running để cấpprocessor cho nó và chuyển nó sang trạng thái Running. Tiến trình bị thu hồi processorsẽ được chuyển về lại trạng thái Not running.DispatchEnterExitNotRunningRunningPauseẢnh 1.2: Sơ đồ chuyển trạng thái tiến trìnhTại một thời điểm xác định chỉ có duy nhất một tiến trình ở trạng thái Runnig,nhưng có thể có nhiều tiến trình ở trạng thái Not running, các tiến trình ở trạng thái Notrunning được chứa trong một hàng đợi [Queue]. Tiến trình đang ở trạng thái Running bịchuyển sang trạng thái Not running sẽ được đưa vào hàng đợi. Hình vẽ sau đây mơ tảviệc chuyển trạng thái tiến trình trong các hệ điều hành sử dụng 2 trạng thái tiến trình.QueueEnterDispatchExProcessorPauseẢnh 1.3: Sơ đồ chuyển tiến trình vào hàng đợi➢Tiến trình ba trạng thái: Đa số hệ điều hành đều cho phép tiến trình tồntại ở một trong ba trạng thái, đó là: ready, running, blocked:• Trạng thái Ready [sẵn sàng]: Ngay sau khi khởi tạo tiến trình, đưa tiến trìnhvào hệ thống và cấp phát đầy đủ tài nguyên [trừ processor] cho tiến trình, hệ điều hànhđưa tiến trình vào trạng thái ready. Hay nói cách khác, trạng thái ready là trạng thái củamột tiến trình trong hệ thống đang chờ được cấp processor để bắt đầu thực hiện.• Trạng thái Running [thực hiện]: Là trạng thái mà tiến trình đang được sở hữuprocessor để hoạt động, hay nói cách khác là các chỉ thị của tiến trình đang được thựchiện/ xử lý bởi processor.• Trạng thái Blocked[khố]: Là trạng thái mà tiến trình đang chờ để được cấp5 phát thêm tài nguyên, để một sự kiện nào đó xảy ra, hay một quá trình vào/ra kết thúc.Quá trình chuyển trạng thái của các tiến trình trong được mơ tả bởi sơ đồ sau:New124ReadyRunning36blocked5ExitẢnh 1.4: Sơ đồ chuyển trạng thái tiến trìnhTrong đó:1.[Admit] Tiến trình được khởi tạo, được đưa vào hệ thống, được cấp phátđầy đủ tài nguyên chỉ thiếu processor.2.[Dispatch] Tiến trình được cấp processor để bắt đầu thực hiện/ xử lý.3.[Release] Tiến trình hồn thành xử lý và kết thúc.4.[Time_out] Tiến trình bị bộ điều phối tiến trình thu hồi processor, do hếtthời gian được quyền sử dụng processor, để cấp phát cho tiến trình khác.5.[Event wait] Tiến trình đang chờ một sự kiện nào đó xảy ra hay đang chờmột thao vào/ra kết thúc hay tài nguyên mà tiến trình yêu cầu chưa được hệ điềuhành đáp ứng.6.[Event Occurs] Sự kiện mà tiến trình chờ đã xảy ra, thao tác vào/ra mà tiếntrình đợi đã kết thúc, hay tài nguyên mà tiến trình yêu cầu đã được hệ điều hànhđáp ứng,Bộ phận điều phối tiến trình thu hồi processor từ một tiến trình đang thực hiệntrong các trường hợp sau:Tiến trình đang thực hiện hết thời gian [time-out] được quyền sử dụngprocessor mà bộ phận điều phối dành cho nó.Có một tiến trình mới phát sinh và tiến trình mới này có độ ưu tiên caohơn tiến trình hiện tại.Có một tiến trình mới phát sinh và tiến trình này mới cần một khoảng thời6 gian của processor nhỏ hơn nhiều so với khoảng thời gian cịn lại mà tiến trình hiện tạicần processor.Tại một thời điểm xác định trong hệ thống có thể có nhiều tiến trình đang ở trạngthái Ready hoặc Blocked nhưng chỉ có một tiến trình ở trạng thái Running. Các tiếntrình ở trạng thái Ready và Blocked được chứa trong các hàng đợi [Queue] riêng.Ready QueueAdmitReleaseDispatchProcessorTime-outEventOccursEvent WaitBlocked QueueẢnh 1.5: Sơ đồ chuyển tiến trình vào các hàng đợiCó nhiều lý do để một tiến trình đang ở trạng thái running chuyển sang trạng tháiblocked, do đó đa số các hệ điều hành đều thiết kế một hệ thống hàng đợi gồm nhiềuhàng đợi, mỗi hành đợi dùng để chứa những tiến trình đang đợi cùng một sự kiện nàođó.➢Tiến trình 4 trạng thái: Trong môi trường hệ điều hành đa nhiệm thì việctổ chức các Queue để lưu các tiến trình chưa thể hoạt động là cần thiết, nhưngnếu tồn tại q nhiều tiến trình trong Queue, hay chính xác hơn trong bộ nhớ chính, sẽdẫn đến trình trạng lãng phí bộ nhớ, khơng cịn đủ bộ nhớ để nạp các tiến trình khác khicần thiết. Mặt khác nếu các tiến trình trong Queue đang chiếm giữ tài nguyên của hệthống, mà những tài nguyên này lại là những tài nguyên các tiến trình khác đang cần,điều này dẫn đến tình trạng sử dụng tài ngun khơng hợp lý, làm cho hệ thống thiếu tàinguyên [thực chất là thừa] trầm trọng và có thể làm cho hệ thống tắc nghẽn. Với nhữnglý do trên các hệ điều hành đa nhiệm thiết kế thêm một trạng thái tiến trình mới, đó làtrạng thái Suspend [tạm dừng]. Trạng thái này rất cần thiết cho các hệ thống sử dụng kỹthuật Swap trong việc cấp phát bộ nhớ cho các tiến trình. Khái niệm Swap sẽ được đềcập đến trong chương Quản lý bộ nhớ của tài liệu này.7 NewReadyRunningActivateEndSuspendBlockedSuspendẢnh 1.6: Sơ đồ chuyển trạng thái tiến trình có suspendTrạng thái Suspend là trạng thái của một tiến trình khi nó đang được lưu trữ trênbộ nhớ phụ, hay chính xác hơn đây là các tiến trình đang ở trong trạng thái blockedvà/hoặc ready bị hệ điều hành chuyển ra đĩa để thu hồi lại không gian nhớ đã cấp chotiến trình hoặc thu hồi lại tài nguyên đã cấp cho tiến trình để cấp cho một tiến trình khácđang rất cần được nạp vào bộ nhớ tại thời điểm hiện tại.➢Tiến trình 5 trạng thái: Trong thực tế hệ điều hành thiết kế 2 trạng thái suspend,một trạng thái suspend dành cho các tiến trình từ blocked chuyển đến, trạng thái nàyđược gọi là blocked-suspend và một trạng thái suspend dành cho các tiến trình từ readychuyển đến, trạng thái này được gọi là ready-suspend.Tới đây ta có thể hiểu các trạng thái tiến trình như sau:Ở trạng thái Ready tiến trình được định vị trong bộ nhớ chính và đang chờđược cấp processor để thực hiện.Ở trạng thái Blocked tiến trình được định vị trong bộ nhớ chính và đangđợi một sự kiện hay một q trình I/O nào đó.Ở trạng thái Blocked-suspend tiến trình đang bị chứa trên bộ nhớ phụ [đĩa]và đang đợi một sự kiện nào đó.Ở trạng thái Ready-suspend tiến trình đang bị chứa trên bộ nhớ phụ nhưngsẵn sàng thực hiện ngay sau khi được nạp vào bộ nhớ chính.8 AdmitNAdmitSuspendActivateReadyReadysuspendRunningReleaseSuspendEvent OccursEventBlockedsuspendExitBlockedActivateẢnh 1.7: Sơ đồ chuyển trạng thái tiến trình với 2 suspendSau đây chúng ta xem xét sự chuyển trạng thái tiến trình trong sơ đồ trên:Blocked sang Blocked-suspend: nếu khơng cịn tiến trình ready trong bộ nhớchính và bộ nhớ chính khơng cịn khơng gian nhớ trống thì phải có ít nhất một tiến trìnhblocked bị chuyển ra ngồi, blocked-suspend, để dành bộ nhớ cho một tiến trình khơngbị khố [not blocked] khác.Blocked-suspend sang Ready-suspend: một tiến trình đang ở trạng thái blockedsuspend được chuyển sang trạng thái ready-suspend khi sự kiện mà nó đợi đã xảy ra.1.Ready-suspend sang Ready: có 2 lý do để hệ điều hành chọn khi chuyểnmột tiến trình ở trạng thái ready-suspend sang trạng thái ready:Khơng cịn tiến trình ready trong bộ nhớ chính, hệ điều hành phảinạp một tiến trình mới vào để nó tiếp tục thực hiệnNếu có tiến trình ready-suspend có độ ưu tiên cao hơn so với các tiếntrình ready hiện tại thì hệ điều hành có thể chuyển nó sang trạng thái ready đểnó nhiều cơ hội để được thực hiện hơn.2.Ready sang Ready suspend: Hệ điều hành thường chuyển các tiến trìnhblocked sang suspend hơn là các tiến trình ready, vì các tiến trình ở trạng thái blockedkhông thể thực hiện ngay lập tức nhưng lại chiếm nhiều khơng gian bộ nhớ chính hơnso với các tiến trình ở trạng thái ready. Tuy nhiên, nếu việc chọn tiến trình để chuyểnsang suspend dựa vào 2 điều kiện: chiếm ít khơng gian bộ nhớ hơn và có độ ưu tiên thấphơn thì hệ điều hành có thể chuyển một tiến trình ready sang trạng thái suspend.9 1.3. Quan hệ giữa các tiến trìnhCác tiến trình hoạt động trong hệ thống tồn tại 2 mối quan hệ là: Độc lập và Hợptác [song hành]*Quan hệ độc lậpTiến trình được gọi là độc lập nếu hoạt động của nó khơng gây ảnh hưởng vàkhơng bị ảnh hưởng bởi các tiến trình khác cũng đang hoạt động của hệ thống.Tiến trình độc lập có những đặc trưng sau:-Trạng thái của nó khơng bị chia sẻ với bất kì tiến trình nào khác.-Việc thực hiện tiến trình là đơn định [kết quả chỉ phụ thuộc vào đầu vào].-Tiến trình có thể tái hiện [lặp lại].-Tiến trình có thể dừng hoặc bắt đầu lại mà không gây ảnh hưởng tới cáctiến trình khác trong hệ thống.*Quan hệ hợp tácTiến trình được gọi là hợp tác [song hành] nếu hoạt động của nó gây ảnh hưởnghoặc bị ảnh hưởng bởi các tiến trình khác cũng đang hoạt động trong hệ thống. Tiếntrình hợp tác có những đặc trưng sau:-Trạng thái của nó bị chia sẻ cho các tiến trình khác.-Việc thực hiện tiến trình là khơng đơn định [kết quả phụ thuộc dãy thựchiện tương ứng và khơng dự báo trước].-Tiến trình khơng thể tái hiện.1.4. Ví dụ về tiến trình song hành và Bài toán sản xuất người tiêu dùng[Producer/ Consumer Problem]Bài tốn: Giả sử có 2 tiến trình P và C song hành. Tiến trình P cung cấp thơngtin cho hoạt động của tiến trình C. Thơng tin do P sản xuất được đăt trong vùng đệm vàC lấy thông tin từ vùng đệm để sử dụng. Trong trường hợp vùng đệm có kích thước hạnchế, hãy xây dựng thuật tốn điều khiển hoạt động của hai tiến trình trên.Thuật tốn: Khi kích thước vùng đệm hạn chế sẽ xảy ra hai trường hợp:-Vùng đệm đầy, khi đó tiến trình P phải ở trạng thái phải chờ cho tới khi cóvùng đệm rỗng.10 -Vùng đệm rỗng, khi đó tiến trình C phải ở trạng thái phải chờ cho tới khi cóthơng tin trong vùng đệm.Giả sử:-Vùng đệm chứa được n phần tử;-Thông tin có kiểu Item nào đó;-Biến In chỉ số phân tử được sản xuất;-Biến Out chỉ số phân tử được tiêu thụ;-Tiến trình P sản xuất thơng tin chứa trong biến trung gian NextP;-Tiến trình C tiêu thụ thơng tin chứa trong biến trung gian NextC.Khi đó:-Vùng đệm rỗng khi In= Out;-Vùng đệm đầy khi [ In +1] mod n= Out.Thuật toán:TypeVarItem=…;Buffer: array [0..n - 1] of Item;In, Out: 0..n – 1Begin{ Tiến trình P}Repeat…Sản xuất thơng tin và chứa trong Next P;…While [In + 1] mod n= Out do Skip;Buffer[In]:= NextPIn:= In + 1 mod n;Until false;{ Tiến trình C}RepeatWhile In = Out do Skip;NextC:= Buffer[Out];Out:= Out +1 mod n…Lấy thông tin trong chứa trong NextC…11 Until false;End;12 CHƯƠNG 2: TÀI NGUYÊN GĂNG VÀ ĐOẠN TỚI HẠN2.1. Tài nguyên “găng” và đoạn tới hạn2.1.1. Tài nguyên găng [Critical Resource]Trong môi trường hệ điều hành đa nhiệm - đa chương – đa người sử dụng, việcchia sẻ tài nguyên cho các tiến trình của người sử dụng dùng chung là cần thiết, nhưngnếu hệ điều hành không tổ chức tốt việc sử dụng tài nguyên dung chung của các tiếntrình hoạt động đồng thời, thì khơng những khơng mang lại hiệu quả khai thác tài nguyêncủa hệ thống mà còn làm hỏng dữ liệu của các ứng dụng. Và nguy hiểm hơn là việc hỏngdữ liệu này có thể hệ điều hành và ứng dụng không thể phát hiện được. Việc hỏng dữliệu của ứng dụng có thể làm sai lệch ý nghĩa thiết kế của nó. Đây là điều mà cả hệ điềuhành và người lập trình đều khơng mong muốn.Các tiến trình hoạt động đồng thời thường cạnh tranh với nhau trong việc sử dụngtài nguyên dùng chung. Hai tiến trình hoạt động đồng thời cùng ghi vào một không giannhớ chung [một biến chung] trên bộ nhớ hay hai tiến trình đồng thời cùng ghi dữ liệuvào một file chia sẻ, đó là những biểu hiện của sự cạnh tranh về việc sử dụng tìa nguyêndùng chung của các tiến trình. Để các tiến trình hoạt động đồng thời không cạnh tranhhay xung đột với nhau khi sử dụng tài nguyên dùng chung hệ điều hành phải tổ chứccho các tiến trình này được độc quyền truy xuất/ sử dụng trên các tài nguyên dùng chungnày.Những tài nguyên được hệ điều hành chia sẻ cho nhiều tiến trình hoạt động đồngthời dùng chung, mà có nguy cơ dẫn đến sự tranh chấp giữa các tiến trình này khi sửdụng chúng, được gọi là tài nguyên găng. Tài nguyên găng có thể là tài nguyên phầncứng hoặc tài nguyên phần mền, có thể là tài nguyên phân chia được hoặc không phânchia được, nhưng đa số thường là tài nguyên phân chia được như là: các biến chung, cácfile chia sẻ.Các ví dụ sau đây cho thấy hậu quả của việc sử dụng tài nguyên găng trong cácchương trình có các tiến trình hoạt động đồng thời:Ví dụ 1: Giả sử có một chương trình, trong đó có hai tiến trình P1 và P2 hoạtđộng đồng thời với nhau. Tiến trình P1 phải tăng biến Count lên 1 đơn vị, tiến trình P2phải tăng biến Count lên 1 đơn vị, với mục đích tăng Count lên được 2 đơn vị.13 Chương trình có thể thực hiện như sau:1.Tiến trình P1 ghi nội dung biến toàn cục Count vào biến cục bộ L12.Tiến trình P2 ghi nội dung biến tồn cục Count vào biến cục bộ L23.Tiến trình P1 thực hiện L1:= L1 + 1 và Count := L14.Tiến trình P2 thực hiện L2:= L2 + 1 và Count := L2Như vậy thoạt nhìn ta thấy rằng chắc chắn Count đã tăng được 2 đơn vị, nhưngtrong thực tế có thể Count chỉ tăng được 1 đơn vị. Bởi vì, nếu P1 và P2 đồng thời nhậngiá trị của Count [giả sử ban đầu Count = 4] vào L1 và L2, sau đó P1 tăng L1 lên 1 vàP2 tăng L2 lên 1 [L1 = 5, L2 = 5], rồi sau đó cả P1 và P2 đồng thời ghi giá trị biến Lcủa nó vào lại Count, thì Count chỉ tăng được 1 đơn vị, Count = 6. Đây là điều màchương trình khơng mong muốn nhưng cả chương trình và hệ điều hành đều khó có thểphát hiện được.Nguyên nhân ở trên là do 2 tiến trình P1 và P2 đồng thời truy xuất biến Count,cả khi nhận giá trị của count, lẫn khi ghi giá trị vào Count. Trong trường hợp này nếuhệ điều hành không cho phép hai tiến trình P1 và P2 đồng thời truy xuất Count, hoặc hệđiều hành cho phép mỗi tiến trình được độc quyền truy xuất Count trong đoạn code sau,thì lỗi trên sẽ không xảy ra.P1: BeginP2: BeginL1 := Count;L2 := Count;L1 := L1 + 1;L2 := L2 + 1;Count := L1;Count := L2;End;End;Trong trường hợp này tài nguyên găng là biến count.Ví dụ 2: Giả sử có một ứng dụng Kế tốn, hoạt động trong mơi trường đa nhiệm,đa người sử dụng. Mỗi người sử dụng trong môi trường này khi cần thực hiện thao tácrút tiền từ trong tài khoản chung thì phải khởi tạo một tiến trình, tạm gọi là tiến trình rúttiền, tiến trình rút tiền chỉ có thể thực hiện được thao tác rút tiền khi số tiền cần rút nhỏhơn số tiền còn lại trong tài khoản chung. Trong mơi trường này có thể có nhiều ngườisử dụng đồng thời thực hiện thao tác rút tiền từ tài khoản chung của hệ thống.14 Như vậy các tiến trình rút tiền, giả sử có hai tiến trình rút tiền P1 và P1, có thểhoạt động đồng thời với nhau và cùng chia sẻ không gian nhớ lưu trữ biến Tài khoản,cho biết số tiền còn trong tài khoản dùng chung của hệ thống. Và mỗi tiến trình rút tiềnkhi muốn rút một khoảng tiền từ tài khoản [Tiền rút] thì phải thực hiện kiểm tra Tàikhoản sau đó mới thực hiện việc rút tiền. Tức là mỗi tiến trình rút tiền, khi cần rút tiềnđều phải thực hiện đoạn code sau đây:IF [Tài khoản - Tiền rút >= 0]{kiểm tra tài khoản}Tài khoản := Tài khoản - Tiền rút{thực hiện rút tiền}Thông báo lỗi{không thể rút tiền}ElseEndIf;Nếu tại một thời điểm nào đó:• Trong tài khoản cịn 800 ngàn đồng [Tài khoản = 800].• Tiến trình rút tiền P1 cần rút 500 ngàn đồng [Tiền rút = 500].• Tiến trình rút tiền P2 cần rút 400 ngàn đồng [Tiền rút = 400].• Tiến trình P1 và P2 đồng thời rút tiền.Thì theo nguyên tắc điều trên khơng thể xảy ra, vì tổng số tiền mà hai tiến trìnhcần rút lớn hơn số tiền cịn lại trong tài khoản [500 + 400 > 800]. Nhưng trong môitrường đa nhiệm, đa người sử dụng nếu hệ điều hành không giám sát tốt việc sử dụngtài nguyên dùng chung của các tiến trình hoạt động đồng thời thì điều trên vẫn có thểxảy ra. tức là, cả hai tiến trình P1 và P2 đều thành cơng trong thao tác rút tiền, mà ứngdụng cũng như hệ điều hành khơng hề phát hiện. Bởi vì, q trình rút tiền của các tiếntrình P1 và P2 có thể diễn ra như sau:1.P1 được cấp processor để thực hiện việc rút tiền: P1 thực hiện kiểm tra tàikhoản: Tài khoản - Tiền rút = 800 -500 = 300 > 0, P1 ghi nhận điều này vàchuẩn bị rút tiền.2.Nhưng khi P1 chưa kịp rút tiền thì bị hệ điều hành thu hồi lại processor, vàhệ điều hành cấp processor cho P2. P1 được chuyển sang trạng thái ready.3.P2 nhận được processor, được chuyển sang trạng thái running, nó bắt đầu15 thực hiện việc rút tiền như sau: kiểm tra tài khoản: Tài khoản - Tiền rút = 800 400 = 500 >= 0, P2 ghi nhận điều này và thực hiện rút tiền:Tài khoản = Tài khoản - Tiền rút = 800 - 400 = 400.4.P2 hoàn thành nhiệm vụ rút tiền, nó kết thúc xử lý và trả lại processor chohệ điều hành. Hệ điều hành cấp lại processor cho P1, tái kích hoạt lại P1 để nótiếp tục thao tác rút tiền.5.Khi được hoạt động trở lại P1 thực hiện ngay việc rút tiền mà không thựchiện việc kiểm tra tài khoản [vì đã kiểm tra trước đó]:Tài khoản = Tài khoản - Tiền rút = 400 - 500 = -100.6.P1 hoàn thành nhiệm vụ rút tiền và kết thúc tiến trình.Như vậy cả 2 tiến trình P1 và P2 đều hồn thành việc rút tiền, khơng thơng báolỗi, mà không gặp bất kỳ một lỗi hay một trở ngại nào. Nhưng đây là một lỗi nghiêmtrọng đối với ứng dụng, vì khơng thể rút một khoảng tiền lớn hơn số tiền còn lại trongtài khoản, hay Tài khoản không thể nhận giá trị âm.Nguyên nhân của lỗi này khơng phải là do hai tiến trình P1 và P2 đồng thời truyxuất biến Tài khoản, mà do hai thao tác: kiểm tra tài khoản và thực hiện rút tiền, của cáctiến trình này bị tách rời nhau. Nếu hệ điều hành làm cho hai thao tác này không táchrời nhau thì lỗi này sẽ khơng xảy ra.Kết luận: Chúng ta cũng thấy rằng nguyên nhân tiềm ẩn của sự xung đột giữacác tiến trình hoạt động đồng thời khi sử dụng tài nguyên găng là: các tiến trình này hoạtđộng đồng thời với nhau một cách hoàn toàn độc lập và không trao đổi thông tin vớinhau nhưng sự thực thi của các tiến trình này lại ảnh hưởng đến nhau.2.1.2. Đoạn tới hạn [hay đoạn găng] [Critical Section]:• Bài tốn đoạn tới hạn: Giả sử có n tiến trình P0,P1,…, Pn-1 song hành, mỗi tiến trìnhcó một đoạn tới hạn. Tìm một phương thức sao cho các tiến trình vượt qua đoạntới hạn của hình mà khơng ảnh hưởng tới hoạt động của hệ thống.• Nhân xét: Việc giải quyết bài toán đoạn tới hạn là phải thiết kế một nghi thức saocho các tiến trình có thể sử dụng để hợp tác với nhau và thỏa mãn ba điều kiện:16 o Điều kiện loại trừ lẫn nhau: Tại mỗi thời điểm, chỉ có một tiếng trình đượcphép thực hiện trong đoạn tới hạn của mình.o Điều kiện tiến triển: Khơng tiến trình nào được phép ở lâu vơ hạn trongđoạn tới hạn của mình.o Điều kiện chờ đợi có giới hạn: Các tiến trình khơng phải chờ đợi vơ hạntrước khi đi vào đoạn tới hạn của mình.• Hai xu hướng mà các hệ điều hành thường áp dụng để giải quyết bài toán đoạntới hạn là:o Sử dụng các thuật toán cấp thấp: Là các thuật toán nằm ngay trong tiếntrình.o Sử dụng các thuật tốn cấp cao: Là các thuật tốn nằm ngồi tiến trình.2.2. Các phương pháp giải quyết bài tốn đoạn tới hạn2.2.1. Phương pháp khóa trongNguyên tắc chung:Phương pháp này dựa trên cơ sở nếu hai hay nhiều tiến trình cùng định ghi vàomột địa chỉ nào đó của bộ nhớ trong thì giải thuật chỉ cho phép một tiến trình được thựchiện cịn các tiến trình khác phải chờ.Mỗi tiến trình sử dụng một byte trong bộ nhớ để làm khóa. Khi tiến trình vàođoạn giới hạn, byte khóa của nó được gán giá trị = 1 để thơng báo cho các tiến trình cònlại biết tài nguyên găng đã được sử dụng. Khi ra khỏi đoạn tói hạn, byte khóa được gángiá trị =0 để thông báo tài nguyên găng đã được giải phóng.Trước khi vào đoạn tới hạn, các tiến trình phải kiểm tra byte khóa của các tiếntrình khác. Nếu có byte nào đó chứa giá trị = 1 thì tiến trình phải chờ cho tới khi byteđó nhận giá trị = 0.Thuật tốn: [cho bài tốn hai tiến trình]Var K1,K2: byte;BeginK1 := K2 := 0;{Tiến trình 1}Repeat17 While K2 = 1 do Skip;K1 := 0;Tiến trình 1 vào đoạn tới hạn;K1 := 0;Phần còn lại của tiến trình 1;Until false;{Tiến trình 2}RepeatWhile K1 = 1 do Skip;K2 := 1;Tiến trình 2 vào đoạn tới hạn;K2 := 0;Phần cịn lại của tiến trình 2;Until false;End;Nhận xét: Nhược điểm của giải thuật trên là khơng đảm bảo tính loại trừ lẫn nhau.Giả sử tiếng trình 1 thực hiện rất nhanh so với tiến trình 2 và tiến trình 1 đang trongđoạn tới hạn cịn tiến trình 2 đang chờ vào đoạn tới hạn. Sau khi đang trong đoạn tới hàncịn tiến trình 2 đang chờ vào đoạn tới hạn. Sau khi tiến trình 1 ra khỏi đoạn tới hạn →K1 = 0 và tiến trình 2 thốt khỏi trạng thái chờ nhưng chưa vào đoạn tới hạn → K2 # 1.Trong khi đó tiến trình 1 đã thực hiện xong phần cịn lại của mình và quay trờ lại đầutiến trình. Vì K2 # 1 nên tiến trình 1 có thể thực hiện phép gán K1 = 1 dẫn đến cả haitiến trình cùng vào đoạn tới hạn.Thuật tốn dekkerĐể giải quyết nhược điểm trên, thuật toán của dekker dùng thêm một biếnkhóa TT để xác định độ ưu tiên của các tiến trình khi cả hai tiến trình cùng muốn vàođoạn tới hạn [TT = 1 hoặc TT =2].Var K1,K2,TT: byte;BeginK1 := K2 := 0;TT := 1;{Tiến trình 1}Repeat18 K1 := 1;While K2 = 1 doIf TT = 2 thenbeginK1 := 0While TT = 2 do Skip;K1 = 1;end;Tiến trình 1 vào đoạn tới hạn;K1 := 0; TT := 2;Phần cịn lại của tiến trình 1;Until false;{Tiến trình 2}RepeatK2 := 1;While K1 = 1 doIf TT = 1 thenBeginK2 : = 0;While TT = 1 do Skip;K2 = 1;End;Tiến trình 2 vào đoạn tới hạn;K2 := 0; TT := 1;Phần cịn lại của tiến trình 1;Until false;End;Thuật tốn Dekker giải quyết bài toán đoạn tới hạn hợp lý trong mọi trường hợpdù tốc độ thực hiện của các tiến trình khác nhau.Ưu điểm và nhược điểm của phương pháp khóa trong:-Ưu điểm: Phương pháp khóa trong khơng địi hỏi cơng cụ đặc biệt. do đó có thểtổ chức bằng một ngơn ngữ bất kì và thực hiện trên mọi hệ thống.-Nhược điểm: Độ phức tạp của thuật toán sẽ tăng khi số tiến trình nhiều hoặc sốlượng đoạn tới hạn trong các tiến trinh lớn; các tiến trình phải chờ đợi ở trạngthái tích cực.19 2.2.2. Phương pháp kiểm tra và xác lậpNguyên tắc chung:Phương pháp này dựa vào sự hỗ trợ của phần cứng, có một lệnh thực hiện haiphép xử lý liên tục khơng bị tách rời.Giả sử ta gọi lệnh đó là TS [Test and Set], lệnh này có hai tham số: biến chungG và biến riêng L [biến chung G thông thường là một bit trong từ trạng thái hoặc trongthanh ghi cờ]. Dạng thức thực hiện của lệnh TS[L] như sau:L := G [gán giá trị biến chung cho biến riêng]G := 1 [gán giá trị 1 cho biến chung]Thuật tốn: [cho bài tốn hai tiến trình]Var L1,L2,G, TT:byte;BeginG := 0; TT = 1;{Tiến trình 1}RepeatL1 := 1;While L1 = 1 do TS[L1];Tiến trình 1 vào đoạn tới hạn;G := 0; TT = 2;Phần cịn lại của tiến trình 1;Until false;{Tiến trình 2}RepeatL2 := 1;While L2 = 1 do TS[L2];Tiến trình 2 vào đoạn tới hạn;G := 0; TT = 1;Phần cịn lại của tiến trình 2;Until false;End;Ưu điểm và nhược điểm của phương pháp kiểm tra và xác lập:20 -Ưu điểm: Phương pháp này đơn giản, độ phức tạp khơng tăng khi số tiến trình vàsố đoạn tới hạn tăng. Nhiều máy tính được trang bị tới vài lệnh kiểu này để điềukhiển tiến trình nhu IBM PC có tới 4 lệnh.-Nhược điểm: Tiến trình vẫn phải chờ đợi tích cực; khó xác định được tiến trìnhnào sẽ vào đoạn tới hạn khi có q nhiều tiến trình cùng chờ2.2.3. Phương pháp đèn hiệu:Nguyên tắc chung:Đèn hiệu S là một biến ngun mà chỉ có hai phép xử lí WAIT và SIGNAL mớithay đổi được giá trị của nó.Định nghĩa phép WAIT[S]:S := S – 1;Nếu S>=0 thì tiếp tục thực hiện tiến trình;

Nếu SĐịnh nghĩa phép SIGNAL[S]:S := S + 1;

Nếu S Chú ý:-Phép WAIT và SIGNAL không bị phân chia trong tiến trình thực hiện.-Nêu ban đầu S = 1 và cả hai tiến trình đều đưa ra phép WAIT[S] thì chỉ có mộttiến trình được phép vào đoạn tới hạn, tiếng trình cịn lại sẽ được đưa vào hàngđợi.Thuật tốn: [cho bài tốn hai tiến trình]Var S: byte;BeginS := 1;{Thuật toán 1}21