Biên dịch tại thời điểm nạp load là gì năm 2024
Bài giảng môn học: HỆ ĐIỀU HÀNHTRƯỜNG ĐẠI HỌC NGUYỄN TẤT THÀNHKHOA CÔNG NGHỆ THÔNG TINBiên soạn: ThS. Nguyễn Văn ThànhEmail : [email protected]Số tín chỉ: 3Số tiết: 60 tiết(30 LT + 30 TH)Chương 5:QUẢN LÝ BỘ NHỚChương 5: QUẢN LÝ BỘ NHỚCác khái niệm về quản lý bộ nhớChuyển đổi địa chỉCác kỹ thuật tối ưu sử dụng bộ nhớCấp phát bộ nhớ cho tiến trìnhKỹ thuật Phân trang (paging)Thay thế trang (Page Replacement)Kỹ thuật Phân đoạn (Segmentation)2Các khái niệm cơ bảnBộ nhớ và địa chỉ bộ nhớ:Bộ nhớ là nơi chứa các tiến trình (ready queue) và dữ liệu củatiến trình trước khi được CPU xử lý.Đơn vị lưu trữ là Word (hay Byte).Mỗi Word được gán một địa chỉ(memory address) để truy cập.Cấp phát bộ nhớ cho process:Mỗi process được cấp phát khônggian bộ nhớ riêng.Không gian nhớ của mỗi processđược giới hạn bới:Base address: địa chỉ bắt đầu.Limit: không gian (dung lượng)bộ nhớ được cấp.3 Show
Các khái niệm cơ bảnCác loại địa chỉ bộ nhớ:Địa chỉ vật lý (physical address):Là địa chỉ trỏ đến toàn bộ các words trên bộ nhớ vật lý.Không gian địa chỉ vật lý bao gồm toàn bộ bộ nhớ vật lý. Địa chỉ luận lý / tái định vị (logical / relocatable address):Là địa chỉ lệnh và dữ liệu nội tại của một chương trình.Không gian địa chỉ luận lý giới hạn trong vùng nhớ được cấp. Địa chỉ Tương đối và Tuyệt đối:Địa chỉ tuyệt đối (Absolute address): là địa chỉ vật lý của bộ nhớ.Địa chỉ tương đối (Relative address): là địa chỉ tính từ 1 điểm cơ sở(based address) trong không gian bộ nhớ mà tiến trình được cấp.Địa chỉ tuyệt đối = Based address + Địa chỉ tương đối4 Chuyển đổi địa chỉCác không gian địa chỉ:Symbolic address (địa chỉ danh biểu):là địa chỉ của các biến, hằng, pointer.. source code chươngtrình. Relocatable address (địa chỉ tái định vị):là địa chỉ các mã lệnh và dữ liệu của source code sau khi được CPUbiên dịch (compile). Physical address (địa chỉ vật lý):là địa chỉ các Mã lệnh, Dữ liệu của tiến trình sau khi được nạp (load)vào bộ nhớ.7SymbolicaddressRelocatableaddress Physical address Chuyển đổi địa chỉCác thời điểm chuyển đổi địa chỉ:Chuyển đổi tại thời điểm biên dịch (Compile time):Nếu HĐH biết trước địa chỉ vật lý của vùng nhớ cấp cho tiến trình.Chuyển địa chỉ danh biểu thành địa chỉ vật lý ngay quá trình biên dịch.Khuyết điểm: phải biên dịch lại nếu địa chỉ cấp cho tiến trình thay đổi.8 Tùy vào điều kiện thực thi, HĐH chuyển đổi không gian địa chỉlệnh và dữ liệu của chương trình thành địa chỉ vật lý tại các thờiđiểm khác nhau.SymbolicaddressPhysicaladdressCompiler Chuyển đổi địa chỉCác thời điểm chuyển đổi địa chỉ:Chuyển đổi tại thời điểm nạp (Load time):Nếu không biết trước địa chỉ vật lý của vùng nhớ cấp cho tiến trìnhBộ biên dịch (compiler) sinh địa chỉ tái định vị (Relocatable address).Vào thời điểm nạp, bộ loader chuyển đổi địa chỉ tái định vị thành địachỉ vật lý dựa trên một địa chỉ nền (base address).Khuyết điểm: phải tiến hành reload nếu địa chỉ nền thay đổi9 ####### Symbolic ####### address ####### Relocatable ####### address ####### Compi- ####### ler ####### Physical ####### Loader address Chuyển đổi địa chỉCác thời điểm chuyển đổi địa chỉ:Chuyển đổi tại thời điểm thực thi (Execution time):Nếu trong quá trình thực thi, HĐH có di chuyển process từ vùng nhớnày sang vùng nhớ khác:=> chuyển đổi từ địa chỉ luận lý sang địa chỉ vật lý được thực hiệnngay trong lúc thực thi.Ưu điểm: linh động trong quản lý bộ nhớ; sử dụng bộ nhớ hiệu quả;... Mộ số phương pháp chuyển đổi địa chỉ tại Execution time:Phương pháp dùng thanh ghi Base và Limit (các HĐH sơ khai sử dụng)Phương pháp dùng Paging (kỹ thuật phân trang - trình bày ở phầnsau)Phương pháp dùng Segmentation (kỹ thuật phân đoạn - trình bày ởphần sau)10 Các kỹ thuật tối ưu sử dụng bộ nhớDynamic linking (liên kết động):Cơ chế:Các hàm, thủ tục... thường dùng sẽ được Hệ điều hành code và biêndịch sẵn thành các module ngoài (external module).Dynamic linking library – DLL: bộ thư viện các external module.Dynamic linking là liên kết giữa chương trình chính với các Externalmodule và được gọi khi chương trình chính cần dùng. Ưu điểm:Nhiều chương trình sử dụng chung các external module => khônggian bộ nhớ được tối ưu (tiết kiệm không gian bộ nhớ).13 Các kỹ thuật tối ưu sử dụng bộ nhớDynamic loading (nạp động)Cơ chế: Các module (hàm, thủ tục..) chỉ được nạp vào bộ nhớ chính khinào process chính gọi đến. Nhận xét:Các module không gọi sẽ không chiếm bộ nhớ => tăng độ hiệu dụngcủa bộ nhớ.Hiệu quả đối với những module có tần suất sử dụng thấp.Dynamic loading là do process tự điều khiển. Overlay (phủ lắp)Cơ chế: chỉ giữ lại trong bộ nhớ những lệnh / dữ liệu cần dùng =>giải phóng các dữ liệu chưa dùng đến.Nhận xét:Hữu dụng khi kích thước process lớn hơn vùng nhớ được cấp.Overlay là do process tự điều khiển14 Các kỹ thuật tối ưu sử dụng bộ nhớSwapping (hoán vị / hoán chuyển):Cơ chế hoán vị (swapping):Swap out: process bị HĐH đưa ra khỏi bộ nhớ - > ghi vào thiết bị lưutrữ phụ (thường là hard disk).Swap in: process được nạp lại vào bộ nhớ từ thiết bị lưu trữ phụ.15 Các kỹ thuật tối ưu sử dụng bộ nhớSwapping (hoán vị / hoán chuyển):Swapping policy (chính sách / giải thuật định thời):Round-robin: luân phiên swap out các tiến trình thao quantum time.(P1 swap out - > P2 swap in - > P2 out - > P3 in ... - > P1 in)Priority-based scheduling: đưa những process có độ ưu tiên thấphơn lên trên để swap out trước (gọi là Roll out, roll in) Ưu /nhược điểm của swapping:Đáp ứng chạy cùng lúc nhiều tiến trình có tổng không gian bộ nhớ(cần chiếm dụng của các tiến trình) lơn hơn tổng bộ nhớ vật lý. ####### VD: nhu cầu bộ nhớ cho 3 tiến trình chạy cùng lúc (P1=2MB, P2=4MB, ####### P3=3MB) vẫn chạy được trên bộ nhớ dung lượng khả dung 6MB. Nhược điểm: làm chậm hiệu suất xử lý.16 Cấp phát bộ nhớ cho tiến trìnhKỹ thuật cấp phát bộ nhớ:19 ####### Kỹ thuật cấp phát bộ nhớ ####### Cấp phát bộ nhớ liên tục ####### Phân chia vùng nhớ cố định ####### (Fixed partitioning) ####### Phân vùng nhớ động ####### (Dynamic partitioning) ####### Cấp phát bộ nhớ không liên tục ####### Kỹ thuật phân trang ####### (Paging) ####### Kỹ thuật phân đoạn ####### (Segmentation) Cấp phát bộ nhớ cho tiến trìnhKỹ thuật cấp phát bộ nhớ:Kỹ thuật cấp phát bộ nhớ liên tục: các process được cấp vùngnhớ liên tục (không gián đoạn)Kỹ thuật chia vùng nhớ cố định (Fixed partitioning)Kỹ thuật chia vùng nhớ động (Dynamic partitioning) Kỹ thuật cấp phát bộ nhớ không liên tục: một process được cấpbộ nhớ từ những vùng nhớ rời rạc (không liên tục)Kỹ thuật phân trang (Paging)Kỹ thuật phân đoạn (Segmentation) Nhược điểm của kỹ thuật cấp phát bộ nhớ liên tục:Dễ xảy ra phân mảnh bộ nhớ.Có trường hợp không đủ bộ nhớ cấp cho process dù tổng lượng freecòn nhiều (do bộ nhớ bị phân mảnh)20 Cấp phát bộ nhớ liên tụcKỹ thuật phân chia vùng nhớ cố định (fixed partitioning)Cơ chế:Bộ nhớ được chia thành các phân vùng (partition) cố định, kíchthước có thể bằng hoặc không bằng nhau.Mỗi process được nạp vào 1 partition nếu kích thước process nhỏ hơn.Nếu process có kích thước lớn hơn partition thì phải dùng cơ chếoverlay (chỉ nạp những thread cần dùng) Nhận xét:Không thực thi được các tiến trình phát sinh dữ liệu lớn hơn khônggian được cấp.Không hiệu quả do bị phân mảnh nội.Khi bị phân mảnh => không đủ bộ nhớ để nạp các process lớn.Không thể dời chuyển tiến trình trong bộ nhớ.Cơ chế overlay dễ gây chậm trễ trong xử lý tiến trình.21 Cấp phát bộ nhớ liên tụcKỹ thuật chia vùng nhớ động (dynamic partitioning)Cơ chế:HĐH dùng bảng quản lý không gian bộ nhớ (free / used partition).Khi process kết thúc, used partition được giải phóng và sẵn sàng đểcấp cho process khácVới mỗi process, HĐH xác định lượng bộ nhớ cần dùng và tham chiếuphần bộ nhớ free partition để quyết định cấp phát. Các chiến lược cấp phát bộ nhớ của dynamic partitioningFirst fit: tìm free partition phù hợp đầu tiên cấp cho processBest fit: tìm free partition vừa vặn nhất cấp cho process.Worst fit: tìm free partition chứa được process là cấp ngay.22 Kỹ thuật Phân trang (paging)Chuyển đổi địa chỉ trong phân trang:Địa chỉ luận lý của phân trang có dạng: p, dPhần tử p (page number): địa chỉ page trong pages table => xác đinhđược địa chỉ cơ sở (base address) của frame trên bộ nhớ.Phần tử d (page offset): độ dời (offset) của các bytes trong frame.25 Page table Kỹ thuật Phân trang (paging)Minh họa chuyển đổi địa chỉ trong phân trang:VD: bộ nhớ vật lý 32 B, chia thành 8 frame, mỗi frame = 4 B.Tiến trình P được cấp 4 pages, với page table như hình dưới.Minh họa địa chỉ luận lý (logical address): 1,3 (p=1, d=3):p = 1 , tương ứng frame 6 (frame 6 có based address là 24 ).Địa chỉ luận lý : 1,3 tương ứng với địa chỉ vật lý 24 + 3 = 27Dữ liệu tại địa chỉ vật lý 27 là ký tự “h”.26 Tính toán địa chỉ trong Paging:Số bit địa chỉ là số mũ của cơ số 2.Ví dụ: dùng 3 bit địa chỉ sẽ trỏ được 23 = 8 địa chỉ khác nhau. Dung lượng bộ nhớ cấp cho P = tổng số frames x frame sizehoặc: = tổng số pages x frame sizeNếu dùng số lũy thừa cơ số 2:Không gian bộ nhớ cấp cho P là: 2 mTổng số page frame dành cho P là: 2 pKích thước của frame là: 2 n Ta có:: 2 m = 2 p x 2 n = 2 p+nhay: 2 p = 2 m / 2 n = 2 m-nhay: 2 n = 2 m / 2 p = 2 m-pKỹ thuật Phân trang (paging)27 Tính toán địa chỉ trong Paging:Nếu:Dung lượng bộ nhớ cấp cho process P là 2 m (Bytes)Kích thước của page frame là 2 n (Bytes) Thì:Tổng số Page frame cấp cho Process là 2 m/ 2 n = 2 m-n (pages) Địa chỉ của không gian bộ nhớ luận lý có dạng (p,d), trong đó:Số bit dùng làm địa chỉ của p = m-n bits.Số bít dùng làm địa chỉ của d = n bits. Kỹ thuật Phân trang (paging)28 Thay thế trang (Page Replacement)Bộ nhớ ảo và vai trò của bộ nhớ ảoBộ nhớ ảo (virtual memory):Là một không gian lưu trữ trên bộ nhớ phụ (thường là đĩa cứng).Hệ điều hành chuyển mộ phần dữ liệu của process trong bộ nhớ chínhsang bộ nhớ ảo (cơ chế sang swapping) Ưu điểm:Bộ nhớ chính chứa được nhiều process hơn.Có thể chạy process kích thước lớn hơn bộ nhớ chính. Thực tiễn:Swap space (không gian bộ nhớ ảo) của Linux là “Swap partition”Swap space của Windows là tập Pagefile.31 Thay thế trang (Page Replacement)Dẫn nhập về Page Replacement (thay thế trang):Quy tắc xử lý process của Hệ điều hành:Process chỉ được running khi page dữ liệu nằm trong bộ nhớ chính.Nếu xảy ra hiện tượng page-fault (page mà process cần dùng khôngcó trong bộ nhớ chính) => page đó phải dược swap-in. Hai tình huống xảy khi swap-in:1 : bộ nhớ luận lý của process còn frame trống để chứa page => Hệđiều hành Swap-in và thực thi process bình thường.2 : bộ nhớ luận lý của process không còn frame trống để chứa page =>không thể thực thi process. Thay thế trang (Page Replacement) là giải pháp:Chọn một victim page (trang hy sinh) nào đó của process trong bộnhớ chính để swap-out sang bộ nhớ ảo.Swap-in trang (page) cần dùng vào frame mới được giải phóng.32 Thay thế trang (Page Replacement)Các giải thuật thay thế trang:Giải thuật thay thế trang là lựa chọn victim page trong bộ nhớchính nhường chỗ cho page mà process cần dùng khi swap-in.Giải thuật FIFO (First In – First Out):page nào nạp vào trước sẽ được chọn làm victim page trước. Giải thuật OTP (Optimal):page nào sẽ sử dụng lại ở tương lai xa nhất, page đó sẽ được chọnlàm victim page.OTP tham chiếu vào chuỗi page sẽ dùng trong tương lai của processnên xác xuất gây page-fault (lỗi trang) là thấp nhất. Giải thuật LRU (Least Recently Used):page nào mới được sử dụng, page đó sẽ không được chọn làmvictim page.LRU bit tham khảo (reference bit) để nhận biết page nào mới dùng33 Thay thế trang (Page Replacement)Minh họa các giải thuật thay thế trang:Process P dự kiến sẽ lần lượt thực thi các page dữ liệu theo chuỗithứ tự như hình.F là thời điểm cần thay trang. Mỗi giải thuật thực hiện khác nhau34 An toàn cho vùng nhớ trong PagingBảo vệ bộ nhớ trong phân trang:Phương pháp 2: gắn các bit bảo vệ (protection bit) vào mỗi entry(mục nhập) trong bảng phân trang.Giá trị của protection bit sẽ xác định thuộc tính của entry:Thuộc tính: read-only (bit 0 ):Thuộc tính: read-write ( 1 )37 ####### pages frame protection ####### 0 20 0 ####### 1 24 0 ####### 2 4 1 ####### 3 8 1 Kỹ thuật Phân đoạn (Segmentation)Không gian địa chỉ bộ nhớ phân đoạn:Không gian địa chỉ (bộ nhớ luận lý) là một tập các phân đoạn(segments) kích thước khác nhau.Bảng phân đoạn (segment table) gồm nhiều dòng index, mỗi dòngcó 2 thông tin cơ bản:Limit: kích thước của đoạn.Base address: địa chỉ vật lý nơi bắt đầu của phân đoạn trong bộ nhớ.38 Kỹ thuật Phân đoạn (Segmentation)Chuyển đổi địa chỉ phân đoạn:Địa chỉ luận lý phân đoạn gồm 2 phần tử: s: số hiệu phân đoạn trỏ đến các dòng chỉ mục trên bảng phân đoạn.Giá trị của s từ 0 đến segment cuối trong bảng.d: địa chỉ tương đối trỏ đến các địa chỉ offset trong đoan.Do kích thước các segment không bằng nhau => phải check d trước.đến giới hạn chiều dài của phân đoạn.39 Kỹ thuật Phân đoạn (Segmentation)Ưu điểm của kỹ thuật phân đoạn:Mỗi phân đoạn biểu diễn cho một phần của chương trình.Lập cơ chế bảo mật riêng biệt cho từng phần chương trình.Khả năng chia sẻ chương trình ở mức độ phân đoạn.40 |
