Câu hỏi 4.1:

a)    Trình bày các tiêu chí đánh giá thuật toán điều độ.

+ Lượng tiến trình đc thực hiện xong : Số lượng tiến trình thực hiện xong trong 1 đơn vị time. Đo tính hiệu quả của hệ thống

+ Hiệu suất sd CPU

+ Thời gian vòng đời trung bình của tiến trình:  Từ lúc có yêu cầu tạo tiến trình đến khi kết thúc

+ Thời gian chờ đợi:Tổng time tiến trình nằm trong trạng thái sẵn sàng và chờ cấp CPU, anh hưởng trực tiếp của thuật toán điều độ tiến trình

+ Thời gian đáp ứng

+ Tính dự đoán đc: Vòng đời, thời gian chờ đợi, thời gian đáp ứng phải ổn định, ko phụ thuộc vào tải của ht

+ Tính công bằng: Các tiến trình cùng độ ưu tiên phải đc đối xử như nhau

b)    Trình bày thuật toán điều độ đến trước phục vụ trước và điều độ có mức ưu tiên.

Đến trc phục vụ trc(FCFS)

- Tiến trình yêu cầu CPU trc sẽ đc cấp trc

- HDH sắp xếp các tiến trình sẵn sàng vào hàn đợi FIFO

-  Tiến trình mới đc sắp xếp vào cuối hàn đợi

- Đơn giản đảm bảo tính công bằng

- Time chờ tb lớn =>a/h lớn tới hiệu suất chung của toàn hệ thống

- Thường là thuật toán điều độ ko phân phối lại

Điều độ có mức ưu tiên

-  Mỗi tiến trình có 1 mức ưu tiên

- Tiến trình có mức ưu tiên cao hơn sẽ đc cấp CPU trc

-  Cac tiến trình có mức ưu tiên bằng nhau đc điều độ theo FCFS

- Mức ưu tiên đc xd theo tiêu trí khác nhau

Câu hỏi 4.2 :

a)    Trình bày thuật toán điều độ ưu tiên tiến trình ngắn nhất, thời gian còn lại ngắn nhất.

Điều độ ưu tiên tiến trình ngắn nhất(SPF)

§ Chọn trong hàng đợi tiến trình có chu kỳ sử dụng CPU tiếp theo ngắn nhất để phân phối CPU

§ Nếu có nhiều tiến trình với chu kỳ CPU tiếp theo bằng nhau, chọn tiến trình đứng trước

§ Thời gian chờ đợi trung bình nhỏ hơn nhiều so với FCFS

§ Khó thực hiện vì phải biết độ dài chu kỳ CPU tiếp:

§ Trong các hệ thống xử lý theo mẻ: dựa vào thời gian đăng kí tối đa do lập trình viên cung cấp

§ Dự đoán độ dài chu kỳ CPU tiếp theo: dựa trên độ dài TB các chu kỳ CPU trước đó

§ Không có phân phối

Điều độ ưu tiên thời gian còn lại ngắn nhất (SRTF)

§ Khi 1 tiến trình mới xuất hiện trong hàng đợi, HDH so sánh thời gian còn lại của tiến trình đang chạy với thời gian còn lại của tiến trình mới xuất hiện. Nếu tiến trình mới xuất hiện có thời gian còn lại ngắn hơn, HDH thu hồi CPU của tiến trình đang chạy, phân phối cho tiến trình mới

§ Thời gian chờ đợi trung bình nhỏ

§ HDH phải dự đoán độ dài chu kỳ CPU của tiến trình

§ Việc chuyển đổi tiến trình ít hơn so với RR(quay vòng)

- Co cơ chế phân phối lại

b)    Điều độ theo mức ưu tiên có phân phối lại và không phân phối lại khác nhau thế nào ?

Điều độ theo mức ưu tiên có phân phối lại

Điều độ theo mức ưu tiên ko phân phối lại

- Ưu tiên thời gian còn lại ngắn nhất

- Ưu tiên tiến trình nào có mức ưu tiên cao hơn sẽ đc cấp CPU

Câu hỏi 4.3:

a) Trình bày về các giải pháp phần cứng (cấm ngắt, sử dụng lệnh máy đặc biệt) cho vấn đề loại trừ tương hỗ và đoạn nguy hiểm.

+  Cấm các ngắt:

§ Tiến trình đang có CPU: thực hiện cho đến khi tiến trình đó gọi dịch vụ hệ điều hành hoặc bị ngắt => cấm không để xẩy ra ngắt trong thời gian tiến trình đang ở trong đoạn nguy hiểm để truy cập tài nguyên

§ Đảm bảo tiến trình được thực hiện trọn vẹn đoạn nguy hiểm và không bị tiến trình khác chen vào

§ Đơn giản

§ Giảm tính mềm dẻo của HDH, không áp dụng với máy tính nhiều CPU

+ Sử dụng lệnh máy đặc biệt (tt)

Logic của lệnh Test_and_Set:

 Bool Test_and_Set(bool & val)

{

bool temp = val;

val = true;

return temp;

}

§ Ưu điểm:

+Việc sử dụng tương đối đơn giản và trực quan

+Có thể dùng để đồng bộ nhiều tiến trình

+Có thể sử dụng cho trường hợp đa xử lý với nhiều CPU nhưng có bộ nhớ chung

§ Nhược điểm:

+Chờ đợi tích cực

+ Có thể gây đói

b) Sử dụng Test_and_Set để thực hiện loại trừ tương hỗ cho bài toán các triết gia ăn cơm.

const int n; //n là số lượng tiến trình

bool lock;

void P(int i){    //tiến trình P(i)

for(;;){    //lặp vô hạn

while(Test_and_Set(lock)[i]);// lấy đũa bên trái

while(Test_and_Set(lock)[(i+1)%5]);// lấy đũa bên phải

<Ăn Cơm>

lock [i]= false;

lock [(i+1)%5]= false;

<Suy nghĩ>

}

}

void main(){

for(int i=0;I;<5;i++)

lock [i]= false;

//tắt tiến trình chính, chạy đồng thời n tiến trình

StartProcess(P(1)); ….    StartProcess(P(n));

}

c) Phân tích rõ giải pháp sử dụng Test_and_Set sử dụng ở trên có thể gây bế tắc hoặc đói không.

Sd lệnh test_and_set có thể gây ra tình trạng bế tắc trong TH cả 5 ông cùng lấy 1 đũa bên phải hoặc bên trái. Như vậy sẽ ko có ông nào đc ăn do vòng while() ko có điều kiện t/m. Ngoài ra lênh test_and_set gây đói tài nguyên

Câu hỏi 4.4 :

a)Trình bày phương pháp sử dụng cờ hiệu (semaphore) cho vấn đề loại trừ tương hỗ và đoạn nguy hiểm.

Cờ hiệu S là 1biến nguyên được khởi tạo bằng khả năng phục vụ đồng thời của tài nguyên

Giá trị của S chỉ có thể thay đổi nhờ gọi 2 thao tác là Wait và Signal

Wait(S):

§ Giảm S đi 1 đơn vị

§ Nếu giá trị của S<0 thì tiến trình gọi wait(S) sẽ bị phong tỏaSignal(S):

§ Tăng S lên 1 đơn vị

§ Nếu giá trị của S≤0: 1 trong các tiến trình đang bị phong tỏa được giải phóng và có thể thực hiện tiếp Wait và Signal là những thao tác nguyên tử

§ Để tránh tình trạng chờ đợi tích cực, sử dụng 2 thao tác phong tỏa và đánh thức:

§ Nếu tiến trình thực hiện thao tác wait, giá trị cờ hiệu âm thì thay vì chờ đợi tích cực nó sẽ bị phong tỏa  ( bởi thao tác block) và thêm vào hàng đợi của cờ hiệu

§ Khi có 1 tiến trình thực hiện thao tác signal thì 1 trong các tiến trình bị khóa sẽ được chuyển sang trạng thái sẵn sàng nhờ thao tác đánh thức  (wakeup) chứa trong signal

b) Sử dụng cờ hiệu để thực hiện đồng bộ hóa cho bài toán Người sản xuất, người tiêu dùng với bộ đệm hạn chế.

const int N; //kích thư_c bo ñem

semaphore lock = 1;

semaphore empty = 0;

semaphore full = N;

void producer () { //tiên trình ngư_i s_n xuât

for (;;) {

<s_n xuât >

wait (full);

wait (lock);

<thêm mot s_n pham vào bo ñem>

signal (lock);

signal (empty);

}

}

void consumer () { //tiên trình ngư_i tiêu dùng

for (;;) {

wait (empty);

wait (lock);

<lây mot s_n pham t_ bo ñem>

signal (lock);

signal (full);

<tiêu dùng>

}

}

void main(){

StartProcess(producer); StartProcess(consumer);

}

Câu hỏi 4.5 :

a)Trình bày giải pháp sử dụng monitor cho vấn đề loại trừ tương hỗ và đoạn nguy hiểm

- Tiến trình đang thực hiện trong monitor và bị dừng lại để đợi sự kiện=> trả lại monitor để tiến trình khác dùng

Tiến trình chờ đợi sẽ được khôi phục lại từ điểm dừng sau khi điều kiện đang chờ đợi được thỏa mãn

=> Sử dụng các biến điều kiện

Được khai báo và sử dụng trong monitor với 2 thao tác: cwait() và csignal()

- x.cwait():Tiến trình đang ở trong monitor và gọi cwait bị phong tỏa cho tới khi điều kiện x xẩy ra

Tiến trình bị xếp vào hàng đợi của biến điều kiện x.

Monitor được giải phóng và một tiến trình khác sẽ được vào

- x.csignal():Tiến trình gọi csignal để thông báo điều kiện x đã thỏa mãn Nếu có tiến trình đang bị phong tỏa và nằm trong hàng đợi của x.  do gọi x.cwait() trước đó sẽ được giải phóng

Nếu không có tiến trình bị phong tỏa thì thao tác csignal sẽ không có tác dụng gì cả

b) Sử dụng monitor để thực hiện loại trừ tương hỗ cho bài toán Người sản xuất, người tiêu dùng với bộ đệm hạn chế.

monitor BoundedBuffer

product buffer[N];    //bộ đệm chứa N sản phẩm kiểu product

int count;           //số lượng sản phẩm hiện thời trong bộ đệm

condition notFull, notEmpty;    //các biến điều kiện

public:

boundedbuffer( ) {  //khởi tạo

count = 0;

}

void append (product x) {

if (count == N)

notFull.cwait ( );  //dừng và chờ đến khi buffer có chỗ

<Thêm một sản phẩm vào buffer>

count++;

notEmpty.csignal  ();

}

product take ( ) {

if (count == 0)

notEmptry.cwait ();  //chờ đến khi buffer không rỗng

<Lấy một sản phẩm x từ buffer>

count --;

notFull.csignal ( );

}

}

void producer ( )  {   //tiến trình người sản xuất

for (;;){

<Sản xuất sản phẩm x>

BoundedBuffer.append (x);

}

}

void consumer ( )  {   //tiến trình người tiêu dùng

for (;;){

product x = BoundedBuffer.take ();

<Tiêu dùng x>

}

}

void main() {

Thực hiện song song producer và consumer.

}

Câu hỏi 4.7 :

a) khái niệm phân trang bộ nhớ

Bộ nhớ vật lý được chia thành các khối nhỏ, kích thước cố định và bằng nhau gọi là khung trang (page frame)

Không gian địa chỉ logic của tiến trình được chia thành những khối gọi là trang (page), có kích thước bằng khung. Tiến trình được cấp các khung để chứa các trang của mình.  Các trang có thể chứa trong các khung nằm rải rác trong bộ nhớ

HDH quản lý việc cấp phát khung cho mỗi tiến trình bằng bảng trang (bảng phân trang): mỗi ô tương ứng với 1 trang và chứa số khung cấp cho trang đó. Mỗi tiến trình có bảng trang riêng. Duy trì danh sách các khung trống trong MEM

Không có phân mảnh ngoài

Có phân mảnh trong

b)Trình bày về ánh xạ địa chỉ khi phân trang bộ nhớ.

Để tính toán địa chỉ hiệu quả,kích thước khung được chọn là lũy thừa của 2

Địa chỉ logic gồm 2 phần:

§ Số thứ tự trang (p)

§ Độ dịch (địa chỉ lệch) của địa chỉ so với đầu trang (o)

Nếu kích thước trang là 2n.Biểu diễn địa chỉ logic dưới dạng địa chỉ có độ dài (m + n) bit

§ m bit cao: biểu diễn số thứ tự trang

§ n bit thấp: biểu diễn độ dịch trong trang nhớ

Địa chỉ lô gic  số thứ tự trang (p)  độ dịch trong trang (o)

Độ dài  m + n

Quá trình chuyển địa chỉ logic sang địa chỉ vật lý:

§ Lấy m bit cao của địa chỉ => được số thứ tự trang

§ Dựa vào bảng trang, tìm được số thứ tự khung vật lý (k)

§ Địa chỉ vật lý bắt đầu của khung là k*2n

§ Địa chỉ vật lý của byte được tham chiếu là địa chỉ bắt đầu của khung cộng với địa chỉ lệch (độ dịch)

=> Chỉ cần thêm số khung vào trước dãy bit biểu diễn độ lệch

Top of Form

Bottom of Form

Câu hỏi 4.8 :

a) Đổi trang ít sử dụng nhất trong thời gian cuối (LRU):

§ Trang bị đổi là trang mà thời gian từ lần truy cập cuối cùng đến thời điểm hiện tại là lâu nhất. Theo nguyên tắc cục bộ về thời gian, đó chính là trang ít có khả năng sử dụng tới nhất trong tương lai

§ Thực tế LRU cho kết quả tốt gần như phương pháp đổi trang tối ưu

Xác định được trang có lần truy cập cuối diễn ra cách thời điểm hiện tại lâu nhất?

Sử dụng biến đếm:

§ Mỗi khoản mục của bảng phân trang sẽ có thêm một trường chứa thời gian truy cập trang lần cuối - Là thời gian logic

§ CPU cũng được thêm một bộ đếm thời gian lôgic này

§ Chỉ số của bộ đếm tăng mỗi khi xảy ra truy cập bộ nhớ

§ Mỗi khi một trang nhớ được truy cập, chỉ số của bộ đếm sẽ được ghi vào trường thời gian truy cập trong khoản mục của trang đó=> trường thời gian luôn chứa thời gian truy cập trang lần cuối=> trang bị đổi là trang có giá trị thời gian nhỏ nhất

Sử dụng ngăn xếp:

§ Ngăn xếp đặc biệt được sử dụng để chứa các số trang

§ Mỗi khi một trang nhớ được truy cập, số trang sẽ được chuyển lên đỉnh ngăn xếp

§ Đỉnh ngăn xếp chứa trang được truy cập gần đây nhất, Đáy ngăn xếp chính là trang cần trao đổi

§ Tránh tìm kiếm trong bảng phân trang

b)Trình bày chiến lược đổi trang sử dụng thuật toán đồng hồ.

Cải tiến FIFO nhằm tránh thay những trang mặc dù đã được nạp vào lâu nhưng vẫn có khả năng sử dụng

§ Mỗi trang được gắn thêm 1 bit sử dụng U

§ Khi trang được truy cập đọc/ ghi: U = 1=> ngay khi trang được đọc vào bộ nhớ: U =1

§ Các khung có thể bị đổi (các trang tương ứng) được liên kết vào 1 danh sách vòng

§ Khi một trang nào đó bị đổi, con trỏ được dịch chuyển để trỏ vào trang tiếp theo trong danh sách

Khi có nhu cầu đổi trang, HDH kiểm tra trang đang bị trỏ tới

§ Nếu U=0: trang sẽ bị đổi ngay

§ Nếu U=1: đặt U=0 và trỏ sang trang tiếp theo, lặp lại quá trình

Nếu U của tất cả các trang trong danh sách =1 thì con trỏ sẽ quay đúng 1 vòng, đặt U của tất cả các trang =0 và trang hiện thời đang bị trỏ sẽ bị đổi

Căn cứ vào 2 thông tin để đưa ra quyết định đổi trang:

§ Thời gian trang được tải vào, thể hiện qua vị trí trang trong danh sách giống như FIFO

§ Gần đây trang có được sử dụng hay không, thể hiện qua bit U. Việc kiểm tra thêm bit U tương tự việc cho trang thêm khả năng được giữ trong bộ nhớ=> thuật toán cơ hội thứ 2

Câu hỏi 4.9

a)Trình bày phương pháp cấp phát không gian cho file sử dụng các khối liên tiếp. Khi nào nên sử dụng phương pháp này cho hệ thống file ?

Được cấp phát 1 khoảng không gian gồm các khối liên tiếp trên đĩa

Vị trí file trên đĩa được xác định bởi vị trí khối đầu tiên và độ dài (số khối) mà file đó chiếm

Khi có yêu cầu cấp phát, HDH sẽ chọn 1 vùng trống có số lượng khối đủ cấp cho file đó

Bảng cấp phát file chỉ cần 1 khoản mục cho 1 file, chỉ ra khối bắt đầu, và độ dài của file tính = khối

Là cấp phát trước, sử dụng kích thước phần thay đổi

Ưu điểm:

§ Cho phép truy cập trực tiếp và tuần tự

§ Đơn giản, tốc độ cao

Nhược điểm:

§ Phải biết trước kích thước file khi tạo

§ Khó tìm chỗ cho file

§ Gây phân mảnh ngoài:

Câu hỏi 4.10 :

a)    Trình bày phương pháp sử dụng danh sách kết nối trên bảng chỉ số khi cấp phát không gian cho file.

Bảng chỉ số: mỗi ô của bảng ứng với 1 khối của đĩa

Con trỏ tới khối tiếp theo của file được chứa trong ô tương ứng của bảng

Mỗi đĩa logic có 1 bảng chỉ số được lưu ở vị trí xác định

Kích thước mỗi ô trên bảng phụ thuộc vào số lượng khối trên đĩa

Cho phép tiến hành truy cập file trực tiếp: đi theo chuỗi con trỏ chứa trong bảng chỉ mục

Bảng FAT (File Allocation Table): được lưu ở đầu mỗi đĩa logic sau sector khởi động FAT12, FAT16, FAT32: mỗi ô của bảng có kích thước 12,16, 32 bit