Lý thuyêt hệ điều hành
Ngắt là phương tiện để các thiết bị thông báo cho CPU biết việc thay đổi trạng thái của mình.
Từ góc độ CPU, ta có thể coi ngắt là việc ngừng đột xuất việc thực hiện một tiến trình khác khi có một
sự kiện nào đó xảy ra. Như vậy ngắt là công cụ để chuyển điều khiển tới một tiến trình khác mà tiến
trình hiện tại không biết
Lý thuyêt hệ điều hành
5.Trình bày các biện pháp giải quyết khi hệ thống gặp boo tắc. Cho ví dụ đối với một hệ điều
hành cụ thể.
Khi hệ thống gặp boo tắc hệ điều hành có thể áp dụng các phương phương pháp sau:
Thông báo cho operator biết để tự xử lý
Đình chỉ hoạt động của tiến trình: phương pháp này dựa trên việc thu hồi lại các tài nguyên của
những tiến trình bị kết thúc. Có thể áp dụng một trong các cách đình chỉ sau:
Đình chỉ hoạt động của tiến trình trong trạng thái bế tắc.
Đình chỉ hoạt động của từng tiến trình cho tới khi thoát khỏi bế tắc.
ví dụ:
- Hệ điều hành windows XP
- WinServer
- Win2000
………….
8.Nêu khái niệm về ngắt, phân loại ngắt và trình bày quy trình xử lý ngắt của HĐH
Ngắt là phương tiện để các thiết bị thông báo cho CPU biết việc thay đổi trạng thái của mình.
Từ góc độ CPU, ta có thể coi ngắt là việc ngừng đột xuất việc thực hiện một tiến trình khác khi có một
sự kiện nào đó xảy ra. Như vậy ngắt là công cụ để chuyển điều khiển tới một tiến trình khác mà tiến
trình hiện tại không biết
Phân loại ngắt:
Ngắt được chia thành 2 loại:
Ngắt trong
Ngắt ngoài
Quy trình xử lý ngắt của HĐH.
Ghi nhận đặc trưng của sự kiện gây ngắt vào ô nhớ quy định.
Ghi nhận trạng thái của tiến trình bị ngắt
Chuyển địa chỉ chương trình xử lý ngắt vào thanhghi địa chỉ lệnh của CPU
Thực hiện chương trình xử lý sự kiện
Khôi phục lại tiến trình bị ngắt
13. Trình bày khái niệm về file, các yêu cầu của hệ file và các phương pháp tổ chức hệ file.
Khái niệm hệ file
File là đơn vị logic để hệ điều hành quản lý thông tin trên đĩa. File có thể là một chương trình của người
sử dụng, một chương trình của hệ thống hoặc một tập hợp dữ liệu của người sử dụng.
Trên phương diện người sử dụng, dữ liệu trong file được tổ chức thành các bản ghi mà mỗi bản ghi có
thể là một byte hoặc một cấu trúc dữ liệu nào đó.
Bản ghi chính là đơn vị dữ liệu mà các chương trình cần xử lý trong quá trình hoạt động của mình. Như
vậy hệ file là nguyên tắc mà hệ điều hành tổ chức quản lý các file trên các phương tiện lưu trữ.
Các yêu cầu hệ file
Hệ file phải được tổ chức sao cho dễ tìm kiếm, dễ lưu trữ, cập nhật, tiết kiệm không gian nhớ.
Phải đảm bảo tính độc lập của hệ file với hệ thống và thiết bị ngoại vi
Hệ file phải đảm bảo tính an toàn dữ liệu khi có sự cố chương trình hoặc kỹ thuật
Hệ file phải đảm bảo tính an toàn trong vấn đề truy nhập thông tin của người sử dụng
Phương pháp tổ chức của hệ file
Tổ chức thư mục một mức
Tổ chức thư mục hai mức
Tổ chức theo cấu trúc cây
Tổ chức theo đồ thị không chu trình
14. Trình bày nguyên tắc tổ chức và quản lý thiết bị ngoại vi của hệ điều hành.
Tổ chức thiết bị: các thiết bị không kết nối trực tiếp via CPU mà kết nối thông qua một thiét bị đièu
khiển
Mỗi thiết bị điều khiển đóng vai trò như một máy tính chuyên dụng có nhiệm vụ điều khiển các thiết bị
kết nối via nó và tạo thành một kênh vào ra
Mỗi hẹ thống có thể có nhiều kênh vào ra mỗi kênh vào ra có thể có một kênh con
Mõi kênh vào ra thì có ngôn ngữ và tập lệnh riêng dẫn đến dẻ đièu khiển hoạt dọng của các kênh cần có
một chương trình điều khiển ( còn gọi là Driver)
Để hệ thống có thể điều khiển được các kênh vào ra thì chương trình điều khiển kênh phải được nạp
vào hệ thống khi khởi động hệ điều hành
Nguyên tắc quản lý thiết bị
điều khiển các thao tác vào ra thông qua các chương trình điều khiển kênh
Nguyên lý này cho phép trong khi các thao tác vào ra được thực hiện tính toán khi thao tác vào ra kết thúc
các thiết bị sẽ phât tín hiệu ngắt báo cho CP
U biết để xử lý.
3. Trình bày nguyên tắc chung của các phương pháp giải quyết bài toán đoạn tới hạn.
- Phương pháp khóa trong:
Dựa trên cơ sở nếu hai hay nhiều tién trình cùng định ghi vào mộ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ực hiện còn các tiến trình khác phải chờ
- Phương pháp kiểm tra và xác lập:
Dựa vào sự hỗ trợ của phần cứng có một lệnh thực hiện hai phép xử lý liên tục không bị tách rời
- Phương pháp đèn hiệu
đèn hiệu S là một biến nguyên mà chỉ có hai phép xử lý WAIT và SIGNAL mới thay đổi được giá trị của
nó
- Phương pháp dùng trình thư ký
Là các thủ tục và cấu trúc thông tin động hoạt động trong chế độ phân chia thời gian hỗ trợ việc thực
hiện tiến trình. Mỗi thời điểm chỉ có một tiến trình làm việc được với monitor
- Phương pháp tổ chức liên lạc giữa các tiến trình
HĐH sẽ xây dung một hẹ thóng thong báo gữa các tiến trình dựa trên ba phương pháp cơ bản:
Send message
Recive message
Communication link
9. Nêu mục đích của quản lý bộ nhớ; Trình bày nguyên tắc hoạt động của sơ đồ phân hoạch cố
định
Mục đích:
Phân bổ không gian nhớ cho các tiến trình
Thu hồi không gian nhớ khi tiến trình kết thúc
Quản lý được không gian nhớ tự do
Nguyên tắc hoạt động của sơ đồ phân hoạch cố định
Bộ nhớ hệ thống được chia thành n phần không nhất thiết bằng nhau mỗi phần được coi như là một bộ
nhớ độc lập và được gọi là fân hoạch mỗi phân hoạch có thể nạp được một chương trình và tổ chức
thực hiện đồng thời
Vì mỗi phân hoạch được coi như là một bộ nhớ độc lập dẫn đến chương trình được nạp vào phân hoạch
nào sẽ tồn tại ở phân hoạch đó cho tới khi kết thúc
Mỗi phân hoạch sẽ được gắn với một số lớp phục vụ chương trình khi định vị vào bộ nhớ cũng được
phân lớp theo khai báo của người sử dụng mỗi phân hoạch chỉ phục vụ các chương trình thuộc lớp mình
quản lý như vậy chúng ta có thể tránh được trường hợp định vị chương trình nhỏ vào vùng nhớ lớn tránh
lãng phí bộ nhớ
7. Nêu khái niệm lập lịch cho CPU, trình bày các phương pháp lập lịch và tiêu chuẩn đánh giá
Khái niệm:
Để điều kiện các tién trình ở nhiều trạng thái khác nhau hệ thống sẽ tổ chức các tiến trình thành hàng
đợi theo sơ đồ
St ar t End
Ready CPU
Queue
I/ I / O queue
O
I/ I / O queue
O
Lập lịch cho CPU có nghĩa là tổ chức một hàng đợi các tiến trình sẵn sàng để phân phối giờ CPU cho
chúng sao cho hiệu suet sử dụng của CPU là tối ưu nhất
Mỗi tiến trình ở trạng thái sẵn sàng sẽ được gán một độ ưu tiên độ ưu tiên nà phụ thuộc vào yếu tố thời
điểm hình thành, kết thúc, thời gian thực hiện
Các phương pháp lập lịch
- Lập lịch với thời gian dài áp dụng cho các tiến trình đã được lập danh sách chuẩn bị đưa vào bộ nhớ
Lập lịch với thời gian ngắn áp dụng cho các tiến trình đã được đưa vào bộ nhớ trong
- Lập lịch với thời gian trung bình áp dụng cho các tiến trình có thao tác hoán đổi
Tiêu chuẩn đánh giá
- Sự công bằng
- Tiến trình dù sớm hay muộn cũng được cấp phát giờ CPU
- Tận dụng giờ CPU thời gian vô ích của CPU càng ít càng tốt
Tổng thời gian thực hiện tiến trình càng ngắn càng tốt
- Thời gian đáp ứng tính từ khi tiến trình đưa ra yêu cầu giờ CPU cho tới khi tiến trình đưa ra yêu cầu giờ
CPU cho tới khi nó được phân bổ càng ngắn càng tốt
6. Nêu khái niệm về dãy tiến trình an toàn và nội dung thuật toán chuyển hệ sang trạng thái an
toàn
Khái niệm
Cho dãy tiến trình P1, P2........Pn song hành: dãy tiến trình được gọi là an toàn nếu via mọi tiến trình Pi tài
nguyên mà Pi cần sẽ được đáp ứng bởi tài nguyên khả dụng của hệ thống + tài nguyên do tién trình mà
Pi’ đang dữ với điều kiện i’ Stept 4: Kiểm tra tính an toàn của hệ thống:
Nếu ở trạng thái an toàn thì phân bổ tài nguyên theo dự định, ngược lại tiến trình Pi phải đợi cùng với
các yêu cầu tài nguyên Request(i)
15. Trình bày mục đích của vùng đệm trong các phép trao đổi ngoại vi. Phân loại các kiểu vùng
đệm và nêu rõ ưu nhược điểm
Mục đích
- Giảm số lượng vào/ra vật lý
- Cho phép thực hiện song song các thao tác vào/ra via các thao tác xử lý thông tin khác nhau
- Cho phép thực hiện trước các phép nhập dữ liệu
Phân loại vùng đệm và ưu nhược điểm:
- Vùng đệm trung chuyển
+ưu điểm:
Có hệ số song song cao phổ dụng, cách thức tổ chức đơn giản
+nhược điểm:
Tốn bộ nhớ, kéo dài thời gian trao đổi thông tin ở bộ nhớ trong
- Vùng đệm xử lý
+ưu điểm:
Tiết kiệm không gian nhớ, rút ngắn thời gian trao đổi thông tin ở bộ nhớ trong
+nhược điểm:
Tốc độ giải phóng vùng đệm chậm, hệ số song song thấp, không phải thao tác trao đổi vào/ra nào cũng
có thể sử dụng được vùng đệm này
Đây là phương pháp tổ chức vùng đệm phức tạp
- Vùng đệm vòng tròn
+ưu điểm:
Tránh được việc phải thực hiện các thủ tục tạo vùng đệm nhiều lần
+nhược điểm:
Có thời điểm vùng đệm không sử dụng hết, gây lãng phí bộ nhớ
Vùng đệm có thể trở thành tài nguyên găng khi có nhiều file mở đồng thời
2. Trình bày khái niệm về tiến trình và các trạng thái của một tiến trình. Nêu đặc trưng của các
mối quan hệ giữa các tiến trình trong hệ thống
Khái niệm:
Là một chương trình đang hoạt động hoặc đang được xử lý khi đó nó sở hữu một con trỏ lệnh tập các
thanh ghi và yêu cầu một số tài nguyên hệ thống như: CPU, bộ nhớ và các thiết bị.
Các trạng thái của tiến trình:
Trạng thái của tiến trình được xác định bởi hoạt động của tiến trình tại thời điểm đó
Mỗi tiến trình có thể nhận trạng thái sau
New Ready Runi ng Hal t
W t i ng
ai
New: khởi tạo
Ready: sẵn sàng
Runing: thực hiện
Waiting: đợi
Halt: kết thúc
Để điều khiển hoạt động của tiến trình hệ thống sử dụng công cụ là khối điều khiển tiến trình bao gồm 4
thành phần
+ Số thứ tự tiến trình
+ Con trỏ trạng thái
+ 1 vùng nhớ lưu trữ giá trị các thanh ghi tiến trình đang sử dụng
+ Thông tin về tài nguyên tiến trình đang sử dụng hoặc được phép sử dụng
Đặc trưng của các mối quan hệ giữa các tiến trình trong hệ thống
Các tiến trình hoạt động trong hệ thống sẽ tồn tại 2 mối quan hệ
- Độc lập:
Trạng thái của nó không bị chia sẻ với bất kỳ tiến trình nào
Việc thực hiện tiến trình là đơn định
Tiến trình có thể tái hiện 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ác tiến trình trong hệ thống
- Hợp tác:
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 không đơn định
tién trình không thể tái hiện lại
11.Trình bày các phương pháp quản lý và cấp phát không gian đĩa tự do trên đĩa từ của hệ điều
hành
Các phương pháp quản lý không gian nhớ tự do
-Bitmap:
Không gian đĩa được chia thành các khối đĩa và đánh số từ 0 tới max mỗi khối đĩa có 1 bít trạng thái khối
nào đã sử dụng bit trạng thái có giá trị là 1 chưa sử dụng có giá trị 0 tập hợp các giá trị 0,1 sẽ tạo thành 1
bit vector đọc thông tin trong bit vector hệ điều hành sẽ xác định được không gian nhớ tự do
-Liệt kê:
Các khối đĩa tự do sẽ được liệt kê trong 1 danh sách móc nối con trỏ đầu danh sách trỏ tới khối đĩa tự do
đầu tiên mỗi khối đĩa tự do tồn tại 1 con trỏ tới khối kế tiếp
-Phương pháp lập nhóm
Các khối đĩa liên tục sẽ được nhóm thành một nhóm khối đầu trong nhóm ghi địa chỉ các khối còn lại
trong nhóm khối cuối trong nhóm ghi địa chỉ khối đầu của nhóm tiếp theo
-Phương pháp đếm
Hệ thống danh sách quản lý địa chỉ các khối tự do đầu tiên trong các nhóm và số lượng các khối tự do
trong nhóm đó
Các phương pháp cấp phát không gian đĩa tự do
- Cấp phát liên tục:
Để cấp phát không gian nhớ trong 1 file HĐH sẽ chọn một đoạn liên tục các khối đĩa tự do có kích thước
đủ để cấp phát trong khai báo
để định vị một file trên đĩa HĐH chỉ cần xác định địa chỉ khối đầu và số lượng các khối đã dùng
- Cấp phát liên kết
Mỗi file được định vị trong thư mục thiết bị bởi hai con trỏ một con trỏ tới khối đầu 1 con trỏ tới khối
cuối mỗi khối đã cấp phát thì có con trỏ, trỏ tới khối kế tiếp
- Cấp phat theo chỉ số
để cấp phát không gian nhớ trong một file HĐH sẽ sử dụng 1 khối đặc biệt gọi là khối đĩa chỉ số nội
dung khối đĩa chỉ số ghi địa chỉ các khối đã cấp phát cho file
16. Trình bày khái niệm và mục đích của kỹ thuật Spool, cho ví dụ minh họa
Khái niệm:
Các thiết bị vào ra đều có thể mô phỏng bằng chương trình và hoạt động theo nguyên tắc quản lý tiến
trình
Việc mô phỏng thiết bị sẽ tạo ra các thiết bị ảo
Mục đích:
- Mô phỏng qúa trình điều khiển và quản lý thiết bị, thiết bị ảo
- Tạo ra các Spool mới( hệ thống mô phỏng các phép trao đổi ngoại vi trong chế độ trực tiếp)
- Tạo ra các hiệu ứng song song, các thiết bị chỉ được khai thác trong chế độ tuần tự
Ví dụ minh họa:
Máy in là một thiết bị chỉ có thể họat động trong chế độ tuần tự
1. Nêu 7 nội dung cơ bản khi thiết kế và xây dung HĐH
- Nguyên tắc modul:
HĐH được xây dung từ các modul độc lập giữa chúng có quy tắc liên kết để tạo thành 1 chương trình
thống nhất nguyên tắc modul cho phép tổ hợp các modul nhỏ theo nhiều cách khác nhau để giải quyết
những vấn đề phức tạp và đảm bảo tính đa dạng chức năng của HĐH
- Nguyên tắc tương đối trong định vị:
Các modul chương trình được viết theo địa chỉ tương đlei tính từ đầu bộ nhớ khi thực hiện chúng được
định vị vào một vùng nhớ cụ thể sao cho phù hợp via môi trường nguyên tắc này giúp cho hẹ thống sử
dụng bộ nhớ một cách linh hoạt và HĐH không phụ thuộc cấu hình cụ thể của bộ nhớ
- Nguyên tắc macro processor:
Khi có công việc cụ thể cần thực hiện hệ thống mới liệt kê các yêu cầu của công việc trên cơ sở đó xây
dung các chương trình tương ứng để thực hiện chúng nguyên tắc này đảm bảo cho quá trình đối
thoạigiữa người và máy tính linh hoạt không phụ thuộc vào một chương trình dịch phức tạp
- Nguyên tắc lập chức năng:
Mỗi công việc mỗi thao tác hệ điều hành cần phải cung cấp nhiều cách thức thực hiện điều này đảm
bảo tính thuận lợi cho người sử dụng và tính an toàn của hệ thống
- Nguyên tắc giá trị chuẩn:
Mỗi modul có một tập tham số ứng via các trường hợp thường lập và gọi là tập chuẩn khi thực hiện
modul hệ thống sẽ tìm kiếm tham số trong tập chuẩn trước
- Nguyên tắc khởi tạo khi cài đặt:
Khi cài đặt HĐH chương trình cài đặt sẽ kiểm tra cấu hình phần cứng của hệ thống sau đó tạo ra môt
phiên bản làm việc tối ưu cả về cấu trúc và phương thức hoạt động
- Nguyên tắc bảo vệ nhiều mức:
để đảm bảo an toàn hệ thống và dữ liệu các chương trình và dữ liệu phải được bảo vệ ở nhiều mức
khác nhau.
4. Trình bày nguyên tắc chung của phòng ngừa bế tắc và các biện pháp phòng ngừa bế tắc của
HĐH
Nguyên tắc chung:
Ngăn ngừa: áp dụng các biện pháp để hệ thống không rơi vào trạng thái bế tắc
Dự báo và tránh bế tắc: áp dụng biện pháp kiểm tra các tiến trình xem có bị rơi vào trạng thái bế tắc hay
không . Nếu có thì thông báo trước khi bế tắc xảy ra
Nhận biết và khắc phục: tìm cách phát hiện và giải quyết
Biện pháp phòng ngừa bế tắc:
- loại bỏ tài nguyên găng:
mô phỏng tài nguyên găng bằng các tài nguyên có thể dùng chung được
- loại bỏ yếu tố giữ và đợi
thực hiện phân bổ trước tài nguyên tién trình chỉ có thể thực hiện khi mọi tài nguyên mà nó yêu cầu đã
được phân bổ đủ, tiến trình chỉ được phép đòi tài nguyên khi nó không dữ tài nguyên nào cả nếu tiến
trình phải đợi thì mọi tài nguyên nó đang dữ đều được giải phóng
- xây dung hệ thống ngắt tài nguyên
được xây dung theo hai phương pháp
+nếu tiến trình đang dữ một tài nguyên và yêu cầu tài nguyên bổ sung nhưng hệ thống không có để phân
bổ thì các tài nguyên khác hiện có của tiến trình sẽ bị ngắt
+nếu tiến trình đang dữ một số tài nguyên và yêu cầu tài nguyên bổ sung nhưng hệ thống không có dể
phân bổ khi dó hệ thống sẽ kiểm tra tài nguyên mà tiến trình yêu cầu có bị giữ bởi các tiến trình khác
đang đợi hay không nếu có thì ngắt các tiến trình đó lấy lại tài nguyên để phân bổ cho tiến trình yêu cầu
ngược lại tiến trình yêu cầu cũng phải đợi
- loại bỏ yếu tố chờ đợi vòng tròn: có thể loại bỏ bằng cách sắp xếp thứ tự tài nguyên
12. Trình bày các yếu tố liên quan đến thời gian truy nhập đĩa từ, từ đó nêu khái niệm về lập
lịch cho đĩa từ và nội dung của các phương pháp
Các yếu tố liên quan đến thời gian truy nhập đĩa:
- thời gian di chuyển đầu từ đọc/ghi đến track hoặc cylinder cần thiết
- thời gian định vị đầu từ đọc/ghi tại khối đĩa cần truy nhập và thời gian truy nhập dữ liệu
- thời gian định vị đầu từ đọc ghi và thời gian truy nhập dữ liệu thông thường cố định và phụ thuộc
cấu trúc kỹ thuật của ổ đĩa
Khái niệm lập lịch
Lập lịch cho đĩa là xây dung các thuật toán dịch chuyển đầu từ đọc ghi sao cho thời gian truy nhập đĩa là
tối ưu nhất
Nội dung các phương pháp lập lịch cho đĩa
1> FCFS
để truy nhập tới một file hệ thống sẽ tổ chức hàng đợi các yêu cầu phục vụ của các track. Track nào có
yêu cầu phục vụ trước thì đầu từ đọc ghi sẽ dịch chuyển tới đó trước
ví dụ:
file F1 được phân bổ lần lượt tại các track có vị trí sau: 98,183,37,122,14,124,65,67. đầu từ đang đọc ghi
ở track 53:
144 37 53 65 67 98 122 124 183
444
2> SSTF
Track nào có thời gian di chuyển đầu từ đọc/ghi ngắn nhất thì phục vụ trước
144 37 53 65 67 98 122 124 183
444
3> Scan
đầu từ đọc ghi sẽ quét từ track nhỏ nhất đến track lớn nhất sau đó quét ngược lại, track nào có nhu cầu
sẽ phục vụ
144 37 53 65 67 98 122 124 183
444
4> C- Scan
Thuật toán này tương tự thuật toán Scan nhưng đầu từ đọc/ghi không phục vụ đường về
144 37 53 65 67 98 122 124 183
444
5> Look
Tương tự thuật toán Scan nhưng đầu từ đọc ghi chỉ phục vụ các track có yêu cầu không quét tới track
đầu tiên hoặc cuối cùng
144 37 53 65 67 98 122 124 183
444
6> C- look
Tương tự thuật toán look nhưng đầu từ đọc ghi không phục vụ đường về
144 37 53 65 67 98 122 124 183
444
Bài tập
1. giả sử không gian nhớ của đĩa từ được mô tả qua hình vẽ sau (mỗi ô là một block).
File F1 được phân bổ tại các block có số hiệu: 0,2,4,5,9,13,14,15.
Trình bày phương pháp cấp phát liên kết (block đầu là 0, block cuối là 2) và phương
pháp cấp phát theo chỉ số (block chỉ số là 15)
Phương pháp cấp phát liên kết:
Mỗi file được định vị trong thư mục thiết bị bằng hai con trỏ, một con trỏ tới khối đĩa
đầu tiên, một con trỏ tới khối đĩa cuối cùng đã cấp phát cho file. Trong mỗi khối đã cấp
phát cũng có một con trỏ để trỏ tới khối đĩa kế tiếp.
Fi l e St ar t End
0 2
F1 0 2
4 5
9
13 14 15
Phương pháp cấp phát theo chỉ số
để cấp phát không gian nhớ cho một file hệ thống sử dụng một khối đĩa đặc biệt gọi là khối
đĩa chỉ số cho mỗi file. Trong khối đĩachỉ số chứa địa chỉ của các khối đĩa đã cấp phát cho file.
Trong thư mục thiết bị địa chỉ của các khối đĩa chỉ số. Khi một khối đĩa được cấp phát cho file
thì hệ thống loại bỏ địa chỉ của khối đĩa này khỏi danh sách các khối đĩa tự do và cập nhật vào
khối chỉ số của file.
Fi l e i ndex
Bl ock
F1 15
0 2
0
4 5 2
4
5
9 9
13
14
15
13 14 15
2. Giả sử vùng không gian nhớ của khối đĩa được mô tả qua sơ đồ sau: (Các block sẫm màu là
các block đã sử dụng)
Need(4)Nhóm Khối đầu Khối cuối
I 0(0) 0(2)
II 2(2,3) 3(5)
III 5(5,6) 6(8)
IV 8(8,9) 9(11)
V 11(11) 11(14)
VI 14(14) 14(17)
VII 17(17) 17(19)
VIII 19(19,20) 20(22)
IX 22(22,23,24,25,26) 26(28)
X 28(28,29) 29(...)
Phương pháp đếm:
Danh sách Số lượng
0 1
2 2
5 2
8 2
11 1
14 1
17 1
19 2
22 5
28 2
3. Cho dãy tiến trình via thời gian thực hiện tương ứng như sau:
Process T thực hiện
P1 10
P2 2
P3 7
P4 1
P5 5
vẽ sơ đồ Grant theo các thuật toán: FCFS, SJF, RR(q=2) và tính thời gian chờ đợi trung bình
trong các thuật toán.
LG:
FCFS:
P1 P2 P3 P4 P5
0 10 12 19 20 25
Thời gian chờ đợi trung bình: 20/5=4
SJF:
P4 P2 P5 P3 P1
0 1 3 8 15 25
Thời gian chờ đợi trung bình:15/5=3
RR:
P1 P2 P3 P4 P5 P1 P3 P5 P1 P3 P5 P1 P3 P1
0 2 4 6 7 9 11 13 15 17 19 21 23 24 25
Thời gian chờ đợi trung bình: 14/5=2.8
4. Giả sử có 5 tiến trình và 3 kiểu tài nguyên A,B,C như sau
Proces Allocation Max Available
A B C B C A B C
P0 3 0 2 7 0 3 3 3 2
P1 2 1 0 9 2 2
P2 0 1 1 2 5 3
P3 0 0 2 4 3 2
P4 2 0 0 3 2 2
Giả sử quá trình P4 yêu cầu tài nguyên (1,2,2). Hỏi có thể phân bổ tài nguyên cho tiến trình P4
được hay không?
LG:
Need= Max-Allocation
Process Need
P0 4 0 1
P1 7 1 2
P2 2 4 2
P3 4 3 0
4 1 2 2
Gỉa sử tiến trình P4 có yêu cầu tài nguyên (1,2,2). Theo thuật toán chuyển hệ sang trạng thái an
toàn, ta có:
Request(4) thỏa mãn
Request(4) thỏa mãn
Do đó hệ dự định phân bổ:
Available=Available-Request(4)=(2,1,0)
Allocation(4)= Allocation(4)+ Request(4)=(3,2,2)
Need(4)= Need(4) -Request(4)=(0,0,0)
Và có trạng thái như sau:
Proces Allocation Need Available
A B C B C A B C
P0 3 0 2 4 0 1 2 1 0
P1 2 1 0 7 1 2
P2 0 1 1 2 4 2
P3 0 0 2 4 3 0
P4 3 2 2 0 0 0
áp dụng thuật toán kiểm tra tính an toàn của hệ ta có:
Work:=Available=(2,1,0)
Finish(i)=false via i=0,1,2,3,4
xét
Need(0)>=Work=> finish(0)=false
Need(1)>=Work=> finish(1)=false
Need(2)>=Work=> finish(2)=false
Need(3)>=Work=> finish(3)=false
Need(4)
