Lý thuyêt hệ điều hành

Chia sẻ: Nguyen Hoang Hai | Ngày: | Loại File: DOC | Số trang:13

0
313
lượt xem
128
download

Lý thuyêt hệ điều hành

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:
Lưu

Nội dung Text: Lý thuyêt hệ điều hành

  1. 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
  2. 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ơ đồ
  3. 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’
  4. 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
  5. 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
  6. - 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
  7. 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ụ
  8. 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ề
  9. 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
  10. 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)
  11. 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
  12. 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
  13. Need(3)>=Work=> finish(3)=false Need(4)
Đồng bộ tài khoản