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

FacebookTham gia hoặc đăng nhập Facebook   Email hoặc điện thoạiMật khẩuQuê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 1 (Lý thuyết)Lưu Biêu Nghị·Thứ Ba, 4 tháng 6, 2019·Nhóm công khai#HĐH #StudyWithMeChào các bạn !Ở bài viết này, mình sẽ cùng nhau ôn tập lại một vài nội dung phục vụ cho việc ôn tập cuối kỳ nhé.Ôn tập chương 5.Câu 1 : Khi nào thì xảy ra tranh chấp race condition ?Race condition là tình trạng nhiều process truy xuất và thao tác đồng thời lên dữ liệu chia sẻ. Kết quả cuối cùng của việc truy xuất đồng thời này phụ thuộc thứ tự thực thi của các lệnh thao tác dữ liệu.Ví dụ điển hình về bounded buffer :

Code C++ demo Critical Section.

Cho rằng biến counter là biến được chia sẻ giữa Producer và Consumer (tức là, biến counter có thể được đọc và được ghi bởi cả Producer và Consumer). Và Producer và Consumer chạy đồng thời cùng lúc với nhau (Concurrent).Vậy việc gì sẽ xảy ra ?Thực ra, mã giả trên mà bạn thấy sẽ được biên dịch lại thành hợp ngữ. Và dù chỉ 1 dòng lệnh counter++ (hoặc counter--), thực tế mã hợp ngữ được biên dịch ra bao gồm 3 mã như sau :

Hợp ngữ của việc tăng và giảm biến counter.

Như các bạn thấy, để tăng (hoặc giảm) biến counter cần đến những 3 lệnh. Việc đa chương của máy tính chẳng qua chỉ là thực hiện 1 tác vụ tại một thời điểm nhất định, nhưng việc chuyển qua lại tác vụ rất nhanh giữa chúng đã tạo ra một cảm giác cho người sử dụng là máy tính của chúng ta đang thực hiện nhiều công việc cùng 1 lúc.Khi máy tính thực hiện một tác vụ, nó đang thực hiện các lệnh hợp ngữ trên. Và Scheduler có thể cắt (interrupt) một tác vụ bất kỳ ngay sau khi thực hiện xong dòng lệnh của hợp ngữ (VD sau khi thực hiện xong dòng 2, Scheduler ngắt không cho thực hiện tiếp lệnh 3 và chuyển qua process khác, sau đó mới quay lại thực hiện lệnh 3).Vậy giả sử như ta có các thời điểm với các lệnh như sau (biến counter đang có giá trị là 5) : T0: producer thực hiện dòng 1 : register1 = counter {register1 = 5}T1: producer thực hiện dòng 2 : register1 = register1 + 1 {register1 = 6} (ngắt)T2: consumer thực hiện dòng 1 : register2 = counter {register2 = 5} (Oh-No).T3: consumer thực hiện dòng 2 : register2 = register2 − 1 {register2 = 4} (ngắt)T4: producer thực hiện dòng 3 : counter = register1 {counter = 6} (ngắt)T5: consumer thực hiện dòng 3 : counter = register2 {counter = 4} (Oh-No).Kết quả trả ra không đúng như ta mong muốn. Producer chạy 1 lần (counter++), Consumer chạy 1 lần (counter--) thì lẽ ra kết quả của chúng ta phải là counter=5. Thế mà kết quả cuối cùng của chúng ta đã trở thành 4 (kết quả không chính xác). Ngược lại, nếu chúng ta đổi chỗ T4 và T5 với nhau, chúng ta sẽ được counter = 6 (?!).Vậy dữ liệu của chúng ta không được nhất quán.Để dữ liệu chia sẻ được nhất quán, cần bảo đảm sao cho tại mỗi thời điểm chỉ có một process được thao tác lên dữ liệu chia sẻ. Do đó, cần có cơ chế đồng bộ hoạt động của các process này.Câu 2 : Vấn đề Critical Section là gì ?Đầu tiên, chúng ta hãy xét một hệ thống có n tiến trình (tạm đặt tên của n tiến trình này là {P0, P1, ..., Pn−1}). Từng tiến trình đều có một đoạn mã, gọi là critical section (CS), tên tiếng Việt là vùng tranh chấp. Trong CS, các đoạn mã thao tác lên dữ liệu chia sẻ giữa các tiến trình.Một đặc tính quan trọng mà chúng ta cần quan tâm, đó chính là khi process P0 đang chạy đoạn mã bên trong CS thì không một process nào khác được chạy đoạn mã bên trong CS (để đảm bảo cho dữ liệu được nhất quán). Hay nói cách khác là 1 CS trong một thời điểm nhất định, chỉ có 1 process được phép chạy.Và vấn đề vùng tranh chấp (Critical Section Problem) là vấn đề về việc tìm một cách thiết kế một giao thức (một cách thức) nào đó để các process có thể phối hợp với nhau hoàn thành nhiệm vụ của nó.Câu 3 : Yêu cầu của lời giải cho vấn đề vùng tranh chấp (CS Problem) ?Một lời giải cho vấn đề vùng tranh chấp (CS Problem) phải đảm bảo được 3 tính chất sau :

• Loại trừ tương hỗ (Mutual Exclusion) : Khi một process P đang thực thi trong vùng tranh chấp (CS) của nó thì không có process Q nào khác đang thực thi trong CS của Q.
• Phát triển (Progress) : Một tiến trình tạm dừng bên ngoài CS không được ngăn cản các tiến trình khác vào CS.
• Chờ đợi giới hạn (Bounded Waiting) : Mỗi process chỉ phải chờ để được vào CS trong một khoảng thời gian có hạn (finite wait time). Không được xảy ra tình trạng đói tài nguyên (starvation).

Câu 4 : Có mấy loại giải pháp cho vấn đề vùng tranh chấp ? Kể tên.Có 2 nhóm giải pháp chính :Nhóm giải pháp Busy Waiting :

• Tính chất :
  • Tiếp tục tiêu thụ CPU trong khi chờ đợi vào miền găng (thông qua việc kiểm tra điều kiện vào CS liên tục).
  • Không đòi hỏi sự trợ giúp của hệ điều hành.
• Cơ chế chung :

Cơ chế chung của nhóm giải pháp Busy Waiting.

• Bao gồm một vài loại :
  • Sử dụng các biến cờ hiệu.
  • Sử dụng việc kiểm tra luân phiên.
  • Giải pháp của Peterson.
  • Cấm ngắt (giải pháp phần cứng – hardware).
  • Chỉ thị TSL (giải pháp phần cứng – hardware).

Nhóm giải pháp Sleep & Wakeup.

• Tính chất :
  • Từ bỏ CPU khi chưa được vào CS.
  • Cần sự hỗ trợ từ hệ điều hành (để đánh thức process và đưa process vào trạng thái blocked).
• Cơ chế chung :

Cơ chế chung của nhóm giải pháp Sleep & Wakeup.

• Bao gồm một vài loại :
  • Semaphore.
  • Monitor.
  • Message.

Câu 5 : Semaphore là gì ? Nêu cách hoạt động của semaphore và ứng dụng vào một bài toán đồng bộ ?Semaphore là một công cụ đồng bộ cung cấp bởi OS mà không đòi hỏi Busy Waiting.Semaphore là một số nguyên. Có cấu trúc như sau :

Cấu trúc của Semaphore.

Giả sử ta đang có một Semaphore S. Có 3 thao tác có thể thực thi trên S :

• Khởi tạo semaphore. Giá trị khởi tạo ban đầu của Semaphore chính là số lượng process được thực hiện CS trong cùng 1 thời điểm.
• Wait(S) hay còn gọi là P(S) : Giảm giá trị semaphore đi một đơn vị (S = S – 1). Nếu giá trị S âm, process thực hiện lệnh wait() này sẽ bị blocked cho đến khi được đánh thức.

Nội dung hàm wait(S).

• Signal(S) hay còn gọi là V(S) : Tăng giá trị semaphore (S = S + 1). Kế đó nếu giá trị S <= 0 (S<=0 tức là vẫn còn process đang bị blocked), lấy một process Q nào đó đang bị blocked rồi gọi wakeup(Q) để đánh thức process Q đó.

Nội dung hàm signal(S).

Tóm lại :

• P(S) hay wait(S) sử dụng để giành tài nguyên và giảm biến đếm S = S – 1.
• V(S) hay signal(S) sẽ giải phóng tài nguyên và tăng biến đếm S = S + 1.
• Nếu P được thực hiện trên biến đếm <= 0, tiến trình phải đợi V hay chờ đợi sự giải phóng tài nguyên.

Ví dụ : Xét 2 tiến trình xử lý đoạn chương trình sau :

Tiến trình P1 và tiến trình P2.

Ta cần đồng bộ hoá hoạt động của 2 tiến trình sao cho cả A1 và B1 sao cho cả A1 và B1 đều hoàn tất trước khi A2 và B2 bắt đầu.Để đồng bộ hoạt động theo yêu cầu, ta phải định nghĩa P1 và P2 như sau :

Định nghĩa lại tiến trình P1 và P2.

Giải thích cơ chế hoạt động :Có 2TH có thể xảy ra :

• P1 chạy trước.
• P2 chạy trước.

Xét trường hợp P1 chạy trước.Ở đây, ta hình dung signal chính là “chìa khoá” để mở khoá cho cánh cổng. Và wait chính là “cổng” chặn lại không cho process được thực thi tiếp.

• Ở P1, ta thấy signal được đặt sau A1, đồng nghĩa với việc sau khi thực hiện A1 xong, P1 sẽ “mở cổng” chặn của P2 và cho phép P2 thực hiện B2. Sau khi thực hiện signal, P1 tiếp tục bị chặn lại bởi hàm wait.
• Ở đây, ta thấy ở P2 cũng có signal nằm đằng sau B1. Vậy chỉ sau khi thực hiện B1, P1 mới được cho phép thực hiện tiếp A2.

Với 2 phân tích như trên, ta thấy thoả mãn việc đồng bộ hoạt động theo yêu cầu.Xét tương tự với trường hợp P2 chạy trước.Ôn tập chương 6.Câu 1 : Deadlock là gì ? Cho ví dụ thực tế ?Trong một môi trường có nhiều process chạy đồng thời, các process có thể tranh giành nhau một số lượng hữu hạn các tài nguyên (resources). Một process P1 yêu cầu một tài nguyên A, nếu tài nguyên A lúc đó chưa sẵn sàng (available) thì process P1 sẽ vào trạng thái waiting. Đôi khi, process P1 đã vào trạng thái waiting không bao giờ có thể chuyển trạng thái sang Ready nữa, do tài nguyên A đang bị một process P2 nắm giữ, vì P2 cũng đang ở trạng thái waiting đang chờ một tài nguyên B nào đó đang bị nắm giữ cũng bởi >=1 process nào đó (có thể là P1) đang ở trạng thái waiting.Một trường hợp chờ đợi vòng như vậy, và khi đó hệ thống không thể tiến triển được, người ta gọi là trạng thái Deadlock.Ví dụ :

• Hệ thống có 2 file trên đĩa (A và B).
• P1 đang mở (đang khoá) file A và yêu cầu file B.
• P2 đang mở (đang khoá) file B và yêu cầu file A.

=> Deadlock.Câu 2 : Một tiến trình khi nào gọi là bị deadlock ? Trì hoãn vô hạn định ?Một tiến trình gọi là deadlock nếu nó đang đợi một sự kiện sẽ không bao giờ xảy ra. Thông thường, có >=1 process liên quan đến việc gây ra deadlock.VD : Process A yêu cầu một tài nguyên đang bị nắm giữ bởi một process B, mà B lại đang yêu cầu một tài nguyên đang bị nắm giữ bởi process A.Một tiến trình gọi là trì hoãn vô hạn định (Indefinite postponement hay Starvation) nếu nó bị trì hoãn một khoảng thời gian dài lặp đi lặp lại trong khi hệ thống đáp ứng cho những tiến trình khác. Nguyên nhân có thể do Scheduling tệ, khiến cho process có độ ưu tiên thấp không bao giờ được xử lý.Thông thường trì hoãn vô hạn định nếu có xảy ra chỉ liên quan đến một (hoặc một số ít) process.VD : Một process đang ở trạng thái Ready. Chuẩn bị chuyển trạng thái vào Running nhưng lại không bao giờ nhận được CPU.Câu 3 : Khi nào sẽ xảy ra deadlock ?Một tình huống deadlock chỉ xảy ra khi có 4 tình huống sau đây cùng xảy ra đồng thời :

• Loại trừ tương hỗ (Mutual Exclusion) : Có ít nhất 1 tài nguyên đang bị chiếm giữ theo cơ chế không chia sẻ (nonshareable mode). Hay nói cách khác, chỉ có một process P1 duy nhất được sử dụng tài nguyên A trong một thời điểm. Nếu một process P2 khác yêu cầu tài nguyên nói trên, process P2 phải chờ đến khi tài nguyên A đã được process P1 giải phóng.
• Giữ và chờ (Hold and Wait) : Một process P1 phải đang giữ ít nhất một tài nguyên A và đang chờ một hoặc nhiều tài nguyên B đang bị giữ bởi một process B2 khác.
• Không trưng dụng (Non-Preemption) : Tài nguyên không thể bị lấy lại, tức là tài nguyên chỉ có thể được giải phóng khi process đang giữ nó trả lại sau khi đã hoàn thành xong công việc.
• Chu trình đợi (Circular Wait) : Tồn tại một tập {P0,…,Pn} các process đang đợi sao cho :
  • P0 đợi một tài nguyên mà P1 giữ.
  • P1 đợi một tài nguyên mà P2 giữ.
  • …
  • Pn đợi một tài nguyên mà P0 giữ.

Câu 4 : Các phương pháp giải quyết deadlock ?Nói chung, chúng ta có thể xử lý vấn đề deadlock bằng một trong những cách sau :

• Chúng ta có thể dùng một giao thức để bảo vệ hoặc tránh deadlock, bảo đảm rằng hệ thống sẽ không bao giờ rơi vào trạng thái deadlock.
  • Khác biệt :
    • Ngăn deadlock : Không cho phép ít nhất một trong 4 điều kiện cần cho deadlock xảy ra. Hoạt động bằng cách giới hạn yêu cầu tài nguyên của process.
    • Tránh deadlock : Các process cần cung cấp thông tin về tài nguyên nó cần, để hệ thống cấp phát tài nguyên một cách thích hợp.
• Chúng ta có thể cho phép hệ thống rơi vào trạng thái deadlock, kiểm tra deadlock và phục hồi hệ thống.
• Chúng ta có thể bỏ qua deadlock và xem như deadlock chưa từng xuất hiện (Windows/Linux). Tuy nhiên, deadlock không được phát hiện, về lâu dài sẽ dẫn đến việc giảm hiệu suất của hệ thống. Cuối cùng, hệ thống có thể ngưng hoạt động và phải khởi động lại.

Câu 5 : Làm gì để ngăn deadlock ?Chúng ta ngăn deadlock bằng cách ngăn một trong 4 điều kiện cần của deadlock.

• Ngăn loại trừ tương hỗ (Mutual Exclusion) :
  • Đối với tài nguyên không chia sẻ (printer) : Không làm được.
  • Đối với tài nguyên chia sẻ (read-only file) : Không cần thiết.
• Ngăn giữ và chờ (Hold and Wait) :
  • Cách 1 : Mỗi tiến trình yêu cầu toàn bộ tài nguyên cần thiết một lần. Nếu có đủ tài nguyên thì hệ thống sẽ cấp phát, nếu không đủ tài nguyên thì tiến trình phải bị block.
  • Cách 2 : Khi yêu cầu tài nguyên, tiến trình không được giữ tài nguyên nào. Nếu đang có thì phải trả lại trước khi yêu cầu thêm.
• Ngăn không trưng dụng (no preemption) : Nếu tiến trình A có giữ tài nguyên và đang yêu cầu tài nguyên khác nhưng tài nguyên này chưa được cấp phát ngay thì :
  • Cách 1 : Hệ thống lấy lại mọi tài nguyên mà A đang giữ.
    • A chỉ bắt đầu lại được khi có được các tài nguyên đã bị lấy lại cùng với tài nguyên đang yêu cầu.
  • Cách 2 : Hệ thống sẽ xem tài nguyên mà A yêu cầu :
    • Nếu tài nguyên được giữ bởi một tiến trình khác đang đợi thêm tài nguyên, tài nguyên này được hệ thống lấy lại và cấp phát cho A.
    • Nếu tài nguyên được giữ bởi tiến trình không đợi tài nguyên, A phải đợi và tài nguyên của A bị lấy lại. Tuy nhiên hệ thống chỉ lấy lại các tài nguyên mà tiến trình khác yêu cầu.
• Ngăn Circular Wait : Gán một thứ tự cho tất cả các tài nguyên trong hệ thống :
  • Tập hợp tài nguyên : R = {R1, R2, … , Rn}.
    • Ví dụ : F(tap drive) = 1, F (disk) = 5, F (printer) = 12.
  • Mỗi tiến trình chỉ có thể yêu cầu thực thể của một loại tài nguyên theo thứ tự tăng dần (định nghĩa bởi hàm F) của loại tài nguyên.
    • VD : Chuỗi yêu cầu hợp lệ : Tap Drive -> Disk -> Printer.
  • Khi một tiến trình yêu cầu một thực thể của loại tài nguyên Rj thì nó phải trả lại các tài nguyên Ri với F(Ri) > F(Rj).

Các bạn có thể xem tiếp phần 2 - Lý thuyết : http://bit.ly/2FnJt4CCác bạn có thể xem tiếp phần 3 - Bài tập : 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
• 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

Meta © 2024