[HDH] Bài Tập Quản Lí Bộ Nhớ First Fit, Work Fit, Best Fit - UIT - Forum

Có thể bạn quan tâm

Forum
Góc học tập
Kỹ thuật máy tính

If this is your first visit, be sure to check out the FAQ by clicking the link above. You may have to register before you can post: click the register link above to proceed. To start viewing messages, select the forum that you want to visit from the selection below.

Announcement Collapse No announcement yet. [HDH] Bài tập quản lí bộ nhớ first fit, work fit, best fit Collapse X Collapse

Posts
Latest Activity
Photos

Search
Page of 3
Filter

Time All Time Today Last Week Last Month
Show All Discussions only Photos only Videos only Links only Polls only Events only

Filtered by: Clear All new posts Previous 1 2 3 template Next

11520139 Nguyễn Văn Hướng
- Join Date: Aug 2011
- Posts: 325
- Share
- Tweet
#1
[HDH] Bài tập quản lí bộ nhớ first fit, work fit, best fit
29-12-2012, 12:18 Đề 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 Last edited by 11520139; 29-12-2012, 12:21. :love:Tương lai khóc hay cười phụ thuộc vào độ lười của quá khứ. :cry: Tags: None
08520018 Nguyễn Duy Anh
- Join Date: May 2011
- Posts: 75
- Share
- Tweet
#2 29-12-2012, 12:34 em học thầy nào thì làm theo cách của thầy đó đi em.....^^!!
Comment
Post Cancel
10520566 Nguyễn Thế Anh
- Join Date: May 2011
- Posts: 599
- Share
- Tweet
#3 29-12-2012, 12:58 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:
Comment
Post Cancel
11520537 Trần Đại Dương
- Join Date: Sep 2011
- Posts: 2016
- Share
- Tweet
#4 29-12-2012, 13:17 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 Tôi không hối tiếc những gì mình đã làm. Tôi chỉ hối tiếc những gì đã không làm khi có cơ hội!
Comment
Post Cancel
11520549 Ngô Văn Hào
- Join Date: Sep 2011
- Posts: 540
- Share
- Tweet
#5 29-12-2012, 13:53 Originally posted by 11520537 View Post 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. Last edited by 11520549; 29-12-2012, 14:17.
Comment
Post Cancel
11520317 Nguyễn Nam Quý
- Join Date: Aug 2011
- Posts: 348
- Share
- Tweet
#6 29-12-2012, 14:11 Originally posted by 11520139 View Post Đề 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: Top Best Online - The Best Products Review Website
Comment
Post Cancel
11520537 Trần Đại Dương
- Join Date: Sep 2011
- Posts: 2016
- Share
- Tweet
#7 29-12-2012, 14:21 Originally posted by 11520549 View Post 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. Tôi không hối tiếc những gì mình đã làm. Tôi chỉ hối tiếc những gì đã không làm khi có cơ hội!
Comment
Post Cancel
11520537 Trần Đại Dương
- Join Date: Sep 2011
- Posts: 2016
- Share
- Tweet
#8 29-12-2012, 14:30 Originally posted by 11520317 View Post 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. Last edited by 11520537; 29-12-2012, 14:36. Tôi không hối tiếc những gì mình đã làm. Tôi chỉ hối tiếc những gì đã không làm khi có cơ hội!
Comment
Post Cancel
11520215 Phạm Tấn Lộc
- Join Date: Aug 2011
- Posts: 250
- Share
- Tweet
#9 29-12-2012, 16:38 cùng thắc mắc với Hướng.... Last edited by 11520215; 29-12-2012, 16:49.
Comment
Post Cancel
11520317 Nguyễn Nam Quý
- Join Date: Aug 2011
- Posts: 348
- Share
- Tweet
#10 29-12-2012, 17:48 Originally posted by 11520537 View Post 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. Last edited by 11520317; 29-12-2012, 18:02. Top Best Online - The Best Products Review Website
Comment
Post Cancel
11520139 Nguyễn Văn Hướng
- Join Date: Aug 2011
- Posts: 325
- Share
- Tweet
#11 29-12-2012, 17:53 Originally posted by 11520317 View Post 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??? :love:Tương lai khóc hay cười phụ thuộc vào độ lười của quá khứ. :cry:
Comment
Post Cancel
11520317 Nguyễn Nam Quý
- Join Date: Aug 2011
- Posts: 348
- Share
- Tweet
#12 29-12-2012, 18:00 Originally posted by 11520139 View Post 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. Top Best Online - The Best Products Review Website
Comment
Post Cancel
11520537 Trần Đại Dương
- Join Date: Sep 2011
- Posts: 2016
- Share
- Tweet
#13 29-12-2012, 18:01 Originally posted by 11520139 View Post 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. Tôi không hối tiếc những gì mình đã làm. Tôi chỉ hối tiếc những gì đã không làm khi có cơ hội!
Comment
Post Cancel
11520317 Nguyễn Nam Quý
- Join Date: Aug 2011
- Posts: 348
- Share
- Tweet
#14 29-12-2012, 18:06 Originally posted by 11520537 View Post 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 Top Best Online - The Best Products Review Website
Comment
Post Cancel
11520537 Trần Đại Dương
- Join Date: Sep 2011
- Posts: 2016
- Share
- Tweet
#15 29-12-2012, 18:06 Originally posted by 11520317 View Post 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. Tôi không hối tiếc những gì mình đã làm. Tôi chỉ hối tiếc những gì đã không làm khi có cơ hội!
Comment
Post Cancel