Tổng hợp câu trả lời ôn tập !

BÀI 5 : ĐA LUỒNG
Câu 1 : Trình bày so sánh khái niệm luồng với tiến trình , cho biết lợi ích của công nghệ đa luồng :
Khái niệm :
- Luồng(Thread) còn gọi 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 truyền thống (HWP - Heavy Weight Process).
- Tiến trình có thể có một luồng chính với nhiều luồng phụ. Mỗi luồng có khả năng chia sẻ tài nguyên với các luồng khác trong tiến trình.
- Nhiều luồng có thể cùng chung một mã chương trình.

Giống nhau :

- Đều có thông tin trạng thái
- Luồng còn được gọi là tiến trình nhẹ
- Nhiều luồng or nhiều tiến trình có thể liên quan đến một chương trình
- Chia sẻ tài nguyên cho nhau
- Tăng tốc tính toán
- Đảm bảo tính đơn thể

Khác nhau :

- Do luồng cùng vận hành trong 1 vùng địa chỉ vì vậy dể dùng chung tài nguyên hơn đa tiến trình
VD : Mượn đồ dùng trong gia đình thì dể hơn mượn của hàng xóm
- Do luồng chung tài nguyên với cha & các luồng khác nên việc tạo lập & chuyển ngữ cảnh cũng
nhanh hơn tiến trình
VD : Việc ngăn riêng ra một phòng trong nhà thì nhanh hơn là chờ nhà nước cấp cho
một căn hộ
- Cấp phát bộ nhớ & tài nguyên cho tiến trình thì tốn kém hơn luồng
- Lập trình đa luồng thì dể hơn đa tiến trình
Lợi ích của công nghệ đa luồng :
- Đảm bảo được khả năng đáp ứng của tiến trình tốt hơn, khi lập trình đa luồng thì một khi 1 luồng có sự cố thì luồng khác vẫn làm việc, vẫn phản hồi ,trong trường hợp lập trình đơn luồng khi gặp sự cố thì luồng đó sẽ chậm và làm chậm luôn cả tiến trình, đa luồng một ứng dụng giao tiếp cho phép một chương trình tiếp tục chạy thậm chí nếu một phần của nó bị khóa hay đang thực hiện một thao tác dài, do đó gai tăng sự đáp ứng đối với người dùng, Ví dụ : một trình duyệt web vẫn có thể đáp ứng người dùng bằng một luồng trong khi vẫn nạp bằng một luồng khác.
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ô (người thứ nhất) 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

- Theo mặc định các luồng có thể dùng chung bộ nhớ và tai nguyên của luồng cha. Thuận lợi của việc chia sẻ mã là nó cho phép một ứng dụng có nhiều hoạt động của các luồng khác nằm trong cùng không gian, địa chỉ,vài luồng cùng vận hành trong một vùng địa chỉ 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à có kệ sách, xe máy, máy vi tính … mọi người có thể dùng chung và sử dụng chung kệ sách, xe máy, máy vi tính. Trong khi không thể dùng chung những đồ dùng trên với nhà khác được
Trong lớp chúng ta có thể dùng bảng củ lớp mình, chúng ta có thể chia sẻ các thông tin cần thiết cho tất cả các thành viên ở trong lớp biết,trong khi chúng ta khong thể dùng chung bảng của lớp khác để chia sẻ thông tin cho lớp mình được.

- 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 rất tốn kém. Do luồng có thể dùng chung tài nguyên với luồng cha và các luồng khác, việc tạo lập ngữ cảnh cũng nhanh hơn (Solaris2, 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 của lớp, ai cần ghi thì ghi, ai cần thì chụp hình về xem
Có thể bố trí một chỗ ngồi ở trong lớp cho một bạn đến sau dễ dàng hơn việc làm một chiếc ghế khác cho bạn đó.

- Chuyển ngữ cảnh từ luồng này sang luồng khác thì nhanh hơn chuyển ngữ cảnh từ tiến trình này sang tiến trình khác.

- Tận dụng được ưu thế kiến trúc đa xử lý (nhiều CPU). Khi đa luồng thì 1 luồng dùng CPU này và 1 luồng dùng CPU khác sẽ nhanh hơn và các luồng có thể làm việc song song , mỗi luồng có thể chạy bởi CPU riêng. Tiến trình đa luồng sẽ làm việc nhanh hơn tiến trình đơn luồng.

- Lập trình đa luồng dễ dàng hơn lập trình đa tiến trình

Câu 2 : Trình bày nguyên lý tập luồng và ứng dụng ,cho ví dụ minh họa :
Nguyên lý tập luồng :
- 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.

Ứng Dụ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ề).
- 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.
- 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).
- 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.
Ví dụ : Duy trì 1 đội quân 100 người được đào tạo kỉ càng,trang bị đầy đủ, khi có địch đến thì tùy theo tình hình sẽ điều lính ra .

BÀI 6 : ĐIỀU PHỐI CPU

Câu 1 : Trình bày 4 tình huống ra quyết định của trình điều phối. Phân biệt điều phối có tiếm quyền và điều phối không tiếm quyền ?
4 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 3 : RRS
Câu 4 : Trình bày thuật giải điều phối CPU với hang chờ nhiều mức , phân biệt thuật giải MQS và 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


BÀI 7: ĐỒNG BỘ HÓA TIẾN TRÌNH

Câu 1: Những lý do đồng bộ hóa công việc tiến trình. Cho ví dụ minh họa

- Đảm bảo tính nhất quán của tài nguyên dùng chung.
- Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình) .
VD: Trong tình trạng kẹt xe, nếu ta đi đúng luật , tuân thủ sự điều khiển của CSGT thì mọi thứ sẽ đồng bộ , tránh đc tinh trạng kẹt xe .

Câu 2 : Trình bày vấn đề đoạn tương tranh và cách giải quyết vấn đề đó ?
Đoạn tương tranh là 1 đoạn mã trong chương trình điều khiển công việc của tiến trình ,nhưng đặc biệt ở chổ nó chứa các lệnh liên quan đến tài nguyên dung chung với các tiến trình khác (đọc hay sửa nội dung tài nguyên dung chung )
Ví dụ: Sinh viên ghi bài học vào tập của mình không ảnh hưởng tới người khác thì không phải là tương tranh.
- Giả sử có n tiến trình(P0,P1...,Pn-1). Mỗi tiến trình có đoạn mã gọi là Đoạn tương tranh trong đó tiến trình có thể truy cập và thay đổi vùng nhớ, tập tin hay tài nguyên dùng chung.
- Tính loại từ 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 đoạn tương tranh của nó thì không có tến trình nào khác trong nhóm cũng tại đoạn như vậy, 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 dùng chung.
- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry setion(đoạn đăng nhập), Exit setion(đọn đăng xuất) và các Remainder(đoạn còn lại).
- Cấu trúc mã của tiến trình tương tranh P1
while(1)
{
remainder section// đoạn còn lại
entry section// đoạn đăng nhập
critical section// đoạn đăng xuất
exit section
remainder sectio// đoạn còn lại
}
- Giải quyết vấn đề tương tranh phải thỏa các điều kiện sau:
+ Loại trừ lẫn nhau(Mutual Exclusion): mỗi thời điểm chỉ có 1 tiến trình vận hành trong đoạn tương tranh.
+ Tiến triển(Progress) không có tến trình nào phải chờ vô hạn tại đoạn đăng nhập của nó.
Ví dụ: Cùng 1 lúc chỉ có 1 bạn lên bảng sữa bài.

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 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.

BÀI 8 : DEADLOCKS

Câu 1 : Trình bày khái niệm deadlocks và cho các ví dụ minh họa .

Định nghĩa: Tình huống bị kẹt của một nhóm tiến trình do mỗi tiến trình trong nhóm đều chờ một sự kiện (event) có thể chỉ được gây ra bởi một tiến trình khác.

Ví dụ:
- 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 : 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 Giải bài tập tránh Deadlocks bằng thuật giải nhà băng

Tạm thời mình up nhiêu đây , còn thiếu giải bài tập bằng thuật giải RRS và thuật giải nhà băng, mình sẽ sớm post lên sau , Mọi người coi thử sai sót thì góp ý nhé .

Nguồn : từ slide của thầy và tham khảo bài viết của các khóa trước

Thanks bạn nhiều. Tài liệu rất hữu ích