Câu 1: Mục tiêu, ý nghĩa,cấu trúc môn học
Câu 2: Phân tích Định nghĩa “Hệ điều hành là Máy tính mở rộng (Extended Machine) hay Máy tính ảo (Virtual Machine)”
– Ẩn các chi tiết của phần cứng để máy tính dễ sử dụng hơn.
– Người sử dụng và người lập trình được cung cấp một giao diện đơn giản, dễ hiểu và không phụ thuộc vào thiết bị cụ thể.
– Thực tế, HĐH là một hệ thống bao gồm nhiều máy tính trừu tượng xếp thành nhiều lớp chồng lên nhau. Máy tính mức dưới phục vụ cho máy tính mức trên.
– Bản thân chương trình ứng dụng cũng là một máy tính trừu tượng và phải dễ sử dụng nhất.
– Công việc của người lập trình là liên tục xây dựng các máy tính trừu tượng như vậy (cho người khác sử dụng và cho cả chính mình).
Câu 3 Phân tích Định nghĩa “Hệ điều hành là bộ quản lý tài nguyên (Resource Manager)”.
– Đáp ứng các yêu cầu sử dụng tài nguyên thiết bị như: CPU, Bộ nhớ trong, ổ đĩa, ổ băng, Máy in, Card mạng, …
– Trong trường hợp nhiều chương trình, nhiều người dùng cùng chia sẻ các tài nguyên chung như vậy, HĐH phải giải quyết tranh chấp có thể xảy ra và đứng ra làm trung gian điều phối sao cho tài nguyên được sử dụng đúng thứ tự, dùng xong lại được cấp cho đối tượng khác sử dụng.
– Hình dung tình huống: 3 chương trình cùng in ra một máy in duy nhất. Khó chấp nhận trường hợp 1 trang in xen kẽ nhiều kết quả từ nhiều nguồn khác nhau. HĐH giải quyết bằng cách đưa kết quả in của mỗi chương trình tạm thời ra đĩa cứng, sau đó lần lượt in từ đĩa vào thời điểm thích hợp.
Câu 4: Phân biệt HĐH đa xử lý và HĐH gom cụm
Hệ điều hành đa xử lý và hệ điều hành gom cụm giống nhau là đều tập hợp nhiều CPU với nhau để thực hiện công việc tính toán
Hệ điều hành gom cụm khác hệ điều hành đa xử lý ở điểm chúng được hợp thành từ hai hay nhiều hệ thống đơn được kết hợp với nhau.
a. Hệ điều hành đa xử lý
Các hệ hỗ trợ nhiều CPU, còn gọi là các hệ song song (Parallel Systems)
Ích lợi:
– Tăng thông suất : tăng số tác vụ hoàn tất trong 1 đơn vị thời gian, bằng cách tăng số lượng bộ xử lý, chúng ta hy vọng thực hiện nhiều công việc hơn với thời gian ít hơn.
– Tiết kiệm: Nhiều CPU nhưng chung bộ nhớ và các thiết bị ngoài. Ví dụ: Nếu nhiều chương trình điều hành trên cùng tập hợp dữ liệu thì lưu trữ dữ liệu đó trên một đĩa và tất cả bộ xử lý chia sẻ chúng sẽ rẻ hơn là có nhiều máy tính với đĩa cục bộ và nhiều bản sao dữ liệu.
– Tăng độ tin cậy: Nếu 1 CPU gặp sự cố, hệ vẫn chạy tuy có chậm hơn. Ví dụ: Nếu chúng ta có 10 bộ xử lý và có 1 bộ xử lý bị sự cố thì mỗi bộ xử lý trong 9 bộ xử lý còn lại phải chia sẻ của công việc của bộ xử lý bị lỗi. Do đó, toàn bộ hệ thống chỉ giảm 10% năng lực hơn là dừng hoạt động. Các hệ thống được thiết kế như thế được gọi là hệ thống có khả năng chịu lỗi (fault tolerant).
Phân loại:
– Đa xử lý đối xứng (symmetric multiprocessing-SMP). Trong hệ thống này mỗi bộ xử lý chạy bản sao của hệ điều hành và những bản sao này giao tiếp với các bản sao khác khi cần.
. Các CPU chung bộ nhớ và thiết bị
. Các CPU ngang hàng về chức năng
Ví dụ: Windows 2000 professional : 2CPU ; Windows 2000 Server : 4 CPU
– Đa xử lý bất đối xứng (asymmetric multiprocessing).
. Các CPU chung bộ nhớ và thiết bị
. Các CPU được ấn định chức năng riêng: Cơ chế này định nghĩa mối quan hệ chủ-tớ. Bộ xử lý chính lập thời biểu và cấp phát công việc tới các bộ xử lý tớ.
.. Có CPU chủ (Master): kiểm soát toàn hệ thống
.. Các CPU khác đóng vai trò phụ thuộc (Slaves), chuyên trách công việc nào đó. (chờ bộ xử lý chủ ra chỉ thị hoặc có những tác vụ được định nghĩa trước)
Ví dụ: Hệ điều hành SunOS 4.x
b. Hệ điều hành gom cụm
Nhiều máy nối mạng để cùng thực hiệc công việc chung
Phân loại :
– Gom cụm đối xứng (Symmetric Clustering): các máy ngang hàng về chức năng. Mỗi máy thực hiện phần việc của mình và giám sát lẫn nhau. Ví dụ: Trong hệ thống mạng gồm nhiều máy chủ chạy song song và chúng đang kiểm soát lẫn nhau.
– Gom cụm phi đối xứng (Asymmetric Clustering): Một máy chạy trong Hot Standby Mode, nghĩa là chỉ giám sát công việc các máy khác nhưng sẽ đảm đương công việc của máy gặp sự cố. Ví dụ: Hệ thống mạng gồm hai máy server chạy song song, trong đó một máy ở trong chế độ dự phòng (hot standby). Máy dự phòng không là gì cả ngoại trừ theo dõi server hoạt động. Nếu server đó bị lỗi, máy chủ dự phòng nóng trở thành server hoạt động.
<!—nextpage–>
Câu 5: So sánh các hệ Batch System
– Hệ xử lý lô (Batch System)
Mỗi thời điểm chỉ có một tác vụ trong bộ nhớ
– Hệ đa chương (Multiprogramming System)
Nhiều tác vụ (tiến trình) cùng một lúc trong bộ nhớ
Khi một tác vụ không cần đến CPU (do phải thực hiện I/O với thiết bị ngoài), tác vụ khác được thi hành.
– Hệ chia thời gian (Time-Sharing System)
Là hệ đa chương
Mỗi tác vụ chỉ được dùng CPU trong một khoảng thời gian ngắn (ví dụ với thời lượng là 20ms), sau đó bị ngắt, chuyển sang tác vụ khác, cứ thế xoay vòng.
Mỗi người dùng đều có cảm giác là máy tính chỉ phục vụ cho mình là duy nhất.
Ví dụ: Trong nhà hàng, người bồi bàn (CPU) phục vụ mỗi bàn ăn (chương trình người dùng) trong một khoảng thời gian ngắn (chẳng hạn trong 10 giây), sau đó chuyển sang bàn khác.
CHƯƠNG 2: CẤU TRÚC MÁY TÍNH
Câu 1: Trình bày nguyên tắc xử lý ngắt của hệ điều hành
– Hai loại ngắt chính:
. Tín hiệu ngắt (Interrupt Signal) từ các thiết bị (Ngắt cứng) truyền qua System Bus.
. Tín hiệu ngắt từ chương trình người dùng (Ngắt mềm) nhờ Lời gọi hệ thống (System Call hay Monitor Call). Lệnh đặc biệt này ( ví dụ có tên INT hoặc SysCall )cơ chế để tiến trình người dùng yêu cầu một dịch vụ của HĐH (ví dụ, yêu cầu thực hiện lệnh I/O).
– Với mỗi loại ngắt, có đoạn mã riêng của HĐH dùng để xử lý.
– Các HĐH hiện đại được dẫn dắt bởi các sự kiện. Nếu không có tiến trình nào vận hành, không có thiết bị I/O nào làm việc, HĐH im lặng chờ và theo dõi.
– Thông thường, mỗi loại ngắt tương ứng với 1 dòng trong bảng (Véc-tơ ngắt) chứa con
trỏ (Pointer) tới chương trình xử lý loại ngắt đó. Bảng này nằm ở vùng thấp của RAM (ví dụ: 100 bytes đầu tiên).
– Cơ chế xử lý ngắt phải có trách nhiệm ghi lại địa chỉ lệnh bị ngắt để sau đó có thể quay lại. Địa chỉ này cùng với nhiều thông tin khác có thể được ghi vào Ngăn xếp hệ thống (System Stack) với nguyên tắc làm việc LIFO ( Last-In, First-Out )
Câu 2: Trình bày Tuyến thời gian của một tiến trình có nhiều yêu cầu tới thiết bị ngoại vi
Câu 3: Phân biệt hai phương thức I/O đồng bộ và không đồng bộ
– Synchronous I/O: Sau khi phát ra lệnh Nhập/Xuất, tiến trình chuyển sang trạng thái chờ đến
khi Nhập/Xuất hoàn tất rồi mới chạy tiếp (thực hiện lệnh kế tiếp)
Ví dụ: Khi ta tạo mới một tài liệu nhập dữ liệu từ bàn phím, khi muốn lưu lại ta phải chọn Save, sau đó đặt tên file, và chọn nơi lưu trữ. Các tiến trình đó ở trạng thái chờ tiến trình trước nhập
xuất hoàn tất đã.
– ASynchronous I/O: Sau khi phát ra lệnh Nhập/Xuất, tiến trình không chờ Nhập/Xuất hoàn
tất mà thực hiện ngay lệnh kế tiếp. Như vậy, tiến trình vận hành song song với công việc Nhập/Xuất.
Ví dụ: Khi ta nhập dữ liệu mới hoặc thêm vào tài liệu đã có, khi ta muốn lưu thì ta chọn Save và lúc này tiến trình vận hành song song với việc phát ra lệnh từ Save.
Câu 4: Phân tích vai trò phân cấp các loại bộ nhớ trong máy tính
– Một sự phân cấp bộ nhớ kiểu mẫu được chỉ ra ở hình trên. Khi chúng ta đi từ trên xuống trong sơ đồ phân cấp này, những sự kiện sau sẽ xảy ra:
. Giảm phí tổn cho một bit
. Tăng dung lượng
. Tăng thời gian truy cập
. Giảm tần số truy cập bộ nhớ bởi CPU
– Do vậy bộ nhớ nhỏ hơn, nhanh hơn, đắt tiền hơn được phụ trợ bởi bộ nhớ lớn hơn, chậm hơn, rẻ hơn. Chìa khóa cho sự thành công trong cách tổ chức này là yếu tố cuối cùng, tức là giảm thiểu tần số truy cập.
Câu 5: Nguyên lý lưu gần
– Là nguyên tắc quan trọng của hệ thống máy tính.
– Thông tin từ RAM có thể được cơ chế phần cứng đưa vào bộ nhớ nhanh hơn gọi là Cache. Khi CPU cần chính thông tin đó, không cần phải truy xuất RAM, mà lấy ngay từ Cache.
– Loại bộ nhớ này không do HĐH quản lý và cấp phát.
– Thực tế, RAM (Bộ nhớ Sơ cấp) là loại Cache nhanh so với đĩa cứng (Bộ nhớ thứ cấp) và HĐH có chức năng quản lý sự lưu chuyển dữ liệu giữa 2 loại bộ nhớ này
Câu 6: Nguyên lý bảo vệ bộ nhớ chính bằng thanh ghi cơ sở và thanh ghi giớ hạn
– Để tiến trình người dùng không can thiệp được vào vùng nhớ của hệ điều hành và các tiến trình khác, thường sử dụng hai thanh ghi :
. Thanh ghi Cơ sở (Base register): được dùng để lưu trữ địa chỉ ô nhớ hợp lệ nhỏ nhất
. Thanh ghi Giới hạn (Limit register): lưu trữ kích thước của cả ô nhớ.
Ví dụ, nếu thanh ghi base lưu trữ giá trị 300040 và thanh ghi limit lưu trữ giá trị là 120900 thì chương trình sẽ có thể truy cập hợp lệ vào các địa chỉ ô nhớ trong khoảng từ 300040 cho đến 420940.
– Chỉ có HĐH mới có thể sửa được nội dung hai thanh ghi này. Vì thanh ghi base và limit chỉ có thể được nạp bởi hệ điều hành
CHƯƠNG 3: CẤU TRÚC HỆ ĐIỀU HÀNH
Cấu 1: Trình bày vai trò và chức năng của bộ thông dịch lệnh (Command-Interpreter)
Chức năng : lấy câu lệnh tiếp theo và thực thi nó. (Các câu lệnh giải quyết việc: tạo, hủy, xem thông tin tiến trình, hệ thống. Điều khiển truy cập I/O . Quản lý, truy cập hệ thống lưu trữ thứ cấp. Quản lý, sử dụng bộ nhớ.Truy cập hệ thống file…..)
Vai trò :
– Là giao diện chủ yếu giữa người dùng và HĐH. Ví dụ: shell, mouse-based window-and-menu
– Liên hệ chặt chẽ với các thành phần khác của hệ điều hành để thực thi các yêu cầu của người dùng
Câu 2: Trình bày và so sánh hai mô hình liên lạc giữa các tiến trình
Liên lạc giữa các tiến trình (Interprocess Communication):
– Mỗi máy tính trong mạng có Host Name và (hoặc) IP Address. Các tên này được HĐH chuyển đổi thành một số nguyên gọi là HostID.
– Mỗi tiến trình có ProcessName và ProcessID.
– Cặp số (HostID, ProcessID) xác định duy nhất tiến trình trong mạng và được dùng để Mở/Đóng kết nối với tiến trình đó.
– Có các lời gọi hệ thống kiểu Open, Close, Read, Write, Wait để thao tác với tiến trình.
Truyền thông điệp:
– Cho phép các tiến trình gởi các khuôn dữ kiệu có khuôn dạng tới bất kì tiến trình nào
– Chức năng của hệ thống truyền thông điệp là cho phép các quá trình giao tiếp với các quá trình khác mà không cần sắp xếp lại dữ liệu chia sẻ.
– Đơn vị truyền thông tin trong cơ chế truyền thông điệp là một thông điệp, do đó các tiến trình có thể trao đổi dữ liệu ở dạng cấu cấu trúc.
Dùng bộ nhớ chung:
– Với phương thức này, các tiến trình chia sẻ một vùng nhớ vật lý thông qua trung gian không gian địa chỉ của chung. Một vùng nhớ chia sẻ tồn tại độc lập với các tiến trình, và khi một tiến trình muốn truy xuất đến vùng nhớ này, tiến trình phải kết gắn vùng nhớ chung đó vào không gian địa chỉ riêng của từng tiến trình, và thao tác trên đó như một vùng nhớ riêng của mình.
– Đây là phương pháp nhanh nhất để trao đổi dữ liệu giữa các tiến trình. Nhưng phương thức này cũng làm phát sinh các khó khăn trong việc bảo đảm sự toàn vẹn dữ liệu (coherence)
– Một khuyết điểm của phương pháp liên lạc này là không thể áp dụng hiệu quả trong các hệ phân tán , để trao đổi thông tin giữa các máy tính khác nhau.
<!—nextpage–>
Câu 3: Kỹ thuật máy ảo, với ưu nhược điểm của nó. Phân biệt Vmware và VirtualPC
Kỹ thuật máy ảo
– Máy ảo là sự phát triển lô-gic của kiến trúc phân lớp.
– Bằng cách Điều phối CPU và kỹ thuật Bộ nhớ ảo, có thể tạo cho người dùng ảo giác rằng người đó đang dùng bộ xử lý và bộ nhớ của riêng mình.
– Nói cách khác: Máy tính ảo của người dùng được giả lập trên nền máy tính vật lý.
– Ví dụ: Trên nền CPU loại PowerPC, Motorola, Alpha,… có thể giả lập máy tính ảo Intel chạy HĐH Windows và ngược lại. Khi đó, các lệnh của Intel được chuyển đổi sang lệnh vật lý trước khi thực hiện.
– HĐH máy ảo thương mại đầu tiên: VM/370 của IBM.
Ưu điểm:
– Tính bảo mật cao do các máy ảo độc lập với nhau. Các tài nguyên của máy vật lý được bảo vệ hoàn toàn vì các máy ảo có Thiết bị ảo (Một ổ đĩa ảo, thậm chí toàn bộ máy ảo thực tế chỉ là một tập tin của máy vật lý). Có thể lấy từ Internet về một chương trình lạ và thử vận hành trên máy ảo mà không sợ bị ảnh hưởng (ví dụ do virus) vì nếu có sao cũng chỉ hỏng máy ảo.
– Dễ phát triển hệ thống (System Development) mà không sợ làm ảnh hưởng đến công việc toàn hệ máy đang vận hành. HĐH là chương trình phức tạp, cần liên tục thử nghiệm, tinh chỉnh, hoàn thiện và nâng cấp. Có thể tiến hành Phát triển hệ thống trên một máy ảo thay vì làm trên máy thực.
Nhược điểm:
– Vấn đề lưu trữ vật lý. Thông thường, mỗi máy ảo chỉ dùng một tập tin để lưu tất cả những gì diễn ra trong máy ảo. Do đó nếu bị mất tập tin này xem như mất tất cả.
– Nếu máy tính có cấu hình phần cứng thấp nhưng cài quá nhiều chương trình máy ảo, máy sẽ chậm và ảnh hưởng đến các chương trình khác.
– Do tập trung vào một máy tính, nếu máy bị hư thì toàn bộ các máy tính ảo đã thiết lập trên nó cũng bị ảnh hưởng theo.
– Ở góc dộ bảo mật, nếu hacker nắm quyền điều khiển máy tính chứa các máy ảo thì hacker có thể kiểm soát được tất cả các máy ảo trong nó.
Phân biệt Vmware và VirtualPC
Giống nhau:
– Giúp giả lập máy tính ảo trên một máy tính thật. Khi cài đặt chúng lên, ta có thể tạo nên các máy ảo chia sẻ CPU, RAM, Card mạng với máy tính thật. Điều này cho phép xây dựng nên một hệ thống với một vài máy tính được nối với nhau theo một mô hình nhất định, người sử dụng có thể tạo nên hệ thống của riêng mình, cấu hình theo yêu cầu của bài học.
Khác nhau:
– Về mạng nội bộ, VMW cung cấp tới 4 phương thức kết nối: ‘Bridged Connection’, ‘Network Address Translation’, ‘Host Only’ và ‘Custom’. ‘Bridged Connection’ cho phép máy ảo trực tiếp kết nối với mạng LAN hoặc Internet. ‘Network Address Translation’ cho phép máy ảo kết nối mạng bằng cách dùng chung địa chỉ IP của máy chủ. ‘Host Only’ tạo một mạng riêng mà trong đó máy chủ được coi như một máy tính tách rời. Với ‘Custom’, bạn có thể tạo một mạng ảo theo những yêu cầu cụ thể. Chúng tôi sử dụng phương thức ‘Network Address Translation’ và nhận thấy việc kết nối mạng không gặp bất kỳ khó khăn gì trong cả 2 môi trường Windows và Linux.
– VPC đòi hỏi 2 cửa sổ chương trình: một cho việc quản lí các máy ảo, một cho từng máy ảo. Ngược lại, VMW lại gộp cả 2 cửa sổ trên vào làm một. Tuy nhiên, VPC cung cấp menu của cửa sổ chương trình đơn giản hơn của VMW. Cả 2 phần mềm đều cho phép thực hiện tất cả các thao tác cấu hình chi tiết thông qua menu chính, song bạn cũng có thể trực tiếp thực hiện một số thiết đặt thông qua các biểu tượng ở thanh trạng thái phía dưới.
CHƯƠNG 4: QUẢN LÝ TIẾN TRÌNH
Câu 1: Trình bày mô hình chuyển trạng thái của tiến trình
New: tiến trình đang được tạo lập.
Running: các chỉ thị của tiến trình đang được xử lý.
Blocked: tiến trình chờ được cấp phát một tài nguyên, hay chờ một sự kiện xảy ra .
Ready: tiến trình chờ được cấp phát CPU để xử lý.
Kết thúc: tiến trình hoàn tất xử lý.
Tiến trình P1: vào hàng đợi Job-Queue ở trạng thái New, sẽ đợi 1 khoảng thời gian của quá trình điều phối chậm (Scheduler Long Term) của hệ điều hành(HĐH) để chọn tiến trình, sau khi được O.S chọn, P1 chuyển sang hàng đợi reday quueue và ở trạng thái Ready. Lúc này P1 chỉ đợi cấp CPU và running.
Sau một khỏang thời gian running, tiến trình P2 xuất hiện. Lúc này, hệ điều hành sẽ ghi lại thông tin của P1 vào thanh PCB1 bao gồm những thông tin: con trỏ, trạng thái của P1, số hiệu của tiến trình P1, Bộ đếm P1, nội dung của P1…Và chuyển P1 sang hàng đợi Waiting và chuyển trạng thái Ready. Lúc này, P2 sẽ được cấp CPU và running. Và sau một khỏang thời gian running, P2 cũng sẽ chuyển sang hàng đợi waiting và chuyển trạng thái ready, lúc này HĐH cũng ghi lại thông tin vào thanh ghi PCB2 như đã làm ở P1. Sau đó, HĐH sẽ load lại thông tin của PCB1 và P1 sẽ tiếp tục running. Quá trình này cũng sẽ lập lại cho P2. Đển khi P1 và P2 kết thúc.
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.
Các cung chuyển tiếp trong sơ đồ trạng thái biễu diễn sáu sự chuyển trạng thái có thể xảy
ra trong các điều kiện sau :
• Tiến trình mới tạo được đưa vào hệ thống
• Bộ điều phối cấp phát cho tiến trình một khoảng thời gian sử dụng CPU
• Tiến trình kết thúc
• Tiến trình yêu cầu một tài nguyên nhưng chưa được đáp ứng vì tài nguyên chưa sẵn sàng để cấp phát tại thời điểm đó ; hoặc tiến trình phải chờ một sự kiện hay thao tácnhập/xuất.
• Bộ điều phối chọn một tiến trình khác để cho xử lý .
• Tài nguyên mà tiến trình yêu cầu trở nên sẵn sàng để cấp phát ; hay sự kiện hoặc thao tác nhập/xuất tiến trình đang đợi hoàn tất.
Câu 2: Phân tích vai trò của khối kiểm soát tiến trình
Khối kiểm soát tiến trình (Process Control Block – PCB ) – Bảng thông tin về môi trường và trạng thái hoạt động của tiến trình:
Chứa các thông tin ứng với mỗi process. Process ID, parent process ID
• Credentials (user ID, group ID, effective ID,…)
• Trạng thái process : new, ready, running, waiting…
• Program counter: địa chỉ của lệnh kế tiếp sẽ thực thi
• Các thanh ghi CPU
• Thông tin dùng để định thời CPU: priority,…
• Thông tin bộ nhớ: base/limit register, page tables…
• Thông tin thống kê: CPU time, time limits…
• Thông tin trạng thái I/O: danh sách thiết bị I/O được cấp phát, danh sách các file đang mở,…
• Con trỏ (pointer) đến PCBs khác.
PCB đơn giản phục vụ như kho chứa cho bất cứ thông tin khác nhau từ quá trình này tới quá trình khác.
Câu 3: Trình bày mô hình luân chuyển CPU giữa hai tiến trình
Câu 4: Phân biệt các loại trình điều phối
Điều phối chậm (Long-term scheduler (or job scheduler)) :
• Chọn process nào sẽ được đưa vào ready queue (từ New chuyển sang Ready)
• Kiểm soát Độ đa chương
• Do có nhiều thời gian (tới vài phút), loại scheduler này có điều kiện để lựa chọn kỹ càng nhằm phối hợp cân đối 2 loại tiến trình
. Hướng CPU: tính toán nhiều, ít I/O.
Ví dụ: Công ty có một chiếc ô tô (CPU), nhiều nhân viên cần đi công tác (nhiều tiến trình) phải sử dụng ô tô. Do đó, ô tô (CPU) phải bận (phục vụ) cho nhiều người (nhiều tiến trình).
. Hướng I/O: tính toán ít, nhiều I/O
Ví dụ: Công ty có một chiếc ô tô (CPU), các nhân viên trong công ty chỉ ngồi nghiên cứu (I/O), không sử dụng đến ô tô. Vậy quá lãng phí ô tô (CPU)
• Mục đích cân bằng tải
Điều phối nhanh (Short-term scheduler (or CPU scheduler)) :
• Còn gọi là Điều phối CPU.
• Chọn tiến trình từ Ready Queue để cấp CPU.
• Có tần suất công việc cao. Thường cứ 100 ms lại tốn 10 ms để xác định tiến trình kế tiếp, như vậy 10/(100+10)=9% thời gian CPU được dùng để điều phối công việc.
Điều phối vừa (Medium-term scheduler) :
• Là Short-Term Scheduler được thêm chức năng rút các tiến trình khỏi bộ nhớ, dẫn đến làm giảm Độ đa chương, sau đó đưa lại chúng vào bộ nhớ vào thời điểm thích hợp để tiếp tục thực hiện từ vị trí bị tạm ngừng trước đó.
• Nhờ cách điều phối này, hỗn hợp các tiến trình trong Ready Queue có tính tối ưu hơn.
Ví dụ: Phòng thực hành nhỏ, nhưng nhiều bạn đi học thực hành (nhiều tiến trình). Thầy (HĐH) sẽ đẩy một số bạn ra khỏi lớp (rút tiến trình ra khỏi bộ nhớ). Sau khi nhóm trong phòng học xong Thầy sẽ đẩy các bạn bên ngoài vào phòng học (đưa tiến trình vào bộ nhớ vào thời điểm thích hợp).
<!—nextpage–>
Câu 5: Trình bày những lý do công tác giữa các tiến trình
• Chia sẻ thông tin (Information Sharing): Một tiến trình sử dụng thông tin do tiến trình khác cung cấp. Ví dụ: các bạn trong lớp chia nhóm học. Nhóm một nghiên cứu chương 1, nhóm hai nghiên cứu chương 2. Sau đó, hai nhóm trao đổi thông tin cho nhau. Kết quả hai nhóm mau chóng tìm hiểu hết hai chương.
• Tăng tốc tính toán (Computation Speedup): Các tiến trình cùng làm việc song song trên 1 hoặc nhiều máy để giải quyết bài toán chung.
• Đảm bảo tính đơn thể (Modularity): Chương trình được chia thành các đơn thể chức năng vận hành trong các tiến trình hoặc luồng khác nhau. Ví dụ: mỗi bạn học một bài, đảm bảo tính đơn thể.
• Đảm bảo tính tiện dụng (Convenience): Người dùng có nhu cầu làm nhiều việc một lúc: Soạn thảo, In ấn, Duyệt Web, Lấy file về, Biên dịch chương trình, Kiểm tra chính tả,…
Câu 6: Phát biểu bài toán Tiêu thụ – sản xuất vời thuật giải phù hợp
Phát biểu bài toán:
• Giả sử có Bộ nhớ đệm (Buffer) bao gồm nhiều khoang (Items) được tiến trình Producer lần lượt đưa các sản phẩm S1, S2,… vào.
• Tiến trình Consumer lần lượt lấy sản phẩm ra theo đúng thứ tự.
• Công việc của Producer phải đồng bộ với Consumer: Không được đưa sản phẩm vào khi Buffer đầy, Không được lấy ra khi chưa có.
Trình bày giải thuật:
Câu 7: Truyền thông điệp trong windows (Message-Passing in Windows)
Các hàm API dùng để Gửi/Nhận thông điệp
– SendMessage – Gửi có chờ
– PostMessage – Gửi không chờ
– SendMessageTimeout- Gửi có chờ nhưng với thời hạn
– WaitMessage – Chờ thông điệp đến
– GetMessage – Nhận có chờ
– PeekMessage – Nhận không chờ
Phân biệt khái niệm luồng với tiến trình
• Luồng: là tiến trình nhẹ (LWP – Light Weight Process), một đơn vị cơ bản sử dụng CPU. Luồng cũng có thông tin trạng thái như của tiến trình hệ thống (HWP – Heavy Weight Process)
Ví dụ: Lớp học là một tiến trình. Trong lớp sẽ có một giáo viên(đơn luồng) và các học viên (đa luồng)
• Tiến trình: là chương trình trong thời gian thực hiện (đặt dưới sự quản lý của hệ điều hành). Có sự phân biệt Tiến trình hệ thống (của Hệ điều hành) với Tiến trình người dùng.
Ví dụ: Lớp HCTH102C đang học là một tiến trình
Những ích lợi của công nghệ đa luồng
• Khả năng đáp ứng (Responsiveness) tốt hơn: Trong khi một luồng bị ách hoặc quá bận, luồng khác vẫn vận hành bình thường (Luồng chính của trình duyệt vẫn tương tác với người dùng trong khi dữ liệu được lấy về).
Ví dụ: Các cô ở tổng đài 108 là các luồng. Khi khách hàng điện thoại hỏi 108, thì một trong các cô (cô thứ 1) sẽ trả lời. Nếu trong thời điểm đó khách hàng thứ hai gọi 108, thì một trong các cô (cô thứ 2) còn lại sẽ trả lời cho khách hàng.
• Chia sẻ tài nguyên (Resource Sharing): Theo mặc định, các luồng có thể dùng chung bộ nhớ và tài nguyên của luồng cha. Vài luồng cùng vận hành trong 1 vùng địa chỉ, do đó dễ dùng chung tài nguyên hơn so với trường hợp đa tiến trình.
Ví dụ: Trong nhà ta có kệ sách, tivi, xe gắn máy, … mọi người trong nhà có thể dùng chung sách, tivi, xe máy.
• Tiết kiệm (Economy): Cấp phát bộ nhớ và tài nguyên cho tiến trình là công việc tốn kém. Do luồng chung tài nguyên với cha và các luồng khác, việc tạo lập và chuyển ngữ cảnh cũng nhanh hơn (Solaris 2: Tạo tiến trình chậm hơn 30 lần, Chuyển ngữ cảnh chậm hơn 5 lần).
Ví dụ: Các bạn trong lớp là các luồng đang dùng chung một cái bảng, ai cần ghi thi ghi, ai cần thì chụp hình về xem
• Tận dụng được thế mạnh của kiến trúc đa xử lý: Đa luồng làm tăng tính song song trên hệ máy nhiều CPU. Mỗi luồng có thể chạy bởi CPU riêng.
Câu 2: Trình bày nguyên lý tập nguồn và cho ví dụ minh họa
Tập luồng (Thread Pools):
• Tiến trình cha tạo lập sẵn một tập luồng khi khởi động.
• Các luồng trong tập luồng luôn sẵn sàng chờ công việc.
• Khi tiến trình cha (ví dụ Web Server) nhận thêm một yêu cầu, một luồng được đánh thức và đưa vào vận hành.
• Phục vụ xong, luồng được đưa trả về tập luồng.
• Nếu số yêu cầu lớn hơn số luồng trong tập, tiến trình cha chờ đến khi có luồng được giải phóng.
Ví dụ:
Trong một doanh trai quân đội sẽ có một tướng lĩnh (tiến trình cha) và sẽ có một đội binh (tập luồng).
Đội binh này sẽ sẳn sàng chiến đầu khi có mệnh lệnh (sẵn sàng chờ công việc).
Khi có một tên địch đột nhập, Tướng lĩnh sẽ điều binh sĩ 1 (một luồng) đi bắt tên địch (một luồng được đánh thức và đưa vào vận hành).
Trong khi đó, lại có thêm một tên địch khác đột nhập (nhận thêm một yêu cầu), Tướng lĩnh sẽ điều binh sĩ 2 (một luồng) đi bắt địch (một luồng khác được đánh thức và đưa vào vận hành).
Sau khi bắt địch xong, binh sĩ sẽ trở về doanh trại (luồng được trả về tập luồng)
Câu 3: Lập trình đa luồng trong windows
• Windows sử dụng các hàm trong thư viện Win32 API.
• Ứng dụng Windows vận hành như một tiến trình với 1 hoặc nhiều luồng.
• Bài toán Sản xuất-Tiêu thụ có thể được thực thi bằng Ứng dụng đa luồng (Visual C++ 6.0).
• Nhận độ ưu tiên của luồng bằng hàm: int GetThreadPriority (HANDLE threadHandle)
• Thay đổi độ ưu tiên của luồng bằng hàm:BOOL SetThreadPriority (HANDLE threadHandle, int priority)
Với độ ưu tiên priority:
THREAD_PRIORITY_LOWEST ( -2)
THREAD_PRIORITY_BELOW_NORMAL ( -1)
THREAD_PRIORITY_NORMAL ( 0 )
THREAD_PRIORITY_ABOVE_NORMAL (+1)
THREAD_PRIORITY_HIGHEST (+2)
• Có thể lập trình đa luồng với Visual Basic 6.0:
. Sản xuất – Tiêu thụ
. Animations
. Colors
Câu 1: 4 tình huống ra quyết định của trình điều phối. Và phân biệt điều phối không tiếm quyền và điều phối có tiếm quyền
Bốn tình huống ra quyết định của trình điều phối:
1. Khi tiến trình chuyển từ Running sang Waiting (chờ I/O, chờ tiến trình con)
2. Khi tiến trình chuyển từ Running sang Ready (do ngắt xảy ra)
3. Khi tiến trình chuyển từ Waiting sang Ready (khi kết thúc I/O)
4. Khi tiến trình kết thúc công việc.
Phân biệt điều phối không tiếm quyền và điều phối có tiếm quyền– Điều phối Không tiếm quyền (Non-Preemptive): sơ đồ điều phối chỉ tiến hành trong tình huống 1 và 4. Tiến trình giữ CPU cho đến khi kết thúc bình thường hoặc khi chuyển sang trạng thái Waiting (cách làm trong Windows 3.1 và Macintosh OS). Dùng khi máy không có Timer.- Điều phối Có tiếm quyền (Preemptive): sơ đồ điều phối tiến hành trong cả 4 tình huống được
Câu 2 – BÀI TẬP: Thuật giải ngắn hơn chạy trước
Câu 3 – BÀI TẬP: Điều phối CPU theo vòng RobinCâu 4: Phân biệt thuật giải MQS với thuật giải MFQS
Điều phối hàng chờ nhiều mức (Multilevel Queue Scheduling – MQS)
• Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau, ví dụ: Mức các tiến trình tương tác (Interactive) chạy ở mặt trước ( Foreground ) có độ ưu tiên cao nhất và Mức các tiến trình lô ( Batch ) vận hành trong hậu trường (Background ) .
• Mỗi hàng chờ có thuật giải điều phối riêng, ví dụ: Foreground dùng RRS, Background dùng FCFS.
• Quan hệ giữa các mức:
– Ưu tiên cố định: Xong hết các tiến trình mức trên rồi mới chuyển xuống mức dưới. Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mới mức cao hơn, tiến trình mức dưới sẽ bị tiếm quyền cho tiến trình mới có độ ưu tiên cao hơn ( Hệ Solaris 2 dùng cách này ) .
– Phân bổ theo tỉ lệ thời lượng, ví dụ: 80% thời lượng CPU dành cho Foreground, 20 % cho Background.
Điều phối hàng chờ nhiều mức có điều tiết ( Multilevel Feedback Queue Scheduling – MFQS )• Như MQS nhưng cho phép Điều tiết tiến trình sang mức khc, ví dụ: những tiến trình hướng CPU được đưa xuống mức dưới, trong khi tiến trình hướng I/O hoặc chờ lâu được chuyển lên trên.
• MFQS đặc trưng bởi các thông số:
– Số mức ( số hàng chờ )
– Thuật giải điều phối cho mỗi mức
– Phương thức nâng cấp tiến trình
– Phương thức hạ cấp tiến trình
– Phương thức chọn hàng chờ ( chọn mức ) cho tiến trình mới
– Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình) .
VD: một trường học chỉ có 1 phòng lab (tài nguyên dùng chung) , lớp có giờ học trước thì được vào phòng lab học, các lớp còn lại phải chờ đến khi lớp học trước đó hết giờ mới được vào phòng lab
Câu 2: Khái niện đoạn tương tranh và loại trừ lẫn nhau. Cho ví dụ minh họa.
– Đoạn tương tranh :Xét một hệ có n tiến trình P0,P1, …,Pn, mỗi tiến trình có một đoạn mã lệnh, nếu như trong đoạn mã này các tiến trình thao tác trên các biến chung,đọc ghi file… (tổng quát: thao tác trên dữ liệu chung) thì đoạn mã lệnh đó là đoạn tương tranh.
– Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.
– Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).
Ví dụ:
Kính gửi: Giám đốc công ty x
Tôi tên là: Lê Văn Ba
……….(nội dung đơn)………….
TP Hồ Chí Minh, ngày 5 tháng 5 năm 2011
Người làm đơn
….(chữ ký)….
Lê Văn Ba
. Nội dung đơn này phải được đảm bảo tính toàn vẹn (Integrity), ví dụ: Phía trên là Lê Văn Ba thì phía dưới cũng phải là Lê Văn Ba.
. Nếu vài tiến trình (hơn 1) cùng sửa đơn trên một lúc (không đảm bảo được tính Loại trừ lẫn nhau) thì nội dung của nó có thể không đúng. Ví dụ, giả sử tiến trình P1 (nhà sản xuất) sửa Lê Văn Ba phía trên thành Lê Văn Bàng, trong khi P2 (nhà sản xuất khác) sửa Lê Văn Ba phía dưới thành Lê Văn Bá, mà có tiến trình P3 (nhà tiêu thụ) nào đó “lấy” đơn về dùng (để in ra) thì kết quả sẽ không nhất quán như sau:
Kính gửi: Giám đốc công ty x
Tôi tên là: Lê Văn Bàng
……….(nội dung đơn)………….
TP Hồ Chí Minh, ngày 5 tháng 5 năm 2011
Người làm đơn
….(chữ ký)….
Lê Văn Bá
Câu 3: Khái niệm đèn hiệu (Semaphores).Và 2 ứng dụng của đèn hiệu.
Khái niệm đèn hiệu
– Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề xuất năm 1965.
– Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu):
typedef int semaphore; // Định nghĩa kiểu Đèn hiệu
wait (semaphore S)
{
while ( S <= 0 ); // Chờ bận nếu S<=0
S –; // Giảm S đi 1
}
signal (semaphore S)
{
S ++; // Tăng S lên 1
}
-Việc kiểm tra S <= 0 và giảm S (trong Wait) hoặc tăng S (trong Signal) phải được thực hiện trọn vẹn (không xảy ra ngắt trong thời gian thi hành), do đó Wait và Signal được gọi là các tác nguyên (Atomic Operations).
Câu 4: Thực thi đèn hiệu trong windows
Câu 5: Thực thi bài toán sản xuất và tiêu thụ được đồng bộ bằng ba đèn hiệu
HANDLE semEmpty, semFull; //hai đèn hiệu
CRITICAL_SECTION critSec;//Biến kiểu Mutex
void Producer(void * p)
{
while (1)
{
// … Sản xuất (nextProduced)
// Chờ đến khi có chỗ trống
WaitForSingleObject(semEmpty, INFINITE);
EnterCriticalSection(&critSec);
//…Sắp sản phẩm vào Buffer
// Tăng (semFull) lên 1
ReleaseSemaphore(semFull, 1, NULL);
LeaveCriticalSection(&critSec);
SuspendThread(GetCurrentThread());
}
}
void Consumer()
{
int nextConsumed;
while (1)
{
// Chờ đến khi có sản phẩm
WaitForSingleObject(semFull, INFINITE);
EnterCriticalSection(&critSec);
nextConsumed=buffer[out];
out=(out+1)%BUFFER_SIZE;
// Tăng (semEmpty) lên 1
ReleaseSemaphore (semEmpty, 1, NULL);
LeaveCriticalSection(&critSec);
// … Tiêu thụ (nextConsumed)
SuspendThread(GetCurrentThread());
}
}
– Biến semEmpty dùng để chứa mục quản của đèn hiệu quản lý số vùng trống trong bộ đệm.
– Biến semFull dùng để chứa mục quản của đèn hiệu quản lý số sản phẩm trong bộ đệm.
– CritSec là đối tượng đèn hiệu kiểu mutex dùng để bảo vệ đoạn tương tranh để đảm bảo tính loại trừ lẫn nhau trong công việc của các tiến trình với tài nguyên dùng chung.
– 5 thầy giáo đều cần máy chiếu để dạy ngay trong khi ở phòng thiết bị hiện tại chỉ có 1 máy chiếu => dẫn đến tranh chấp
– 2 xe đi ngược chiều cùng qua 1 cây cầu hẹp, mà cầu thì chỉ có 1 làn xe nên khi 2 xe vào đến giữa cầu thì không thể tiếp tục tiến tới nữa, xãy ra kẹt xe (deadlock) vì không xe nào chịu nhường xe nào.Câu 2: Trình bày bốn điều kiện cần để dẫn đến deadlock
-Loại trừ lẫn nhau (Mutual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-sharable), nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được sử dụng nó.
-Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ 1 tài nguyên và xin thêm tài nguyên đang độc chiếm bởi tiến trình khác.
-Không có tiếm quyền (No Preemption): Tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiến trình ny tự nguyện trả lại hệ thống sau khi sử dụng xong.
-Chờ xoay vịng (Circular Wait): Giả sử cĩ n tiến trình đang chờ ti nguyn l { P1 , P2, … , Pn }, khi đó P1 chờ TN giữ bởi P2 , tiến trình P2 chờ TN giữ bởi P3 , … , Pn chờ P1 .
Câu 3: Khái niện đồ thị cấp phát tài nguyên. Biết cách vẽ và cách giải thich một đồ thị cho trước
– Đồ thị cấp phát tài nguyên (Resource allocation graph-RAG) là đồ thị có hướng với tập nút V và tập cung E.
+ Tập nút V gồm 2 loại:
P ={P1, P2, …, Pn} tập hợp các tiến trình đang vận hành trong hệ thống.
R ={R1, R2, …, Rm} tất cả các tài nguyên trong hệ thống. Mỗi loại Rj có từ 1 đến nhiều
phiên bản. VD: máy in có 3 phiên bản, …
+Tập cung E bao gồm:
Cung yêu cầu (Request edge): có hướng từ Pi -> Rj, P1 yêu cầu 1 phiên bản tài nguyên Rj.
Cung ấn định (Assignment edge): có hướng từ Rj->Pi, 1 phiên bản tài nguyên Rj được cấp
phát cho Pi.
Đồ thị cấp phát tài nguyên gồm có: chu trình và không có chu trình.
o Không có chu trình: không tồn tại Deadlock
o Có chu trình: có hoặc không có Deadlock
.Có Deadlock khi mỗi tài nguyên trên chu trình chỉ có duy nhất 1 phiên bản.
.Có thể không có Deadlock khi tài nguyên thuộc chu trình có nhiều phiên bản.
– Cách vẽ:
Hiển thị mỗi tiến trình Pi là một hình tròn, và mỗi loại tài nguyên Rj là hình chữ nhật. Vì loại tài nguyên Rj có thể có nhiều hơn một phiên bản, chúng ta hiển thị mỗi phiên bản là một chấm nằm trong hình vuông. Chú ý rằng một cung yêu cầu trỏ tới chỉ một hình vuông Rj (tới đường viền), trái lại một cung ấn định cũng phải trỏ tới một trong các dấu chấm trong hình vuông(vào trong viền).
– Giải thích:
Hình 1:
Các tập P, R, và E:
P = {P1, P2, P3}
R = {R1, R2, R3, R4}
E = {P1→R1, P2 →R3, R1 →P2, R2→P2, R3→P3}
Tiến trình P1 đang giữ một phiên bản của loại tài nguyên R2 và yêu cầu được cấp phát 1 phiên bản của loại tài nguyên R1. Tiến trình P2 đang giữ 1 phiên bản của loại tài nguyên R1 và 1 phiên bản của R2 và yêu cầu được được tài nguyên R3 cấp cho 1 phiên bản của nó. Tiến trình P3 đang giữ 1 phiên bản của tài nguyên R3. Còn lại tài nguyên R4 với các phiên bản của nó vẫn chưa có tiến trình nào xin được cấp phát. Từ hình vẽ Đồ thị cấp phát tài nguyên cho thấy không tồn tại chu trình cũng như Deadlock.
Hình 2:
Các tập P, R tương tự hình 1, tập E = {P1 → R1, R1 → P2, P2 → R3, R3 → P3, P3 → R2, R2 → P1, R2→P2}
Tiến trình P1 đang giữ một phiên bản của loại tài nguyên R2 và yêu cầu được cấp phát 1 phiên bản của loại tài nguyên R1. Tiến trình P2 đang giữ 1 phiên bản của loại tài nguyên R1 và 1 phiên bản của R2 và yêu cầu được được tài nguyên R3 cấp cho 1 phiên bản của nó. Tiến trình P3 đang giữ 1 phiên bản của tài nguyên R3 và yêu cầu cấp phát 1 phiên bản của tài nguyên R2. Trong trường hợp này, một chu trình trong đồ thị là điều kiện cần nhưng chưa đủ để tồn tại deadlock, do nhìn hình lại chúng ta thấy có 2 chu trình: P1 → R1 → P2 → R3 → P3 → R2 → P1 và P2 → R3 → P3 → R2 → P2. Nghĩa là tiến trình P3 đang chờ tiến trình P1 hay P2 trả lại tài nguyên R2. Ngoài ra, tiến trình P1 đang chờ tiến trình P2 trả lại phiên bản tài nguyên R1 cho nên tiến trình P1, P2, P3 đã bị Deadlock vì không có phiên bản tài nguyên yêu cầu hiện có (vi phạm điều kiện deadlock).
Hình 3:
Các tập P, R, và E:
P = {P1, P2, P3, P4}
R = {R1, R2}
E = {P1 → R1, R1 → P2 , R1 → P3, P3 → R2, R2 → P1, R2→P4}
Tiến trình P1 đang giữ một phiên bản của loại tài nguyên R2 và yêu cầu được cấp phát 1 phiên bản của loại tài nguyên R1. Tiến trình P2 đang giữ 1 phiên bản của loại tài nguyên R1. Tiến trình P3 đang giữ 1 phiên bản của tài nguyên R1 và yêu cầu cấp phát 1 phiên bản của tài nguyên R2. Tiến trình P4 đang giữ 1 phiên bản của tài nguyên R2. Từ hình chúng ta thấy xảy ra 1 chu trình P1 → R1 → P3 → R2 → P1 nhưng không có deadlock vì tiến trình P4 có thể trả lại phiên bản của loại tài nguyên R2. Tài nguyên đó có thể được cấp phát tới P3 sau đó, chu trình sẽ không còn.
Câu 4: Khái niệm trạng thái an toàn và giải pháp tranh deadlock
• Thế nào là trạng thái an toàn của hệ thống?
Một trạng thái được gọi là an toàn “safe” nếu tồn tại ít nhất một cách mà trong một khoảng thời gian hữu hạn nào đó, hệ thống có thể cấp phát tài nguyên thỏa mãn cho tất cả process thực thi hoàn tất .
Khi đó hệ thống tồn tại một Chuỗi an toàn {P1, P2, … , Pn } bao gồm tất cả các tiến trình sao cho với mỗi Pi, các tài nguyên mà nó yêu cầu có thể được đáp ứng bởi số lượng hiện có cộng thêm của tất cả các Pj mà j < i.
Nếu các TN yêu cầu không có đủ, Pi phải chờ cho đến khi tất cả các Pj trả lại các TN mà chúng chiếm giữ.
Khi Pi nhận được đủ TN cần thiết, nó sử dụng và trả lại HĐH để Pi+1 có thể vận hành, cứ như thế cho đến Pn
Khi một process yêu cầu một tài nguyên đang sẵn có, hệ thống sẽ kiểm tra: nếu việc cấp phát này không dẫn đến tình trạng unsafe thì sẽ cấp phát ngay.
• Trình bày 4 cách ngăn chặn Deadlock.
Để ngăn chặn Deadlock ta phải làm sao cho ít nhất 1 trong 4 điều kiện dẫn đến Deadlock không xảy ra. Cụ thể:
– Với Mutual Exclusion: Đảm bảo TN(tai nguyên) nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình.
– Với Hold and Wait:
1- Khi TT yêu cầu TN, nó không được giữ 1 TN nào khác.
2- TT phải yêu cầu và được cấp tất cả các TN mà nó cần ngay đầu công việc.
– Với No Preemption:
1- Khi TT giữ TN mà xin thêm nhưng không được, các TN mà nó giữ phải bị tiếm quyền sử dụng và trả lại HĐH.
2- Khi TT xin thêm TN, nếu TN này đang được giữ bởi TT khác đang ở trạng thái chờ, TN của TT khác này bị tiếm quyền sử dụng để cấp cho TT đang xin.
– Với Circular Wait: Cấp TN theo một thứ tự nào đấy.
<!—nextpage–>
Câu 5: Thuật giải tránh deadlock RAG (áp dụng cho trường hợp loại tài nguyên chỉ có 1 phiên bản) nếu có nhiều phiên bản thuật giải này không dùng được:
– Trên RAG, lúc đầu tất cả nhu cầu về tài nguyên của tiến trình phải được khai báo trước bằng các Cung Nhu cầu (Claim edge) Pi • • •> Rj chỉ báo rằng Pi có thể sẽ yêu cầu Rj
– Cung Nhu cầu Pi • • •> Rj được chuyển thành Cung Yêu cầu (Request edge) Pi • • •> Rj khi Pi thực sự bắt đầu cần đến Rj .
– Nếu yêu cầu Pi • • •> Rj được HĐH đáp ứng, cung Pi • • •> Rj chuyển thành Cung Ấn định (Assignment edge) Pi <• • • Rj nối phiên bản duy nhất của Rj với Pi .
– Khi HĐH xét yêu cầu Pi • • •>Rj. Hệ chỉ cấp phát Rj cho Pi nếu Cung Ấn định Pi <• • • Rj không tạo ra vòng tròn đồng hướng trong RAG (xét cả các Cung Nhu cầu).
– Thuật giải có độ phức tạp o(n²) với n là số tiến trình trong hệ.
Ví dụ trách deadlock dùng RAG:
Đầu tiên khai báo tất cả các nhu cầu của P1 và P2:P1 và P2 có thể sử dụng R1,R2.
Blog IT 