Giáo trình môn học Trình biên dịch - Chương 7: Quản lý bộ nhớ trong thời gian thực thi

CHƯƠNG 7 QUẢN LÝ BỘ NHỚ TRONG THỜI GIAN THỰC THI 7.1. Các phần tử yêu cầu cấp phát bộ nhớ trong thời gian thực thi Tất cả các phần tử cần được cấp phát bộ nhớ, bao gồm: 1. Đoạn mã của chương trình được biên dịch. 2. Các chương trình hệ thống cần thiết trong thời gian thực thi. 3. Cấu trúc dữ liệu và hằng do người sử dụng định nghĩa. 4. Các điểm trở về của chương trình con. 5. Môi trường tham khảo. 6. Các vị trí nhớ tạm cho việc tính trị biểu thức. 7. Nhập, xuất bộ đệm. 8. Các bảng, trạng thái thông tin. Ngoài dữ liệu và các chương trình được biên dịch, các tác vụ cũng cần bộ nhớ: 1) Gọi chương trình con và các tác vụ trở về. 2) Khởi tạo và hủy bỏ cấu trúc dữ liệu. 3) Tác vụ thêm vào hoặc loại bỏ các phần tử. 7.2. Các vấn đề về ngôn ngữ nguồn Chương trình con Mô phỏng 7.1. Chương trình Pascal đọc và sắp xếp thứ tự các số nguyên (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) program sort (input, output); var a: array [010]; procedure readarray; var i: integer; begin for i := 1 to 9 do read (a [1]); end; function partition (y, z: integer): integer; var i, j, x, v: integer; begin end; procedure quicksort (m, n: integer); (13) (14) (15) (16) (17) (18) (19) (20) (21) (22) (23) (24) (25) var i: integer; begin if (n > m) then begin i := partition (m, n); quicksort (m, i – 1); quicksort (i + 1, n); end; end; begin a[0] := -9999; a[10] := 9999; readarray; quicksort (1, 9); end Cây hoạt động (activation tree) Cây hoạt động dùng để miêu tả con đường mà sự điều khiển đi vào và đi ra khỏi các hoạt động của chương trình. Một số tính chất của cây hoạt động: 1. Mỗi nút của cây tượng trưng cho một hoạt động của chương trình con. 2. Nút gốc (root) tượng trưng cho hoạt động của chương trình chính. 3. Nút a là cha của nút b nếu và chỉ nếu dòng điều khiển đi từ sự hoạt động a sang sự hoạt động b. 4. Nút a ở bên trái nút b nếu và chỉ nếu thời gian sống của a xuất hiện trước thời gian sống của b. Mô phỏng 7.2. Các phát biểu in của chương trình ở mô phỏng 7.1 miêu tả sự thực thi của nó. Sự thực thi chương trình bắt đầu vào readarray ra khỏi readarra vào quicksort (1,9) vào partition (1,9) ra khỏi partition (1,9) vào quicksort (1,3) ra khỏi quicksort (1,3) vào quicksort (5,9) ra khỏi quicksort (5,9) ra khỏi quicksort (1,9) Sự thực thi kết thúc Thí dụ 6.1. s: viết tắt cho sort p: viết tắt cho partition r: viết tắt cho readarray q: viết tắt cho quicksort S q(1,9) q(1,3) r q(5, 9) p(1,9) q(7,9) p(5,9) q(5,5) p(7,9) q(7,7) q(2,3) p(1,3) q(1,0) q(3,3)p(2,3) q(2,1) Hình 7.1. Cây hoạt động được xây dựng từ chuỗi xuất ở mô phỏng 7.2. Stack điều khiển (Control stack) S r q(1,9) p(1,9) q(1,3) p(1,3) q(2.3) q(1,0) Hình 7.2. Stack điều khiển bao gồm các nút trên con đường từ s đến q (2,3) và trở về • Tầm vực của sự khai báo Khai báo có thể tường minh, Var I: integer nhưng có thể là khai báo ngầm như Fortran, khi ta dùng tên biến i mà không khai báo, Fortran mặc nhiên hiểu i là biến nguyên. Tầm ảnh hưởng của các khai báo được quy tắc tầm vực quyết định. • Sự ràng buộc của tên Môi trường là tên của hàm, ánh xạ tên đến vị trí nhớ và trạng thái là hàm ánh xạ từ vị trí nhớ đến trị mà nó lưu giữ. tên vị trí nhớ trị Hình 7.3. Phép chiếu hai mức từ tên đến trị Sự ràng buộc chính là bản sao động của khai báo, trong thời gian thực thi. Bảng 7.1. Các khái niệm tĩnh và động của chương trình con 7.3. Tổ chức ký ức Sự phân chia bộ nhớ trong thời gian thực thi Trong thời gian dịch, trình biên dịch đã tính toán kích thước bộ nhớ dành cho chương trình đối tượng, nó bao gồm: 1. Mã của chương trình đối tượng. 2. Các đối tượng dữ liệu. 3. Một phần trong stack điều khiển (stack trung tâm) lưu giữ bản ghi hoạt động của chương trình con. Khái niệm tĩnh Bản sao động Định nghĩa chương trình con Sự hoạt động của chương trình con Khai báo tên Sự ràng buộc tên với vị trí nhớ Tầm vực ý nghĩa của khai báo Thời gian sống của sự ràng buộc tên Mô phỏng 7.2. Sự phân chia bộ nhớ trong thời gian thực thi cho vùng mã của chương trình và vùng dữ liệu. Không phải tất cả các ngôn ngữ lập trình đều dùng stack điều khiển và heap, nhưng Pascal và C thì dùng cả hai. Bản ghi hoạt động (Activation record) 1. Vùng giá trị khứ hồi 2. Vùng thông số 3. Đường liên kết động 4. Đường liên kết tĩnh 5. Các trạng thái máy 6. Vùng dữ liệu cục bộ 7. Vùng nhớ tạm Mã của chương trình đối tượng Dữ liệu tĩnh Stack điều khiển heap Mô phỏng 7.3. Dạng tổng quát của bản ghi hoạt động 7.4. Chiến thuật cấp phát bộ nhớ 1. Cấp phát tĩnh 2. Quản trị bộ nhớ theo cơ chế stack 3. Cơ chế heap Giá trị khứ hồi Thông số thực Đường liên kết động Đường liên kết tĩnh Các trạng thái máy Dữ liệu cục bộ Vùng nhớ tạm 1. Cấp phát tĩnh (Static allocation) Cơ chế này sẽ dẫn đến một số hạn chế sau đây: 1) Kích thước và vị trí của đối tượng dữ liệu phải được xác định ngay trong thời gian biên dịch. 2) Không cho phép gọi đệ quy. 3) Không cho phép cấp phát động các đối tượng dữ liệu. Mô phỏng 7.4. Chương trình trong ngôn ngữ Fortran. (1) (2) (3) (4) (5) (6) (7) (8) (9) PROGRAM CNSUME CHARACTER * 50 BUF INTEGER NEXT CHARACTER C, PRDUCE DATA NEXT /1/, BUF /’’/ C = PRDUCE () BUF (NEXT: NEXT) = C NEXT = NEXT + 1 IF (C. NE. ‘’) GOTO 6 (10) (11) (12) (13) (14) (15) (16) (17) (18) (19) (20) (21) (22) (23) WRITE (*, ‘(A)’) BUF END CHARACTER FUNCTION PRDUCE () CHARACTER * 80 BUFFER INTEGER NEXT SAVE BUFFER, NEXT DATA NEXT /81/ IF (NEXT. GT. 80) THEN READ (*, ‘’(A)’’) BUFFER NEXT = 1 END IF PRDUCE = BUFFER (NEXT: NEXT) NEXT = NEXT + 1 END Mã cho CNSUME Mã cho PRDUCE CHARACTER * 50 BUF INTEGER NEXT CHARACTER C CHARACTER * 80 BUFFER INTEGER NEXT mã của chương trình Bản ghi hoạt động CNSUME Dữ liệu tĩnh Bản ghi hoạt động PRDUCE Hình 7.4. Vị trí nhớ tĩnh cho các biến cục bộ cho chương trình Fortran 77 Thí dụ 7.2. Chương trình ở (mô phỏng 7.4) sẽ làm việc với các giá trị cục bộ được lưu lại qua các lần hoạt động. Các kýhiệu xuất ra trong chương trình chính CNSUME, được lấy từ bản ghi hoạt động của PRDUCE là hello, do CNSUME gọi PRDUCE 6 lần, như ở (H.7.5). 2. Cấp phát theo cơ chế stack CNSUME PRDUCE h PRDUCE e PRDUCE l PRDUCE l PRDUCE o PRDUCE Hình 7.5. Các ký hiệu được trả về qua các lần hoạt động của PRDUCE cây hoạt động stack điều khiển s a: array s a: array r i: integer s a: array q(1,9) i: integer s s r s q(1,9)r s a: array q(1,9) i: integer p(1,9) i, j, x, v: integer s a: array q(1,9) i: integer q(1,3) i: integer q(1,0) i: integer s r q(1,9) p(1,9) s r q(1,9) p(1,9) q(1,3) p(1,3) q(1,0) s a: array q(1,9) i: integer q(1,3) i: integer s q(1,9) p(1,9) q(1,3) q(1,0)p(1,3) Hình 7.6. Các bản ghi hoạt động được cấp phát và loại bỏ khỏi stack điều khiển. Sự gọi chương trình con 1. Chương trình gọi tính toán các thông số thực và cất vào vùng thông số của bản ghi hoạt động của chương trình bị gọi. 2. Chương trình bị gọi lưu giữ địa chỉ khứ hồi vào vùng trị trả về và trị top-sp vào vùng liên kết, tăng top-sp lên một khoảng vị trí nhớ, chính là kích thước của vùng biến tạm và biến cục bộ của nó với kích thước vùng thông số, trị trở về, đường liên kết và các trạng thái máy của chương trình bị gọi. 3. Chương trình bị gọi sẽ lưu bộ nhớ giá trị, các thanh ghi, đường liên kết và trạng thái khác. 4. Chương trình bị gọi khởi động các giá trị cục bộ của nó và bắt đầu thực thị. .. Thông số và trị trở về Đường liên kết và trạng thái của máy Biến tạm và biến cục bộ Thông số và trị trở về Đường liên kết và trạng thái của máy Biến tạm và biến cục bộ Đường liên kết Bản hoạt động của chương trình gọi Những thông tin chương trình gọi có trách nhiệm cung cấp Bản hoạt động của chương trình bị gọi top-sp Các thông tin chương trình bị gọi có trách nhiệm cung cấp Hình 7.7. Sự phân chia công việc giữa chương trình gọi và bị gọi Chuỗi trở về có thể là các công việc sau 1. Chương trình bị gọi gửi các giá trị trở về vào bản ghi hoạt động của chương trình con. 2. Chương trình bị gọi xác lập lại trị: top-sp cho chương trình gọi, trị các thanh ghi, địa chỉ khứ hồi. 3. Chương trình gọi sẽ sử dụng các giá trị trong vùng biến tạm, giá trị trở về để tính toán các biểu thức sau này khi nó thực thi tiếp tục. Dữ liệu có kích thước thay đổi Ở một số ngôn ngữ như C, Algol, dãy được phép có kích thước thay đổi trong thời gian thực thi. Thí dụ 7.4. Cho khai báo dãy trong Algol như sau: DIMENSION A [L1 : U1, L2: U2, Ln: Un] di là kích thước chiều thứ I, được tính: di = Ui – Li + 1 Vùng thông tin cho dãy A là: L1 U1 d1 L2 U2 d2 Ln Un dn n Vùng p sẽ chức địa chỉ bắt đầu của vị trí nhớ dãy A Hình 7.8. Vùng thông tin của dãy trong bản ghi hoạt động Thí dụ 7.5. DIMENSION p[1: n, x: y], q[1: m]; Hình 7.9. Bản ghi hoạt động của chương trình con A, có các biến dãy p, q với kích thước thay đổi Thông số và trị trở về Liên kết và các trạng thái máy Biến tạm và biến cục bộ Thông số và trị trở về Liên kết và các trạng thái máy Biến tạm và biến cục bộ 1 n d1 x y d2 2 1 m d1 1 p q Vùng biến tạm và các biến cục bộ của bản ghi hoạt động của A Bản ghi hoạt động của chương trình gọi chương trình con A Phần tĩnh của bản ghi hoạt động của chương trình con A Bản ghi hoạt động của chương trình con A Phần biến thiên của A Tham chiếu treo (Dangling reference) Mô phỏng 7.5. Đoạn chương trình Pascal gây ra tham chiếu treo. var p, q: ^ integer; begin new(p); q: = p; dispose (p) end; pp q p q đối tượng được cấp phát new (p) q = p dispose (p) đối tượng dữ liệu bị loại bỏ Hình 7.10. Tham chiếu treo q xuất hiện do lệnh dispose (p). 3. Cấp phát theo cơ chế heap 1. Trị của các biến cục bộ được lưu giữ ngay cả khi sự hoạt động của chương trình con tương ứng không còn nữa. 2. Sự hoạt động của chương trình bị gọi sống sau cả chương trình gọi. Bảng 7.2. Các bản ghi hoạt động của heap và stack cùng sự so sánh với cây hoạt động. Các bản ghi hoạt động trên stack Vị trí trên cây hoạt động Các bản ghi hoạt động trong heap Ghi chú Theo cơ chế heap r đã hết thực thi nhưng bản ghi hoạt động của nó vẫn còn tồn tại s liên kết động q(1,9) liên kết động s liên kết động r liên kết động q(1,9) liên kết động S r q(1,9) Cấp phát vị trí nhớ cho các khối có kích thước cố định Cấp phát vị trí nhớ cho các khối có kích thước thay đổi đầu danh sách 1 2 3 4 5 6 đầu danh sách a) b) Hình 7.11. Các khối bị loại bỏ sẽ được thêm vào danh sách của các khối chưa sử dụng. 2 3 4 5 6 Hình 7.12. Các khối đang được sử dụng và đang trống Loại bỏ ngầm vị trí nhớ Mô phỏng 7.6. Dạng của một khối 1. Đếm các tham khảo 2. Kỹ thuật đánh dấu kích thước khối số lượng con trỏ tham khảo tới đánh dấu các con trỏ chỉ đến các khối thông tin của người sử dụng 1 1 Hình 7.13. Hai khối này là rác mặc dù vẫn có số đếm tham khảo là 1 7.5. Truy xuất biến không cục bộ Mô phỏng 7.7. Chương trình dùng để minh họa việc truy xuất biến không cục bộ. program MAIN var x: integer; procedure sub1; var x: real; begin read (x) sub2; end; procedure sub2; (Không có khai báo x) begin write (x); end begin {main} sub1; end. Cấu trúc khối Quản trị bộ nhớ và việc cấp phát vị trí nhớ cho các khối của Algol Mỗi bản ghi hoạt động gồm các thành phần chính sau đây: 1. Dãy display của chương trình con. Nếu chương trình ở cấp i thì display chiếm i + 1 ô nhớ. 2. Vị trí nhớ chứa trị stack top của chương trình con. 3. Các thông tin về địa chỉ khứ hồi, liên kết tĩnh và liên kết động, stack_top của chương trình con gọi. 4. Các vị trí nhớ dành cho các thông số của chương trình con. Các phần 1, 2, 3, 4 tạo thành phần cơ bản của chương trình con. 5. Mỗi chương trình con có thể có nhiều khối, mỗi khối được cấp phát một khoảng ký ức để chứa các thành phần sau: 1) Vị trí nhớ chứa trị stack top của khối. 2) Vị trí nhớ dành cho các biến cục bộ là biến đơn. 3) Các thông tin về dãy (nếu khối có khai báo dãy). 4) Vị trí nhớ chứa các biến tạm. Thí dụ 7.9. Cho chương trình con trong Algol. procedure A (x, y); integer x, y; L1: begin real z; array B [x: y]; L2: begin real: D, E; .. .. end; L3: begin array a[a: x]; L4: begin real E; .. . end; end; end; B1 B2 B3 B4 B Display của A Stack-top của A Các thông số RA, SL, DL Thông số X, Y Trị stack-top của B1 Z Vùng thông tin của dãy B Stack-top của B2 d, E B a Phần cơ bản của A Vị trí nhớ của khối B1 Stack-top của B3 Vùng thông tin của dãy a Stack-top của B4 E Phần cố định của chương trình con A Hình 7.16. Bản ghi hoạt động của chương trình con A có chứa các khối Các hành vi thâm nhập vào một khối và ra khỏi khối - Hành vi thâm nhập vào một khối - Hành vi ra khỏi khối Tầm vực tĩnh với các chương trình con không lồng nhau Tầm vực tĩnh với các chương trình con lồng nhau Bảng tầm vực (display) Để truy xuất biến không cục bộ, người ta sử dụng bảng tầm vực. Tuy nhiên, liên kết tĩnh vẫn tồn tại trong các bản ghi hoạt động, dùng để phục hồi hình ảnh bảng tầm vực khi chương trình con cấp i gọi chương trình con cấp j, với i > j và sau khi chương trình con cấp j hoàn tất sự thực thi. Thí dụ 7.12. Cho chương trình sau: Mô phỏng 7.10. Chương trình Pascal có cấu trúc khối program M; : procedure P; : procedure Q; begin : P ; end; procedure R; begin Q; end; begin; R; end; begin P; end; Mức tầm vực của các chương trình con là: M P Q R và M gọi P gọi R gọi Q gọi P Các bước thực thi Display Stack điều khiển 1 M 0 M M 2 M gọi P 0 M M 1 P P 3 P gọi R 0 M M 1 P P 2 R R Q 5 Q gọi P 0 M M 1 P’ P R Q P’ 4 R gọi Q 0 M M 1 P P 2 Q R SL 6 0 M M 1 P P Q R Q P’ hoàn tất thực thi trả sự điều khiển cho Q Hình 7.20. Các bước gọi chương trình con cùng với sự thay đổi nội dung của display và stack điều khiển Tầm vực động 7.6. Truyền thông số 1. Thông số nhập – xuất - Truyền bằng tham khảo - Truyền bằng trị 2. Thông số chỉ nhập - Truyền bằng trị - Truyền bằng trị hằng 3. Thông số chỉ xuất - Truyền thông số bằng tên Thí dụ 7.6. Cho chương trình type VECT = array [1 .. 3] of integer; procedure SUB2 (var I, J: integer); begin I := I + 1; J := J + 1; write (I, J); end; procedure SUB1; var A: VECT; K :integer; begin A[1] := 7; A[2] := 8; A[3] := 9; K :=2: SUB2 (K, A[K]); for K := 1 to 3 do write (A [K]); end; Stack trung tâm stack trung tâm sub 1 sub 1 liên kết liên kết A[1] A[1] A[2] A[2] A[3] A[3] K K sub 2 sub 2 liên kết liên kết I I J J a) b) Thunk tính toán A[k] Thunk tính toán K Hình 7.23. Phương pháp truyền thông số bằng tên và bằng tham khảo Chương trình con đóng vai trò thông số Thí dụ 7.7. Cho chương trình program MAIN; var X : real; procedure SUB2 (X, Y: real; function F (u: real): real); var z: real; begin z := abs (Y - X); z := (F (X) + F (Y)) * Z/2; write (Z); end; procedure SUB1; var Y :real; function FUNC: (V: real): real; begin FUNC := X + V + Y end; begin Y := 1 SUB2 (0, 1, FUNC) end; begin X := 3; SUB1; end. Nhìn vào chương trình trên chúng ta thấy trình tự thực thi của chương trình như sau: MAIN gọi SUB1 gọi SUB2 (0, 1, FUNC) gọi FUNC Bảng 7.3. Stack trung tâm khi một chương trình con gọi chương trình con khác thông qua thông số hình thức Bước 1 Sự thực thi Stack trung tâm 1 2 3 1 2 MAIN MAIN gọi SUB1 liên kết tĩnh MAIN X = 3 SUB2 SUB1 liên kết tĩnh MAIN X = 3 SUB2 SUB1 3 SUB1 gọi SUB2 liên kết tĩnh Y = 1 SUB1 FUNC liên kết tĩnh MAIN X = 1 SUB2 SUB1 SUB1 liên kết tĩnh Y = 1 FUNC liên kết tĩnh SUB2 X Y F địa chỉ phần mã của FUNC 4 SUB2 gọi FUNC z liên kết tĩnh MAIN X = 1 SUB2 SUB1 SUB1 liên kết tĩnh Y FUNC SUB2 liên kết tĩnh X Y F địa chỉ phần mã của FUNC Z FUNC liên kết tĩnh V