[HDH] Bài tập quản lí bộ nhớ first fit, work fit, best fit

[11520139]

Đề bài:
Giả sử bộ nhớ chính được phân thành các phân vùng có kích thước là 600K, 500K, 200K, 300K ( theo thứ tự ), cho biết các tiến trình có kích thước 212K,
417K, 112K và 426K ( theo thứ tự ) sẽ được cấp phát bộ nhớ như thế nào, nếu sử dụng :
a) Thuật toán First fit
b) Thuật toán Best fit
c) Thuật toán Worst fit
Thuật toán nào cho phép sử dụng bộ nhớ hiệu qủa nhất trong trường hợp trên ?
Cho mình hỏi thử là làm cái bài tập quản lí bộ nhớ này thì làm như thế nào là đúng theo 3 cách sau đây:

cách 1: (cách này tìm thấy trên google )
a. First fit:
212k được cấp phát vùng nhớ 600K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 388K(vùng nhđược tạo thành sau khi cấp phát cho tiến trình 212K, 600K-212K=388K)
426K phải chờ, vì không còn vùng nhớ trống thỏa yêu cầu
b. Best fit:
212K được cấp phát vùng nhớ 300K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 200K
426K được cấp phát vùng nhớ 600K
c. Worst fit:
212K được cấp phát vùng nhớ 600K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 300K
426 phải đợi, do không còn vùng nhớ trống thỏa yêu cầu

cách 2:
(cách này hôm bữa thấy có người lên chữa mà thầy lung bảo đúng rồi)
a. First fit:
212k được cấp phát vùng nhớ 600K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 200k
426K phải chờ, vì không còn vùng nhớ trống thỏa yêu cầu
b. Best fit:
212K được cấp phát vùng nhớ 300K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 200K
426K được cấp phát vùng nhớ 600K
c. Worst fit:
212K được cấp phát vùng nhớ 600K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 300K
426 phải đợi, do không còn vùng nhớ trống thỏa yêu cầu

cách 3: (cách này do thầy Lương Ngọc Khánh chữa bài)
a. First fit:
212k được cấp phát vùng nhớ 600K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 388K(vùng nhđược tạo thành sau khi cấp phát cho tiến trình 212K, 600K-212K=388K)
426K phải chờ, vì không còn vùng nhớ trống thỏa yêu cầu
b. Best fit:
212K được cấp phát vùng nhớ 300K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 200K
426K được cấp phát vùng nhớ 600K
c. Worst fit:
212K được cấp phát vùng nhớ 600K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 388K(vùng nhớ được tạo thành sau khi cấp phát cho tiến trình 212K, 600K-212K=388K)
426 phải đợi, do không còn vùng nhớ trống thỏa yêu cầu
Ai biết giúp đỡ với nha chuẩn bị thi rồi

[08520018]

em học thầy nào thì làm theo cách của thầy đó đi em.....^^!!

[10520566]

Nhớ lần trước học hệ điều hành thầy nói là chỉ ra 3 dạng bài thôi, tới lúc thi thì 4 dạng, trong đó có 2 dạng lạ hoắc :stick:

[11520537]

hèm hèm, cẩn than nhầm Fist fit với Next fit nha, First là duyệt từ đầu bộ nhớ, gặp phân đoạn nào lớn hơn hoặc bang yêu cầu thì dừng lại và lấy luôn, Next fit là duyệt từ vị trí đã cấp phát trước đó, gặp phân đoạn nào lớn hơn hoặc bang yêu cầu thì dừng lại và lấy luôn, còn về Worst fit thì duyệt từ đầu bộ nhớ cho đến hết xem cái nào lớn nhất mà chứa được theo yêu cầu thì hốt luôn, như thế thì cách của thầy Lương Ngọc Khánh là đúng. Ủng hộ thầy Khánh nào, dù biết về mặt rắn thì chỉ có đứng sau thầy Khải ở khoa KTMT thôi, mà giờ thầy Khải đi học tiến sĩ rồi, thì Khánh tiên sinh là giảng viên nguy hiểm nhất của khoa:sogood:

p/s: đừng chém em nha mấy anh ở khoa KTMT

[11520549]

hèm hèm, cẩn than nhầm Fist fit với Next fit nha, First là duyệt từ đầu bộ nhớ, gặp phân đoạn nào lớn hơn hoặc bang yêu cầu thì dừng lại và lấy luôn, Next fit là duyệt từ vị trí đã cấp phát trước đó, gặp phân đoạn nào lớn hơn hoặc bang yêu cầu thì dừng lại và lấy luôn, còn về Worst fit thì duyệt từ đầu bộ nhớ cho đến hết xem cái nào lớn nhất mà chứa được theo yêu cầu thì hốt luôn, như thế thì cách của thầy Lương Ngọc Khánh là đúng. Ủng hộ thầy Khánh nào, dù biết về mặt rắn thì chỉ có đứng sau thầy Khải ở khoa KTMT thôi, mà giờ thầy Khải đi học tiến sĩ rồi, thì Khánh tiên sinh là giảng viên nguy hiểm nhất của khoa:sogood:

p/s: đừng chém em nha mấy anh ở khoa KTMT

có sự nhầm lẫn giữa phân trang và phân đoạn.

[11520317]

Đề bài:
Giả sử bộ nhớ chính được phân thành các phân vùng có kích thước là 600K, 500K, 200K, 300K ( theo thứ tự ), cho biết các tiến trình có kích thước 212K,
417K, 112K và 426K ( theo thứ tự ) sẽ được cấp phát bộ nhớ như thế nào, nếu sử dụng :
a) Thuật toán First fit
b) Thuật toán Best fit
c) Thuật toán Worst fit
Thuật toán nào cho phép sử dụng bộ nhớ hiệu qủa nhất trong trường hợp trên ?
Cho mình hỏi thử là làm cái bài tập quản lí bộ nhớ này thì làm như thế nào là đúng theo 3 cách sau đây:

cách 1: (cách này tìm thấy trên google )
a. First fit:
212k được cấp phát vùng nhớ 600K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 388K(vùng nhđược tạo thành sau khi cấp phát cho tiến trình 212K, 600K-212K=388K)
426K phải chờ, vì không còn vùng nhớ trống thỏa yêu cầu
b. Best fit:
212K được cấp phát vùng nhớ 300K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 200K
426K được cấp phát vùng nhớ 600K
c. Worst fit:
212K được cấp phát vùng nhớ 600K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 300K
426 phải đợi, do không còn vùng nhớ trống thỏa yêu cầu

cách 2:
(cách này hôm bữa thấy có người lên chữa mà thầy lung bảo đúng rồi)
a. First fit:
212k được cấp phát vùng nhớ 600K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 200k
426K phải chờ, vì không còn vùng nhớ trống thỏa yêu cầu
b. Best fit:
212K được cấp phát vùng nhớ 300K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 200K
426K được cấp phát vùng nhớ 600K
c. Worst fit:
212K được cấp phát vùng nhớ 600K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 300K
426 phải đợi, do không còn vùng nhớ trống thỏa yêu cầu

cách 3: (cách này do thầy Lương Ngọc Khánh chữa bài)
a. First fit:
212k được cấp phát vùng nhớ 600K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 388K(vùng nhđược tạo thành sau khi cấp phát cho tiến trình 212K, 600K-212K=388K)
426K phải chờ, vì không còn vùng nhớ trống thỏa yêu cầu
b. Best fit:
212K được cấp phát vùng nhớ 300K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 200K
426K được cấp phát vùng nhớ 600K
c. Worst fit:
212K được cấp phát vùng nhớ 600K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 388K(vùng nhớ được tạo thành sau khi cấp phát cho tiến trình 212K, 600K-212K=388K)
426 phải đợi, do không còn vùng nhớ trống thỏa yêu cầu
Ai biết giúp đỡ với nha chuẩn bị thi rồi

Theo mình, cách của Thầy Lung là chuẩn nhất. Một vùng nhớ đã được cấp phát dành cho 1 P thì sẽ không cho phép 1 P khác "chui" vào nữa. :doubt:

[11520537]

có sự nhầm lẫn giữa phân trang và phân đoạn.

thế mi nghĩ đây là phân trang hay phân đoạn? với tau thì là phân đoạn.

[11520537]

Theo mình, cách của Thầy Lung là chuẩn nhất. Một vùng nhớ đã được cấp phát dành cho 1 P thì sẽ không cho phép 1 P khác "chui" vào nữa. :doubt:

thế sinh ra cơ chế kết khối để làm cảnh à, khi một khối nhớ đã cấp phát cho một tiến trình mà còn dư, nếu có một vài cái thì không sao, nhưng nếu nhiều thì hệ điều hành sẽ tiến hành gom các phần còn trống lại để đủ cấp cho tiến tình khác.

[11520215]

cùng thắc mắc với Hướng....

[11520317]

thế sinh ra cơ chế kết khối để làm cảnh à, khi một khối nhớ đã cấp phát cho một tiến trình mà còn dư, nếu có một vài cái thì không sao, nhưng nếu nhiều thì hệ điều hành sẽ tiến hành gom các phần còn trống lại để đủ cấp cho tiến tình khác.

Nếu theo bạn thì bài giải này có mâu thuẫn ??? Nếu mà có cơ chế kết khối ở đây thì 426K vẫn phải đợi ???

cách 3: (cách này do thầy Lương Ngọc Khánh chữa bài)
a. First fit:
212k được cấp phát vùng nhớ 600K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 388K(vùng nhđược tạo thành sau khi cấp phát cho tiến trình 212K, 600K-212K=388K)
426K phải chờ, vì không còn vùng nhớ trống thỏa yêu cầu
c. Worst fit:
212K được cấp phát vùng nhớ 600K
417K được cấp phát vùng nhớ 500K
112K được cấp phát vùng nhớ 388K(vùng nhớ được tạo thành sau khi cấp phát cho tiến trình 212K, 600K-212K=388K)
426 phải đợi, do không còn vùng nhớ trống thỏa yêu cầu

Tập hợp các lỗ trống được tìm thấy để xác định lỗ nào là tốt nhất để cấp phát. Các chiến lược first-fit, best-fit, worst-fit là những chiến lược phổ biến nhất được dùng để chọn một lỗ trống từ tập hợp các lỗ trống.

First-fit: cấp phát lỗ trống đầu tiên đủ lớn. Tìm kiếm có thể bắt đầu tại đầu tập hợp các lỗ trống hay tại điểm kết thúc của tìm kiếm first-fit trước đó. Chúng ta dừng tìm kiếm ngay khi chúng ta tìm thấy một lỗ trống đủ lớn.
Best-fit: cấp phát lỗ trống nhỏ nhất đủ lớn. Chúng ta phải tìm toàn bộ danh sách, trừ khi danh sách được xếp thứ tự theo kích thước. Chiến lược này tạo ra lỗ trống nhỏ nhất còn thừa lại.
Worst-fit: cấp phát lỗ trống lớn nhất. Chúng ta phải tìm toàn danh sách trừ khi nó được xếp theo thứ tự kích thước. Chiến lược này tạo ra lỗ trống còn lại lớn nhất mà có thể có ích hơn lỗ trống nhỏ từ tiếp cận best-fit.
Các mô phỏng hiển thị rằng cả first-fit và best-fit là tốt hơn worst-fit về việc giảm thời gian và sử dụng lưu trữ. Giữa first-fit và best-fit không thể xác định rõ chiến lược nào tốt hơn về sử dụng lưu trữ, nhưng first-fit có tốc độ nhanh hơn.

Tuy nhiên, các giải thuật này gặp phải vấn đề phân mãnh ngoài (external fragmentation). Khi các quá trình được nạp và được xoá khỏi bộ nhớ, không gian bộ nhớ trống bị phân rã thành những mãnh nhỏ. Phân mãnh ngoài tồn tại khi tổng không gian bộ nhớ đủ để thoả mãn một yêu cầu, nhưng nó không liên tục; vùng lưu trữ bị phân mãnh thành một số lượng lớn các lỗ nhỏ. Vấn đề phân mãnh này có thể rất lớn. Trong trường hợp xấu nhất, chúng có thể có một khối bộ nhớ trống nằm giữa mỗi hai quá trình. Nếu tất cả bộ nhớ này nằm trong một khối trống lớn, chúng ta có thể chạy nhiều quá trình hơn.

Chọn lựa first-fit so với best-fit có thể ảnh hưởng tới lượng phân mãnh. (First-fit là tốt hơn đối với một số hệ thống, ngược lại best fit là tốt hơn cho một số hệ thống khác). Một yếu tố khác là phần cuối của khối trống nào được cấp phát. (phần còn dư nào-phần trên đỉnh, hay phần ở dưới đáy?). Vấn đề không do giải thuật nào được dùng mà do phân mãnh ngoài.

Đây là chiến lược Placement.

[11520139]

Tập hợp các lỗ trống được tìm thấy để xác định lỗ nào là tốt nhất để cấp phát. Các chiến lược first-fit, best-fit, worst-fit là những chiến lược phổ biến nhất được dùng để chọn một lỗ trống từ tập hợp các lỗ trống.

First-fit: cấp phát lỗ trống đầu tiên đủ lớn. Tìm kiếm có thể bắt đầu tại đầu tập hợp các lỗ trống hay tại điểm kết thúc của tìm kiếm first-fit trước đó. Chúng ta dừng tìm kiếm ngay khi chúng ta tìm thấy một lỗ trống đủ lớn.
Best-fit: cấp phát lỗ trống nhỏ nhất đủ lớn. Chúng ta phải tìm toàn bộ danh sách, trừ khi danh sách được xếp thứ tự theo kích thước. Chiến lược này tạo ra lỗ trống nhỏ nhất còn thừa lại.
Worst-fit: cấp phát lỗ trống lớn nhất. Chúng ta phải tìm toàn danh sách trừ khi nó được xếp theo thứ tự kích thước. Chiến lược này tạo ra lỗ trống còn lại lớn nhất mà có thể có ích hơn lỗ trống nhỏ từ tiếp cận best-fit.
Các mô phỏng hiển thị rằng cả first-fit và best-fit là tốt hơn worst-fit về việc giảm thời gian và sử dụng lưu trữ. Giữa first-fit và best-fit không thể xác định rõ chiến lược nào tốt hơn về sử dụng lưu trữ, nhưng first-fit có tốc độ nhanh hơn.

Tuy nhiên, các giải thuật này gặp phải vấn đề phân mãnh ngoài (external fragmentation). Khi các quá trình được nạp và được xoá khỏi bộ nhớ, không gian bộ nhớ trống bị phân rã thành những mãnh nhỏ. Phân mãnh ngoài tồn tại khi tổng không gian bộ nhớ đủ để thoả mãn một yêu cầu, nhưng nó không liên tục; vùng lưu trữ bị phân mãnh thành một số lượng lớn các lỗ nhỏ. Vấn đề phân mãnh này có thể rất lớn. Trong trường hợp xấu nhất, chúng có thể có một khối bộ nhớ trống nằm giữa mỗi hai quá trình. Nếu tất cả bộ nhớ này nằm trong một khối trống lớn, chúng ta có thể chạy nhiều quá trình hơn.

Chọn lựa first-fit so với best-fit có thể ảnh hưởng tới lượng phân mãnh. (First-fit là tốt hơn đối với một số hệ thống, ngược lại best fit là tốt hơn cho một số hệ thống khác). Một yếu tố khác là phần cuối của khối trống nào được cấp phát. (phần còn dư nào-phần trên đỉnh, hay phần ở dưới đáy?). Vấn đề không do giải thuật nào được dùng mà do phân mãnh ngoài.

Đây là chiến lược Placement.

cuối cùng là ông đứng về bên nào đây? ai biết ông làm như thế nào đâu???

[11520317]

cuối cùng là ông đứng về bên nào đây? ai biết ông làm như thế nào đâu???

Theo mình, cách của Thầy Lung là chuẩn nhất. Một vùng nhớ đã được cấp phát dành cho 1 P thì sẽ không cho phép 1 P khác "chui" vào nữa.

Tất nhiên là thầy Lung à bạn.

[11520537]

cuối cùng là ông đứng về bên nào đây? ai biết ông làm như thế nào đâu???

tau cũng nghĩ thế, Qúy Huynh đệ copy ở đâu cái đoạn đó rồi paste vào đây không biết để làm gì? Nó lại vấp phải cái dòng định nghĩa First fit, nó gom cả Next fit vào First fit, hai cái này chỉ khác nhau ở địa điểm duyệt đầu tiên. Không biết thế nào nhưng trong các sách mình đọc thì Next fit đứng độc lập với First fit. Tiêu biểu là tài liệu của Lung tiên sinh.

[11520317]

tau cũng nghĩ thế, Qúy Huynh đệ copy ở đâu cái đoạn đó rồi paste vào đây không biết để làm gì? Nó lại vấp phải cái dòng định nghĩa First fit, nó gom cả Next fit vào First fit, hai cái này chỉ khác nhau ở địa điểm duyệt đầu tiên. Không biết thế nào nhưng trong các sách mình đọc thì Next fit đứng độc lập với First fit. Tiêu biểu là tài liệu của Lung tiên sinh.

Bạn có thể xem lại post mình đã UPDATE, rồi có gì trao đổi... Còn đáp án của 2 sự khác nhau đó thì .... chỉ có 2 thầy mới biết

[11520537]

Tất nhiên là thầy Lung à bạn.

nè, cái bài làm đó là sinh viên làm chứ không phải thầy Lung làm nha. Về chuyện cái vùng nhớ thì bạn nên xem lại, vùng nhớ đó không phải cố định đâu, đầu tiên nó tìm vùng nhớ đạt yêu cầu thì nhảy vô, nếu vùng nhớ đó dư thì ngay chính đó sẽ hình thành một vùng nhớ mới có dung lượng bang dung lượng ban đầu trừ cho dung lượng của tiến trình.