Giáo trình Kiến trúc hệ điều hành: Phần 2

Chia sẻ: Codon_03 Codon_03 | Ngày: | Loại File: PDF | Số trang:55

Thêm vào BST

Báo xấu

102
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nối tiếp phần 1 cuốn "Giáo trình Kiến trúc hệ điều hành" mời các bạn đến với phần 2 để nắm bắt một số thông tin cơ bản về bộ nhớ vật lý; tổ chức bộ nhớ ảo; điều khiển bộ nhớ ảo;...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Kiến trúc hệ điều hành: Phần 2

Phần III Chương 7: Bộnhớvậ t lý 7.1 Mởđầu Việc tổchức và điều khiển bộnhớvậ t lý là một trong những yếu tốquan trọng nhất xác định cách xây dựng HĐH. Đểthực hiện các chương trình hay truy nhậ p dữliệu, chúng cần được nạp vào bộnhớvậ t lý. Bộnhớngoài (bộnhớthứcấ p như ổđĩ a cứng) thường có dung lượng rấ t lớn và giá rẻdùng đểchứa chương trình và dữliệ u. 7.2 Tổchức bộnhớ Trước kia bộnhớvậ t lý là tài nguyên đắ t nhất. Do đó nó cần được tổchức tốtđểcó thểsửdụng với hiệu quảcao nhấ t. Tổchức bộnhớlà cách mà chúng ta hình dung và sửdụng bộnhớvậ t lý. Ví dụnhưchúng ta sẽnạp vào bộnhớmột chương trình hay nhiề u chương trình cùng một lúc? Nế u nhưtrong bộnhớcó một sốchương trình thì mỗi chương trình sẽđược cấ p vùng nhớbằ ng nhau hay chia bộnhớthành các phầ n (section, part) với kích thước khác nhau. Chúng ta có cầ n đòi hỏi các chương trình ứng dụng được thiế t kếđểnạ p vào phần bộnhớcốđị nh hay cho phép nạ p vào bấ t cứvùng nào phù hợp. Chúng ta có cầ n mỗi chương trình nằ m trong một vùng nhớliên tục hay có thểchia chương trình thành các khối nằ m trong các vùng nhớbấtkỳ. 7.3 Điều khi ển bộnh ớ. Không phụthuộc vào cách tổchức bộnhớ, chúng ta cầ n giải quyết cầ n dùng các tiêu chuẩn nào đểđạ t được các thông sốtối ưu. Các phương pháp điề u khiển bộ nhớxác đị nh cách làm việc của bộnhớvới tổchức cụthểnào đó trong các cách giải quyế t khác nhau các vấn đề: chúng ta nạ p chương trình vào chỗnào, nêu như không còn đủbộnhớtrống thì chương trình nào đang nằ m trong bộnhớsẽphải đưa ra... 7.4 Phân lớp bộnh ớ Vào những năm 50/60 bộnhớvậ t lý rấ t đắ t. Do đó việc chọn lựa kích thước bộnhớ vật lý cần phải tính toán trước. Khách hàng không muốn mua lớn hơn anh ta có thể, mặt khác anh ta phả i mua một sốít nhất nào đó đểđảm bảo hoạ t động của
HĐH và sốlượng đị nh trước các user. Vấn đềlà xác đị nh dung lượng bộnhớtối u thoảmãn bài toán và đồng thời nằ thiể m trong khảnăng tài chính cho phép. Đểcó thểchạ y chương trình hay truy nhập dữliệu, chúng cần phải được nạp vào bộnhớvậ t lý. Các chương trình và dữliệ u chưa cầ n có thểlưu trong bộnhớngoài, n thiế khi cầ t sẽđ ược nạp vào bộnhớvật lý. Bộnhớngoài (đĩ a cứng,...) thường rẻ hơn và có dụng lượng lớn hơn nhưng thời gian truy cậ p bộnhớvậ t lý lại nhanh hơn nhiều. Ví dụvềtốc độtruy cậ p, bộnhớvậtlý: 60ns, HDD: 9ms. Hệthống với các lớp bộnhớcó đặ c tình tầ n suất trao đổi chương trình, dữliệu giữa các lớp khác nhau tương đối lớn. Sựtrao đổi đó cũng làm hao hụt tài nguyên hệthống ví dụthời gian BXL,... Vào những nă m 60 xuất hiệ n thêm một lớp (ngoài bộnhớvậ t lý và bộnhớngoài) nữa, đó là cache memory, cho phép làm tăng tốc độvà hiệ u quảsửdụng bộnhớ. Cache memory có tốc độtruy cập nhanh hơn nhiều (15ns) so với bộnhớvậ t lý. Nhưng nó cũng đắ t hơn nhiều, do đó trong hệthống thông thường dung lượng cache không lớn. Cache memory làm tăng thêm một lớp trao đổi nhưng chi phí đó được bù lạ i bởi tốc độtruy cập. Và do đó tốc độcủa cảhệthống được nâng lên nhiề u. Hình vẽ Cache Memory BXL cã thÓ truy  Thêi gian truy cËp trùc tiÕp m· cËp gi¶m lÖnh, d÷ liÖu  Tèc ®é truy cËp t¨ng Physical Memory  Gi¸ thµnh t¨ng  Dung l-îng gi¶m BXL kh«ng truy cËp trùc tiÕp, cÇn Secondary Memory n¹p vµo Physical Memory 7.5 Các chi ến lược điều khi ển bộnh ớ Đểđả m bảo sửdụng tốtcác tài nguyên giá trị , chúng cần được điều khiển mộtcách có hiệu quả. Các chiến lược điề u khiển bộnhớtheo hướng đảm bả o sửdụng tốt nhất bộnhớvậ t lý, và chia theo các hướng sau: n lược lựa chọn 1/ Chiế n lược lựa chọn theo yêu cầ a- chiế u (demand fetch) n lược lựa chọn trước b- chiế n lược phân bố 2/ Chiế
n lược loạ 3/ Chiế i ra Mục đích của chiến lược lựa chọn là xác đị nh xem khi nào phả i nạp block chương trình hay dữliệu vào bộnhớvậ t lý. Trong nhiều nă m người ta cho rằ ng cách tốt nhấ t là lựa chọn theo yêu cầu: theo đó block chương trình hay dữliệu được nạ p vào bộnhớkhi chương trình đang hoạ t động đòi hỏi đến. Bởi vì rằng nói chung khó mà nói trước được điều khiể n sẽđược chuyể n đếnđ âu (địa chỉlệ nh tiếp theo) và chi phí thêm gắ n với việc dựđoán trước sẽtă ng đáng kểthời gian chờ. Còn ngày nay, nhiề u nhà thiếtkếtin rằ ng lựa chọn dựđoán trước hoàn toàn có thểđảm bả o tăng tốc độcủa hệthống. Các chiế n lược phân bốcó mục đích xác đị nh xem chương trình mới sẽđược nạ p vào vịtrí nào của bộnhớ. Chúng ta sẽxem xét mộtsốchiế n lược như'first suitalbe' (chọn block đầu tiên phù hợp), 'most suitable' (chọn block phù hợp nhất) và 'least suitable' (block ít phù hợp nhấ t), theo kích thước các vùng trống. Các chiến lược loạ i bỏxác đị nh xem block chương trình hoặc dữliệu nào sẽbịloại ra khỏi bộnhớđểgiả i phóng chỗcho việc nạp chương trình hay dữliệu. 7.6 Phân bốbộnhớli ên tục và khôn g l iên tục Trong các máy tính đầ u tiên bộnhớđược phân bốliên tục- tức là mỗichương trình phải nằm trong một vùng nhớ.Chỉsau khi xuấthiện khái niệ m đa chương trình với phân đoạn thay đổi (variable partition multi programming) thì việ c phân bốbộnhớ không liên tục mới chứng tỏsựhiệu quảcủa mình. Trong phân bốbộnhớkhông liên tục, chương trình được chia làm nhiề u phân đoạn (block hay segment), và chúng có thểnằm tạ i các vùng nhớkhác nhau, không nhất thiết phải liền nhau. Vềphía HĐH, việc đảm bảo phân bốbộnhớkhông liên tục là rất phức tạ p, nhưng nó đem lạinhiề u ưu thế: nếu bộnhớcó nhiều vùng nhớtrống thay vì một vùng lớn thì HĐH vẫ n có thểnạp và thực hiện chương trình mà trong trường hợp ngược lạ i sẽphả i chờ. 7.7 Ph ân bốbộnh ớl iên tục đối với một u ser Trong các máy đầu tiên tạ i mỗi thời điể m chỉcó một user (một chương trình ứng dụng) và tấ t cảtài nguyên đề u thuộc quyề n của anh ta. Và tiền sửdụng máy được tính theo nguyên tắ c đơn giả n- bởi vì user toàn quyền sửdụng các tài nguyên do đó anh ta phả i trảcho tấtcả , không phụthuộc việc chương trình của anh ta có sửdụng hế t các tài nguyên hay không. Do đó cơchếtính tiền thực hiệ n theo thời gian máy đã sửdụng. Trong các hệlàm việ c trong chếđộphân chia thời gian thì việ c tính toán sửdụng các thuậ t toán phức tạ p hơn nhiề u.
Đầ u tiên mỗi user đều phải tựmình viế t toàn bộchương trình kểcảcác hàm thực hiện vào/ra bằ ng ngôn ngữmáy. Sau đó thì phầ n lệ nh thực hiệ n các thao tác vào/ra cơbả n được đưa vào IOCS- hệthống điều khiển vào/ra, và người dùng không phải viết lại các hàm vào/ra mà chỉphải gọi các hàm tương ứng của hệthống. Điề u đó làm đơn giả n và tăng hiệu quảlập trình và có thểcho rằ ng đó là bắt đầu sựphát n khái niệ triể m vềOS hiệ n đại. Tổchức bộnhớtrong trường hợp phân bốliên tục đốivới một người dùng được biểu diễ n bằng h.7.2 Hình 7.2 OS Ch-¬ng tr×nh øng dông Vïng nhí trèng Thông thường thì kích thước chương trình phụthuộc dung lượng bộnhớ(hay không gian quả n lý bởi HĐH), nếu kích thước chương trình nhỏhơn kích thước bộ nhớthì không có vấn đềnảy sinh, còn khi kích thước chương trình vượt quá thì sao? Nhờcơchếoverlay cho phép chúng ta có thểviế t các chương trình lớn hơn giới hạ n trên. Khái niệm của nó được thểhiệ n trong hình 7.3. Nếu nhưmodule nào đó của chương trình không hoạ t động trong cảquá trình thực hiện chương trình thì nó hoàn toàn có thểđược lưu trong bộnhớngoài, khi cầ n thiết mới được nạp vào bộnhớvật lý và sau khi kế t thúc nó lại được ghi ra bộnhớngoài, giải phóng bộ nhớvậtlý cho module tiếp theo. Chếđộoverlay cho phép lập trình viên thiế t kếcác chương trình lớn vượt qua hạ n chếbộnhớ.Nhưng việc thiết kếoverlay module đòi hỏinhiề u công sức và trí tuệ . Các chương trình với cấu trúc overlay phức tạp rất khó thay đổi. Ngày nay chúng ta không còn phải dùng chếđộoverlay đểvượt qua giới hạn vềbộnhớdo đã có các hệthống vớibộnhớả o - virtual memory u trúc overlay Hình 7.3 Cấ
0 a Module OS ®iÒu khiÓn a PhÇn ch-¬ng tr×nh, d÷ liÖu cÇn cã trong suèt qu¸ b tr×nh b Module Module Overlay 2 Overlay 1 Module Overlay 3 Vïng Overlay Bảo vệbộnhớtrong hệthống đơn nhiệ m Trong hệthống đơn nhiệ m, user được cấp vùng nhớliên tục và nói chung là có quyề n điều khiể n, truy nhập toàn bộbộnhớvậ t lý. Trong trường hợp này bộnhớ thường chia làm 3 vùng: vùng cho HĐH, vùng cho chương trình ứng dụng và vùng trống. Vấ n đềbảo vệbộnhớtrong trường hợp này cũng tương đối đơn giả n. Bả o vệbộnhớtrong trường hợp này là bả o vệHĐH đểchương trình ứng dụng không làm hỏng nó. Nế u nhưchương trình hoạ t động không đúng, điều đó có thểdẫn tới phá vỡHĐH, nếu nhưHĐH bịhỏng đế n mức chương trình khác ứng dụng không thểtiế p tục hoạ t động thì người dùng ít nhất cũng nhậ n thấ y, sửa lỗi và chạ y lại chương trình. Trong trường hợp này thì sựcần thiếtbả o vệHĐH không phả i là rõ ràng. Nế u trong trường hợp khác, chương trình ứng dụng phá hỏng HĐH một cách 'tinh vi'. Ví dụnhưnó 'vô tình' làm thay đổi một hàm vào/ra của hệthống. Khi đó chương trình có thểvẫ n hoạ t động nhưng tất cảkết quảcó thểbịmất. Còn có thể xả y ra trường hợp tồi tệhơn là hệthống đưa ra kết quảsai mà việc phát hiện ra không dễdàng. Do đó rõ ràng cần phảibảo vệHĐH. Việ c bả o vệcó thểthực hiệ n bằ ng thanh ghi m trong BXL (h.7.4) biên nằ Hình 7.4
S Ch XL -¬ng tr×nh T hanh ghi iªn Vïng nhí trèng Thanh ghi biên chứa địa chỉthấp nhất của lệ nh. Nế u nhưuser cốgắ ng truy nhậ p vào vùng của HĐH thì lệnh đó bịcấm và sẽđưa ra thông báo lỗi. Tấtnhiên, user cũng cầ n truy nhập đến HĐH, ví dụnhưthực hiệ n các thao tác vào/ ra. Đểphục vụđiề u này user có thểdùng các lệ nh đặc biệt, với chúng anh ta có thẻ yêu cầu dịch vụnào đó của HĐH (ví dụnhưngắ t SVC) Trong trường hợp này OS thực hiện dịch vụđược yêu cầu và sau đó trảlại điề u khiển cho chương trình ứng dụng. Với việc OS ngày càng phức tạp, cần phảicó các cơchếtốt hơn đểbảo vệOS đối với user cũng nhưgiữa các user vớinhau. 7.8 Đa chươn g trì nh với các đoạn cố đị nh (fi xed partitio n multi programmin g) Đốivới các hệthống đơn nhiệ m và ngay cảhệthống xửlý gói (packeg processing) thì vẫ n bịlãng phí một phần đáng kểtài nguyên. Trên h.7.5 ta thấ y rằng chương trình chỉthực sựsửdụng BXL khi mà nó không thực hiệ n thao tác vào/ra. Sau khi bắ t đầu thao tác vào/ra chương trình không thểtiếp tục cho đến khi kết thúc thao tác. Tốc độthực hiệ n thao tác vào/ra thường chậ m hơn nhiều so với tốc độcủa BXL. Nhưvậy BXL bịbỏphí trong suốt thời gian chờthực hiện tác vụvào/ra, và phầ n này chiếm đáng kểthời gian chung. Hình 7.5 Sửdụng BXL trong hệthống đơn nhiệ m Sö dông BXL cña øng dông tÝnh to¸n nhiÒu BXL thùc sù ho¹t ®éng Sö dông BXL cña øng dông thùc hiÖn nhiÒu thao t¸c I/O chê kÕt thóc thao t¸c I/O
Các nhà thiết kếthấy rằ ng hoàn toàn có thểtă ng hiệu quảsửdụng BXL. Họđã thực hiện các hệthống đa nhiệ m, trong đó các user cùng 'cạnh tranh' đểcó được tài nguyên. Chương trình đang chờkế t thúc thao tác vào/ra sẽphả i nhường BXL cho chương trình đã sẵn sàng hoạt động (tấtnhiên nếu có chương trình nhưthế ). Do đó đảm bả o khảnăng cùng thực hiện thao tác vào/ra và BXL- nâng cao hiệ u quảsử dụng BXL và cảhệthống. Các ưu thếcủa multiprogramming chỉcó thểtận dụng hế t khi trong bộnhớcó nhiều chương trình. Nhờđó khi một chương trình thưc hiệ n thao tác vào/ra thì BXL có thểchuyể n sang phục vụchương trình khác và thực hiện tính toán với thời gian trễnhỏnhấ t. Khi chương trình thứhai giải phóng BXL thí đế n chương trình thứba khác lạ i có thểsẵn sàng sửdụng nó. Multiprogramming đòi hỏi dung lượng bộnhớlớn hơn so với trường hợp đơn nhiệm nhưng chi phí đó được bù lạ i bởi việ c sửdụng hiệ u quảcác tài nguyên khác (BXL, thiết bịvào/ra) 7.8.1 Fixed partition multiprogramming (đa nhiệ m với phân đoạn cốđị nh) dịch và nạp theo chương trình theo đị a chỉtuyệ t đối Trong các hệđa nhiệm đầ u tiên, bộnhớđược chia thành các phần (phân đoạ n) với kích thước cốđịnh. Trong mỗi đoạ n chỉcó thểnạp một chương trình. Còn BXL nhanh chóng chuyển từchương trình này sang chương trình khác, do đó tạo ra hiệu quảlà tấtcảchương trình dường nhưđược thực hiện đồng thời. Việc biên dị ch chương trình được thực hiện bởi assembler và compiler với đị a chỉ tuyệtđối bịgiới hạ n bởi việc chương trình chỉcó thểchạy trong mộtphân đoạ n cụ thể(h.7.6) Hình 7.6 hµng ®îi c¸c øng dông chØ ch¹y trong ph©n ®o¹n 1 OS .... Ph©n ®o¹n 1 hµng ®îi c¸c øng dông chØ ch¹y trong ph©n ®o¹n 2 .... Ph©n ®o¹n 2 hµng ®îi c¸c øng dông chØ ch¹y trong ph©n ®o¹n 3 .... Ph©n ®o¹n 3 Nế u nhưchương trình đã sẵ n sàng nhưng phân đoạ n của nó đã có chương trình khác thì nó phải đợi dù rằ ng các phân đoạn khác có thểtrống (h.7.7). Điề u này dẫn tới sựlãng phí bộnhớnhưng việc thiế t kếOS lạitương đốiđơn giả n. Trên hình 7.7 thểhiệ n tình huống xấu nhấ t của phương pháp phân bốbộnhớliên tục với phân đoạn cốđị nh và chương trình được dị ch và nạp vào đị a chỉtuyệt đối (phân đoạn cốđị nh). Cảhai phân đoạ n một và hai đề u bỏphí còn hàng chờcủa
phân đoạ n ba quá nhiề u trong khi chúng đã có thểđược nạ p vào phân đoạ n một và hai. Hình 7.7 hµng ®îi c¸c øng dông chØ ch¹y trong ph©n ®o¹n 1 OS .... Ph©n ®o¹n 1 hµng ®îi c¸c øng dông chØ ch¹y trong ph©n ®o¹n 2 (trèng) .... Ph©n ®o¹n 2 (trèng) hµng ®îi c¸c øng dông chØ ch¹y trong ph©n ®o¹n 3 .... task task task task Ph©n ®o¹n 3 D C B A (bËn) 7.8.2 Đa nhiệ m với phân đoạn cốđị nh: dị ch và nạp chương trình các module tựdo. Các chương trình dị ch, assembler và loader tựdo được sửdụng đểdị ch và nạp các chương trình có thểthực hiệ n tại bất cứphân đoạn trống nào đủlớn (hình 7.8). Phương pháp này khắc phục được một sốnhược điểm vềsửdụng bộnhớtrong trường hợp trước (đa nhiệ m với phân đoạ n cốđị nh, dị ch và nạ p chương trình theo địa chỉtuyệt đối). Nhưng đểđạ t được điều đó, việc thiếtkếlạiphức tạp hơn nhiều. Hình 7.8 OS Ph©n ®o¹n 1 hµng ®îi tÊt c¶ c¸c øng dông .... task D task C task B task A Ph©n ®o¹n 2 Ph©n ®o¹n 3 øng dông cã thÓ ®-îc n¹p vµo ph©n ®o¹n trèng bÊt kú 7.8.3 Bảo vệbộnhớtrong các hệđa nhiệ m Trong các hệthống đa nhiệ m với phân bốbộnhớliên tục (contiguous memory allocation), thường người ta sửdụng các thanh ghi biên đểbả o vệbộnhớ. Hai thanh ghi chỉra cậ n dưới và cận trên của phân đoạn, hoặc một cận và kích thước của phân đoạ n; chương trình có yêu cầ u truy nhậ p đến các dịch vụcủa OS phải dùng ngắ t SVC đểyêu cầ u. Hình 7.9
0 OS a BXL Ph©n ®o¹n 1 2 sè hiÖu curent process b b cËn d-íi Ph©n ®o¹n 2 c cËn trªn c Ph©n ®o¹n 3 B¶o vÖ bé nhí trong hÖ ®a nhiÖm ph©n ®o¹n cè ®Þnh d 7.8.4 Vấn đềchia nhỏbộnhớ(fragmentation) trong đa chương trình với phân đoạn cốđị nh Fragmentation xả y ra trong bấ t kỳhệthống nào không phụthuộc vào tổchức bộ nhớ. Trong các hệđa nhiệ m với các phân đoạn cốđị nh, fragmentation xả y ra do các chương trình ứng dụng không chiế m hết toàn bộphân đoạn của nó hoặc là do các phân đoạn quá nhỏđểcó thểnạp các chương trình đang chờvào đó. 7.9 Đa nhi ệm với các p hân đoạn th ay đổi Khi xem xét các vấ n đềcủa đa nhiệm với phân đoạ n cốđị nh, các kỹsưthiếtkếOS thấy rằng tốt hơn là cho phép các chương trình chỉchiếm bộnhớkích thước vừa đủ kích thước nó cầ n. Không chia bộnhớthành các đoạn cốđị nh mà có kích thước thay đổi theo chương trình ứng dụng. Phương pháp đó gọi là đa nhiệm với các phân đoạn thay đổi. Sựphân bốbộnhớban đầ u được thểhiện trong h.7.10 Chúng ta chỉxem xét phương pháp phân chia bộnhớliên tục tức là mỗi chương trình nạp vào vùng nhớliên tục. Trong phương pháp đa nhiệ m với các phân đoạ n thay đổi chúng ta không đềra bấ t cứgiảsửgì vềchương trình (trừkhi kích thước của chúng không vượt quá kích thước bộnhớ). Các chương trình khi được nạ p (thực hiện) sẽđược cấ p vùng nhớchúng cầ n. Mỗi phân đoạn có kích thước đúng bằ ng kích thước chương trình nằm trong đó. Hình 7.10
App D: 14k App C: 20k App B: 10k App A: 15k OS OS OS OS App A: 15k App A: 15k App A: 15k App A: 15k App B: 10k App B: 10k App B: 10k App C: 20k App C: 20k Free Memory App D: 14k Free Memory Free Memory Free Memory Mỗi sơđồtổchức bộnhớđề u có sựlãng phí nhất đị nh. Trong trường hợp đa nhiệm với các phân đoạn thay đổi, sựlãng phí này xuất hiệ n khi các chương trình kế t thúc và trong bộnhớxuấ t hiện các vùng trống (hole) nhưh.7.11. Các vùng trống này có thểsửdụng đểnạ p các chương trình khác nhưng dù sao vẫn sẽcòn các vùng trống vì không phả i các chương trình đề u có kích thước đúng bằ ng vùng trống. Nhưvậ y đa nhiệ m với các phân đoạ n thay đổivẫn không tránh khỏi lãng phí bộnhớ. Hình 7.11 App A kÕt thóc & gi¶i phãng OS bé nhí OS OS App A: 15k Hole App C kÕt Hole thóc App B: 10k App B: 10k & gi¶i phãng App B: 10k bé nhí App C: 20k App C: 20k Hole App D: 14k App D: 14k App D: 14k Free Memory Free Memory Free Memory 7.9.1 Hợp nhất các vùng trống liề n nhau Đểkhắ c phục tình trạ ng bộnhớbịchia nhỏchúng ta có thểdồn các vùng nhớ trống kểnhau. Trong đa nhiệm với các phân đoạ n thay đổi, khi một chương trình kết thúc chúng ta có thểkiểm tra xem vùng được giải phóng có nằ m liề n kềvới vùng trống khác không? Nế u tồn tạ i thì chúng ta có thểhoặ c đưa thêm vào danh sách các phân đoạ n
trống thêm một bả n ghi nữa hoặ c nối liề n với vùng trống liền kềthành một vùng trống. Quá trình hợp nhấ t (nối liền) các vùng trống kềnhau biểu diễ n trên hình 7.12. Nhờsựhợp nhấ t này mà chúng ta tạo được các vùng nhớliên tục với kích thước lớn nhất có thể. Hình 7.12 OS OS App B: 10k App B: 10k H§H hîp c¸c Free vïng trèng liÒn nhau Free Free App D: 14k App D: 14k Free Memory Free Memory 7.9.2 Dồn bộnhớ Nhưchúng ta thấy sau khi thực hiệ n hợp nhấ t các vùng trống (holes) liề n kềnhau thì nhìn tổng thểthì trong bộnhớvẫn tồn tạicác vùng trống - cho dù ít hơn và kích thước lớn hơn. Đôi khi chương trình cần thực hiện tiếp theo lại khó lớn đế n mức không có vùng trống nào đủlớn đểnạp cho dù tổng cộng kích thước các vùng trống vẫn lớn hơn cầ n thiết. Vấ n đềnày được khắ c phục nhờphương pháp gọi là dồn bộnhớ(h.7.13) và bả n chất là chuyể n (dồn) tất cảcác phân đoạn đang có chương trình vềmột phía bộ nhớ. Nhờđó thay vì có nhiều phân đoạn trống (vùng trống) vụn vặt chúng ta có được một vùng trống lớn duy nhấ t trong bộnhớ. Khi đó chương trình tiếp theo có xác suấ t lớn sẽcó đủbộnhớcần thiế t đểchạy. Đôi khi phương pháp 'dồn bộnhớ' còn gọi là 'dọn rác'. Tuy có nhiều ích lợi nhưng phương pháp dồn bộnhớvẫ n có những nhược điểm nhất đị nh: 1. Nó cũng làm hao phí tài nguyên hệthống có thểđược sửdụng vào mục đích khác tốt hơn. 2. Vào thời gian dồn bộnhớ, hệthống phải dừng tấ t cảcác công việc khác. Kết quảdần tới thời gian không thểdựđoán trước trong việc phả n ứng lại các sự kiện (trảlời user trong chếđộdialog chẳng hạn) và điều đó có thểkhông chấ p nhận được trong các hệthống thờigian thực. 3. Dồn bộnhớdịch chuyể n các task trong bộnhớ. Điều đó có nghĩ a là thông tin vềsựphân bốchương trình phả i được lưu lạ i ởdạ ng nào đó.
4. Trong TH các bài toán thực hiệ n liên tục thì tầ n sốthực hiệ n thao tác dồn bộ nhớcó thểtrởnên thường xuyên và hao phí thực hiện nó có thểvượt quá lợi i. ích nó mang lạ Hình 7.13 OS OS Free App B: 10k H§H dån c¸c vïng trèng App D: 14k App B: 10k Free App D: 14k Free Free Memory 7.9.3 Các chiến lược phân bốthông tin trong bộnhớ. Các chiến lược phân bốbộnhớđược áp dụng đểxác đị nh chương trình và dữliệu sẽđược tiếp tục nạp vào vùng nào của bộnhớ. Chúng ta thường gặp 3 chiến lược được biểu diễn trên h.14 1. Chiến lược 'first suitable': chương trình sẽđược nạ p vào vùng trống gặp đầu tiên (trong danh sách các vùng trống) có kích thước đủlớn. Chiế n lược này có vẻtrực giác và thực tếvì nó cho phép tìm lời giảinhanh nhất. 2. Chiến lược 'most suitable': Chương trình được nạp vào vùng trống 'vừa nhấ t' do đó không gian lãng phí là ít nhất. Với nhiều người thì chiế n lược này trực giác có vẻlà đúng nhấ t. 3. Chiến lược 'least suitable': đầu tiên thì chiến lược này có vẻlạlùng, nhưng xem xét kỹthì nó cũng có các ưu điể m nhấtđị nh. Với chiến lược này chương trình nạ p vào vùng trống lớn nhấ t. Ưu điể m là sau khi đã nạ p chương trình, vẫn còn đủ không gian trống tương đốilớn đẻcó thểnạp thêm chương trình mới khá lớn. Hình 7.14 OS a Danh s¸ch c¸c vïng trèng Free 16k §Þa chØ ®Çu KÝch th-íc b App A a 16 k c Free 14k c 14 k Yªu cÇu 13k d e 5k App B e Free 5k g 30 k f App C ( S¾p theo ®Þa chØ hoÆc thø tù bÊt kú ) g Free 30k 14(a): ChiÕn l-îc FS
OS a Danh s¸ch c¸c vïng trèng Free 16k §Þa chØ ®Çu KÝch th-íc b App A e 5k c Free 14k c 14 k Yªu cÇu 13k d a 16 k App B e Free 5k g 30 k f App C ( S¾p theo thø tù kÝch th-íc t¨ng dÇn ) g Free 30k 14(b): ChiÕn l-îc MS OS a Danh s¸ch c¸c vïng trèng Free 16k §Þa chØ ®Çu KÝch th-íc b App A g 30 k c Free 14k a 16 k Yªu cÇu 13k d c 14 k App B e Free 5k e 05 k f App C ( S¾p theo thø tù kÝch th-íc gi¶m dÇn ) g Free 30k 14(c): ChiÕn l-îc LS 7.10 Đa n hiệm với sw ap pin g Trong các hệđa nhiệ m đã xem xét ởtrên thì chúng ta đều giảsửrằng chương trình ứng dụng luôn nằm trong bộnhớđế n khi nó kế t thúc. Còn có cơchếkhác gọi là swapping mà không cần điều kiện đó. Trong một sốhệthống dùng swapping (h.7.15) thì mỗi thời điểm trên cảbộnhớ chỉcó một chương trình ứng dụng. Chương trình đó thực hiệ n đế n khi có thểsau đó nó giải phóng cảBXL và bộnhớđểcho chương trình tiếp theo. Nhưthế , toàn bộbộnhớđược giành cho mộtchương trình trong khoả ng thời gian ngắ n, và sẽbị đưa ra khỏi bộnhớ, chương trình tiếp theo được nạp vào bộnhớ. Bình thường thì một chương trình trong quá trình chạ y từđầu đến lúc kế t thúc sẽbịswap nhiều lầ n. Trong các hệthống phân chia thời gian có sửdụng swapping, khi sốchương trình khá ít thì hệthống có thểđảm bảo thời gian trảlời chấ p nhận được, còn khi số chương trình nhiều thì các nhà thiế t kếhiểu rằng cần có các phương pháp và công cụhiệ u quảhơn. Trên cơsởhệthống vớiswapping đầ u những nă m 60, người ta đã xây dựng nhiều hệthống với sựtổchức bộnhớtheo trang (page) và ngày nay trở nên thông dụng. Cũng đã có xây dựng các hệthống phức tạ p hơn với swapping, trong đó cho phép phân bốtrong bộnhớnhiều chương trình. Trong các hệthống đó, chương trình bị đưa ra khỏibộnhớchỉkhi vùng bộnhớcủa nó cầ n thiế t đểnạp chương trình khác.
Trong TH dung lượng bộnhớkhá lớn thì các hệthống đó hoạt động tốt hơn đáng kểdo giả m được thờigian thực hiệ n swapping. Hình 7.15 a a a 0 A B C OS a e f Vïng d Swapping ¶nh bé nhí, ®-îc l-u trªn bé nhí ngoµi b Hệthống đa nhiệ m với swapping, tạ i mỗi thời điể m chỉcó một chương trình trong bộnhớ. Chương trình đó tiếp tục đến khi có mộttrong các sựkiệ n sau xảy ra: t hiệ 1. Xuấ n tín hiệ u timer t thúc 2. Nó kế Vùng swapping của chương trình đó sẽđược copy vào bộnhớngoài, còn ả nh bộ nhớcủa chương trình tiế p theo sẽđược nạ p vào vùng swapping. Chương trình thứ hai tiếp tục được thực hiệ n, quá trình cứthếtiếp tục. Chương 8: Tổchức bộnhớảo 8.1 Mởđầu Thuật ngữvirtual memory thường gắn liền với khảnă ng đánh đị a chỉcho không gian nhớlớn hơn nhiều dung lượng bộnhớvậ t lý. Virtual memory xuất hiệ n (ứng dụng) lần đầ u vào năm 1960 tại trường đạihọc Manchester và sau đó nhanh chóng được phổbiến. Có hai phương pháp được chấ p nhận một cách tựnhiên khi thực hiệ n (tổchức) bộ nhớảo: đó là tổchức theo trang (page) và theo phân đoạn (segment). Trong mộtsố hệthống, ứng dụng một trong hai phương pháp đó còn trong một sốkhác thì áp dụng tổhợp cảhai phương pháp. Tấtcảcác cơchếbộnhớảo đề u đặc trưng bởi tính chấ t rằ ng đị a chỉđược tính bởi chương trình, không nhấtthiết phải trùng với địa chỉbộnhớ(vậ t lý). Trong thực tế địa chỉảo thểhiện không gian lớn hơn nhiề u so với thực tếbộnhớvậ t lý. 8.2 Qu á trì nh phát triển các dạng tổch ức b ộn hớ H.8.1 biểu diễ n quá trình phát triể n từcác hệthống bộnhớthực đơn nhiệm (1 user) đến các hệthống bộnhớảo sửdụng tổhợp cảhai phương pháp page và segment.
Vì tổchức bộnhớả o phức tạp hơn nhiều nên có hai chương: C8: tổchức bộnhớả o và C9: điề u khiể n bộnhớảo Hình 8.1 Bé nhí vËt lý Bé nhí ¶o HÖ thèng ®¬n HÖ ®a nhiÖm, bé nhí vËt lý HÖ ®a nhiÖm, bé nhí ¶o nhiÖm Tæ chøc theo Tæ chøc theo Tæ chøc kÕt Ph©n ®o¹n cè ®Þnh Ph©n ®o¹n thay ®æi trang segment hîp §Þa chØ §Þa chØ tuyÖt ®èi thay ®æi 8.3 Bộnhớảo: các khái niệ m cơbản Cốtlõi các khái niệm vềbộnhớả o là ởchỗđịa chỉmà process có thểtruy nhập gọi là không gian địa chỉảo V của process đó, còn vùng đị a chỉthực tồn tại trong bộ nhớgọi là không gian địa chỉthực R. Dù rằ ng process làm việc với đị a chỉảo thì thậtsựchúng phả i làm việ c vớibộnhớ. Do đó vào thời gian thực hiệ n process, các địa chỉảo cần phả i biến đổi thành đị a chỉthực, ngoài ra việc xửlý phải nhanh chóng vì nếu không thì hiệu quảcủa máy tính có thểgiảm tới mức không chấ p nhậ n được và lợi ích của tổchức bộnhớả o không thểứng dụng được. : ánh xạcác ô nhớtừbộnhớvậ Hình vẽ t lý sang bộnhớả o Bé nhí ¶o Bé nhí vËt lý Đểxác đị nh ánh xạgiữa đị a chỉthực và ảo, người ta đã thiế t kếcác phương pháp khác nhau. Cơchếbiế n đổi địa chỉđộng (DAT-dynamic address translation) đảm bảo sựbiến đổi địa chỉả o sang đị a chỉả o vào thời gian thực hiện process. Tấ t cả các hệthống đó đề u có tính chất chung: đó là các đị a chỉảo liền nhau chưa chắ c đã tương ứng với các địa chỉthực liề n nhau (h.8.3). Nhưthếuser không cần phả i quan tâm đến việc nạp chương trình hay dữliệu của mình trong bộnhớ(vậ t lý). Anh ta có được khảnăng viếtchương trình mộtcách tựnhiên hơn, chỉphảiquan tâm đế n các vấn đềthiết kếchương trình, thuậ t toán mà không cầ n đểý đến chi tiế t cụthể
của thíêt bị. Khi đó máy tính (có thể) được coi nhưlà mộtcài gì đó trừu tượng hơn- một công cụlogic nào đó đểchạ y chương trình chứkhông phả i nhưmột cái máy vật lý với các chi tiế t cầ n đểý, làm khó khă t kếchương trình. n cho quá trình thiế Hình 8.3 C¬ chÕ ¸nh x¹ DAT Bé nhí ¶o Bé nhí vËt lý 8.4 Tổchức bộnhớnh iều l ớp Nế u nhưchúng ta đềra rằ ng không gian địa chỉả o của user sẽlớn hơn không gian địa chỉthực, và nế u chúng ta đị nh hướng rằng hệthống sẽlàm việ c tốttrong chếđộ đa nhiệ m và tài nguyên bộnhớđược chia sẻ(dùng chung), thì chúng ta cầ n có môi trường, công cụlưu trữchương trình, dữliệu trong bộnhớthứcấ p. Thường thì người ta sửdụng mô hình bộnhớhai cấ p (h.8.4). Lớp thứnhấ t- bộnhớvậ t lý, tại đó cầ n nạp các chương trình đựơc thực hiệ n và các dữliệu cầ n truy cập. Lớp thứ hai- bộnhớngoài có dung lượng lớn đểlưu trữcác chương trình, dữliệ u lúc đó chưa cần nạ p. Đểchạy chương trình, code và dữliệu của nó cầ n được đưa vào bộnhớ Hình 8.4 Bé nhí vËt lý Bé nhí ngoµi HDD BXL TAPE ... Bởi vì bộnhớthực hiệ n được chia sẻgiữa nhiều chương trình và mỗi chương trình (process) có thểcó không gian đị a chỉảo lớn hơn không gian đị a chỉthực do đó vào thờigian thực hiệ n, chỉcó mộtphầ n mã (code) và dữliệu của mỗiprocess nằm trong bộnhớthực. Trên h.8.5 thểhiện cấ u trúc bộnhớhai lớp, trong bộnhớthực lưu chỉmộtphầ n bộnhớả o của các chương trình.
Hình 8.5 Vïng lµm bé nhí ¶o A Bé nhí vËt lý øng dông A Bé nhí ¶o B B Bé nhí vËt lý øng dông B øng dông B Bé nhí ¶o A C øng dông C C A Bé nhí ¶o øng dông A Bé nhí vËt lý Bé nhí ngoµi 8.5 Blocking map pin g: ánh xạtheo khối Cơchếbiế n đổi đị a chỉđộng (DAT) phả i sửdụng các bả ng ánh xạ- chỉrằ ng các ô nhớảo nào tạ i thời điểm hiện thời nằm trong bộnhớvà ởô nhớthực nào. Nế u như ánh xạđược thực hiệ n theo từng byte hay word thì rõ ràng thông tin vềánh xạcòn lớn hơn bản thân bộnhớthực. Do đó đểcó thểáp dụng bộnhớảo, cầ n có phương pháp cho phép giảm kích thước của bả ng ánh xạ. Vì ánh xạtừng ô nhớlà không thểchấ p nhận, chúng ta phải gộp theo các khối - block, và hệthống theo dõi xem các block của bộnhớảo nằm đâu trong bộnhớ. Kích thước block càng lớn thì thông tin vềánh xạcàng nhỏ, nhưng các block lớn lạicần nhiều thời gian nạ p hơn và ngoài ra với xác suấtlớn còn hạn chếsốprocess có thểchia sẻchung bộnhớvậ t lý. Khi thiế t kếcơchếbộnhớảo xuấ t hiện câu hỏi là các block có kích thước như nhau hay khác nhau. Nế u các block có kích thước nhưnhau thì chúng (block) được gọi là các trang (page), còn tổchức bộnhớả o tương ứng gọilà tổchức theo trang. Nế u các block có thểcó kích thước khác nhau thì chúng được gọi là các đoạ n (segment), tổchức bộnhớả o là tổchức theo đoạ n. Trong một sốhệthống cảhai cách được tổhợp tức là các segment được tạo thành từcác page có kích thước như nhau. Các địa chỉtrong các hệthống ánh xạtheo khối là các đị a chỉgồm hai thành phầ n (hai chiều). Đểtruy nhậ p đến một dữliệ u cụthể, program chỉra block và offset của dữliệ u trong block của dữliệ u trong block đó (h.8.6) b (Block No) d (Offset ) §Þa chØ ¶o v = (b,d) Đị a chỉảo V được chỉra với cặp sốv=(b,d) trong đó b- sốblock (sốthứtự) còn d- offset (độlệch) tương đối so với đầ u block.
Sựbiế n đổi từđị a chỉảo v=(b,d) thành địa chỉthực r được thực hiệ n nhưtrên hình 8.7. Mỗi process có bả ng ánh xạblock của mình (nằ m trong bộnhớthực). Đị a chỉ thực a của bảng này được nạ p vào thanh ghi riêng của BXL gọi là thanh ghi đị a chỉ (đầ u) của bả ng ánh xạ(block table origin register). Mỗidòng của bả ng ánh xạchứa ánh xạcủa một block của process, ngoài ra các dòng được sắp xếp theo thứtựsố block, từblock 0, block 1. Sốblock b được cộng với đị a chỉcơsởcủa bả ng ánh xạ a, ta được đị a chỉthực của dòng chứa ánh xạcủa block b. Dòng này chứa đị a chỉ thực b' của block b. Sau đó cộng thêm vào đị a chỉb' này với offset d ta được đị a chỉthực cầ n tìm r=b'+d. Tất cảcác phương pháp block mapping dùng trong các hệ thống tổchức theo trang, segment hay tổhợp được thểhiện trên h.8.7 Hình 8.7 Block table origin Register a §Þa chØ ¶o v = (b,d) + b d a+b B¶ng ¸nh x¹ b §Þa chØ thùc b' l b' + r §Þa chØ block §é dµi trong bé nhí vËt lý Cầ n phả i đểý rằng block mapping được thực hiện động (dynamic) ngay trong thời gian thực hiện process. Nếu cơchếbiế n đổi địa chỉDAT không đủhiệu quả , thì chi phí của nó có thểlàm giảm hiệu suất của hệthống tới mức vượt quá ưu thếmà bộnhớảo mang lạ i. 8.6 Tổchức theo trang: các khái n iệm cơbản Chúng ta xem xét ánh xạtheo khối với kích thước cốđị nh tức là tổchức bộnhớ n này chúng ta chỉxem xét tổchức theo trang thuần tuý. theo trang. Trong phầ Địa chỉảo trong hệthống theo trang được thểhiệ n bằng cặ p v=(p,d) trong đó p- số thứtựtrang trong bộnhớả o còn d-offset trong trang p (h.8.8) Hình 8.8 p (Page No) d (Offset ) §Þa chØ ¶o v = (p,d) Process có thểđược thực hiện tiế p nế u trang hiện thời cần đế n của nó nằ m trong bộ nhớthực. Các trang đ ược ghi từbộnhớngoài vào bộnhớthực, theo các block gọi
là page frame và có kích thước đúng bằ ng kích thước trang. Các page frame bắt đầ u từcác địa chỉ(trong bộnhớthực) là bội sốcủa kích thước trang (h.8.9). Các trang có thểđược nạ p vào bấtkỳpage frame trống nào. Hình 8.9 0 page frame 0 Sè trang KÝch th-íc Vïng ®Þa chØ p 0 p 0 p-1 page frame 1 1 p p 2p-1 2p 2 p 2p 3p-1 page frame 2 3p Biến đổi địa chỉđộng trong hệthống tổchức theo trang, thực hiện theo cách sau: Process truy nhập đến đị a chỉả o v=(p,d). Cơchếánh xạtrang thểhiện trên h.8.10, đầu tiên tìm sốtrang p trong bảng ánh xạtrang và xác đị nh được page frame p' tương ứng vớitrang p. Địa chỉthực được tính bằ ng tổng của p' và d. Hình 8.10 Bé nhí vËt lý page frame 0 §Þa chØ ¶o p d page frame 1 p' .... DAT offset d page frame p' Page frame p' t-¬ng øng víi trang ¶o p Chúng ta sẽxem xét quá trình này kỹhơn. Trong thực tế , thường thì không phảitất cảcác page của process đề u nằm trong bộnhớ, do đó bảng ánh xạphải chỉra là trang cầ n truy nhập có nằm trong bộnhớkhông và nằ m ởđâu, còn nếu không thì nó nằ m đâu trong bộnhớngoài. Trên h.8.11 biểu diễ n mộtdòng dữliệ u trong bả ng ánh xạtrang. Bit flag r chỉra sựhiện diệ n của trang trong bộnhớ: nế u r=1 tức là trang nằ m trong bộnhớthực, còn nế u r=0 thì trang đó hiệ n không có trong bộnhớ thực. Nếu nhưtrang đó không có trong bộnhớthì s là đị a chỉ(vịtrí) của trang trong bộnhớngoài, còn nế u nó nằm trong bộnhớthì p' là sốpage frame. Chú ý rằng p' không phả i là đị a chỉthực thậ t sự. Địa chỉthực a - của page frame p' được tính bằng a=(p)*(p') (sốtrang p có giá trịtừ0.1.2.3...) Hình 8.11
§Þa chØ trong bé nhí Page frame (nÕu Bit flag ngoµi (nÕu kh«ng cã trang cã trong bé trong bé nhí) nhí) r s p Đểtiế t kiệm bộnhớ(giả m kích thước của bảng ánh xạ ) thì mỗi dòng có thểkhông cần chứa thông tin đị a chỉcủa trang trong bộnhớngoài. 8.6.1 Biến đổiđị a chỉ , ánh xạtrực tiế p Chúng ta sẽxem xét một sốphương pháp biế n đổi đị a chỉtrang. Đầ u tiên chúng ta sẽxem xét biế n đổi(ánh xạ) trực tiế p, được biểu diễn trên h.8.12 Hình 8.12 Process đưa yêu cầ u truy cập địa chỉả o v=(p,d). Trước khi process tiếp tục thực hiện, OS nạp đị a chỉthực của bả ng ánh xạtrang vào thanh ghi. Địa chỉcơsởb này được cộng với sốtrang p, thu được đị a chỉthực b+p của dòng chứa ánh xạtrang p. Dòng này chỉra page frame p' của p. Sau đó page frame được cộng với offset d và ta có địa chỉthực r. Cách tính này gọi là phương pháp biến đổi trực tiế p (ánh xạ trực tiếp), bởi vì bảng ánh xạtrang chứa từng dòng cho mỗi trang bộnhớảo của process. Nế u process có n trang bộnhớả o thì bảng ánh xạtrong phương pháp ánh xạtrực tiế p chứa n dòng liên tiếp cho các trang từ0 đến n-1 Đị a chỉả o cần tính và đị a chỉbảng ánh xạđề u chứa trong các thanh ghi của BXL do đó các thao tác với chúng có thểthực hiện rấ t nhanh trong vòng xửlý lệ nh. Nhưng còn bảng ánh xạ , kích thước khá lớn, thường nằ m trong bộnhớ, do đó để truy nhậ p nó cầ n một thao tác đọc bộnhớ. Vì thời gian đọc dữliệ u từbộnhớlớn hơn nhiề u thời gian xửlý lệnh và chúng ta cần thêm một lầ n đọc bộnhớđểlấ y được dòng cầ n thiết của bảng anhý xạ , điề u đó có nghĩ a là phương pháp ánh xạ trực tiếp có thểlàm giả m tốc độcủa hệthống khi thực hiện chương trình gầ n hai lần. Điề u đó tấ t nhiên không chấp nhận được, do đó cầ n có các phương pháp biế n đổi đị a chỉnhanh hơn. Nhưng điề u đó cũng không có nghĩ a là phương pháp này hoàn toàn không thểáp dụng, ví dụnhưtrong một sốhệthống đã sửdụng phương pháp này thành công bằ ng cách lưu toàn bộbả ng ánh xạtrong cache memory có tốc độrấ t cao. 8.6.2 Biến đổiđị a chỉtrang dùng bộnhớkế t hợp associative memory