Đề tài Cấu trúc SWAP trên Unix

Bộ nhớ là tài nguyên quan trọng của hệ thống tính toán (hệ thống) nên cần phải được quản lý một cách chặt chẽ. Mặc dù ngày nay, những chiếc máy tính để bàn thông thường có bộ nhớ lớn hơn rất nhiều so với “siêu máy tính” những năm 60 như IBM 7094, nhưng như chúng ta đã biết, các chương trình thường phát triển nhanh hơn rất nhiều so với bộ nhớ. Vì vậy việc quản lý bộ nhớ không bao giờ được phép xem nhẹ. Trong trường hợp lý tưởng, tất cả những gì các chương trình cần về bộ nhớ đó là không gian rộng, truy cập nhanh và không bị mất thông tin trong trường hợp bị mất điện. Điều đó là có thể làm được, nhưng chi phí phải trả cho bộ nhớ lý tưởng đó là quá đắt. Bởi vậy, hầu hết các máy tính đều có một hệ đẳng cấp bộ nhớ. Hệ này thường chia bộ nhớ thành ba loại: một là cache memory với dung lượng nhỏ, chỉ khoảng vài trăm KB đến vài MB nhưng có tốc độ rất nhanh; hai là RAM (Random Access Memory), đây là phần chính của bộ nhớ, có tốc độ trung bình và dung lượng trung bình từ vài chục MB đến vài GB; ba là đĩa cứng với dung lượng có thể lên rất lớn nhưng tốc độ chậm. Công việc của hệ điều hành là phải sử dụng sao cho có hiệu quả nhất những loại bộ nhớ này. Trong bài báo cáo này, em xin trình bày về cơ chế Swapping trong quản lý bộ nhớ của các hệ điều hành Unix. Đây là một cơ chế hợp lý để khắc phục nhược điểm hạn chế về dung lượng của bộ nhớ chính bằng cách sử dụng đĩa cứng làm bộ nhớ phụ trợ.

doc15 trang | Chia sẻ: tuandn | Ngày: 25/05/2013 | Lượt xem: 1734 | Lượt tải: 3download
Bạn đang xem nội dung tài liệu Đề tài Cấu trúc SWAP trên Unix, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ──────── * ─────── BÀI TẬP LỚN MÔN: HỆ ĐIỀU HÀNH Đề tài : Cấu trúc swap trên Unix Sinh viên thực hiện : Đỗ Đức Đông        20070793 Vũ Việt Dũng       20070626               Bùi Vũ Hải           20070984  Đỗ Hoài Nam        20072001   Lớp : HTTT – K52 Giáo viên hướng dẫn : Đỗ Tuấn Anh Hà Nội, tháng 5 năm 2010 MỤC LỤC I. Giới thiệu chung về Swapping…………………………………..………………...….……..……..2 1.1 Giới thiệu chung………………………………..……………………….….…………….2 1.2 Hệ điều hành UNIX…………………………………………………..….…….…………2 1.3 Sơ lược về Swapping…………………………………………….……...…….….………2 II. Quản lí không gian trên Swap device……………….………………..………….…….…….……3 III. Swap một tiến trình ra ngoài…………………………………………………….…..…….……..6 IV. Swap một tiến trình vào…………………………………………………….……….…..………..9 4.1 Swapper……………………………………………………………….….…….……….9 4.2 Giải thuật Swapping………………………………………………..….………………..9 4.3 Thiếu sót của giải thuật……………………………...……………...…….….………...13 V. Kết luận………………………………………………………………………………………......14 I. Giới thiệu về Swapping 1.1 Giới thiệu chung Bộ nhớ là tài nguyên quan trọng của hệ thống tính toán (hệ thống) nên cần phải được quản lý một cách chặt chẽ. Mặc dù ngày nay, những chiếc máy tính để bàn thông thường có bộ nhớ lớn hơn rất nhiều so với “siêu máy tính” những năm 60 như IBM 7094, nhưng như chúng ta đã biết, các chương trình thường phát triển nhanh hơn rất nhiều so với bộ nhớ. Vì vậy việc quản lý bộ nhớ không bao giờ được phép xem nhẹ. Trong trường hợp lý tưởng, tất cả những gì các chương trình cần về bộ nhớ đó là không gian rộng, truy cập nhanh và không bị mất thông tin trong trường hợp bị mất điện. Điều đó là có thể làm được, nhưng chi phí phải trả cho bộ nhớ lý tưởng đó là quá đắt. Bởi vậy, hầu hết các máy tính đều có một hệ đẳng cấp bộ nhớ. Hệ này thường chia bộ nhớ thành ba loại: một là cache memory với dung lượng nhỏ, chỉ khoảng vài trăm KB đến vài MB nhưng có tốc độ rất nhanh; hai là RAM (Random Access Memory), đây là phần chính của bộ nhớ, có tốc độ trung bình và dung lượng trung bình từ vài chục MB đến vài GB; ba là đĩa cứng với dung lượng có thể lên rất lớn nhưng tốc độ chậm. Công việc của hệ điều hành là phải sử dụng sao cho có hiệu quả nhất những loại bộ nhớ này. Trong bài báo cáo này, em xin trình bày về cơ chế Swapping trong quản lý bộ nhớ của các hệ điều hành Unix. Đây là một cơ chế hợp lý để khắc phục nhược điểm hạn chế về dung lượng của bộ nhớ chính bằng cách sử dụng đĩa cứng làm bộ nhớ phụ trợ. 1.2 Hệ điều hành UNIX Unix hay UNIX là một hệ điều hành máy tính viết vào những năm 1960 và 1970 do một số nhân viên của công ty AT&T Bell Labs bao gồm Ken Thompson, Dennis Ritchie và Douglas McIlroy. Ngày nay hệ điều hành Unix được phân ra thành nhiều nhánh khác nhau, nhánh của AT&T, nhánh của một số nhà phân phối thương mại và nhánh của những tổ chức phi lợi nhuận. Unix có thể chạy trên nhiều loại máy tính khác nhau, từ những máy tính cá nhân cho đến các máy chủ dịch vụ. Nó là một hệ điều hành đa nhiệm (có thể cùng lúc thực hiện nhiều nhiệm vụ) hỗ trợ một cách lý tưởng đối với các ứng dụng nhiều người dùng. Unix được viết bằng ngôn ngữ lập trình C, một ngôn ngữ rất mạnh và mềm dẻo. Unix hỗ trợ các ứng dụng mạng và hỗ trợ nhiều môi trường lập trình khác nhau. Với hàng trăm lệnh và một số lượng rất lớn các tùy chọn, Unix thực sự là một khó khăn đối với người mới bắt đầu. Với sự phát triển của các shell Unix hệ điều hành này đã trở nên phổ dụng hơn trong lĩnh vực điện toán. Vì Bell Laboratories bị cấm không cho phép tiếp thị Unix vì lệnh chống độc quyền đối với AT & T nên Unix đã được cung cấp miễn phí cho các trường đại học trên toàn Bắc Mỹ từ năm 1976. Năm 1979 Đại học California tại Berkeley đã xây dựng một phiên bản của Unix dùng cho các máy tính VAX. Sau khi đã được ưa thích trong các lĩnh vực công nghệ, AT & T đã dành được quyền tiếp thị đối với Unix và đã cho ra đời System V vào năm 1983. Cho đên nay Unix vẫn được sử dụng rất rộng rãi trong thị trường dành cho máy chủ. Đã có nhiều phiên bản phát triển khác nhau, trong đó có Linux. Hiện nay Unix được sử dụng bởi nhiều công ty tập đoàn lớn trên thế giới vì mức độ bảo mật của nó tương đối cao. 1.3 Sơ lược về Swapping Trong lịch sử, hệ điều hành UNIX sẽ luân chuyển toàn bộ các tiến trình giữa bộ nhớ chính và không gian swap, chứ không phải truyền chỉ 1 phần của tiến trình, trừ những đoạn thông tin liên lạc. Một cách quản lý bộ nhớ như vậy được được gọi là swapping. Hệ thống BSD (phiên bản 4.0) đã cho giới thiệu lần đầu tiên kế hoạch demand paging, chuyển một trang nhớ thay vì chỉ chuyển các tiến trình qua một bộ nhớ thứ cấp; phiên bản gần đây mới ra của UNIX System V cũng hỗ trợ đòi hỏi phân trang. Toàn bộ tiến trình sẽ không phải lưu vào bộ nhớ chính khi thực hiện, trung tâm xử lý (kernel) sẽ gọi các trang cần cho 1 tiến trình theo yêu cầu khi nào tiến trình tham chiếu tới các trang đó. Ưu điểm của phương pháp phân trang là nó cho phép đơn giản hoá việc sắp đặt các không gian bộ nhớ ảo của 1 tiến trình vào bộ nhớ vật lý trong máy tính, thường cho phép một không gian có kích cỡ lớn hơn kích cỡ của bộ nhớ vật lý và cho phép hơn 1 tiến trình được chạy đồng bộ trong main memory. Ưu điểm của swapping là nó làm đơn giản hoá và làm một hệ thống đỡ bị nặng nề. Để trình bày về thuật toán swapping chúng ta quan tâm đến 3 thành phần sau : +Quản lí không gian nhớ trên swap devices. +Quá trình swapping ra ngoài bộ nhớ chính. +Quá trình swapping vào bộ nhớ chính. II. Quản lí không gian trên swap device Biểu đồ định địa chỉ của 1 công cụ swap khác với biểu đồ định chỉ của hệ thống file, cấu trúc dữ liệu để liệt kê các vùng trống cũng khác nhau. Kernel lưu trữ các vùng trống trong các hệ thống file bằng một danh sách móc nối của các khối trống, có thể truy cập được từ một hệ thống file lớn, nhưng chúng lại lưu trữ các không gian trống của công cụ swap bằng 1 loại bảng, gọi là map. Maps, được dùng trong một số tài nguyên khác bên cạnh công cụ swap (như là device drivers chẳng hạn), sẽ dùng cách định địa chỉ first-fit cho các khối liên tục của một tài nguyên. Một map là một mảng mà ở đó mỗi entry có một địa chỉ bắt đầu của một tài nguyên và số lượng đơn vị tài nguyên sẵn có; Kernel sẽ thông dịch địa chỉ và đơn vị tùy theo loại map. Ban đầu, một map kèm theo 1 entry mà trong đó chứa địa chỉ và tổng số các tài nguyên. Kernel sẽ xử lí mỗi đơn vị của 1 swap map như một nhóm của những khối đĩa, và nó xử lí địa chỉ như là một độ lệch khối so với điểm bắt đầu của khu vực swap. Hình 1 mô tả 1 khởi tạo swap map của 10000 khối bắt đầu bởi địa chỉ 1. Address Units 1 10000 Hình 1: Khởi tạo Swap Map Thuật toán malloc Input: (1): Địa chỉ map (2): Đơn vị tài nguyên yêu cầu Output: địa chỉ, nếu thành công. 0, nếu trái lại { For(mỗi entry trong map) { If(map hiện tại có thể cung cấp đủ số tài nguyên yêu cầu) { If(số tài nguyên yêu cầu==số tài nguyên trên entry) xóa entry; Else cập nhật lại địa chỉ bắt đầu của entry; return (dịa chỉ ban đầu entry); } } return(0); } Hình 2: Giải thuật cấp phát không gian từ Map. Khi kenel cấp phát và giải phóng những tài nguyên , nó cập nhật map vì vậy nó tiếp tục chứa những thông tin chính xác về những tài nguyên trống. Hình 2 đưa ra giải thuật malloc để cấp phát không gian từ Map. Kernel sẽ tìm ra trên map entry đầu tiên có đủ khoảng trống để thỏa mãn yêu cầu. Nếu yêu cầu có chứa tất cả tài nguyên của map entry, kernel sẽ xóa entry ra khỏi mảng và giảm kích thước của map. Còn nếu khác, chúng sẽ chỉnh lại địa chỉ và trường đơn vị của entry tùy theo số tài nguyên cần được cấp phát. Ta có một ví dụ như sau: Khởi tạo Map: Address Units 1 10000 Cấp phát 100 Units: Address Units 101 9900 Cấp phát 50 Units: Address Units 151 9850 Cấp phát 100 Units: Address Units 251 9750 Khi giải phóng tài nguyên, kernel tìm ra vị trí chính xác trên bản đồ bởi địa chỉ Các trường hợp có thể xảy ra: + Khi tài nguyên được giải phóng chỉ lấp đầy một phần của lỗ trong map nhưng không tiếp giáp với một entry nào trong map. Kenel sẽ tạo một entry mới và đặt nó vào vị trí thích hợp trên map. Ví dụ: Khi giải phóng 50 units bắt đầu từ địa chỉ 101 Address Units 251 9750 Map trước giải phóng 101 50 251 9750 Map sau khi giải phóng + Khi tài nguyên được giải phóng chỉ lấp đầy một phần lỗ trong map. Nếu tài nguyên trống tiếp giáp với entry mà ngay trước hoặc ngay sau(nhưng không phải cả hai) thì kenel sẽ sửa chữa trường địa chỉ và Units của entry thích hợp để giải phóng tài nguyên. Số lượng entry không thay đổi. Ví dụ: Khi giải phóng 100 units bắt đầu từ 1 101 50 251 9750 Trước khi giải phóng 1 150 251 9750 Sau khi giải phóng + Khi tài nguyên được giải phóng lấp đầy một lỗ trên map, chúng tiếp giáp với những entry có địa chỉ mà đứng ngay trước và ngay sau chúng trong map. Trong trường hợp này, kenel sẽ kết hợp tài nguyên đã giải phóng và hai entry trên thành một entry trong map. Ví dụ: Khi cấp phát 200 units, sau đó giải phóng 300 units 1 150 251 9750 Trước khi cấp phát 1 150 451 9750 Sau khi cấp phát 200 units Do entry đầu không đủ 200 units nên nó sẽ cấp phát từ entry sau. 1 10000 Sau khi giải phóng 300 units Phiên bản truyền thống của hệ thống UNIX sử dụng 1 công cụ swap, nhưng phiên bản gần đây nhất của System V cho phép có nhiều công cụ swap. Kernel sẽ chọn lựa công cụ swap theo một lược đồ hình tròn, cung cấp cho nó một nguồn bộ nhớ liền kề. Người quản lý có thể tạo và xoá công cụ swap một cách tự động. Nếu 1 công cụ bị xoá, kernel sẽ ko swap dữ liệu lên chúng nữa; nếu dữ liệu đã được swap từ nó, nó sẽ bị đổ ra cho đến khi là trống và được xoá đi. III. Swap một tiến trình ra ngoài Kernel swap các tiến trình ra bên ngoài nếu nó cần không gian trong bộ nhớ, điều này có thể dẫn từ bất kì điều gì sau đây: Các lệnh gọi hệ thống fork phải cấp phát không gian cho các tiến trình con. Các lệnh gọi hệ thống brk tăng kích thước của tiến trình. Tiến trình trở nên lớn hơn bởi sự phát triển tự nhiên do các stack của nó. Kernel muốn giải phóng không gian trong bộ nhớ cho các tiến trình nó đã swap out trước đó và bây giờ cần swap in. Trường hợp của fork nổi bật lên, bởi vì nó là trường hợp duy nhất mà bộ nhớ lõi bên trong đã bị sở hữu trước đó bởi các tiến trình không bị bỏ đi. Khi kernel quyết định một tiến trình được chọn để swapping từ bộ nhớ chính: Nó giảm biến đếm tham chiếu của mỗi miền trong tiến trình và swap miền ra ngoài khi tham chiếu của nó giảm bằng 0. Kenel cấp phát không gian trên swap device. Khóa những tiến trình trong bộ nhớ ( cho những trường hợp 1-3) để ngăn cản swapper swap nó ra ngoài trong khi quá trình swap đang diễn ra. Kenel lưu địa chỉ swap của miền vào region table entry. Kernel không cần thiết viết toàn bộ không gian địa chỉ ảo của tiến trình vào swap device. Thay vào đó, nó sao chép bộ nhớ vật lý được chỉ định cho tiến trình tới không gian được cấp phát trên swap device, lờ đi các địa chỉ ảo không được chỉ định. Khi kernel swap tiến trình trở lại bộ nhớ, nó biết bản đồ địa chỉ ảo của tiến trình nên nó có thể chỉ định lại tiến trình tới đúng địa chỉ ảo. Kernel loại trừ việc sao chép thêm từ bộ đệm dữ liệu tới bộ nhớ vật lý bằng cách đọc dữ liệu vào các vị trí bộ nhớ vật lý đã được thiết lập trước đó theo các vị trí địa chỉ ảo. Hình 3 dưới đây đưa ra ví dụ về sự ánh xạ ảnh lõi của tiến trình lên swap device. Tiến trình gồm có 3 khu vực cho text, data, stack: text region kết thúc tại địa chỉ ảo 2K, và data region bắt đầu tại địa chỉ ảo 64K. Khi kernel swap tiến trình ra ngoài, nó swap các trang cho địa chỉ ảo 0, 1k, 64K, 66K và 128K; nó không cấp phát không gian swap cho 62K bytes trống giữa text region và data region hoặc 61Kbytes trống giữa data region và stack region nhưng điền vào không gian swap một cách liền kề nhau. Khi kernel swap tiến trình trở lại, nó biết tiến trình có 62Kbyte trống bằng việc tra cứu bản đồ bộ nhớ tiến trình, và chỉ định bộ nhớ vật lý một cách phù hợp. Hình 4 giải thích trường hợp trên. So sánh hình 4 và 5 cho thấy các địa chỉ vật lý được sử dụng bởi tiến trình trước và sau khi swap không giống nhau; tuy nhiên tiến trình không nhận thấy sự thay đổi ở cấp độ người dùng, vì nội dung không gian ảo của nó giống nhau. Hình 3: Ánh xạ không gian tiến trình vào trong Swap Device Hình 4: Swapping một tiến trình vào trong bộ nhớ 3.1 Fork swap Với lời gọi hệ thống fork giả định tiến trình cha luôn tìm đủ ko gian nhớ cho tiến trình con. Mặt khác, kernel chuyển tiến trình ra ngoài mà ko giải phóng vùng nhớ được chiếm giữ bởi cha của nó. Khi quá trình swap hoàn thành, tiến trình con tồn tại trên công cụ swap; tiến trình cha sẽ đặt tiến trình con ở trạng thái "read-to-run" và trở về chế độ người dùng. Khi đó, bộ swap sẽ swap chúng vào bộ nhớ, nơi mà kernel lập lịch cho nó; tiến trình con sẽ thực hiện phần của nó trong lời gọi hệ thống và trở về chế độ người dùng. 3.2 Mở rộng swap Nếu như một tiến trình cần nhiều không gian nhớ vật lý hơn cái đã được cấp phát cho nó, kết quả của một lần stack tăng thêm hoặc sau lời gọi hệ thống brk và chúng cần nhiều bộ nhớ hơn hiện tại, kernel sẽ thực hiện expansion swap cho tiến trình Nó cung cấp đủ không gian nhớ trên swap device để chứa không gian nhớ cho tiến trình, trong đó sẽ có phần không gian mới được yêu cầu. Sau đó, nó sẽ đặt địa chỉ mới để tính toán cho vùng nhớ ảo mới có địa chỉ song không gán địa chỉ vật lý cho chúng. Cuối cùng, nó sẽ swap tiến trình ra ngoài như là swap thông thường, điều chỉnh khoảng không gian mới cần được thêm trên công cụ swap(hình 5). Khi kernel swap tiến trình trở lại bộ nhớ, nó sẽ xác định bộ nhớ vật lý cho cái phần mới. Hình 5: Chỉnh sửa ánh xạ bộ nhớ cho Expansion Swap IV. Swapping một tiến trình vào 4.1 Swapper Quá trình 0, swapper, chỉ là một quá trình mà chuyển các quá trình từ swap device vào bộ nhớ. Nó làm nhiệm vụ chuyển quá trình vào bộ nhớ từ swap device hoặc chuyển ra khỏi bộ nhớ nếu nó cần không gian trong bộ nhớ chính. Swapper ở trạnh thái sleep nếu không có công việc cho nó làm (ví dụ như, không có quá trình để chuyển vào) hoặc nếu nó không thể làm việc (ví dụ như, không có quá trình thích hợp để chuyển ra). Nhân kích hoạt nó một cách định kì. 4.2 Hoạt động giải thuật Swapping Bộ xử lí đồng hồ đo thời gian mỗi quá trình ở trong nhân và hoán đổi ra ngoài. Khi swapper “thức dậy” để swap các quá trình vào, nó xem xét tất cả các quá trình đang ở trạng thái “sẵn sàng thực hiện nhưng đã bị swap ra” và lựa chọn một quá trình mà đã bị swap ra dài nhất. Nếu có sẵn đủ bộ nhớ trống, swapper sẽ swap quá trình vào, đảo chiều quá trình đã làm cho swap ra: nó cấp phát bộ nhớ vật lí, đọc quá trình từ swap device, giải phóng không gian nhớ trong swap device. Nếu swapper thực hiện hoán đổi thành công trong một quá trình, nó tìm một tập hợp quá trình khác “Sẵn sàng thực hiện nhưng đã bị swap ra” để hoán đổi và lặp lại thủ tục trên. Một trong những trạng thái kết thúc xuất hiện: Không có quá trình “sẵn sàng thực hiện” tồn tại trên swap device: swapper ở trạng thái sleep cho đến khi một quá trình trên swap device kích hoạt hoặc đến khi nhân chuyển ra một quá trình “sẵn sàng thực hiện” . Swapper tìm ra một quá trình thích hợp để swap vào nhưng hệ thống không chứa đủ bộ nhớ : swapper thử chuyển một quá trình ra, và nếu thành công, khởi động lại thuật toán hoán đổi, tìm một quá trình để chuyển vào. Nếu swapper phải chuyển một quá trình ra Nó kiểm tra mọi quá trình trong bộ nhớ: các quá trình “chết” không được chuyển ra, vì chúng không chiếm bộ nhớ vật lí; các quá trình bị khóa trong bộ nhớ, thực hiện hoạt động vùng chẳng hạn, cũng không được chuyển ra ngoài. Nhân chuyển ra ngoài các quá trình đang sleep hơn là các quá trình “sẵn sàng hoạt động” vì các quá trình “sẵn sàng hoạt động” sẽ sớm có một sự thay đổi lớn về lịch hoạt động. Việc lựa chọn quá trình nào đang sleep để chuyển ra ngoài là một hàm của quá trình ưu tiên và thời gian quá trình trong bộ nhớ. Nếu không có quá trình đang sleep trong bộ nhớ thì việc lựa chọn quá trình “sẵn sàng hoạt động” nào để chuyển ra ngoài là một hàm của quá trình giá trị nice và thời gian quá trình trong bộ nhớ. Hình 6: Giải thuật cho Swapper Điều kiện hoạt động của Swapper: Một quá trình “sẵn sàng thực hiện” phải ở trong nhân ít nhất 2s trước khi bị swap ra ngoài và một quá trình chuyển vào thì phải có thời gian bị swap ra ngoài ít nhất 2s. Nếu swapper không tìm được quá trình nào thoả mãn 1 trong 2 yêu cầu trên, swapper sẽ chờ và được đồng hồ đánh thức 1s 1 lần. Kernel cũng đánh thức swapper nếu một quá trình khác cũng rơi vào tình trạng nghỉ ngơi Nếu swapper trao đổi ra ngoài một quá trình xử lí hoặc nếu nó nghỉ ngơi bởi vì nó không thể trao đổi ra ngoài một quá trình xử lí, nó sẽ thực hiện lại ở điểm bắt đầu của giải thuật hoán đổi, cố gắng để trao đổi những quá trình xử lí thích hợp. Hình 7: Tuần tự thực hiện Swapping Hình 7 mô tả 5 quá trình và thời gian chúng lưu trú trong bộ nhớ hoặc trên swap device khi chúng đi qua một dãy những toán tử hoán đổi. Để đơn giản, giả thuyết rằng tất cả các quá trình là CPU mạnh và chúng không thực hiện một lời gọi hệ thống nào. Swapper chạy ở ưu tiên xếp hàng cao nhất, vì vậy nó luôn chạy một thời gian ngắn ở khoảng thời gian 1 giây nếu nó có việc để làm. Sau đó giả thuyết rằng những quá trình có kích cỡ giống nhau và hệ thống có thể chứa nhiều nhất 2 quá trình đồng thời trong bộ nhớ chính. Ban đầu, những quá trình A và B trong bộ nhớ chính và những quá trình khác được swap ra ngoài. Swapper không thể swap bất cứ quá trình nào trong hai giây đầu tiên, bởi vì không tiến trình nào trong bộ nhớ hoặc trên swap device trong hai giây Nhưng ở mốc hai giây, nó sẽ đưa ra ngoài hai quá trình A và B và đưa và trong hai quá trình C và D. Nó cũng cố gắng để đưa quá trình E vào nhưng không thể bởi vì không còn chỗ trong bộ nhớ chính. Ở mốc 3 giây, quá trình E thích hợp cho việc swap bởi vì nó đã ở trên swap device trong 3 giây, nhưng swapper không thể swap những quá trình ra khỏi bộ nhớ chính bởi vì thời gian lưu trú của chúng dưới 2 giây. Ở mốc 4 giây, swapper chuyển C,D ra ngoài và chuyển E,A vào trong. 4.3 Những thiếu sót của giải thuật Tuy nhiên, giải thuật chọn một quá trình đưa ra để lấy chỗ trong bộ nhớ có một thiếu sót nghiêm trọng: Mặc dù nó đưa ra một quá trình chỉ để lấy chỗ cho một quá trình được đưa vào, nó có thể đưa ra một quá trình mà không cung cấp đủ bộ nhớ cho quá trình sắp đưa vào. Ví dụ, nếu swapper cố gắng để đưa vào một quá trình chiếm 1 MB bộ nhớ và hệ thống không chứa bộ nhớ tự do, nó là không đáng kể để đưa ra một quá trình mà chỉ chiếm 2 KB bộ nhớ. Cách khắc phục là chỉ đưa ra những nhóm quá trình nếu chúng cung cấp đủ bộ nhớ cho quá trình chuẩn bị được đưa vào. Nếu swapper nghỉ ngơi bởi vì không thể tìm thấy bộ nhớ đủ để đưa một quá trình vào, nó tìm trở lại một quá trình để đưa vào mặc dù nó đã được chọn một lần trước đây. Nguyên nhân do những quá trình được hoán đổi khác có thể được đánh thức trong thời gian chờ đợi và chúng có thể thích hợp hơn cho việc đưa vào hơn quá trình đã chọn trước. Nhưng đó là solace nhỏ cho quá trình ban đầu vẫn đang cố gắng để được đưa vào. Trong một vài sự thực hiện, swapper cố gắng để đưa ra nhiều quá trình nhỏ hơn để lấy chỗ cho quá trình lớn để đưa vào trước khi tìm kiếm quá trình khác để đưa vào. Nếu swapper chọn một quá trình “ sẵn sàng để chạy” để đưa ra ngoài, nó là có thể rằng quá trình chưa được thực hiện vì nó được đưa ra trước. Hình 8 miêu tả một trường hợp, nơi kernel đưa vào quá trình D và C ở mốc 2 giây, và sau đó đưa quá trình D ra ngoài ở mốc 3 giây sự thiên vị quá trình E( bởi vì tác động của giá trị tốt ) thậm chí quá trình D chưa bao giờ được chạy. Giới hạn như vậy là không ai ưa. Hình 8: Giới hạn tới Swapping Nếu Swapper cố gắng để đưa ra một quá trình nhưng không thể tìm thấy không gian trên swap device, một sự tắc ngẽn hệ thống có thể bắt nguồn nếu 4 điều kiện sau đồng thời xảy ra: tất cả các quá trình trong bộ nhớ chính đều
Luận văn liên quan