Nguyên lý hệ diều hành - Chương 2: Quản lý tiến trình

GV: Đỗ Công ĐứcKhoa khoa học máy tínhNGUYÊN LÝ HỆ ĐIỀU HÀNH (3 Tín chỉ)Date1Chương 2. Quản lý tiến trìnhChương 2: QUẢN LÝ TIẾN TRÌNH2.1. Các mô hình xử lý đồng hành 2.2. Tổ chức và quản lý tiến trình 2.3. Điều phối tiến trình 2.4. Tài nguyên găng và đoạn găng2.5. Các giải pháp về đồng bộ hóa2.6. Bế tắc và chống bế tắcDate2Chương 2. Quản lý tiến trìnhCÁC MÔ HÌNH XỬ LÝ ĐỒNG HÀNH 2.1.1 Nhu cầu xử lý đồng hành (1/2)Đa số các HĐH hiện nay đều cho phép người dùng xử lý nhiều tác vụ đồng thời cùng một lúc trên máy tính để: Tăng hiệu suất sử dụng CPU: các công việc phải trải qua nhiều chu kỳ xử lý (xử dụng CPU) và chu kỳ nhập xuất (IO) xen kẽ nhauCPUIOCPUIOCPUTác vụ 1CPUIOCPUIOCPUIOTác vụ 2CPUIOCPUIOCPUNếu chỉ có 1 tiến trình duy nhất trong hệ thống, thì vào các chu kỳ IO của tác vụ, CPU sẽ  hoàn toàn nhàn rỗi. Ý tưởng tăng cường số lượng tác vụ trong hệ thống là để tận dụng CPU: nếu tác vụ 1 xử lý IO, thì có thể sử dụng CPU để thực hiện tác vụ 2 Date3Chương 2. Quản lý tiến trìnhCÁC MÔ HÌNH XỬ LÝ ĐỒNG HÀNH 2.1.1 Nhu cầu xử lý đồng hành (2/2)Tăng tốc độ xử lý: xử lý song song nếu được xây dựng thành nhiều modul hoạt động đồng thời thì sẽ tiết kiệm được thời gian xử lý Ví dụ: Tính giá trị của biểu thức a*b + c*d Nếu tiến hành song song tính a*b và c*d thì giải quyết bài toán nhanh hơn tính tuần tự a*b, c*d và sau đó mới tính tổngTrong các trường hợp đó, cần có một mô hình xử lý đồng hành thích hợp. Trên máy tính có cấu hình nhiều CPU, hỗ trợ xử lý song song (multiprocessing) thật sự, điều này sẽ giúp tăng hiệu quả thi hành của hệ thống đáng kể Date4Chương 2. Quản lý tiến trìnhCÁC MÔ HÌNH XỬ LÝ ĐỒNG HÀNH 2.1.2 Tiến trình và mô hình đa tiến trình (1/2)Sự đa chương của máy tính là sự thực hiện nhiều tác vụ đồng thời. Để thực hiện điều này HĐH xử lý mô hình song song giả lập. Nghĩa là chuyển đổi bộ xử lý qua lại giữa các tiến trình trong khoảng 1% hoặc 1/10 mili giây để duy trì hoạt động của chương trình. Để hoàn thành tác vụ của mình, một tiến trình có thể cần đến một số tài nguyên như CPU, bộ nhớ chính, các tập tin và thiết bị Phân biệt chương trình và tiến trình: chương trình là một thực thể thụ động, khi thi hành thì thực thi các tác vụ, chỉ thị thì chương trình chuyển thành tiến trình là một thực thể hoạt động, xác định chỉ thị tiếp theo thi hành và cung cấp các tài nguyên cho tiến trìnhDate5Chương 2. Quản lý tiến trìnhCÁC MÔ HÌNH XỬ LÝ ĐỒNG HÀNH 2.1.2 Tiến trình và mô hình đa tiến trình (2/2)Trong thực tế, chỉ có một bộ xử lý thật sự, được chuyển đổi qua lại giữa các tiến trình. Sự chuyển đổi nhanh chóng này được gọi là sự đa chương. HĐH chịu trách nhiệm sử dụng một thuật toán điều phối để quyết định thời điểm cần dừng hoạt động của tiến trình đang xử lý để phục vụ một tiến trình khác và lựa chọn tiến trình tiếp theo sẽ được phục vụ. Bộ phận thực hiện chức năng này của HĐH được gọi là bộ điều phối Một con trỏ lệnhTiến trìnhABCDABDC4 con trỏ lệnhDCBA(a)(b)Thời gian(c)Date6Chương 2. Quản lý tiến trìnhCÁC MÔ HÌNH XỬ LÝ ĐỒNG HÀNH 2.1.3 Tiểu trình và mô hình đa tiểu trìnhMỗi tiến trình có một không gian địa chỉ và chỉ có một dòng xử lý, nhưng người sử dụng mong muốn có nhiều dòng xử lý cùng chia sẻ một không gian địa chỉ và các dòng xử lý này hoạt động song song.HĐH cung cấp một cơ chế xử lý mới cho phép có nhiều dòng xử lý trong cùng một tiến trình và gọi là tiểu trình Tiểu trình là một đơn vị xử lý cơ bản, mỗi tiểu trình xử lý tuần tự đoạn code, sở hữu một con trỏ lệnh, tập các thanh ghi, stack riêng. Các tiểu trình chia sẻ CPU với nhau giống như cách chia sẻ giữa các tiến trình. Một tiến trình có thể sở hữu nhiều tiểu trình Tiến trình là một chương trình hoạt động và cần có nhiều tiến trình được lưu trữ trong bộ nhớ tại một thời đểm và điều phối qua lại giữa các tiến trình làm cho sự đa chương của HĐH tăng lên. Date7Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNHTrong môi trường đa chương, một CPU có thể chuyển từ chương trình này sang chương trình khác, thực hiện mỗi chương trình trong khoảng 1% hoặc 1/10 mili giây. Thực chất tại một thời điểm, CPU chỉ thực hiện được một chương trình. Nhưng xét trong khoảng thời gian phần trăm giây thì CPU có thể thực hiện được nhiều công việc Tiến trình là một dãy các trạng thái của hệ thống tính toán và việc chuyển từ trạng thái này sang trạng thái khác S0 S1 S2 S3 S4 S5 S6 S7 .Sn-1 Sn Sn+1 .Các trạng thái này nhất thiết không phải liên tiếp. Chương trình nào thì tạo ra tiến trình đó, gồm tiến trình của hệ thống và tiến trình của người sử dụngDate8Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.1 Các loại tiến trình:2 loại là tuần tự và song songTiế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: Hai tiến trình gọi là song song nếu thời điểm bắt đầu của của tiến trình này nằm giữa thời điểm bắt đầu và kết thúc của chương trình kia Tiến trình 1 Tiến trình 2Bắt đầuBắt đầuKết thúcDate9Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.1 Các loại tiến trình:2 loại là tuần tự và song songTiến trình song song khi thực hiện thì có thể thực hiện song song vật lý và song song đan xen.+ Tiến trình song song độc lập: Không có quan hệ thông tin với nhau+ Tiến trình song song có quan hệ thông tin: trong quá trình hoạt động các tiến trình thường trao đổi thông tin với nhau + Tiến trình song song phân cấp: trong khi hoạt động nó sản sinh ra một tiến trình nữa và hoạt động song song chính nó. Tiến trình khởi tạo là tiến trình cha, tiến trình được tạo ra gọi là tiến trình con + Tiến trình song song đồng mức: sử dụng chung tài nguyên theo nguyên tắc lần lược, mỗi tiến trình sau một khoảng thời gian chiếm giữ tài nguyên phải tự động trả lại tài nguyên cho tiến trình kia Date10Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH+ Thứ nhất là các tiến trình của HĐH.+ Thứ hai là các tiến trình của chương trình người sử dụng. Các tiến trình của HĐH hoạt động trong chế độ độc quyền, nhờ đó mà nó có thể truy xuất vào 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ười sử dụng hoạt động trong chế độ không độc quyền, nên nó không thể truy xuất vào hệ thống, nhờ đó mà HĐH được bảo vệ. Các tiến trình của chương trình người sử dụng truy xuất vào hệ thống thông qua HĐH bằng lời gọi hệ thống P1P2P3Timea. Trong hệ thống uniprocessorP1P2P3Timeb. Trong hệ thống multiprocessorKhảo sát hoạt động của tiến trình song hệ thống uniprocessor. Đối với người sử dụng thì trong hệ thống chỉ có hai nhóm tiến trình Date11Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.2 Các mô hình tiến trình (1/4)Về nguyên tắc thì mỗi processor có nhiệm vụ thực hiện một chương trình. Người sử dụng thì muốn sự đa chương, đa nhiệm nhưng chỉ thực hiện trên một processor. Để thực hiện, HĐH đã 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ý. Các processor logic có thể hoạt động song song với nhau, mỗi processor logic chịu trách nhiệm thực hiện một tiến trình. Mỗi chương trình chia thành nhiều tiến trình, khởi tạo và đưa vào hệ thống, cấp phát đầy đủ tài nguyên cho tiến trình, đưa các tiến trình sang trạng thái sẵn sàng. HĐH cấp processor cho tiến trình để hoạt động, sau một khoảng thời gian thu hồi processor để cấp cho một tiến trình và như thế cho đến khi tất cả các tiến trình mà HĐH khởi tạo đều hoạt động và kết thúc được Date12Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.2 Các mô hình tiến trình (2/4)P1P2P3Timet1t2t3t4t5t6Giả sử trong hệ thống có 3 tiến trình sẵn sàng P1, P2, P3 quá trình chuyển: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 P3: được cấp processor t3 P3: bị thu hồi processor P1: được cấp processor t4 P1: kết thúc và trả lại P2: được cấp processor t5 P2: kết thúc và trả lại P3: được cấp processor t6 P3: kết thúc và trả lại Date13Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH2.2.2 Các mô hình tiến trình (3/4)Processor là thực hiện chỉ thị của máy thường trú trong bộ nhớ chính việc chuyển processor từ tiến trình này sang tiến trình khác là việc điều khiển processor để nó thực hiện xen kẽ các chỉ thị bên trong tiến trình Điều này có thể thực hiện dễ dàng bằng cách thay đổi hợp lý giá trị của con trỏ lệnh, đó chính là cặp thanh ghi CS:IP trong các processorGiả sử hệ thống cần thực hiện đồng thời 3 tiến trình P1, P2, P3, bắt đầu từ tiến trình P1. Các chỉ thị của các tiến trình này được nạp vào bộ nhớ tại các địa chỉ Tiến trình P1: Tiến trình P2: Tiến trình P3: a + 0 b + 0 c + 0a + 1 b + 2 c + 1a + 3 b + 3 c + 4a + 5 c + 6 Date14Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH2.2.2 Các mô hình tiến trình (4/4)Processor thực hiện xen kẽ các chỉ thị của 3 tiến trình P1,P2,P3 từ lệnh đầu tiên đến lệnh cuối cùng, cho đến khi tất cả các chỉ thị của 3 tiến trình đều thực hiện. Nhưng khoảng thời gian từ khi con trỏ lệnh =a+0 đến khi =a+1, hay từ khi =b+0 đến khi =b+2 là rất nhỏ, nên hệ thống có “cảm giác” 3 tiến trình P1, P2, P3 hoạt động đồng thời Mô hình thực hiện đồng thời của tiến trình uniprocessor có 2 thuận lợi:Tiết kiệm được bộ nhớ: vì nó chỉ nạp các tiến trình cần thiết sau đó mới nạp các tiến trình khác khi có yêu cầuCho phép các chương trình hoạt động song song nên tốc độ của hệ thống tăng lên và khai thác tối đa thời gian xử lý processor.HĐH có một cơ chế thích hợp để chọn điểm dừng, thu hồi processor để chuyển cho tiến trình sẵn sàng tiếp theo khác.Date15Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.3 Các trạng thái của tiến trìnhTiến trình 2 trạng thái: Not Running và Running Not RunningRunningExitDispatchPauseEnterKhi HĐH tạo ra một tiến trình mới, đưa tiến trình đó vào hệ thống ở trạng thái Not Running, chờ chuyển sang trạng thái Running. Khi đang thực hiện bị ngắt thì bộ điều phối thu hồi lại processor và chọn một tiến trình ở trạng thái Not Running để cấp processor cho nó và chuyển nó sang trạng thái Running. Tiến trình bị thu hồi processor sẽ được chuyển về lại trạng thái Not Running Sơ đồ chuyển tiến trình 2 trạng tháiDate16Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.3 Các trạng thái của tiến trìnhTiến trình 2 trạng thái: Not Running và Running Tại một thời điểm xác định chỉ duy nhất một tiến trình ở trạng thái Runnig, nhưng có nhiều tiến trình ở trạng thái Not Running, các tiến trình ở trạng thái Not Running đượ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 EnterQueueDispatchPauseExitProcessor Sơ đồ chuyển tiến trình vào hàng đợiDate17Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.3 Các trạng thái của tiến trìnhTiến trình 3 trạng thái: Ready, Running, Blocked - Ready: trang thái sẵn sàng chờ cấp phát Processor để thực hiênSơ đồ chuyển tiến trình 3 trạng thái- Running: là tiến trình đang sở hữu Processor để hoạt động- Blocked: tiến trình đang chờ cấp phát thêm tài nguyên để một sự kiện nhập xuất nào đó xảy ra hoặc kết thúcRunningBlockedReady34651NewExit21. 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. Tiến trình được cấp processor để bắt đầu thực hiện/xử lý 3. Tiến trình hoàn thành xử lý và kết thúc 4. Tiến trình bị bộ điều phối thu hồi processor, do hết thời gian được quyền sử dụng processor, để cấp phát cho tiến trình khác 5. Tiến trình đang chờ một sự kiện nào đó xảy ra hay đang chờ một thao tác nhập/xuất kết thúc6. Sự kiện mà tiến trình chờ đã xảy ra, thao tác nhập/xuất mà tiến trình đợi đã kết thúc Date18Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.3 Các trạng thái của tiến trìnhTiến trình 3 trạng thái: Ready, Running, Blocked ReleaseAdmitReady QueueDispatchTime-outEvent WaitEventOccursBlocked QueueProcessor Sơ đồ chuyển tiến trình vào hàng đợiTạ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ạng thái Ready hoặc Blocked nhưng chỉ có một tiến trình ở trạng thái Running. Các tiến trình ở trạng thái Ready và Blocked được chứa trong các hàng đợi (Queue) riêng. Các tiến trình đang chạy vì 1 lý do nào đó có thể chuyển sang BlockedDate19Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.3 Các trạng thái của tiến trìnhTiến trình 4 trạng thái: Ready,Running,Blocked,SuspendReadyBlockedSuspendRunningActivate Suspend EndNewSuspend là trạng thái của một tiến trình khi nó đang được lưu trữ trên bộ nhớ phụ, là các tiến trình đang ở trong trạng thái blocked hoặc ready bị HĐH chuyển ra đĩa để thu hồi lại không gian nhớ đã cấp hoặc thu hồi lại tài nguyên đã cấp để 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 Date20Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.3 Các trạng thái của tiến trình 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 các tiến trình khác đang cần, rõ ràng sử dụng tài nguyên không hợp lý, làm cho hệ thống thiếu tài nguyên trầm trọng và có thể làm cho hệ thống bế tắc. HĐH thiết kế thêm trạng thái Suspend. 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 Tổ chức Queue để lưu các tiến trình chưa hoạt động là cần thiết, nhưng tồn tại quá nhiều tiến trình trong Queue, sẽ lãng phí không đủ bộ nhớ để nạp các tiến trình khác. Date21Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.3 Các trạng thái của tiến trìnhTiến trình 5 trạng thái: Ready,Running,Blocked, Blocked-Suspend  và Ready-SuspendReadyBlockedRunningActivateBlockedsuspendEvent OccursReleaseSuspendAdmitReadysuspendNewExitAdmitSuspendActivateEvent OccursDate22Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH2.2.3 Các trạng thái của tiến trìnhTrạ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ưng sẵn sàng thực hiện ngay sau khi được nạp vào bộ nhớ chính 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ình blocked bị chuyển ra ngoài, blocked-suspend, để dành bộ nhớ cho một tiến trình không bị khoá (not blocked) khác.Date23Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.3 Các trạng thái của tiến trìnhBlocked-suspend sang Ready-suspend: một tiến trình chờ sự kiện mà nó đợi đã xảy raReady-suspend sang Ready: có 2 lý do để HĐH chọn khi chuyển một tiến trình ở trạng thái ready-suspend sang trạng thái readyReady sang Ready suspend: HĐH thường chuyển các tiến trình blocked sang suspend hơn là các tiến trình ready, vì các tiến trình ở trạng thái blocked khô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ơn so với các tiến trình ở trạng thái ready. Khi chọn tiến trình để chuyển sang 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ấp hơn thì HĐH có thể chuyển một tiến trình ready sang trạng thái suspend Date24Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.4 Cấu trúc dữ liệu của khối tiến trình Để quản lý các tiến trình và tài nguyên hệ thống, HĐH xây dựng 1 bảng thông tin để lưu các trạng thái hiện thời. Xây dựng bảng thông tin cho các đối tượng:+ Memory table: theo dõi thông tin cho bộ nhớ thực và bộ nhớ ảo+ I/O table: thông tin cho thiết bị+ File table: thông tin cho các file+ Process table: thông tin cho tiến trình, biết được vị trí nạp tiến trình trong bộ nhớ chính, phải biết được các thuộc tính của tiến trình cần thiết cho việc quản lý tiến trình của nó để quản lý và điều khiển.Các bảng thông tin cho I/O table, file table, Memory table cũng tương tự như Process table để quản lý và điều khiển chúng.Date25Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.4 Cấu trúc dữ liệu của khối tiến trình2.2.4.1 Định vị tiến trình: khi tiến trình ở trạng thái Blocked hoặc ready được HĐH lưu lại trong bộ nhớ phụ (đĩa). Để tiến trình thực hiện được phải được nạp vào bộ nhớ chính nhưng chỉ nạp 1 phần tiến trình vào bộ nhớ, còn 1 phần vẫn lưu lại trên đĩa hay khi tiến trình trên bộ nhớ chính thì có 1 phần bị Swap out ra lại đĩa. HĐH phải theo dõi tiến trình để biết phần nào ở bộ nhớ chính, phần nào ở trên đĩaHĐH quản lý không gian của tiến trình thành một tập các block và các block này có thể liên tiếp hoặc không liên tiếp. Block có chiều cố định (chiến lược phân trang bộ nhớ:page), thay đổi (chiến lược phân đoạn bộ nhớ:segment) hoặc cả 2. HĐH không nạp hết các trang/đoạn vào bộ nhớ do đó HĐH phải biết vị trí mỗi trang/đoạn trên hệ thống.Date26Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH2.2.4 Cấu trúc dữ liệu của khối tiến trình2.2.4.2 Thuộc tính tiến trình:Các thông tin về tiến trình thường trú trong khối quản lý tiến trình:PCB (Process Control Bolck). Mỗi HĐH có PCB khác nhau chia 3 nhóm:- Định danh tiến trình: PID(Process identification) mỗi tiến trình có tên và nó xuất hiện trong memory table hoặc I/O table. Khi tiến trình này truyền thông với tiến trình khác thì định danh tiến trình được sử dụng để HĐH xác định tiến trình đích.- Thông tin trạng thái processor (processor state information): Bao gồm các thanh ghi trạng thái và điều khiển, các con trỏ stack - Thông tin điều khiển tiến trình (process control information): Bao gồm thông tin trạng thái và lập lịch, cấu trúc dữ liệu, quyền truy cập tiến trình, quản lý bộ nhớ, tài nguyên khởi tạo và tài nguyên sinh ra Date27Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.5 Các thao tác điều khiển tiến trình2.2.5.1 Các thao tác khi khởi tạo tiến trình của HĐHHĐH dùng entry trong PID để chưa các thông tin có liên quan khi tiến trình mới tạo raKhi cấp phát không gian nhớ cho tiến trình HĐH xác định kích thước của tiến trình như: code, data và stack,Khi khởi tạo tiến trình cần các thông tin cần thiết cho tiến trình như định danh, thông tin trạng thái, độ ưu tiên.Cung cấp đầy đủ tài nguyên cần thiết cho tiến trình để có thể rơi vào trạng thái ready hoặc bắt đầu hoạt động.Đưa tiến trình vào một danh sách tiến trình ready list, suspend list, waiting list sao cho phù hợp với chiến lược điều phối tiến trình hiện tại của bộ phận điều phối tiến trình của HĐH Date28Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.5 Các thao tác điều khiển tiến trình2.2.5.2 Các thao tác khi kết thúc tiến trình của HĐHKhi tiến trình kết thúc hoặc hoàn thành, HĐH sẽ thực hiện các thao tác Thu hồi tài nguyên đã cấp phát cho tiến trình. Loại bỏ tiến trình ra khỏi danh sách quản lý của hệ thống.Huỷ bỏ khối điều khiển tiến trình.Hầu hết các HĐH đều không cho phép tiến trình con hoạt động khi tiến trình cha đã kết thúc. Trong những trường hợp như thế HĐH sẽ chủ động việc kết thúc tiến trình con khi tiến trình cha vừa kết thúc Date29Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.5 Các thao tác điều khiển tiến trình2.2.5.3 Các thao tác khi thay đổi trạng thái tiến trình của HĐHLưu lại ngữ cảnh bộ xử lý gồm các thanh ghi bộ đếm count và thanh ghi khácCập nhật PCB của tiến trình, sao cho phù hợp với trạng thái mới Di chuyển PCB của tiến trình đến một hàng đợi thích hợp Chọn một tiến trình khác để cho phép nó thực hiện Cập nhật PCB của tiến trình vừa được chọn thực hiện Cập nhật các thông tin liên quan đến quản lý bộ nhớ Khôi phục lại ngữ cảnh của processor và thay đổi giá trị của bộ đếm Khi tiến trình ở trạng thái runnig chuyển sang trang thái khác như ready, blocked thì phải thực hiện các bước sau:Date30Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.6 Cấp phát tài nguyên cho tiến trình Khi có nhiều người sử dụng đồng thời trong hệ thống, cần phải cấp phát đầy đủ tài nguyên theo yêu cầu cho người sử dụng. Nhưng tài nguyên thì có hạn nên không thể thỏa mãn đồng thời cho tất cả được. Vì vậy HĐH phải có chiến lược quản lý và cấp phát tài nguyên sao cho có hiệu quả. HĐH quản lý nhiều loại tài nguyên như bộ nhớ, các thiết bị ngoại vi và mỗi loại thì có cấu trúc dữ liệu khác nhau qua các thông tin sau:PIDDanh sách các phần có thể sử dụngDanh sách các tiến trình đang đợi tài nguyênCon trở đến đoạn code cấp phát tài nguyênĐịnh danhTrạng thái tài nguyênHàng đợi nguyênBộ cấp phát nguyênDate31Chương 2. Quản lý tiến trìnhTỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.6 Cấp phát tài nguyên cho tiến trìnhCác mục tiêu của kỹ thuật cấp phát:Bảo đảm một số lượng hợp lệ các tiến trình truy xuất đồng thời đến các tài nguyên không chia sẻ được.Cấp phát tài nguyên cho tiến trình có yêu cầu trong một khoảng thời gian trì hoãn có thể chấp nhận được.Tối ưu hoá sử dụng tài nguyên.Để có thể thoả mãn các mục tiêu kể trên, cần phải giải quyết các vấn đề nảy sinh khi có nhiều tiến trình đồng thời yêu cầu một tài nguyên không thể chia sẻ.Date32Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNHCó nhiều tiến trình đồng thời sẵn sàng xử lý. Mục tiêu của các hệ phân chia thời gian (time-sharing) là chuyển đổi CPU qua lại giữa các tiến trình một cách thường xuyên để nhiều người sử dụng có thể tương tác cùng lúc với từng chương trình trong quá trình xử lý.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.Khi đã có được processor thì phải lựa chọn tiến trình trong số các tiến trình ở trạng thái ready để cấp processor cho nó. Bộ điều phối sẽ sử dụng một giải thuật điều phối thích hợp để thực hiện nhiệm vụ nàyDate33Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH 2.3.1 Mục tiêu điều phối2.3.1.1 Các cơ chế điều phối tiến trìnhĐiều phối độc quyền: khi có được processor tiến trình toàn quyền sử dụng processor cho đến khi tiến trình kết thúc xử lý hoặc tiến trình tự động trả lại processor cho hệ thống. Các quyết định điều phối xảy ra khi: chuyển trạng thái từ Running sang Blocked hoặc khi tiến trình kết thúc. Bộ điều phối sử dụng 2 cơ chế điều phối : điều phối độc quyền và điều phối không độc quyền.Hạn chế: Điều phối độc quyền thì tiến trình có thể giữ CPU một thời gian không xác định nên có thể ngăn cản một số tiến trình còn lại trong hệ thống có một cơ hội để xử lýDate34Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH 2.3.1 Mục tiêu điều phối2.3.1.1 Các cơ chế điều phối tiến trìnhĐiều phối không độc quyền: bộ phận điều phối có thể cho phép tạm dừng tiến trình đang sẵn sàng xử lý để thu hồi processor của nó, để cấp cho tiến trình có độ ưu tiên cao hơn. Như vậy là tiến trình có thể tạm dừng bất kỳ lúc nào mà không được báo trước để tiến trình khác xử lý. Các quyết định điều phối xảy ra khi: tiến trình chuyển trạng thái Running - Blocked, Running-Ready, Blocked-Ready hoặc khi tiến trình kết thúc Hạn chế: tiến trình có thể tạm dừng bất kỳ lúc nào Date35Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH 2.3.1 Mục tiêu điều phốiĐiều phối độc quyền: Các tác vụ có thời gian xử lý ngắn phải chờ các tác vụ xử lý với thời gian rất dài hoàn tất.Thích hợp cho HĐH xử lý theo lôĐiều phối không độc quyền:Đáp ứng kịp thời các tiến trình quan trọng có cơ hội hồi đáp kịp thời để xử lý.Thích hợp cho HĐH xử lý theo thời gian và thời gian thựcViệc phân định độ ưu tiên các tiến trình, phát sinh thêm cho phí chuyển đổi CPU qua lại giữa các tiến trìnhDate36Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH 2.3.1 Mục tiêu điều phối2.3.1.2 Các đặc điểm của tiến trìnhTiến trình hướng nhập/xuất: các tiến trình cần nhiều thời gian cho việc thực hiện các thao tác nhập/xuất dữ liệu, so với thời gian mà tiến trình cần để thực hiện các chỉ thị trong nó Tiến trình hướng xử lý: các tiến trình cần nhiều thời gian cho việc thực hiện các chỉ thị trong nó, so với thời gian mà tiến trình để thực hiện các thao tác nhập/xuất Điều phối hoạt động giữa các tiến trình là công việc phức tạp, đòi HĐH khi giải quyết phải xem xét nhiều yếu tố kác nhau để có thể đạt được những mục tiêu đề ra:Date37Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH 2.3.1 Mục tiêu điều phối2.3.1.2 Các đặc điểm của tiến trìnhĐộ ưu tiên của tiến trình: mỗi tiến trình được gán một độ ưu tiên và nó có thể phát sinh tự động. Có 2 loại:Ưu tiên tĩnh: được gán trước và không thay đổi trong suốt quá trình sống của tiến trìnhƯu tiên động: được gán độ ưu tiên trong quá trình hoạt động và nó được gán lại nếu như môi trường xử lý của tiến trình thay đổi để phù hợp với tình trạng hiện tại và công tác điều phốiTiến trình tương tác hay xử lý theo lô: yêu cầu tiến trình cần phải trả lại kết quả tức thời. Các tiến trình của tác vụ được xử lý theo lô có thể trì hoãn một thời gian chấp nhận đượcDate38Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH 2.3.1 Mục tiêu điều phối2.3.1.2 Các đặc điểm của tiến trìnhThời gian đã sử dụng CPU của tiến trình: tiến trình cần bao nhiêu khoảng thời gian của processor để hoàn thành xử lý Thời gian còn lại tiến trình cần để hoàn tất: tiến trình còn cần bao nhiêu khoảng thời gian của processor nữa để hoàn thành xử lý. Bộ phận điều phối tiến trình thường dựa vào đặc điểm của tiến trình để thực hiện điều phối ở mức tác vụ và nó phải được thực hiện trước điều phối tiến trìnhDate39Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH 2.3.1 Mục tiêu điều phối2.3.1.3 Mục tiêu của điều phối tiến trìnhSự công bằng: Các tiến trình phải chia sẻ CPU một cách công bằng, không có tiến trình nào phải chờ vô hạn để chờ cấp phát CPUTính hiệu quả: hệ thống phải tận dụng tối đa thời gian CPU là 100% Thời gian đáp ứng hợp lý: cực tiểu hóa thời gian hồi đáp cho các tương tác của người sử dụng Thời gian lưu lại trong hệ thống: cực tiểu hóa thời gian hoàn tất các tác vụ xử lý theo lôThông lương tối đa: cực đại hóa số công việc trong một thời gian HĐH xây dựng nhiều chiến lược khác nhau để thực hiện việc điều phối nhưng cần phải đạt được mục tiêu là:Date40Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH 2.3.1 Mục tiêu điều phốiVí dụ: Hệ thống có bốn tiến trình P1, P2, P3, P4, thời gian (t) mà các tiến trình này cần processor để xử lý lần lượt là 1, 12, 2, 1.Ban đầu P1 và P2 ở trạng thái ready bộ phận điều phối sẽ cấp processor cho P1.Khi P1 kết thúc thì processor sẽ được cấp cho P2 để hoạt độngKhi P2 thực hiện được 2t thì P3 được đưa vào trạng thái ready.Nếu P2 tiếp tục thì P3 phải chờ lâuvi phạm mục tiêu thời gian hồi đáp và thông lượng tối đa (đối với P3). Nếu P2 dừng cấp processor cho P3 hoạt động đến khi kết thúc.Khi đó P4 vào trạng thái ready, bộ điều phối sẽ cấp processor cho P4, và cứ như thế, thì P2 phải chờ lâu, như vậy sẽ đạt được mục tiêu: thời gian hồi đáp và thông lượng tối đa nhưng vi phạm mục tiêu: công bằng và thời gian lưu lại trong hệ thống (đối với P2). Date41Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH 2.3.2 Tổ chức điều phối2.3.2.1 Các danh sách sử dụng trong quá trình điều phốiĐể tổ chức điều phối HĐH sử dụng 2 danh sách:Danh sách sẵn sàng (Ready list): chứa tiến trình ở trạng thái sẵn sàng Danh sách đợi (Waiting list): chứa tiến trình đang đợi để bổ sung vào danh sách ready listCác tiến trình trong ready list mới được chọn để cấp processor.Các tiến trình bị chuyển về trạng thái blocked sẽ được bổ sung vào waiting list. Hệ thống có một ready list, nhiều waiting list và mỗi waiting list dùng để chứa các tiến trình đang đợi được cấp phát một tài nguyên hay một sự kiện riêng biệt nào đó. Date42Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH 2.3.2 Tổ chức điều phối2.3.2.1 Các danh sách sử dụng trong quá trình điều phối1234567Ready listWaiting list 1Waiting list 28ProcessorTiến trình nào trong Ready list mới được cấp Processor, các tiến trình Blocked chuyển vào Waiting list. Hệ thống chỉ có 1 Ready list nhưng có nhiều Waiting list để chứa các tiến trình chờ cấp phát tài nguyên hay đợi một sự kiện nào đó xảy raDate43Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH 2.3.2 Tổ chức điều phối1. Tiến trình trong hệ thống được cấp đầy đủ tài nguyên chỉ thiếu processor 2. Tiến trình được bộ điều phối chọn ra để cấp processor để bắt đầu3. Tiến trình kết thúc xử lý và trả lại processor cho hệ điều hành 4. Tiến trình hết thời gian được quyền sử dụng processor bộ điều phối tiến trình thu hồi lại processor 5. Tiến trình bị khoá do yêu cầu tài nguyên nhưng chưa được HĐH cấp phát đưa vào danh sách Waiting list 16. Tiến trình bị khoá do đang đợi một sự kiện nào đó xảy ra. Tiến trình được bộ điều phối đưa vào danh sách Waiting list 27. Tiến trình yêu cầu tài nguyên đã được cấp phát, bộ điều phối chuyển tiến trình này sang danh sách Ready list để chờ cấp CPU hoạt động8. Tiến trình chờ một sự kiện xảy ra, tiến trình được bộ điều phối chuyển vào danh sách ready list chờ cấp CPUDate44Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH 2.3.2 Tổ chức điều phối2.3.2.2 Các cấp độ điều phốiHĐH thực hiện 2 cấp độ, điều phối tác vụ và điều phối tiến trìnhĐiều phối tác vụ: Chọn tác vụ nào đưa vào hệ thống và nạp những tiến trình của tác vụ vào bộ nhớ chính. Chức năng điều phối quyết định sự đa chương của hệ thống.Bộ điều phối cần biết tính chất của các tiến trình hướng nhập xuất hay hướng xử lý. Hướng nhập xuất sử dụng CPU để thực hiện thao tác nhập xuất, hướng xử lý là sử dụng CPU để thực hiện tính toánCân bằng CPU và thiết bị nhập xuất thì phải pha trộn xử lý theo hướng nhập xuất và xử lý Date45Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH 2.3.2 Tổ chức điều phối2.3.2.2 Các cấp độ điều phốiĐiều phối tiến trình: Chọn tiến trình ở trạng thái sẵn sàng và cấp CPU cho tiến trình đó Các HĐH thường không tác biệt 2 cấp độ điều phối này mà thường đưa ra cấp độ điều phối trung gian là kết hợp cả 2Tiến trình trong bộ nhớ phụ được nạp từng phần để xử lýReady listDanh sách chờ trên tài nguyênI/O CPUDate46Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH 2.3.3 Các chiến lược điều phối2.3.3.1 Chiến lược FIFO (First in First out)ABCCPUReady ListNguyên tắc: CPU được cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng khi có yêu cầu. Đây là thuật toán theo nguyên tắc độc quyền. Một khi CPU được cấp phát cho tiến trình, CPU chỉ được tự nguyện giải phóng khi kết thúc xử lý hay khi có môti yêu cầu nhập xuấtDate47Chương 2. Quản lý tiến trìnhTiến trình Thời điểm Thời gian thực hiện P1 0 24 P2 1 3 P3 2 3 P1P2P32427300ĐIỀU PHỐI TIẾN TRÌNH2.3.3.1 Chiến lược FIFO (First in First out)Giả sử các tiến trình được thực hiên theo thứ tự: P1 , P2 , P3 Sơ đồ của điều phối:Thời gian chờ của P1 = 0; P2 = 24-1=23; P3 = 24+3-2=25Thời gian chờ trung bình: (0 + 23 + 25)/3 = 16Date48Chương 2. Quản lý tiến trìnhGiả sử các tiến trình được thực hiện theo thứ tự: P2 , P3 , P1 .Sơ đồ của điều phối:P1P3P263300ĐIỀU PHỐI TIẾN TRÌNH2.3.3.1 Chiến lược FIFO (First in First out)Thời gian chờ của: P1 = 6; P2 = 0; P3 = 3Thời gian chờ trung bình: (6 + 0 + 3)/3 = 3Đây là phương án tốt nhất.Date49Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH2.3.3.2 Chiến lược phân phối xoay vòng RR (Round Robin)ABCCPUReady ListAHết timesliceNguyên tắc: Danh sách sẵn sàng được xử lý như một danh sách xoay vòng. Tiến trình được bộ điều phối cấp phát là ở đầu danh sách ready list và sau một khoảng thời gian nhất định bộ điều phối thu hồi lại processor và chuyển processor cho tiến trình kế tiếp trong ready list. Tiến trình vừa thu hồi được đưa cuối danh sách. Đây là một giải thuật điều phối không độc quyền. Khoảng thời gian mà mỗi tiến trình được sở hữu processor để hoạt động là bằng nhau và được gọi là Quantum Date50Chương 2. Quản lý tiến trình Tiến trình Độ ưu tiên Thời gian xử lý P1 0 24 P2 1 3 P3 2 3Nếu sử dụng quantum là 4 milliseconds, thứ tự cấp phát CPU sẽ là: ĐIỀU PHỐI TIẾN TRÌNH2.3.3.2 Chiến lược phân phối xoay vòng RR (Round Robin)P1P2P3P1P1P1P1P1047101418222630Vậy thời gian chờ đợi trung bình sẽ là: (0+6+3+5)/3= 4.67milisecondes.Date51Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH2.3.3.3 Chiến lược theo độ ưu tiênTiến trình chọn để cấp processor là tiến trình có độ ưu tiên số 1 tại thời điểm hiện tạiGán độ ưu tiên theo nguyên tắc gán tĩnh và gán động. Khi khởi tạo thì nó được gán tĩnh, sau đó phụ thuộc quá trình hoạt động của tiến trình và công tác điều phối có thể thay đổi lại độ ưu tiênKhi phát sinh ra một tiến trình ready mới thì bộ điều phối so sánh tiến trình phát sinh và tiến trình hiện tại đang sử dụng :Nếu có độ ưu tiên thấp hơn thì bộ điều phối chèn nó vào danh sách ready list tại vị trí thích hợpNếu có độ ưu tiên cao hơn thì bộ điều phối thu hồi Processor của tiến trình hiện tại để cấp cho tiến trình mới có yêu cầu (không độc quyền) chèn vào danh sách ready list tại vị trí thích hợp (điều phối độc quyền)Date52Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH2.3.3.3 Chiến lược theo độ ưu tiênChiến lược này cũng sử dụng ready list và được xếp theo thứ tự giảm dần của độ ưu tiên kể từ đầu danh sách. Điều này có nghĩa là tiến trình được chọn để cấp processor là tiến trình ở đầu ready list Tiến trình Độ ưu tiên Thời gian xử lýP1 3 24P2 1 3P3 2 3 P2P3P147300Các tiến trình có độ ưu tiên thấp sẽ rơi vào tình trạng chờ đợi vô hạn. Hạ độ ưu tiên của các tiến trình cao sau mỗi lần nó được cấp Processor Date53Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH2.3.3.4 Chiến lược SJF (Shortest Job First công việc ngắn nhất)Mỗi tiến trình đều biết thời gian thực hiện. Sử dụng đại lượng này để lập lịch với phương pháp thời gian ngắn nhất.Hai cách thức: Không ưu tiên – một tiến trình được sử dụng CPU đến khi hoàn thành hoặc bị ngắt.Ưu tiên – một tiến trình đến có thời gian thực hiện nhỏ hơn thời gian thực hiện còn lại của tiến trình đang thực thi sẽ được ưu tiên. SJF là tối ưu cho thời gian chờ trung bình của các tiến trình nhỏ nhất.Date54Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH2.3.3.5 Chiến lược nhiều cấp độ ưu tiênPhân lớp các tiến trình theo độ ưu tiên của chúng để có cách thức điều phối thích hợp cho từng lớp tiến trình và mỗi lớp có một danh sách ready list riêng.Sử dụng độ ưu tiên tĩnh và điều phối không độc quyền, do đó một tiến trình thuộc ready list ở cấp độ ưu tiên i sẽ chỉ được cấp phát processor khi trong ready list ở cấp độ ưu tiên j (j>i) không còn một tiến trình nào. Tiến trình ở ready list có độ ưu tiên thấp sẽ phải chờ đợi processor trong một khoảng thời gian dài và có thể là vô hạn. HĐH thực hiện chiến lược nhiều mức độ ưu tiên xoay vòng: Tiến trình có độ ưu tiên cao trong ready list xuống thấp Tiến trình ở lâu trong ready list có độ ưu tiên thấp thì sẽ được chuyển dần lên ready list có độ ưu tiên cao hơn Date55Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNH2.3.3.6 Chiến lược điều phối xổ số (Lottery)Giải thuật là phát hành một số vé số và phân phối cho các tiến trình trong hệ thống. Khi đến thời điểm ra quyết định điều phối, sẽ tiến hành chọn 1 vé "trúng giải", tiến trình nào sở hữu vé này sẽ được nhận processorGiải thuật Lottery cung cấp một giải pháp đơn giản nhưng bảo đảm tính công bằng cho thuật toán điều phối với chi phí thấp để cập nhật độ ưu tiên cho tiến trình Date56Chương 2. Quản lý tiến trìnhĐIỀU PHỐI TIẾN TRÌNHTrong suốt chu trình sống, tiến trình chuyển đổi qua lại giữa các trạng thái ready, running và blocked Bộ điều phối của HĐH chịu trách nhiệm áp dụng một giải thuật điều phối thích hợp để chọn tiến trình thích hợp được sử dụng processor và bộ phân phối sẽ chuyển giao processor cho tiến trình này Các giải thuật điều phối thông dụng: FIFO, RR, điều phối với độ ưu tiên, SJF Tóm lạiDate57Chương 2. Quản lý tiến trìnhTÀI NGUYÊN GĂNG VÀ ĐOẠN GĂNG 2.4.1 Tài nguyên găngTrong HĐH đa nhiệm, đa chương việc chia sẻ tài nguyên cho các tiến trình, nếu HĐH mà không tổ chức tốt sử dụng tài nguyên dùng chung của các tiến trình hoạt động đồng thời thì sẽ dẫn đến việc không khai thác tài nguyên hệ thống, làm hỏng dữ liệu của các ứng dụng.Các tiến trình hoạt động đồng thời dùng chung tài nguyên ghi vào không gian nhớ chung. Đó là biểu hiện của sự cạnh tranh tài nguyên dùng chung của các tiến trình.Để ngăn chặn tình huống lỗi truy xuất đồng thời tài nguyên không chia sẻ cần phải áp đặt truy xuất độc quyền khi một tiến trình đang sử dụng tài nguyên thì những tiến trình khác không được truy xuất đến tài nguyên Date58Chương 2. Quản lý tiến trìnhTÀI NGUYÊN GĂNG VÀ ĐOẠN GĂNG 2.4.1 Tài nguyên găngNhững tài nguyên mà HĐH chia sẻ cho nhiều tiến trình hoạt động đồng thời dùng chung dẫn đến sự tranh chấp giữa các tiến trình gọi là tài nguyên găngTài nguyên găng là tài nguyên mà trong một khoảng thời gian nhất định thì chỉ phục vụ hợp lý cho một số hữu hạn các tiến trình Tài nguyên găng có thể tài nguyên phần cứng, phần mềm, tài nguyên phân chia được, không phân chia đượcVí dụ: Trong ứng dụng kế toán hực hiện thao tác rút tiền trong tài khoản người dùng thì phải khởi tạo một tiến trình gọi là rút tiền và tiến trình thực hiện được khi mà số tiền cần rút phải nhỏ hơn số tiền còn lại trong tài khoản và có thể có nhiều người sử 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 Date59Chương 2. Quản lý tiến trìnhTÀI NGUYÊN GĂNG VÀ ĐOẠN GĂNG 2.4.1 Tài nguyên găngCó 2 tiến trình rút tiền P1 và P2 hoạt động đồng thời 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 lại trong tài khoản dùng chung. Mỗi tiến trình rút tiền khi muốn rút một khoản tiền từ tài khoản (Tiền rút) thì phải thực hiện kiểm tra tài khoản sau đó mới rút tiền 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 không thể rút tiền EndIf; Date60Chương 2. Quản lý tiến trìnhTÀI NGUYÊN GĂNG VÀ ĐOẠN GĂNG 2.4.1 Tài nguyên găngGiả sử tại một thời điểm nào đó có: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 Điều này không thể xảy ra vì số tiền cần rút là 500+400>800. Nhưng trong môi trường đa nhiệm, đa người sử dụng nếu HĐH không giám sát tốt việc sử dụng chung tài nguyên của các tiến trình hoạt động đồng thời thì có thể xảy ra và tiến trình P1, P2 thực hiện thành công trong quá trình rút tiền mà HĐH cũng như ứng dụng không phát hiện ra. Quá trình rút tiền của P1 và P2 diễn ra như sau:Date61Chương 2. Quản lý tiến trìnhTÀI NGUYÊN GĂNG VÀ ĐOẠN GĂNG 2.4.1 Tài nguyên găngP1 được cấp Processor để thực hiện rút tiền, P1 kiểm tra tài khoả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 Nhưng P1 chưa kịp rút tiền thì HĐH thu hồi Processor và cấp cho P2. P1 trở lại trạng thái ready P2 nhận processor chuyển sang trạng thái running thực hiện rút tiền thì kiểm tra: Tài khoản - Tiền rút = 800 - 400 = 400 >= 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 P2 thực hiện xong rút tiền trả processor lại cho HĐH cấp cho P1 tái kích hoạt để tiếp tục rút tiềnDate62Chương 2. Quản lý tiến trìnhTÀI NGUYÊN GĂNG VÀ ĐOẠN GĂNG 2.4.1 Tài nguyên găngP1 hoạt động trở lại thực hiện thao tác rút tiền mà không thực hiện kiểm tra nữa (vì đã kiểm tra rồi) Tài khoản - Tiền rút = 800 -500 = 300 > 0 Nhưng thực chất thì tài khoản 400-500=-100Nhưng P1 vẫn thực hiện được thao tác rút tiền và kết thúcNhư vậy cả P1 và P2 đều thực hiện rút tiền thành công mà không có một thông báo lỗi nào. Đây là lỗi nghiêm trọng vì không thể rút tiền nếu như số tài khoản còn nhỏ hơn số tiền cần rútQua trên ta thấy nếu cho nhiều hơn hai tiến trình cùng truy xuất vào một vùng nhớ chung kết quả phụ thuộc vào sự điều phối tiến trình của hệ thống, được gọi là các tình huống tranh đoạt điều khiển Date63Chương 2. Quản lý tiến trìnhTÀI NGUYÊN GĂNG VÀ ĐOẠN GĂNG2.4.1 Tài nguyên găngNguyên nhân của lỗi này không phải do P1, P2 đồng thời truy xuất tài khoản mà do 2 thao tác kiểm tra và thực hiện rút tiền bị tách rời nhau. HĐH phải làm cho 2 thao tác này đừng tách rời nhau thì không gây ra lỗi nàyQua ví dụ trên ta thấy để ngăn chặng các tình huống như trên thì HĐH phải xác lập cơ chế độc quyền truy xuất trên tài nguyên dùng chung nghĩa là tại một thời điểm chỉ có duy nhất một tiến trình truy xuất. Nếu có nhiều tiến trình hoạt động đồng thời cùng yêu cầu truy xuất tài nguyên dùng chung thì chỉ có một tiến trình được chấp nhận truy xuất, các tiến trình khác phải xếp hàng chờ để được truy xuất sau Date64Chương 2. Quản lý tiến trìnhTÀI NGUYÊN GĂNG VÀ ĐOẠN GĂNG 2.4.1 Tài nguyên găngNguyên nhân xung đột của các tiến trình hoạt động đồng thời khi sử dụng tài nguyên găng là: hoạt động độc lập với nhau và không có trao đổi thông tin với nhau nhưng thi hành có liên quan với nhau. Để đảm bảo tại một thời điểm chỉ có một tiến trình xử lý lệnh trong miền găng phải thỏa mãn các điều kiện:Không có 2 tiến trình ở trong miền găng cùng một lúcMột tiến trình tạm dừng bên ngoài miền găng không được ngăn cản các tiến trình khác vào miền găng Không có tiến trình nào phải chờ vô hạn để được vào miền găng Date65Chương 2. Quản lý tiến trìnhTÀI NGUYÊN GĂNG VÀ ĐOẠN GĂNG 2.4.2 Đoặn găngĐoạn code trong các chương trình dùng để truy cập đến các vùng nhớ chia sẻ, các tập tin chia sẻ được gọi là các đoạn găng Ví dụ đoạn code sau là đoạn găng { IF (Tài khoản - Tiền rút >= 0) Tài khoản:= Tài khoản - Tiền rút }Để khắc phục các hạn chế lỗi xảy ra thì HĐH phải điều khiển : Tại một thời điểm chỉ có 1 tiến trình vào miền găngCác tiến trình muốn vào miền găng phải chờ ngoài miền găngTiến trình ra khỏi miền găng phải báo cho HĐH biết để cho các tiến trình khác vào miền găngDate66Chương 2. Quản lý tiến trìnhTÀI NGUYÊN GĂNG VÀ ĐOẠN GĂNG 2.4.2 Đoặn găngHĐH tổ chức cho mọi tiến trình vào đoạn găng một cách hợp lý công việc này gọi là công tác điều độ tiến trình qua đoạn găng Công tác điều độ qua đoạn găng phải được kết hợp giữa vi xử lý, HĐH và người lập trình : Vi xử lý đưa ra các chỉ thịHĐH cung cấp các công cụ Người lập trình xây dựng các sơ đồ điều phối hợp lýDate67Chương 2. Quản lý tiến trìnhTÀI NGUYÊN GĂNG VÀ ĐOẠN GĂNG 2.4.3 Yêu cầu công tác điều độ tiến trình qua đoạn găngNhiệm vụ điều độ phải đạt được các yêu cầu sau: Tại một thời điểm không có 2 tiến trình vào miền găngNếu có nhiều tiến trình vào miền găng thì chỉ có một tiến trình vào miền găng còn các tiến trình khác phải xếp hàng chờ trong hàng đợiTiến trình ngoài đoạn găng không được ngăn cảng các tiến trình khác vào đoạn găngKhông có tiến trình nào được phép ở lâu vô hạn trong đoạn găng và cũng không có tiến trình nào phải chờ lâu mới vào được đoạn găngNếu tài nguyên găng được giải phóng thì HĐH phải đánh thức các tiến trình trong hàng đợi để tạo điều kiện đưa nó vào đoạn găngDate68Chương 2. Quản lý tiến trìnhTÀI NGUYÊN GĂNG VÀ ĐOẠN GĂNG 2.4.3 Yêu cầu công tác điều độ tiến trình qua đoạn găngTổ chức truy xuất trên tài nguyên găng là truy xuất độc quyền và nó còn có hạn chế sau:Có thể dẫn đến bế tắc (deadlock): R1 được giao cho P2, R2 được giao cho P1. Mỗi tiến trình đều chờ đợi được sử dụng tài nguyên thứ hai nhưng không có tiến trình nào giải phóng tài nguyên của nó đang sở hữuCó thể bị đói tài nguyên (Starvation): 3 tiến trình P1, P2, P3 truy xuất vào tài nguyên R, P1 truy xuất thì P2 và P3 chờ. Khi P1 giải phóng thì P3 được truy xuất, P3 kết thúc thì P1 lại truy xuất. P2 đói tài nguyênDate69Chương 2. Quản lý tiến trìnhCÁC GIẢI PHÁP VỀ ĐỒNG BỘ HÓAKhi có nhiều tiến trình hoạt đồng đồng thời, các tiến trình liên lạc với nhau có thể tác động lẫn nhau làm sai lệch. Do đó HĐH phải cung cấp cơ chế đồng bộ hóa để đảm bảo hoạt động của các tiến trình:Yêu cầu truy xuất độc quyền: Tài nguyên có 2 loại là có thể chia sẻ và tài nguyên không thể chia sẻ. Tính không thể chia sẻ xuất phát nguồn gốc từ nguyên nhân sau: Do đặc tính của phần cứng không cho chia sẻ Nhiều tiến trình hoạt động đồng thời có nguy cơ các tiến trình ảnh hưởng lẫn nhauYêu cầu phối hợp: các tiến trình hoạt động không đồng bộ: tầng suất xảy ra ngắt, thời gian được cấp CPU xử lý khác nhau, để thực hiện hoàn thành một số các tác vụ cần phải hợp tác với nhau nên phải thực hiện đồng bộ hóaDate70Chương 2. Quản lý tiến trìnhCÁC GIẢI PHÁP VỀ ĐỒNG BỘ HÓA 2.5.1 Các giải pháp BUSY WAITING2.5.1.1 Giải pháp phần mềm¾ Sử dụng biến khóa- Dùng biến lock chung cho các tiến trình- Nếu lock= =1 thì khóa, không cho tiến trình vào miền găng. Chờ cho đến khi lock= =0- Nếu lock= =0 thì cho tiến trình vào miền găng, đặt lock= =1 để khóa không cho các tiến trình khác vào miền găngDate71Chương 2. Quản lý tiến trìnhCÁC GIẢI PHÁP VỀ ĐỒNG BỘ HÓA 2.5.1 Các giải pháp BUSY WAITING2.5.1.1 Giải pháp phần mềm¾ Sử dụng việc kiểm tra luân phiên- Các tiến trình muốn đi vào miền găng thì được gắn nhãn 0|1- Sử dụng biến turn để chỉ thứ tự luân phiên.- Nếu turn= =0: tiến trình có nhãn 0 được vào miền găng- Nếu turn= =1: tiến trình có nhãn 1 vào vòng lặp chờ cho đến khi nhận giá trị =0. Khi tiến trình A rời khỏi miền găng thì nó đặt lại turn =1 để cho phép tiến trình B đi vào miền găng. Date72Chương 2. Quản lý tiến trìnhCÁC GIẢI PHÁP VỀ ĐỒNG BỘ HÓA 2.5.1 Các giải pháp BUSY WAITING2.5.1.1 Giải pháp phần mềm¾Giải pháp Peterson: kết hợp cả 2 giải pháp trên,dùng 2 biến chungint turn; // đến phiên aiint interesse[2]; // khởi động là FALSE Nếu interesse[i]=TRUE Pi muốn vào miền găngKhởi đầu interesse[0]=interesse[1]=false interesse khởi động là 0|1Vào miền găng thì interesse[i]=true và sau đó đặt turn =jNếu interesse[j]=false không quan tâm vào miền găng thì Pi vào miền găng, sau đó ra khỏi miền găng thì đặt lại là interesse[i]=falseDate73Chương 2. Quản lý tiến trìnhCÁC GIẢI PHÁP VỀ ĐỒNG BỘ HÓA2.5.1.2 Giải pháp phần cứng 2.5.1 Các giải pháp BUSY WAITING¾Dùng cặp chỉ thị STI:(Setting interup) và CLI(Clearn Interup) mở ngắt và cấm ngắtTrước khi vào miền găng tiến trình thực hiện chỉ thị CLI để yêu cầu cấm các ngắt trong hệ thống Khi kết thúc truy xuất tài nguyên găng, tiến trình ra khỏi đoạn găng, tiến trình thực hiện chỉ thị STI để cho phép ngắt trở lại Khi tiến trình trong đoạn găng không có khả năng ra khỏi đoạn găng nên nó không thể thực hiện chỉ thị STI để mở ngắt cho hệ thống, nên hệ thống dễ dẫn đến bị treo hoàn toàn Date74Chương 2. Quản lý tiến trìnhCÁC GIẢI PHÁP VỀ ĐỒNG BỘ HÓA2.5.1.2 Giải pháp phần cứng 2.5.1 Các giải pháp BYSY WAITING¾Dùng chỉ thị TSL:(Test and Set Lock)Đây là giải pháp cần hỗ trợ phần cứng, cung cấp một chỉ thị đặc biệt cho phép kiểm tra và cập nhật nội dung một vùng nhớ trong một thao tác không thể phân chia, gọi là chỉ thị Test-and-Set Lock (TSL) Test_and_Setlock(boolean target){ Test_and_Setlock = target; target = TRUE;}Date75Chương 2. Quản lý tiến trìnhCÁC GIẢI PHÁP VỀ ĐỒNG BỘ HÓA 2.5.2 Các giải pháp SLEEP and WAKEUPĐối với giải pháp này thì tiến trình nào chưa đủ điều kiện vào miền găng thì sẽ chuyển sang trạng thái blocked. Dùng 2 thủ tục Sleep and wakeup để thay đổi trạng thái Khi tiến trình không đủ điều kiện vào đoạn găng thì hệ thống gọi thủ tục Sleep để chuyển sang trạng thái blocked và đưa vào hàng đợi cho đến khi một tiến trình khác gọi thủ tục wakeup để giải phóng nó ra khỏi hàng đợi và đưa vào đoạn găng Một tiến trình ra khỏi hàng đợi phải gọi thủ tục wakeup để đánh thức một tiến trình trong hàng đợi blocked ra để tạo điều kiện cho nó vào đoạn găngDate76Chương 2. Quản lý tiến trìnhCÁC GIẢI PHÁP VỀ ĐỒNG BỘ HÓA 2.5.2 Các giải pháp SLEEP and WAKEUP Giải pháp này do Dijkstra đưa ra 1965, S là Semaphore được định nghĩa như sau:2.5.2.1 Giải pháp dùng Semaphore Là một biến nguyên dương e(s) Ứng với S là hàng đợi F(s) lưu các tiến trình bị khóa Có 2 thao tác:+ Down giảm giá trị semaphore 1 đơn vị+ Up tăng giá trị Semaphore 1 đơn vịDate77Chương 2. Quản lý tiến trìnhCÁC GIẢI PHÁP VỀ ĐỒNG BỘ HÓA 2.5.2 Các giải pháp SLEEP and WAKEUP2.5.2.1 Giải pháp dùng SemaphoreDown(s): e(s)= e(s)-1; //e0 thì tiếp tục xử lý vào đoạn găng s=0 Gọi p là tiến trình thực hiện thao tác Down, Down cài đặt như sauDate78Chương 2. Quản lý tiến trìnhCÁC GIẢI PHÁP VỀ ĐỒNG BỘ HÓA 2.5.2 Các giải pháp SLEEP and WAKEUP2.5.2.1 Giải pháp dùng SemaphoreUp(s): e(s) = e(s) + 1; if s > 0 { exit(Q,f(s)); //Q là tiến trình đang chờ trên s status (Q) = ready; //chuyển tiến trình sang ready enter(Q,ready_list); //đưa tiến trình vào ready list} Mỗi tiến trình ra khỏi miền găng phải gọi Up để kiểm tra còn tiến trình trong hàng đợi không. Khi goi Up thì hệ thống thực hiện s=s+1. Nếu sF(Ri) Date90Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.4 Phát hiện bế tắcĐể phát hiện bế tắc HĐH thường cài đặt một thuật toán để phát hiện hệ thống có tồn tại hiện tượng chờ đợi vòng tròn hay không.HĐH phải cài đặt cơ chế độc quyền để bảm bảo tài nguyên chia sẻ và thực hiện cấp phát tài nguyên một lần để ngăn chặng việc chiếm giữ và yêu cầu cấp mới tài nguyên.Kiểm tra hệ thống thường xuyên để phát hiện bế tắcDate91Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.4 Phát hiện bế tắcKhi phát hiện bế tắc HĐH sử dụng một số giải pháp:Thoát tất cả các tiến trình bị bế tắc.Sao lưu lại mỗi tiến trình bị bế tắc tại một vài điểm, sau đó khởi động lại tất cả các tiến trình Thu hồi tài nguyên của tiến trình bế tắc, để cấp phát cho một tiến trình trong tập tiến trình bế tắc, giúp tiến trình này ra khỏi bế tắc Dùng toàn bộ quyền ưu tiên sử dụng tài nguyên cho một tiến trình, để tiến trình này ra khỏi bế tắc Date92Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.4 Phát hiện bế tắcCần sử dụng các cấu trúc dữ liệu sau:int Available[NumResources];// Available[r]= số lượng các thể hiện còn tự do của tài nguyên rint Allocation[NumProcs, NumResources];// Allocation[p,r] = số lượng tài nguyên r thực sự cấp phát cho pint Request[NumProcs, NumResources];// Request[p,r] = số lượng tài nguyên r tiến trình p yêu cầu thêmDate93Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.4 Phát hiện bế tắcGiải thuật phát hiện bế tắc.1. int Work[NumResources] = Available; int Finish[NumProcs]; for (i = 0; i < NumProcs; i++) Finish[i] = (Allocation[i] = = 0);2. Tìm i sao cho Finish[i] = = false Request[i] <= Work ; nếu không có i như thế, đến bước 4.3. Work = Work + Allocation[i]; Finish[i] = true ; đến bước 24. Nếu Finish[i] = = true với mọi i, thì hệ thống không có bế tắc. Nếu Finish[i] = = false với một số giá trị i, thì các tiến trình mà  Finish[i] =false sẽ ở trong tình trạng bế tắc. Date94Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.5 Tránh bế tắcĐể giải quyết bài toán bế tắc ta sử dụng phương pháp tránh bế tắc :Ngăn chặn một trong ba điều kiện cần của bế tắc, hoặc trực tiếp ngăn chặn không cho xảy ra hiện tượng chờ đợi vòng tròn Tránh bế tắc có thể thực hiện là cho phép 3 điều kiện cần xảy ra nhưng cung cấp các lựa chọn đúng để không xảy ra điểm bế tắc HĐH tuân thủ 2 nguyên tắc cơ bản để tránh bế tắc - Không hoạt động nếu yêu cầu tài nguyên có nguy cơ dẫn đến bế tắc - Không cấp thêm tài nguyên nếu cung cấp có nguy cơ dẫn đến bế tắc Date95Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.5 Tránh bế tắcHệ điều hành sử dụng 2 khái niệm là trạng thái và trạng thái an toàn để tránh được bế tắc trong công tác phòng chống bế tắc Trạng thái của hệ thống: là sự cấp phát tài nguyên hiện tại cho các tiến trình Trạng thái an toàn: Trạng thái A là an toàn nếu hệ thống có thể thỏa mãn các nhu cầu tài nguyên (đến tối đa) của mỗi tiến trình mà vẫn ngăn chặn được bế tắc HĐH xây dựng thuật toán, tác động vào cấu trúc dữ liệu để xác định trạng thái an toàn hoặc không an toàn để phục vụ cấp phát tài nguyên. Nếu là an toàn thì cấp phát, nếu không an toàn thì từ chối cấp phát cho đến khi nào xác định được trạng thái an toàn Date96Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.5 Tránh bế tắcSử dụng các cấu trúc dữ liệu sau:int allocation[numprocs,numresources];//allocation[p,r] số lượng tài nguyên r thực sự cấp phát cho pint max[numprocs,numresources];// max[p,r] nhu cầu tối đa của tiến trình p về tài nguyên rint need[numprocs,numresources];//need[p,r]=max[p,r]-allocation[p,r]int available[numresources]//available[r] số lượng tài nguyên r còn tự doDate97Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.5 Tránh bế tắcint word[numresouces]=available;int finish[numproces]=false;1.Tìm i sao cho a. finish[i]==false; b. need[i,j]<=word[j]; với mọi tài nguyên j nếu không có i như thế, đến bước 32.Word[j]=word[j]+allocation[i,j]; finish[i]=true; đến bước 1;3.Nếu finish[i]==true với mọi i thì hệ thống ở trạng thái an toàn. Ngược lại hệ thống bị tắc nghẽnDate98Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.5 Tránh bế tắcví dụ: giả sử tình trạng hiện hành của hệ thống được mô tả ở bảng dưới. Nếu tiến trình P2 yêu cầu cấp 4 R1, 1 R3. Hãy cho biết yêu cầu này có thể đáp ứng mà không xảy ra tình trạng tắt nghẽnMaxAllocationAvailableR1R2R3R1R2R3R1R2R3P1322100412P2613211P3314211P4422002Date99Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.5 Tránh bế tắcví dụ: Available[1]=4, Available[3]=2 đủ để thoả mãn yêu cầu của P2, ta có NeedAllocationAvailableR1R2R3R1R2R3R1R2R3P1222100011P2001612P3103211P4420002Date100Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.5 Tránh bế tắcNeedAllocationAvailableR1R2R3R1R2R3R1R2R3P1222100623P2000000P3103211P4420002Date101Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.5 Tránh bế tắcNeedAllocationAvailableR1R2R3R1R2R3R1R2R3P1000000723P2000000P3103211P4420002Date102Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.5 Tránh bế tắcNeedAllocationAvailableR1R2R3R1R2R3R1R2R3P1000000934P2000000P3000000P4420002Date103Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.5 Tránh bế tắcNeedAllocationAvailableR1R2R3R1R2R3R1R2R3P1000000936P2000000P3000000P4000000Trạng thái kết quả là an toàn, có thể cấp phát Date104Chương 2. Quản lý tiến trìnhBẾ TẮC VÀ CHỐNG BẾ TẮC 2.6.6 Hiệu chỉnh bế tắcKhi đã phát hiện được bế tắc, có 2 lựa chọn chính để hiệu chỉnh bế tắc 1. Đình chỉ hoạt động của các tiến trình có liên quan, thu hồi tất cả các tài nguyên bị kết thúc và sử dụng 2 phương pháp sau Đình chỉ tất cả các tiến trình trong tình trạng bế tắc  Đình chỉ từng tiến trình liên quan cho đến khi không còn chu trình gây bế tắc 2. Thu hồi tài nguyên để cấp cho một số tiến trình khác loại bỏ bế tắc Chọn lựa tiến trình thu hồi và thu hồi tài nguyên của tiến trình đóTrở lại trạng thái trước bế tắcTình trạng đói tài nguyênDate105Chương 2. Quản lý tiến trình