Ôn tập thi Cuối kỳ

1. Tiến trình cha tạo lập sẵn một tập luồng khi khởi động.
2. Các luồng trong tập luồng luôn sẵn sàng chờ công việc.
3. 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.
4. Phục vụ xong, luồng được đưa trả về tập luồng.
5. 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.
Ví dụ:
Trong 1 doanh trại quân đội có 1 tướng lĩnh(tiến trình cha) và sẽ có một đội binh(tập luồng). Đội binh này sẽ sẵn sàng chiến đấu khi co mệnh lệnh(sẵn sằng chờ công việc). Khi có 1 tên địch đột nhập, tướng lĩnh sẽ điều binh sĩ 1(1 luồng) đi bắt tên địch(1 luồng đc đánh thức và đưa vào vận hành). Trong khi đó lại có them 1 tên địch khác đột nhập(nhận thêm một yêu cầu) tướng lĩnh sẽ điều binh sĩ 2(một luồng)đi bắt địch(1 luồng khác đc đánh thức và đưa vào vận hành). Sauk hi bắt địch xong binh sĩ sẽ trở về doanh trại(luồng đc trả về tậ luồng)

Bốn tình huống ra quyết định của trình điều phối CPU:
* Các 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 có tiếm quyền(Preemptive Scheduling) và điều phối không tiếm quyền (Non-Preemptive Scheduling)
+ Có tiếm quyền: Điều phối chỉ xảy ra ở thời điểm 1 va 4, không xảy ra điều phối ở thời điểm 2 và 3. 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. Trên HĐH hiện đại đa số có tiếm quyền.
+ Không tiếng quyền: Xảy ra trong cả 4 tình huống. Có thể bắt được tiến đang chạy, không cho độc chiếm CPU

- Đả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) .
Ví dụ: Một công ty có 1 một thang máy ( tài nguyên dùng chung), nhân viên nào vào trước thì được dùng thang máy trước và đi trước. Các nhân viên còn lại phải chờ cho đến khi thang máy trống thì nhân viên kế tiếp mới được vào thang máy.

Đoạn tương tranh là đoạn mã chương trình, điều khiển công việc của tiến trình có tính chất, mà khi thể hiện đoạn mã đó tác động tới tài nguyên dùng chung.

- Tính Loại trừ 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 ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: 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 chung.

- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).

Ví dụ trong 1 lớp học khi bạn A lên bảng để làm 1 công việc nào đó thì bạn B dù có muốn cũng không thể lên bảng được và chỉ khi A đã làm xong việc thì B mới được phép lên bảng(thì ở đây tài nguyên dùng chung chính là cái bảng).

Deadlocks:Tình huống hay trạng thái bị kẹt của của một nhóm tiến trình p1,p2,...pn 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ụ đời thường: 2 xe đi cùng chiều qua một cây cầu hẹp, mà cầu chỉ có một 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 (deadlocks) vì không xe nào chịu nhường.

Ví dụ trong máy tính:Có 3 tiến trình p1,p2,p3.Và 2 tài nguyên máy in,máy fax.
p3 xin cấp máy in,máy fax,nhưng 2 tài nguyên này đã được cấp cho p1 và p2.
dẫn đến kẹt tiến trình (deadlocks)

Trường hợp deadlock có thể phát sinh nếu bốn điều kiện sau xảy ra cùng một
lúc trong hệ thống:
1) Loại trừ tương hỗ(Mutual exclusion): ít nhất một tài nguyên phải được giữ trong chế độ
không chia sẻ; nghĩa là: chỉ một quá trình tại cùng một thời điểm có thể sử
dụng tài nguyên. Nếu một quá trình khác yêu cầu tài nguyên đó, quá trình
yêu cầu phải tạm dừng cho đến khi tài nguyên được giải phóng.
2) Giữ và chờ cấp thêm tài nguyên (Hold and wait): quá trình phải đang giữ ít nhất một tài
nguyên và đang chờ để nhận tài nguyên thêm mà hiện đang được giữ bởi
quá trình khác.
3) Không có ưu tiên (No preemption): Các tài nguyên
không thể bị đòi lại; nghĩa là, tài nguyên có thể được giải phóng chỉ tự ý
bởi quá trình đang giữ nó, sau khi quá trình đó hoàn thành tác vụ.
4) Tồn tại chu trình trong đồ thị cấp phát tài nguyên (Circular wait): một tập hợp các quá
trình {P0, P1,…,Pn} đang chờ mà trong đó P0 đang chờ một tài nguyên
được giữ bởi P1, P1 đang chờ tài nguyên đang giữ bởi P2,…,Pn-1 đang chờ
tài nguyên đang được giữ bởi quá trình P0.

Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau:

Tiến trình Thời điểm đến (ms) CPU-Burst (ms)
P1 5 34
P2 17 23
P3 24 9
Dùng thuật giải Round-Robin với thời lượng 10 ms để điều phối CPU:
a. Thể hiện bằng biểu đồ Gantt.
b. Tính thời gian chờ trung bình của các tiến trình.

Giải:
a. Biểu đồ Gantt

---| P1 | P1 | P2 | P3 | P1 | P2 | P1 | P2|
5 15 25 35 44 54 64 68 71
b. Thời gian chờ trung bình của các tiến trình:
T(tb)= (T1+T2+…+Tn)/n
T1= (5 – 5)+(15-5)+(44-35)+(64-54)=29
T2=(25-15)+(54-44)+(68-64)=24
T3=(35-25)=10
T(tb)=(29+24+10)/3=21ms

1. Trình bày thuật giải điều phối CPU với hàng chờ nhiều mức MQS và so sánh với thuật giải MFQS?
2. Trình bày khái niệm đèn hiệu và 2 ứng dụng của đèn hiệu? Cho ví dụ?

PhamThiThao (I22B) đã viết:1. Trình bày thuật giải điều phối CPU với hàng chờ nhiều mức MQS và so sánh với thuật giải MFQS?
2. Trình bày khái niệm đèn hiệu và 2 ứng dụng của đèn hiệu? Cho ví dụ?

thêm cái này nữa các bạn nha:
Thuật giải Nhà Băng

- Đoạn tương tranh là 1 đoạn mã( mã dùng chung )của tiến trình mà khi thực hiện nó sẽ truy cập và tác động vào tài nguyên dùng chung.
+ Cấu trúc mã đoạn tương tranh
While(1)
{
Remainder section // chưa ảnh hưởng đến tài nguyên dùng chung
Entry section // các tiến trình(1 lệnh hoặc chuỗi lệnh) được chờ tại đây.
Critical section //vùng tương tranh
Exit section //TT thực hiện xong thoát và thông báo cho TT kế tiếp thực thi.
Remainder section
}
- Tính loại trừ tương hổ( tính loại trừ lần nhau ) là mỗi thời điểm chỉ có 1 tiến trình vận hành trong đọan tương tranh.

VD: xe qua cầu yếu
Mã của tiến trình Xei có cấu trúc như sau:
Typedef int semaphore;
Semaphore mutex = 1; //đèn hiệu nhị phân, có hai trạng thái
//0: đèn màu đỏ
//1: đèn màu xanh
While(1)
{
Đi đến cầu;
Wait(mutex); //chờ đèn xanh
Lên cầu; //đoạn tương tranh, đèn màu đỏ
Qua cầu; //đoạn tương tranh, đèn màu đỏ
Signal(mutex); //đèn chuyển sang màu xanh
Đi tiếp;
Quay về theo cầu khác;
}
Do chiếc cầu yếu nên mỗi thời điểm chỉ có 1 xe được phép qua cầu. Những xe khác khi đi đến đầu cầu sẽ ngủ tại lệnh wait(mutex) vì đèn đỏ. Sau khi một xe đã lên cầu và qua cầu xong thì lệnh signal(mutex) được thực hiện, tăng đèn mutex lên 1, đèn chuyển sang màu xanh. Một xe sau sẽ được đánh thức và lên cầu. Trong trường hợp này vùng tranh chấp là cây cầu.

#include
#include
#include
#define BUFFER_SIZE 10
int buffer[BUFFER_SIZE];
char s[BUFFER_SIZE];
int in=0;
int out=0;
int nextProduced=1;
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);// vào đoạn tương tranh
//…Sắp sản phẩm vào Buffer
buffer[in]=nextProduced++;
switch ((int)p){
case 1:
s[in]=’P’;
break;
case 2:
s[in]=’p’;
break;
default:
s[in]=’S’;
};
in=(in+1)%BUFFER_SIZE;
// Tăng (semFull) lên 1
ReleaseSemaphore(semFull, 1, NULL);
LeaveCriticalSection(&critSec);// rời khỏi đoạn tương tranh
SuspendThread(GetCurrentThread());
}
}

void Consumer()
{
int nextConsumed;
while (1)
{
// Chờ đến khi có sản phẩm
WaitForSingleObject(semFull, INFINITE);
EnterCriticalSection(&critSec); // vào đoạn tương tranh
nextConsumed=buffer[out];
out=(out+1)%BUFFER_SIZE;
// Tăng (semEmpty) lên 1
ReleaseSemaphore (semEmpty, 1, NULL);
LeaveCriticalSection(&critSec); // rời khỏi đoạn tương tranh
// ... 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 nhằm đả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.

Tiến trình (Process)là chương trình trong thời gian thực hiện (đặt dưới sự quản lý của HDH)
- 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).
- Một 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

Câu hỏi:
BÀI 5 : ĐA LUỒNG

Câu 1: Trình bày khái niệm Luồng và so sánh với khái niệm tiến trình truyền thống? Phân tích những lợi ích của công nghệ Đa luồng?
Câu 2: Trình bày nguyên lý tập luồng và ứng dụng? Cho ví dụ trên máy tính và từ đời thường?
BÀI 6 : ĐIỀU PHỐI CPU

Câu 1: Trình bày 4 tình huống (thời điểm) 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 điều phối không tiếm quyền?
Câu 2: Trình bày thuật giải điều phối CPU với hàng chờ nhiều mức MQS và so sánh với thuật giải MFQS?
BÀI 7 : ĐỒNG BỘ HÓA TIẾN TRÌNH

Câu 1: Trình bày mục đích của đồng bộ hóa công việc các tiến trình? Nêu ví dụ minh họa?
Câu 2: Trình bày khái niệm đoạn tương tranh và cách giải quyết vấn đề này?
Câu 3: Trình bày khái niệm đèn hiệu và 2 ứng dụng của đèn hiệu? Cho ví dụ?

BÀI 8 : DEADLOCKS

Câu 1: Trình bày khái niệm Deadlocks và các ví dụ minh họa từ đời thường?
Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau:


Câu 2: Trình bày 4 điều kiện cần dẫn đến Deadlocks và biện pháp ngăn chặn Deadlocks?
Câu 3: Biết vẽ và giải thích cũng như đánh giá trạng thái của đồ thị cấp phát tài nguyên?

BÀI TẬP TRONG ĐỀ THI
Cấu trúc câu 4,5:

CÂU 4: Chỉ có thuật giải Round Robin.
Dùng thuật giải RRS với thời lượng bằng 20 ms để điều phối CPU:
a. Thể hiện bằng biểu đồ Gantt
b. Tính thời gian chờ trung bình của các tiến trình
Bài giải:

Bảng trợ giúp


a) Thể hiện bằng biểu đồ Gantt:



b) Thời gian chờ trung bình của các tiến trình
- Thời gian chờ của các tiến trình:
P1 = (70 - 4) - 46 = 66 - 46 = 20 ms
P2 = (98 - 30) - 28 = 68 - 28 = 40 ms
P3 = (111 - 51) - 33 = 60 - 33 = 27 ms
- Thời gian chờ trung bình = (20 + 40 + 27)/3 = 87/3 = 29 ms
CÂU 5: Thuật giải Nhà Băng.
Hệ thống có 12 ổ băng từ
Tiến Trình Đã Cấp Tối Đa Cần(MAX)
P1 5 10
P2 2 4
P3 2 9

câu 1:dùng giải thuật nhà băng để chứng minh trạng thái này là an toàn.
câu 2:xác định có nên đáp ứng hay không khi P3 xin thêm 1 ổ nữa

Giải


Câu 1:
Tiến Trình Đang Giữ MAX Need Hệ Có
P1 5 10 (MAX- ĐangGiữ)=10-5=5 12-(5+2+2)=3
P2 2 4 (MAX- ĐangGiữ)=4-2=2
P3 2 9 (MAX- ĐangGiữ)=9-2=7



Work >= Needi Pi Allocationi
3 2 P2 2
5 5 P1 5
10 7 P3 2

chuỗi an toàn là:{P2,P1,P3}
vậy trạng thái này là an toàn(điều cần chứng minh)

Câu 2:
giả sử P3 xin thêm một ổ nữa
thỏa 2 điều kiện:
request3<= Need vì 1< 7
request3<= Available vì 1< 3
Trạng thái mới
Tiến Trình Đang Giữ MAX Need Hệ Có
P1 5 10 (MAX- ĐangGiữ)=10-5=5 12-(5+2+3)=2
P2 2 4 (MAX- ĐangGiữ)=4-2=2
P3 3 9 (MAX- ĐangGiữ)=9-3=6


Work >= Needi Pi Allocationi
2 >= 2 P2 2
4 ? ? ?



P1 và P3 ko thỏa điều kiện Work >= NEEDi, do đó không xác định được chuỗi an toàn nên trạng thái này không an toàn, vậy không thể cấp thêm 1 ổ nữa cho P3
Chúc các bạn làm bài tốt trong ki thi sắp tới và mình cũng dẽ cố gắng để đạt số điểm cao nhất.=))

DoThiHaDuc(I22B) đã viết:Tình hình là thày miễn giảm lý thuyết bài 1 đến bài 4, chỉ còn học bài 5, bài 6, bài 7 và bài 8 thôi. Vậy lý thuyết tụi mình chỉ còn học 10 câu thôi Ôi yêu thày quá, cám ơn thày nhiều lắm lắm lắm... Tụi em sẽ cố gắng ko chỉ đậu mà đậu điểm thật cao môn HĐH!!! Biết ơn thày đã tâm lý và giúp đỡ tụi em!

Sau đây là tổng hợp các câu lý thuyết mà tụi mình cần phải vượt qua để dành trọn điểm CÂU 1 và CÂU 2 của thầy nha các bạn:

BÀI 5 : ĐA LUỒNG

Câu 1: Trình bày khái niệm Luồng và so sánh với khái niệm tiến trình truyền thống? Phân tích những lợi ích của công nghệ Đa luồng?
Câu 2: Trình bày nguyên lý tập luồng và ứng dụng? Cho ví dụ trên máy tính và từ đời thường?

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

Câu 1: Trình bày 4 tình huống (thời điểm) 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 điều phối không tiếm quyền?
Câu 2: Trình bày thuật giải điều phối CPU với hàng chờ nhiều mức MQS và so sánh với thuật giải MFQS?

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

Câu 1: Trình bày mục đích của đồng bộ hóa công việc các tiến trình? Nêu ví dụ minh họa?
Câu 2: Trình bày khái niệm đoạn tương tranh và cách giải quyết vấn đề này?
Câu 3: Trình bày khái niệm đèn hiệu và 2 ứng dụng của đèn hiệu? Cho ví dụ?

BÀI 8 : DEADLOCKS

Câu 1: Trình bày khái niệm Deadlocks và các ví dụ minh họa từ đời thường?
Câu 2: Trình bày 4 điều kiện cần dẫn đến Deadlocks và biện pháp ngăn chặn Deadlocks?
Câu 3: Biết vẽ và giải thích cũng như đánh giá trạng thái của đồ thị cấp phát tài nguyên?

BÀI TẬP TRONG ĐỀ THI

CÂU 4: Chỉ có thuật giải Round Robin.
CÂU 5: Thuật giải Nhà Băng.

CHÚ Ý: trong tất cả các câu trả lời, các bạn nhớ nêu VÍ DỤ MINH HỌA nha!!!
( Không biết mình có thiếu sót bỏ qua chỗ nào không...các bạn góp ý mình nhé! )

Chúc tất cả các bạn thi cuối kì thật tốt môn thày! Vì thày đã tận tình với chúng ta rất nhiều! Đừng phụ lòng thày nha các bạn!!! CỐ LÊN!!!

Cùng bạn cố gắng Thi điểm cao để không phụ công lao Giảng dạy của Thầy.

NguyenVanQuoc (I22B) đã viết:

DoThiHaDuc(I22B) đã viết:Tình hình là thày miễn giảm lý thuyết bài 1 đến bài 4, chỉ còn học bài 5, bài 6, bài 7 và bài 8 thôi. Vậy lý thuyết tụi mình chỉ còn học 10 câu thôi Ôi yêu thày quá, cám ơn thày nhiều lắm lắm lắm... Tụi em sẽ cố gắng ko chỉ đậu mà đậu điểm thật cao môn HĐH!!! Biết ơn thày đã tâm lý và giúp đỡ tụi em!

Úi Thầy miễn bài 1 đến bài 4 thiệt ah, mình đâu vắng buổi nào đâu sao không nghe thông tin này, hay Thầy thông trúng buổi mình đi muộn mấy phút đầu giờ.

Bạn này chắc là vào trể rồi, Thầy giảm cho như thế là để giảm tải và thi cho tốt.
Nhưng Thầy nhấn mạnh là Thầy sẽ chấm thi khó hơn, yêu cầu chất lượng gấp đôi so với các năm trước và nhớ 1 điều Thầy dặn nữa là làm bài chỉ làm ngắn gọn, súc tích, chỉ trên 1 tờ giấy thi thôi.

Semaphore SemEmpty,SemFull;
//khai báo 2 biến dùng chứa 2 đối tượng đèn hiệu thuộc lớp Semaphore.

SemEmpty = new Semaphore(2,10,"SemEmpty");
// khởi tạo đèn hiệu với giá trị ban đầu là 2,giá trị tối đa là 10,với tên SemEmpty đây là đèn hiệu liên tiến trình nên tính bảo mật không cao.

SemFull = new Semaphore(8,10,"SemFull");
// khởi tạo đèn hiệu với giá trị ban đầu là 8,giá trị tối đa là 10,với tên SemFull đây là đèn hiệu liên tiến trình nên tính bảo mật không cao.

SemFull.WaitOne();
//Chờ với giá trị là 8 sau đó giảm còn 7

SemEmpty.Release();
//Tăng giá trị từ 2 lên 3


Câu này em xung phong lên bảng nhưng giải thích chưa được tốt Thầy cho nữa điểm thưởng.

CÂU 4: Chỉ có thuật giải Round Robin.
Dùng thuật giải RRS với thời lượng bằng 20 ms để điều phối CPU:
a. Thể hiện bằng biểu đồ Gantt
b. Tính thời gian chờ trung bình của các tiến trình
Bài giải:

Bảng trợ giúp


a) Thể hiện bằng biểu đồ Gantt:



b) Thời gian chờ trung bình của các tiến trình
- Thời gian chờ của các tiến trình:
P1 = (70 - 4) - 46 = 66 - 46 = 20 ms
P2 = (98 - 30) - 28 = 68 - 28 = 40 ms
P3 = (111 - 51) - 33 = 60 - 33 = 27 ms
- Thời gian chờ trung bình = (20 + 40 + 27)/3 = 87/3 = 29 ms


Thi đợt này câu này Thầy dặn các bạn phải nêu thêm lý thuyết Round - Robin nữa nhé.

Một hệ thống có 10 máy quét và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài nguyên ở thời điểm Ti thể hiện bằng các vector Allocation (3,1,1) và Max (9,4,8 ).
Dùng thuật giả nhà băng để
a. Chứng minh trạng thái này an toàn
b. Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy cho tiến trình P3?
Giải
a.
Allocation = (3,1,1)
Max = (9,4,8 )
Avaible = 10 - (3+1+1) = 5

Process---Allocation---Max---Need---Available
P1----------3-----------9--------6---------5
P2----------1-----------4--------3
P3----------1-----------8--------7


Bảng trợ giúp:
Work >=---Needi---Pi---Allocation
5-------------3------P2---1
6-------------6------P1---3
9-------------7------P3---1

Tìm được chuỗi an toàn P2, P1, P3
Do đó trạng thái hệ thống ở thời điểm Ti là an toàn
b.
Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy cho tiến trình P3
Gọi yêu cầu là Request3. Ta có Request3 = 1
Request3 =< Need3 (vì 1 =<7)
Request3 =< Available (vì 1 =<5)
Trạng thái mới của hệ thống
Allocation = (3,1,2)
Max = (9,4,8 )
Avaible = 10 - (3+1+2) = 4

Process---Allocation---Max---Need---Available
P1---------3------------9-------6--------4
P2---------1------------4-------3
P3---------2------------8-------6


Bảng trợ giúp:
Work >=-----Needi---Pi---Allocation
4--------------3-------P2---1
5--------------?-------?-----?

Cả 2 tiến trình P1 và P3 điều không thỏa điều kiện Work >= Needi (vì Need2 = 6, Need3 = 6)
Vậy ta không nên đáp ứng yêu cầu Request3 vì hệ thông sẽ không còn an toàn.

Chúc các bạn thi thật tốt

Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau:

Tiến trình--Thời điểm đến--CPU-Burst
P1---------5---------25
P2---------20-------15
P3---------30-------10

Dùng thuật giải Round-Robin với thời lượng 10ms để điều phối CPU
a. Thể hiện bằng biểu đồi Gantt.
b. Tính thời gian trung bình của các tiến trình.
Giải
a.
Thể hiện bằng biểu đồ Gantt

Bảng trợ giúp
P1----------P2--------P3
5 (25)-----20 (15)-----30 (10)
15 (15)----35 (5)------50 (0)
25 (5)-----55 (0)------
40 (0)-------------------------

Biểu đồ Gantt:
|----|------P1------|---P1----|---P2----|--P1--|----P3---|--P2-|
0....5...................15............25...........35.......40..........50.....55
b.
Thời gian chờ trung bình
* Thời gian chờ trung bình của các tiến trình
- P1 = (40 - 5) - 25 = 10 ms
- P2 = (55 - 20) - 15 = 20 ms
- P3 = (50 - 30) - 10 = 10 ms
Vậy thời gian chờ trung bình = (P1 + P2 + P3)/3 = (10 + 20 + 10)/3=13.33 ms

Đang chỉnh sửa tính post bài này hồi qua thầy mới dạy
mà mạng nhà dỏm quá
Thanks bài gia chi tiết của bạn nha!

VoMinhThang(I22B) đã viết:Trong bài tạp thuật giải Nhà băng, các bạn có để ý các P0 P1 P2 P3 P4, sắp xếp không thứ tự khi giải không, lúc mà chia cái bảng đó. Vậy cho phép mình hỏi câu này "tuy hơi ngố":

Tại sao ta không giải theo thứ tự P0 P1 P2 P3 P4 mà giải theo như bài tập mà thầy giải ở lớp: P1 P3 P4 P2 P0...

vì đây la lúc mình tìm chuổi an toàn. trong bảng trợ giúp có cột work và need[i]. nếu tiến trình nào ma work>=need[i] thì được chọn trc. không nhất thiết phải là theo thứ tự p1, p2,p3 .. miễn sao thỏa điều kiện trên là đươc. chúng ta có thể tìm được nhiều chuổi an toàn khác nhau, chứ ko phải là 1 cái... theo mình la vậy, có gì sai sót, mong thầy và các bạn giúp đỡ

BuiThucTuan(I22B) đã viết:

VoMinhThang(I22B) đã viết:Trong bài tạp thuật giải Nhà băng, các bạn có để ý các P0 P1 P2 P3 P4, sắp xếp không thứ tự khi giải không, lúc mà chia cái bảng đó. Vậy cho phép mình hỏi câu này "tuy hơi ngố":

Tại sao ta không giải theo thứ tự P0 P1 P2 P3 P4 mà giải theo như bài tập mà thầy giải ở lớp: P1 P3 P4 P2 P0...

vì đây la lúc mình tìm chuổi an toàn. trong bảng trợ giúp có cột work và need[i]. nếu tiến trình nào ma work>=need[i] thì được chọn trc. không nhất thiết phải là theo thứ tự p1, p2,p3 .. miễn sao thỏa điều kiện trên là đươc. chúng ta có thể tìm được nhiều chuổi an toàn khác nhau, chứ ko phải là 1 cái... theo mình la vậy, có gì sai sót, mong thầy và các bạn giúp đỡ

hii, đây cũng là thắc mắc của mình từ khi học bài 8, công nhận lúc thầy giản cũng chưa hình dung lắm..., mình mất 1 đêm mới "đả thông kinh mạch" được, cảm ơn bạn đã góp ý nha.. hiii

NguyenThiHongCuc đã viết:Đang chỉnh sửa tính post bài này hồi qua thầy mới dạy
mà mạng nhà dỏm quá
Thanks bài gia chi tiết của bạn nha!

hii, bạn co tin nãy giờ mình vừa sửa máy tính- cài đặt soft vừa post không .

Chỉ hi vọng duy nhất là: các bạn + mình không học lại thôi (mơ ước nhỏ nhoi ^^)

Câu 1 : Trình bày khái niệm Luồng và so sánh với khái niệm tiến trình truyền thống? Phân tích những lợi ích của công nghệ Đa luồng?[b]
- Luồng là tiến trình đặc biệt(tiến trình nhẹ) nằm trong tiến trình truyền thống.Luồng là đơn vị cấp phát CPU( có PCB riêng)
-Nhiều luồng có thể chung mã,khác với tiến trình(vì tiến có mã riêng)
Tiến trình(process) là trạng thái tức thời của một chương trình đang chạy trên máy tính.
-Lợi ích của công nghệ Đa luồng là :
. Khả năng đáp ứng
VD : Tổng đài trả lời 1080 là 1 hệ thống đa luồng.Các tổng đài viên là 1 luồng trả lời các thắc mắc.Tại 1 thời điểm có nhiều cuộc điện thoại đến tổng đài cần được giải đáp,thì lúc đó tổng đài sẽ chia ra cho mỗi tổng đài viên giải quyết 1 cuộc điện thoại,đảm bảo cùng 1 lúc có thể phải hồi được nhiều yêu cầu.
.Chia sẽ tài nguyên
VD : Cả lớp là 1 tiến trình,1 sinh viên trong lớp là 1 luồng cùng dùng chung máy chiếu,bảng,.....
. Tiết kiệm
VD : Tạo thêm 1 chổ ngồi trong lớp cho 1 bạn mới(là 1 luồng) sẽ dễ hơn là tạo thêm 1 lớp mới (tiến trình)
. Tận dụng được thế mạnh của kiến trúc đa xử lý(kiến trúc đa xử lý là gồm nhiều CPU)
VD : ô tô có nhiều động cơ sẽ hoạt động nhanh hơn
* Có thiếu hay sai gì mong thầy và các bạn góp ý để lớp mình có câu trả lời tốt cho bài thi

le thi thanh thuy đã viết:Hệ thống có 12 ổ băng từ

Tiến Trình	Đã Cấp	Tối Đa Cần(MAX)
P1	5	10
P2	2	4
P3	2	9

câu 1:dùng giải thuật nhà băng để chứng minh trạng thái này là an toàn.
câu 2:xác định có nên đáp ứng hay không khi P₃ xin thêm 1 ổ nữa

Giải


Câu 1:

Tiến Trình	Đang Giữ	MAX	Need	Hệ Có
P1	5	10	(MAX- ĐangGiữ)=10-5=5	12-(5+2+2)=3
P2	2	4	(MAX- ĐangGiữ)=4-2=2
P3	2	9	(MAX- ĐangGiữ)=9-2=7

Work >=	Needi	Pi	Allocationi
3	2	P2	2
5	5	P1	5
10	7	P3	2

chuỗi an toàn là:{P₂,P₁,P₃}
vậy trạng thái này là an toàn(điều cần chứng minh)

Câu 2:
giả sử P₃ xin thêm một ổ nữa
thỏa 2 điều kiện:
request₃<= Need₃ vì 1< 7
request₃<= Available vì 1< 3
Trạng thái mới

Tiến Trình	Đang Giữ	MAX	Need	Hệ Có
P1	5	10	(MAX- ĐangGiữ)=10-5=5	12-(5+2+3)=2
P2	2	4	(MAX- ĐangGiữ)=4-2=2
P3	3	9	(MAX- ĐangGiữ)=9-3=6

Work >=	Needi	Pi	Allocationi
2 >=	2	P2	2
4	?	?	?

P₁ và P₃ ko thỏa điều kiện Work >= NEED_i, do đó không xác định được chuỗi an toàn nên trạng thái này không an toàn, vậy không thể cấp thêm 1 ổ nữa cho P₃

Bạn giải tốt quá.thanks bạn