HĐH - Ôn Tập Cuối Kỳ - Part 2 (Lý Thuyết) | Facebook

Có thể bạn quan tâm

FacebookTham gia hoặc đăng nhập Facebook Email hoặc điện thoạiMật khẩuBạn quên tài khoản ư?Đăng nhậpBạn có muốn tham gia Facebook không?Đăng kýĐăng kýHĐH - Ôn tập cuối kỳ - Part 2 (Lý thuyết)Lưu Biêu Nghị·Thứ Tư, 19 tháng 6, 2019·Nhóm công khai#StudyWithMe #HĐHNay mình sẽ thêm vài câu lý thuyết ở chương 5, 6 và giải quyết chương 7 và 8 nhé ^^ !Chương 5 :Câu 6 : Monitor là gì ? Nêu cách hoạt động của monitor và ứng dụng vào một bài toán đồng bộ ?Monitor là một công cụ đồng bộ, có chức năng tương tự như semaphore nhưng dễ điều khiển hơn.Monitor, là một kiểu dữ liệu trừu tượng, lưu lại các biến chia sẻ và các phương thức dùng để thao tác lên các biến chia sẻ đó. Các biến chia sẻ trong monitor chỉ có thể được truy cập bởi các phương thức được định nghĩa trong monitor.Một monitor chỉ có 1 process hoạt động, tại một thời điểm bất kỳ đang xét.Bằng cách này, monitor sẽ đảm bảo mutual exclusion và dữ liệu chia sẻ của bạn sẽ được an toàn.Cấu trúc của một monitor :

Cách thức hoạt động :Các process sẽ “vào” monitor bằng cách gọi đến các phương thức (method) được định nghĩa trong monitor.Khi gọi phương thức, nếu không có process nào đang active trong monitor thì process đó được thực hiện phương thức nêu trên trong monitor. Ngược lại, nếu có một process nào đó đang thực thi trong monitor, thì process sẽ vào hàng đợi entry queue. Và sau khi process đã thoát khỏi monitor, thì nó sẽ đánh thức process kế tiếp trong entry queue.

Ngoài ra, trong monitor còn chứa một (hoặc nhiều) biến condition. Biến condition được định nghĩa bằng code như sau :

Biến condition được dùng khi có một process A đang thực thi câu lệnh gì đó trong monitor, nhưng bỗng dưng lại cần yêu cầu một resource chưa được thả. Khi đó, process đó sẽ gọi x.wait() (hoặc y.wait(), tuỳ cách cài đặt của bạn). Khi đó, process B khác sẽ được phép vào monitor mà không phải chờ process A ra khỏi monitor.

Khi process B giải phóng tài nguyên yêu cầu bởi process A, process B sẽ gọi x.signal (hoặc y.signal() tuỳ vào cách cài đặt của bạn). Lệnh trên sẽ chuyển một process từ conditional queue vào monitor. Khi đó, để đảm bảo mutual exclusion cho monitor, process gọi signal sẽ bị blocked và bị đưa vào 1 queue khác gọi là urgent queue.Ứng dụng : Một ứng dụng nổi bật của monitor đó là “Ứng dụng monitor để giải quyết bài toán Dining Philosophers”.Trước khi ăn, mỗi triết gia phải gọi hàm pickup(), ăn xong rồi thì phải gọi hàm putdown() như sau :

Pickup và Putdown là 2 phương thức được định nghĩa trong monitor dp như sau :

Câu 7 : Phân biệt semaphore với monitor ? Nêu ứng dụng của từng giải pháp ?Bảng dưới đây thể hiện sự khác biệt giữa semaphore và monitor :

Cả semaphore và monitor đều được dùng như là một công cụ để đồng bộ hoá. Cả 2 đều có thể thực hiện công việc như nhau và thay thế được cho nhau dễ dàng.Điểm khác biệt có thể thấy rõ nhất, như đã nói ở bảng trên, đó là monitor dễ sử dụng hơn semaphore. Semaphore giống như con trỏ trong C++, mạnh mẽ và low-level nhưng lại yêu cầu sự cẩn thận, chu đáo từ người sử dụng nó. Nếu bạn wait() mà quên release() trên semaphore, bạn sẽ rất có thể gặp phải trường hợp deadlock, hoặc những bug khó phát hiện. Monitor, ngược lại, đã giúp bạn giải quyết vấn đề trên bằng cách gọi hàm thay vì phải tự kiểm soát signal() và wait().Câu 8 : Áp dụng semaphore vào bài toán reader-writer, giải thích rõ hoạt động ?Code hoàn chỉnh :

Chương 6 : Câu 6 : Làm gì để tránh deadlock (Deadlock avoidance) ?Việc ngăn deadlock ngăn cản việc deadlock xảy ra bằng cách giới hạn số lượng yêu cầu tài nguyên của process. Tuy nhiên, việc thiết lập giới hạn như vậy sẽ dẫn đến một hệ luỵ đó là hiệu suất sử dụng thiết bị thấp.Có một cách khác để quản lý deadlock, đó chính là việc xét xem các tài nguyên sẽ được yêu cầu như thế nào bởi process. Ví dụ, trong một hệ thống có một process P1 và P2. Hệ thống cần biết process P1 sẽ yêu cầu tài nguyên A và sau đó là tài nguyên B, sau đó sẽ giữ chúng và chỉ thả ra sau khi đã thực hiện xong công việc của mình. Trong khi đó P2 sẽ yêu cầu tài nguyên B và sau đó là tài nguyên A. Với việc biết trước yêu cầu tài nguyên của 2 process như vậy, hệ thống sẽ có thể quyết định là có cấp phát tài nguyên ngay cho process khi yêu cầu không, hay là sẽ bắt process đó đợi. Đối với từng request tài nguyên của process, để ra quyết định, hệ thống sẽ cần biết số lượng resources còn trống, số lượng resources đã cấp cho từng process và các request trong tương lai, cũng như việc nhả các resource của process. Các thuật toán khác nhau sẽ yêu cầu các thông tin khác nhau.Nghe có vẻ phức tạp nhỉ ? Tuy nhiên, trong phạm vi bài học, chúng ta chỉ xét đến mẫu đơn giản nhất và hiệu quả nhất là việc các process phải cung cấp số lượng tối đa (maximum number) các resources mà nó cần.Vậy, để tránh deadlock, giải thuật của chúng ta xây dựng sẽ :

Yêu cầu mỗi tiến trình khai báo số lượng tài nguyên tối đa cần để thực hiện công việc.
Kiểm tra trạng thái cấp phát tài nguyên để đảm bảo hệ thống không rơi vào deadlock (thông qua việc tìm chuỗi an toàn – bằng giải thuật banker hay cách khác).
Định nghĩa trạng thái cấp phát tài nguyên (cấp hoặc không cấp) dựa trên số tài nguyên còn lại (available resources), số tài nguyên đã được cấp phát (allocated resources) và yêu cầu tối đa về tài nguyên của các tiến trình (maximum number).

Trạng thái an toàn/không an toàn (safe/unsafe) :

Một trạng thái của hệ thống được gọi là an toàn (safe) khi tồn tại một chuỗi an toàn.
Một chuỗi quá trình <P1,P2,…,Pn> là một chuỗi an toàn nếu :
- Với mọi I = 1,…n yêu cầu tối đa về tài nguyên của Pi có thể được thoả bởi :
  - Tài nguyên mà hệ thống đang có sẵn sàng.
  - Cùng với tài nguyên mà tất cả các Pj (j<i) đang giữ.
Một trạng thái của hệ thống được gọi là không an toàn (unsafe) nếu không tồn tại một chuỗi an toàn.
VD : Hệ thống có 12 tap drive và 3 tiến trình P0,P1,P2 :
- Tại thời điểm t0 :

Nếu sau khi cấp tài nguyên, xét thấy hệ thống an toàn -> Có thể cấp tài nguyên -> Cấp tài nguyên.
Nếu sau khi cấp tài nguyên, xét thấy hệ thống không an toàn -> Không cấp -> Rút lại.

Lợi ích của việc sử dụng giải thuật tránh deadlock thay vì ngăn deadlock :

Hiệu quả hơn.
Kiểm soát ở việc cấp tài nguyên.
Đảm bảo hiệu suất sử dụng tài nguyên tối đa đến mức có thể.

Câu 7 : Trình bày giải thuật Banker ?Thuật toán sắp xếp việc cấp phát tài nguyên dựa vào đồ thị RAG không thể áp dụng được đối với các hệ thống có nhiều thực thể (instance) của cùng một loại tài nguyên (ví dụ R có 2 thực thể), lúc đó ta phải dùng đến một giải thuật tránh deadlock có tên là giải thuật Banker. Được gọi là giải thuật Banker là vì thuật toán có thể được sử dụng trong các hệ thống ngân hàng để đảm bảo rằng ngân hàng sẽ không chi tiền đến mức mà nó không thể đáp ứng được nhu cầu của tất cả các khách hàng.Trạng thái an toàn là trạng thái mà số lượng tài nguyên còn lại (Available) của hệ thống có thể đáp ứng được tất cả các process và tạo ra 1 chuỗi an toàn.Chuỗi an toàn là một thứ tự thực hiện việc cung cấp tài nguyên cho các process, với giả định rằng các process sẽ trả lại tài nguyên mà nó đang giữ sau khi thực hiện xong. Hoạt động : Khi một tiến trình vào hệ thống, tiến trình đó cần phải đưa ra số lượng thực thể tối đa mà nó cần (để từ đó hệ thống có thể xác định trạng thái an toàn, dựa vào việc thoả mãn yêu cầu của tất cả process). Con số này không được vượt quá số lượng tài nguyên hiện đang có trong hệ thống.Khi một process yêu cầu tài nguyên, hệ thống sẽ xem xét : Liệu sau khi cấp tài nguyên thì hệ thống có còn đang ở trạng thái an toàn hay không ? Nếu có thì hệ thống sẽ cấp, ngược lại hệ thống sẽ không cấp tài nguyên cho process. Lúc đó process phải chờ đến khi các process khác giải phóng đủ số lượng tài nguyên cần thiết.Cấu trúc dữ liệu cho giải thuật Banker :Gọi m là số loại tài nguyên đang xét trong giải thuật Banker.Gọi n là số tiến trình đang xét trong giải thuật Banker.

Mảng Available có m phần tử : Từng phần tử Available[j] chứa một con số tương ứng với số thể hiện của loại tài nguyên j đó.
Mảng Max[i,j] = k : Tiến trình Pi yêu cầu tối đa k thực thể của loại tài nguyên Rj.
Allocation[i,j] = k : Pi đã được cấp phát k thực thể của Rj.
Need[i,j] = k : Pi cần thêm k thực thể của Rj.
Need[i,j] = Max[i,j] – Allocation[i,j].

Các bước thực hiện giải thuật :(Lưu ý : Ký hiệu Y <= X ó Y[i] <= X[i], ví dụ (0,3,2,1) <= (1,7,3,2) ).

(Các bạn xem thêm trong slide để hiểu cách trình bày tay, hoặc tham khảo bài ôn tập cuối kỳ part 3 đã được ghi kèm link bên dưới).Câu 8 : Trình bày giải thuật yêu cầu tài nguyên ?Request(i) là một vector request của process P(i).Request(i)[j] = k ó P(i) cần k thực thể (instance) của tài nguyên Rj.1. Nếu Request(i) <= Need(i) thì đến bước 2. Nếu không, báo lỗi vì tiến trình đã vượt yêu cầu tối đa.2. Nếu Request(i) <= Available thì qua bước 3. Nếu không, P(i) phải chờ vì tài nguyên không còn đủ để cấp phát.3. Giả định cấp phát tài nguyên đáp ứng yêu cầu của P(i) bằng cách cập nhật trạng thái hệ thống như sau :

Available = Available – Request(i).
Allocation(i) = Allocation(i) + Request(i).
Need(i) = Need(i) – Request(i).

Áp dụng giải thuật Banker lên hệ thống mới.

Nếu hệ thống giả định trên an toàn thì tiến hành cấp phát thực.
Nếu trạng thái là không an toàn thì Pi phải đợi và phục hồi trạng thái :
- Available = Available + Request(i).
- Allocation(i) = Allocation(i) – Request(i).
- Need(i) = Need(i) + Request(i).

Ví dụ yêu cầu được chấp nhận và cấp phát thực tế :

Ví dụ yêu cầu không được chấp nhận và không được cấp phát :

Câu 9 : Nêu các bước giải thuật phát hiện deadlock ?Giải thuật phát hiện deadlock có nhiều nét tương đồng với giải thuật Banker. Tuy nhiên, giải thuật Banker dùng để xác định trạng thái an toàn của hệ thống, từ đó tránh deadlock (deadlock avoidance). Còn giải thuật phát hiện deadlock, như tên gọi của nó, dùng để phát hiện deadlock, sau đó hệ thống sẽ giải quyết deadlock.Một hệ thống ở trạng thái không an toàn không nhất thiết là deadlock, các bạn có thể xem phạm vi deadlock/an toàn/không an toàn trong hình sau :

Giải thuật phát hiện deadlock :Đầu tiên ta có các cấu trúc dữ liệu sau :

Available : Một vector có độ dài m chỉ số lượng resources của từng loại.
Allocation : Một ma trận n x m xác định số resources từng loại đang được cấp cho từng process (có tổng cộng n process).
Request : Một ma trận n x m xác định số lượng resources mà từng process yêu cầu thêm ở từng loại resources.

Bước 1 : Gọi Work và Finish là hai vector có kích thước lần lượt là m và n. Khởi tạo :Work = Available.

Với mọi i = 1,2,…,n, nếu Allocation(i) khác 0 thì Finish[i] = false (tức là còn đang giữ resource thì chưa hoàn thành), ngược lại không giữ resource thì Finish[i] = true.

Bước 2 : Tìm i thoả mãn :

Finish[i] = false.
Request(i) <= Work.

Nếu không tồn tại i như vậy, đến bước 4.Bước 3 : Work = Work + Allocation.Finish[i] = true.Quay lại bước 2.Bước 4 : nếu Finish[i] = false, với một số i = 1,2,…,n bất kỳ (tức là khi đến bước 4 vẫn có tiến trình nào đó chưa hoàn thành), thì hệ thống đang ở trạng thái deadlock. Hơn thế nữa, Finish[i] = false thì process P(i) đang bị deadlocked.Thuật toán trên cần m x n^2 phép tính để xác định xem hệ thống có đang bị deadlock hay không.Câu 10 : Khi deadlock xảy ra, hệ điều hành làm gì để phục hồi ?Khi giải thuật phát hiện deadlock xác định rằng deadlock đang tồn tại trong hệ thống, có nhiều phương pháp có thể giải quyết deadlock. Một trong những cách là cho hệ thống tự khôi phục từ deadlock. Có 2 cách để thoát khỏi deadlock :

Huỷ bỏ một trong các process đang tham gia vào deadlock để phá Circular Wait.
Trưng dụng (Preempt) một vài tài nguyên đang bị nắm giữ bởi process này cho process kia dùng trước.

Câu 11 : Dựa trên yếu tố nào để chấm dứt quá trình bị deadlock ?Rất nhiều các tác nhân khác nhau có thể kể đến, điển hình như :

Độ ưu tiên của tiến trình.
Thời gian đã thực thi của tiến trình và thời gian còn lại.
Loại tài nguyên mà tiến trình đã sử dụng.
Tài nguyên mà tiến trình cần thêm để hoàn tất công việc.
Số lượng tiến trình cần được chấm dứt.
Tiến trình là Interactive hay Batch (xem lại định nghĩa ở các chương trước).

Câu 12 : Việc chấm dứt tiến trình khi xảy ra deadlock như thế nào ?Để loại bỏ deadlock bằng cách huỷ bỏ process đang chạy, chúng ta sử dụng một trong các cách sau :

Huỷ bỏ tất cả các process đang tham gia vào deadlock (Deadlocked Process) : Phương thức này rõ ràng sẽ đưa hệ thống ra khỏi deadlock. Nhưng chi phí thực hiện phương pháp này khá cao. Các process đang bị deadlock có thể đang thực hiện công việc giữa chừng, và việc huỷ tất cả sẽ khiến chúng ta phải thực hiện lại những công việc trên từ đầu.
Huỷ bỏ từng process một cho đến khi hệ thống thoát deadlock : Phương pháp này sẽ có một overhead không nhỏ, vì sau mỗi lần huỷ một process, chúng ta sẽ phải chạy lại thuật toán để xác định xem hệ thống còn deadlock không.

Thực hiện theo cách 1 : Việc huỷ bỏ một process không phải chuyện đơn giản. Nếu một process đang làm dở một công việc nào đó, chẳng hạn, upload file đi. Nếu huỷ process thì file chắc chắn sẽ bị lỗi. Tương tự đối với các công việc khác.Thực hiện theo cách 2 : Chúng ta cần xác định xem process nào bị deadlocked nên được terminated. Ta cần chọn process sao cho mức hao phí (minimum cost) là nhỏ nhất. Thường thì hệ thống sẽ dựa vào các yếu tố ở câu trên để chấm dứt một process.Sau khi đã chấm dứt tiến trình, ta sẽ lấy lại tài nguyên từ tiến trình đó, cấp phát cho tiến trình khác cho đến khi không còn deadlock nữa.Ta cũng cần quan tâm đến Starvation, tức là, không có tiến trình sẽ luôn luôn bị lấy lại tài nguyên mỗi khi deadlock xảy ra.Chương 7.Câu 1 : Thế nào là phân mảnh ngoại ? Phân mảnh nội ? Cho ví dụ.Phân mảnh ngoại tồn tại khi tổng lượng bộ nhớ còn trống đủ để phục vụ một yêu cầu mới từ process, tuy nhiên do các phần trống đó không liên tục nhau mà nằm ở nhiều vị trí cách xa nhau, vì vậy có bộ nhớ trống mà không thể cấp phát được.

Phân mảnh ngoại xảy ra do việc nạp và rút các process trong bộ nhớ. Như hình trên các bạn thấy, những ô xám từng là nơi những process nhỏ được nạp vào hệ thống trước đó. Những process nhỏ đó đã hoàn thành và rút ra khỏi hệ thống, để lại phần trống của bộ nhớ rời rạc như trên. Bây giờ, process 7 muốn vào nhưng không được, do không có vị trí nào đủ bộ nhớ để cung cấp cho nó.Phương pháp giải quyết vấn đề phân mảnh ngoại là compaction (gom cụm). Compaction tức là việc gom các process đang trong bộ nhớ lại thành 1 cục bự, có thể nằm ở đầu hoặc nằm ở cuối bộ nhớ. Một phương án giải quyết khác đó chính là sử dụng phân đoạn (segmentation) và phân trang (paging) để tận dụng tối đa các phần trống trong bộ nhớ, thậm chí cả những vùng không liên tục (non-contiguous).Bộ nhớ cũng có thể bị phân mảnh nội. Phân mảnh nội là hiện tượng khi một process chiếm dung lượng bộ nhớ nhỏ hơn dung lượng mà nó được cấp phát (tức là phần bộ nhớ không được sử dụng nằm bên trong phân vùng đang được cấp phát cho process).

VD : Như hình trên, process đầu tiên được cấp 100KB bộ nhớ nhưng chỉ dùng 80KB, để lại 20KB thừa. Process thứ 2 được cấp 100KB bộ nhớ nhưng chỉ dùng 90KB, để lại 10KB thừa. Phần thừa đó chính là phần phân mảnh nội.Hiện tượng phân mảnh nội thường xảy ra khi bộ nhớ thực được chia thành các khối kích thước cố định (fixed-size block) và các process khi yêu cầu bộ nhớ, sẽ được cấp phát từng khối trong bộ nhớ. Cơ chế phân trang (paging) là một ví dụ điển hình gây ra phân mảnh nội.Hướng giải quyết có thể có là chia bộ nhớ ra thành các phần có kích thích tuỳ chỉnh và sử dụng chiến lược Best-Fit để phân bộ nhớ cho process. Hay nói cách khác, chúng ta sẽ tìm cách làm sao để cung cấp chỉ vừa đủ dùng bộ nhớ cho process.Câu 2 : Fixed Partitioning là gì ? Các chiến lược placement ?Khi khởi động hệ thống, bộ nhớ chính được chia thành nhiều phần rời nhau gọi là các partition có kích thước bằng nhau hoặc khác nhau. Từng phần sẽ được cung cấp cho một và chỉ một process. Đó là Fixed-Partition.

Process nào vừa với kích thước partition thì có thể được nạp vào partition đó (vừa tức là có kích thước nhỏ hơn hoặc bằng kích thước partition).Nếu chương trình có kích thước lớn hơn partition thì phải dùng cơ chế overlay.Fixed-Partitioning không hiệu quả do bị phân mảnh nội : Một chương trình dù lớn hay nhỏ đều được cấp phát trọn một partition.Các chiến lược Placement (đưa process vào bộ nhớ) :Partition có kích thước bằng nhau.

Nếu còn partition trống => Process mới sẽ được nạp vào partition đó.
Nếu không còn partition trống, nhưng trong đó có process đang bị blocked => Swap process đó ra bộ nhớ phụ, nhường chỗ cho process mới.

Nếu các partition không bằng nhau :Giải pháp 1 :

Gán mỗi process vào partition nhỏ nhất phù hợp với nó.
Có hàng đợi cho mỗi partition.
Giảm thiểu phân mảnh nội.
Vấn đề ở đây là : Sẽ có một số hàng đợi trống không (vì không có process với kích thước tương ứng), trong khi đó lại có partition với hàng đợi dày đặc.

Giải pháp 2 :

Dùng chung 1 hàng đợi cho tất cả các partition.
Khi cần nạp một process vào bộ nhớ chính => Chọn partition nhỏ nhất còn trống.

Câu 3 : Dynamic Partitioning là gì ? Các chiến lược placement ?Dynamic Partitioning sẽ chia bộ nhớ thành nhiều phần như Fixed-Partition, tuy nhiên số lượng partition không cố định và partition có thể có kích thước khác nhau.Mỗi process được cấp phát chính xác dung lượng bộ nhớ cần thiết.Dynamic Partitioning không gây ra hiện tượng phân mảnh nội, nhưng lại gây ra hiện tượng phân mảnh ngoại.Chiến lược placement :

Mục tiêu : Giảm chi phí compaction. (chi phí vận chuyển các partition).
Các chiến lượng placement :
- Best-Fit : Chọn khối nhớ trống nhỏ nhất đủ cho process.
- First-Fit : Chọn khối nhớ trống phù hợp đầu tiên kể từ đầu bộ nhớ.
- Next-Fit : Chọn khối nhớ trống phù hợp đầu tiên kể từ vị trí cấp phát cuối cùng (nếu chưa có khối nhớ nào được cấp phát thì khối nhớ đầu tiên của bộ nhớ sẽ được chọn).
- Worst-Fit : Chọn khối nhớ trống lớn nhất.

Câu 4 : Bộ nhớ luận lý là gì ? Bảng phân trang dùng để làm gì ?Bộ nhớ logic là một bản dịch (translation) cho bộ nhớ vật lý. Ở đó, các địa chỉ ảo sẽ được chuyển sang địa chỉ thật và được truy cập như bình thường.Bảng phân trang chứa base address (địa chỉ gốc) của từng trang trong bộ nhớ vật lý. Base address sẽ được kết hợp với page offset (độ dời) để định nghĩa địa chỉ vật lý trong phần cứng.

Câu 5 : Bảng trang được lưu trữ ở đâu ? Các thanh ghi cần sử dụng trong cơ chế phân trang ?Bảng trang thường được lưu trữ trong bộ nhớ chính.Các thanh ghi cần sử dụng :Thanh ghi page-table base (PTBR) trỏ đến bảng phân trang.

Thanh ghi page-table length (PTLR) biểu thị kích thước của bảng phân trang (có thể được dùng trong cơ chế bảo vệ bộ nhớ).
Ngoài ra còn có thanh ghi translation look-aside buffers (TLBs) dùng để truy cập nhanh.

Câu 6 : TLB là gì ? Dùng để làm gì ?TLB (viết tắt của từ Translation Look-aside Buffer) là một bộ phận cache phần cứng có tốc độ truy xuất và tìm kiếm cao. Cấu tạo : TLB là một bảng khá nhỏ, gồm 2 cột : Một cột page number (số trang của bộ nhớ luận lý), một cột frame number. Số mục của TLB nằm trong khoảng từ 32 đến 1024 mục.

Công dụng :TLB được dùng để tìm kiếm nhanh frame number và từ đó cho ra địa chỉ thực (physical address) từ địa chỉ luận lý.Câu 7 : Thế nào là phân trang đa cấp ? Cho ví dụ ?Đầu tiên ta hãy tìm hiểu : Tại sao chúng ta lại cần đến phân trang đa cấp ?Vấn đề của page table : Nếu bộ nhớ ảo rất lớn (được biểu diễn bằng con số 32bit hoặc 64bit), khi đó table của chúng ta sẽ phình to ra đến một kích thước không thể kiểm soát.Vì vậy, chúng ta cần đưa page-table vào bộ nhớ chính và sử dụng 1 thứ gọi là multilevel tables.Địa chỉ ảo sẽ có 2 phần : Một phần là số trang cấp 1 (P1) và một phần là số trang cấp 2 (P2). Có thể có nhiều cấp hơn, tuỳ cách bạn cài đặt.Ví dụ phân trang 2 cấp :

P1 sẽ chỉ đến outer-page table. P2 sẽ chỉ đến page of page table.Câu 8 : Tại sao phải phân đoạn ? Các đoạn được phân chia do cái gì ?

Phân đoạn (Segmentation) nhằm các mục đích sau :

Chia cắt một process lớn với nhiều dữ liệu ra thành nhiều phần.
Giải quyết vấn đề phân mảnh nội.

Thông thường, một chương trình khi được biên dịch, trình biên dịch sẽ tự động xây dựng các segments.Trình loader sẽ gán mỗi segment một số định danh riêng.Câu 9 : Các thanh ghi được sử dụng trong phân đoạn ?Các thanh ghi được sử dụng trong phân đoạn :

Segment-Table base register (STBR) : Trỏ đến vị trí bảng phân đoạn trong bộ nhớ.
Segment-Table length register (STLR) : Số lượng segment của chương trình.

=> Một chỉ số segment s là hợp lệ nếu s < STLR.Câu 10 : Chuyển đổi địa chỉ là gì ? Chuyển đổi địa chỉ có 2 dạng : Chuyển đổi địa chỉ trong paging và chuyển đổi địa chỉ trong segment.Chuyển đổi địa chỉ trong paging :

Chuyển đổi địa chi trong segment :

Câu 11 : Khi nào địa chỉ lệnh và dữ liệu được chuyển thành địa chỉ thật ?Địa chỉ lệnh và dữ liệu được chuyển đổi thành địa chỉ thực có thể xảy ra tại ba thời điểm khác nhau :

Compile time : Nếu biết trước địa chỉ bộ nhớ của chương trình thì có thể kết gắn địa chỉ tuyệt đối lúc biên dịch.
- Ví dụ : Chương trình .COM của Microsoft.
- Khuyết điểm : Phải biên dịch lại nếu thay đổi địa chỉ nạp chương trình.
Load time : Vào thời điểm loading, loader phải chuyển đổi địa chỉ khả tái định vị thành địa chỉ thực dựa trên một địa chỉ nền.
- Địa chỉ thực được tính toán vào thời điểm nạp chương trình -> Phải tiến hành reload nếu địa chỉ nền thay đổi.
Execution time : Khi trong quá trình thực thi, process có thể được di chuyển từ segment này sang segment khác trong bộ nhớ thì quá trình chuyển đổi địa chỉ được trì hoãn đến thời điểm thực thi.

Câu 12 : Thế nào là dynamic linking ? Nêu ưu điểm.Dynamic linking là quá trình link đến một module ngoài (external module) được thực hiện sau khi đã tạo xong load module.Ví dụ trong Windows, module ngoài là các file .DLL. Trong UNIX, module ngoài là các file .so (shared library).Load module chứa các stub tham chiếu (refer) đến routine của external module. Lúc thực thi, khi stub được thực thi lần đầu (do process gọi routine lần đầu), stub nạp routine vào bộ nhớ, tự thay thế bằng địa chỉ của routine và routine được thực thi.Các lần gọi routine sau sẽ xảy ra bình thường.Ưu điểm :

Dùng các phiên bản khác nhau của external module mà không cần biên dịch lại.
Chia sẻ mã : Một external module chỉ cần nạp vào bộ nhớ một lần và có thể dùng chung giữa các process.

Câu 13 : Thế nào là dynamic loading ?Dynamic Loading : Chỉ khi nào cần được gọi đến thì một thủ tục mới được nạp vào bộ nhớ chính => Tăng độ hiệu dụng của bộ nhớ bởi vì các thủ tục không được gọi đến sẽ không chiếm chỗ trong bộ nhớ.Rất hiệu quả trong TH tồn tại khối lượng lớn mã chương trình tần suất sử dụng thấp, không được sử dụng thường xuyên.Câu 14 : Nêu cơ chế overlay ? Swapping ?Cơ chế phủ lắp (overlay) : Tại mỗi thời điểm, chỉ giữ lại trong bộ nhớ những lệnh hoặc dữ liệu cần thiết, giải phóng các lệnh/dữ liệu chưa hoặc không dùng đến.Cơ chế này rất hữu dụng khi kích thước của một process lớn hơn không gian bộ nhớ cấp cho process đó.Cơ chế này được điều khiển bởi người sử dụng, không cần sự hỗ trợ của HĐH.

Swapping : Một process có thể tạm thời bị swap ra khỏi bộ nhớ chính và lưu trên một hệ thống lưu trữ phụ. Sau đó, process có thể được nạp lại vào bộ nhớ để tiếp tục quá trình thực thi.

RR (Round Robin) : Swap in-out theo quantum time.
Roll out, roll in : Process có độ ưu tiên thấp sẽ bị swap out, nhường chỗ cho process có độ ưu tiên cao.

Câu 15 : Nêu các mô hình quản lý bộ nhớ ?Mô hình đơn giản (không có bộ nhớ ảo) :

Phân chia cố định (fixed partitioning).
Phân chia động (dynamic partitioning).
Phân trang đơn giản (simple paging).
Phân đoạn đơn giản (simple segmentation).

Chương 8.Câu 1 : Tại sao cần phải có bộ nhớ ảo ?Hiện nay, như các bạn biết thì các chương trình ngày một phình to ra về kích thước. Vì vậy, việc load toàn bộ chương trình vào bộ nhớ chính để thực thi gần như là chuyện … bất khả thi.Bộ nhớ ảo là một kỹ thuật cho phép chạy một process, mà process đó không cần thiết phải nằm hoàn toàn trong bộ nhớ. Với bộ nhớ ảo, chúng ta sẽ có thể làm được những điều sau :

Thực thi một chương trình có kích thước lớn hơn nhiều so với bộ nhớ chính.
Lượng process trong bộ nhớ cũng nhiều hơn.
Trừu tượng hoá bộ nhớ chính thành một mảng array lớn. Người dùng chỉ thấy được bộ nhớ thông qua bộ nhớ luận lý (logical memory). Từ đó giúp người lập trình viên đỡ cơ cực hơn.
Bộ nhớ ảo cũng giúp cho các tiến trình chia sẻ dữ liệu với nhau dễ dàng, ngoài ra còn hỗ trợ trong việc cài đặt shared memory (bộ nhớ dùng chung).

Ví dụ thực tế : Phân vùng swap trong Linux, file pagefile.sys trong Windows.Câu 2 : Có bao nhiêu kỹ thuật cài đặt bộ nhớ ảo ? Mô tả sơ lược các kỹ thuật đó ?Có hai kỹ thuật :

Phân trang theo yêu cầu (Demand Paging) : Các trang dữ liệu sẽ không được sao chép vào bộ nhớ chính cho đến khi nó được cần tới.
Phân đoạn theo yêu cầu (Segmentation Paging) : Các segment của chương trình sẽ không được chép vào bộ nhớ chính cho đến khi nó được cần tới.
Phần cứng memory management phải hỗ trợ paging, segmentation.
OS phải quản lý swap giữa bộ nhớ chính và bộ nhớ thứ cấp.

Câu 3 : Các bước thực hiện kỹ thuật phân trang theo yêu cầu ?

Phân trang theo yêu cầu :
- Các trang của quá trình chỉ được nạp vào bộ nhớ chính khi được yêu cầu.
- Khi có một tham chiếu đến một trang mà không có trong bộ nhớ chính (valid bit) thì phần cứng sẽ gây ra một ngắt (gọi là pagefault – các bạn hay gặp từ này khi làm bài tập về các giải thuật phân trang), kích khởi pagefault service routine (PFSR) của hệ điều hành.
- PFSR :
  - Chuyển process về trạng thái blocked.
  - Phát ra một yêu cầu đọc đĩa để nạp trang được tham chiếu vào một frame trống, trong khi đợi I/O, một process khác được cấp CPU để thực thi.
  - Sau khi I/O hoàn tất, đĩa gây ra một ngắt đến hệ điều hành, PFSR cập nhập page-table và chuyển process về trạng thái ready.

Bước 2 của PFSR : Giả sử phải thay trang vì không tìm được frame trống, PFSR được bổ sung như sau :

Xác định vị trí trên đĩa của trang đang cần.
Tìm một frame trống.
- Nếu có frame trống thì dùng thôi chờ gì nữa.
- Nếu không có frame trống thì dùng một giải thuật thay trang để chọn một trang hi sinh (victim page).
- Ghi victim page lên đĩa, cập nhật page table và frame table tương ứng.
Đọc trang đang cần vào frame trống (đã có được từ bước 2), cập nhật page table và frame table tương ứng.

Vậy phải xác định victim page như thế nào ? Đó chính là câu hỏi đã dẫn đến sự ra đời của các giải thuật thay trang như FIFO, LRU, OPT,…Câu 4 : Mô tả các giải thuật thay thế trang FIFO, OPT, LRU ?FIFO : First-In-First-Out.Như tên gọi của nó, trang nhớ nào được vào trước sẽ được “ưu tiên” swap ra ngoài khi có page-fault.Ví dụ về FIFO :

OPT : Optimal Page-Replacement Algorithm.Trang nhớ nào được tham chiếu trễ nhất trong tương lai sẽ được swap ra ngoài.Ví dụ :

LRU : Least Recently Used Page-Replacement Algorithm.Mỗi trang được ghi nhận thời điểm được tham chiếu => Trang LRU là trang nhớ có thời điểm tham chiếu nhỏ nhất (OS tốn chi phí tìm kiếm trang LRU này mỗi khi có pagefault).Do vậy, LRU cần sự hỗ trợ của phần cứng cho việc tìm kiếm.(LRU giống OPT, nhưng tìm về quá khứ thay vì tương lai. Tức là, trang nhớ nào được tham chiếu ở thời điểm cách xa thời điểm hiện tại nhất sẽ được chọn để thay thế).Ví dụ :

Đây là phần 2, phần lý thuyết tiếp theo của phần 1 trước đó.Các bạn có thể xem phần 1 - Lý thuyết tại : http://bit.ly/2KsBhE4Các bạn có thể xem phần 3 - Bài tập tại : http://bit.ly/2XT9nEt

Tiếng Việt
English (UK)
中文(台灣)
한국어
日本語
Français (France)
ภาษาไทย
Español
Português (Brasil)
Deutsch
Italiano

Đăng ký
Đăng nhập
Messenger
Facebook Lite
Video
Địa điểm
Trò chơi
Marketplace
Meta Pay
Cửa hàng trên Meta
Meta Quest
Ray-Ban Meta
Meta AI
Instagram
Threads
Chiến dịch gây quỹ
Dịch vụ
Trung tâm thông tin bỏ phiếu
Chính sách quyền riêng tư
Trung tâm quyền riêng tư
Nhóm
Giới thiệu
Tạo quảng cáo
Tạo Trang
Nhà phát triển
Tuyển dụng
Cookie
Lựa chọn quảng cáo
Điều khoản
Trợ giúp
Tải thông tin liên hệ lên & đối tượng không phải người dùng
Cài đặt
Nhật ký hoạt động

Từ khóa » Hệ Thống Rơi Vào Trạng Thái Deadlock Khi

HĐH - Ôn Tập Cuối Kỳ - Part 2 (Lý Thuyết) | Facebook

Deadlock – Wikipedia Tiếng Việt

Hệ điều Hành: Deadlock - .vn

Bai 5 Trac Nghiem Deadlock - PDFCOFFEE.COM

Deadlock Trong Hệ điều Hành? Kiến Thức Cơ Bản - W3seo

Bài Giảng Hệ điều Hành Chương 6 Deadlock (khóa Chết) - Tài Liệu Text

Chương 7 Tắt Nghẽn - Tài Liệu Text - 123doc

Vấn đề Deadlock Trong Hệ Thống - Tài Liệu, Ebook

Deadlock Là Gì? Cách Phát Hiện Và Phương Pháp Xử Lý Tốt Nhất

[PDF] Hệ điều Hành,trần Thị Như Nguyệt,dhcntt

Nguyên Lý Hệ điều Hành - Bế Tắc (Deadlock)

Trắc Nghiệm Hệ Điều Hành - Bài 29

HĐH - Ôn Tập Cuối Kỳ - Part 1 (Lý Thuyết) | Facebook

Chương 6 - Deadlock - Nguyên Lý Hệ điều Hành

Nguyên Lí Hệ điều Hành -Chương 6 ( J White ) Quiz - Quizizz

Liên Hệ