bài tập lớn đề tài quản lý bộ nhớ

Sau khi biên dịch, các lệnh và hầu hết các dữ liệu đều đã có địa chỉ xác định.Khích thước tối đa của không gian địa chỉ không phụ thuộc vào việc bao nhiêu bộ nhớ RAM vật lý thực sự có th

TRƯỜNG ĐẠI HỌC PHENIKAA KHOA KHOA HỌC CƠ BẢN

⸎⸎⸎⸎⸎

BÀI TẬP LỚN

SINH VIÊN THỰC HIỆN : TÔ VĂN ANH QUÂN

BÙI MINH QUÂN NGUYỄN VĂN ĐỨC NGÔ QUỐC TRUNG LỚP : Hệ điều hành-1-1-22(N04) NĂM HỌC : 2022 - 2023

MỞ ĐẦU

Bộ nhớ chính là thiết bị lưu trữ duy nhất thông qua đó CPU có thể trao đổi thông tin với môi trường ngoài, do vậy nhu cầu tổ chức, quản lý bộ nhớ là một trong những nhiệm vụ trọng tâm hàng đầu của hệ điều hành Bộ nhớ chính được tổ chức như một mảng một chiều các từ nhớ (word), mỗi từ nhớ có một địa chỉ VIệc trao đổi thông tin với môi trường ngoài được thực hiện thồn qua các thao tác đọc hoặc ghi dữ liệu vào một địa chỉ cụ thể nào đó trong bộ nhớ

Hầu hết các hệ điều hành hiện đại đều cho phép chế độ đa nhiệm nhằm nâng cao hiệu suất của CPU Tuy nhiên kỹ thuật này lại làm nảy sinh nhu cầu chia sẻ bộ nhớ giữa các tiến trình khác nhau Và bài viết này sẽ cho bạn thêm kiến thức trìu tượng

về không gian bộ nhớ, bộ nhớ api và cách các tiến trình làm việc với bộ nhớ thông qua cơ chế dịch địa chỉ

NỘI DUNG

1.Address Spaces

-Không gian địa chỉ (memory address space) là gì? Đó là dải các số được dùngđể đánh địa chỉ cho các lệnh, hoặc dữ liệu của chương trình Sau khi biên dịch, các lệnh và hầu hết các dữ liệu đều đã có địa chỉ xác định

Khích thước tối đa của không gian địa chỉ không phụ thuộc vào việc bao nhiêu bộ nhớ RAM vật lý thực sự có thể sử dụng được, do đó nó được biết đến là không gian địa chỉ ảo (virtual address space) Một lý do khác cho thuật ngữ này, mỗi process có suy nghĩ rằng chúng chỉ sống trong vùng địa chỉ này và không hề tồn tại các process khác từ quan điểm của chúng ứng dụng không cần quan tâm đến các ứng dụng khác và có thể hoạt động như thể chúng là quá trình duy nhất, điều này không đúng với thực tế nên nó được gọi là không gian địa chỉ ảo

Linux chia virtual address space thành 2 phần: kernel space và userspace Mỗi user process trong hệ thống sở hữu bộ nhớ có kích thước từ 0 -> TASK_SIZE Phần địa chỉ từ TASK_SIZE -> 264/232 được dành cho kernel và không thể bị truy cập từ user process TASK_SIZE là một hằng số kiến trúc mà nó dùng để chia tỷ lệ không gian bộ nhớ Ví dụ trong IA-32(32 bit), không gian địa chỉ được chia ra 3GiB cho mỗi process và 1GiB còn lại dành cho kernel (232 = 4GiB)

Note: 210 = 1KiB, 220 = 1Mib, 230 = 1Gib

Cách chia này không phụ thuộc vào việc có bao nhiêu bộ nhớ RAM có thể sử dụng Vì có sự ảo hóa nên mỗi user process nghĩ rằng nó có 3GiB bộ nhớ Các userspace của các process thực sự tách biệt với nhau nhưng kernel space ở vùng trên cùng của không gian địa chỉ ảo thì luôn giống nhau

-hiện nay, đa số các hệ điều hành sử dụng cơ chế virtual memory để quản lý bộ nhớ.Nhưng vẫn còn một số hệ điều hành không dùng virtual memory, ví dụ uCLinux

2.Địa chỉ ảo(virtual address space)

Khống như hầu hết các kernel hiện đại, Linux sử dụng 1 kỹ thuật được gọi là quản

lý bộ nhớ ảo (virtual memory management) nhằm mục đích sử dụng hiệu quả cả CPU và RAM (bộ nhớ vật lý hay, cũng có thể được gọi là bộ nhớ thật) Kỹ thuật này khai thác 1 đặc điểm chung về truy cập bộ nhớ của hầu hết các chương trình là locality of reference (dịch nôm na là tham chiếu vùng), được biểu hiện qua 2 đặc tính sau:

• Spatial locality: chương trình có xu hướng tham chiếu đến địa chỉ bộ nhớ gần với phân vùng bộ nhớ mà nó đang truy cập Vì chương trình C xử lý các chỉ lệnh một cách tuần tự, hoặc chương trình xử lý các struct (vùng nhớ của các thành phần của struct được sắp xếp liền kề nhau)

• Temporal locality: chương trình có xu hướng truy cập cùng 1 vùng nhớ trong các thời điểm rất gần nhau Ví dụ trường hợp xử lý vòng lặp, các vùng nhớ có thể được truy cập nhiều lần các thời điểm gần nhau mỗi khi vòng lặp quay lại Nhìn vào đăc tính locality of reference này, chúng ta có thể rút ra là 1 chương trình

có thể chạy được khi chỉ cần 1 phần không gian địa chỉ của nó trên RAM, thay vì tải toàn bộ không gian bộ nhớ của tiến trình

Một bộ nhớ ảo chia không gian bộ nhớ của 1 tiến trình ra làm nhiều đoạn nhỏ có kích thước cố định được gọi là các trang (page) Tương tự, RAM cũng được chia làm nhiều đoạn nhỏ cùng kích thước được gọi là page frame Trong 1 thời điểm, chỉ 1 vài trang của tiến trình cần có mặt trong các frame của RAM để chạy Các trang chưa được sử dụng của chương trình sẽ được để trong phân vùng swap (là phân vùng dự trữ của ổ cứng hỗ trợ lưu trũ bổ sung cho RAM) và sẽ được tải vào RAM khi cần thiết

Page table

Để ánh xạ giữa các trang của không gian bộ nhớ ảo đến các frame của bộ nhớ vật

lý, kernel tạo ra 1 bảng trang (page table) cho mỗi tiến trình Mỗi entry của page table ứng với 1 trang của bộ nhớ ảo cho phép chỉ ra vị trí của trang đó trong RAM hoặc chỉ ra nó đang nằm ở phân vùng swap của ổ cứng

Để hình dung rõ hơn về page table, chúng ta xem hình dưới đây:

Hình 1: Page Table của một tiến trình

Trong thực tế, không cần phải xây dựng bảng ánh xạ cho tất cả không gian địa chỉ

bộ nhớ ảo của tiến trình Trái lại, thường chỉ có 1 phần số lượng các trang trong số

đó được sử dụng và cần phải có bảng ánh xạ cho các trang đó Vì vậy, về mặt lý thuyết không cần phải xây dựng entry cho toàn bộ không gian bộ nhớ ảo của tiến trình

3.Multiprogramming and Time Sharing

3.1Hệ thống đa chương trinh( multiprogram) là gì?

Đa chương trình là sự chuyển đổi nhanh chóng của CPU giữa một số chương trình Một chương trình thường được tạo thành từ một số nhiệm vụ Một tác vụ thường kết thúc với một số yêu cầu di chuyển dữ liệu sẽ yêu cầu một số hoạt động I / O được thực hiện Đa nhiệm thường được thực hiện để giữ cho CPU bận rộn, trong khi chương trình hiện đang chạy đang thực hiện các hoạt động I / O So với các lệnh thực thi khác, các thao tác I / O cực kỳ chậm Ngay cả khi một chương trình chứa một số lượng rất nhỏ các thao tác I / O, thì phần lớn thời gian dành cho chương trình được dành cho các hoạt động I / O đó Do đó, việc sử dụng thời gian nhàn rỗi này và cho phép một chương trình khác sử dụng CPU tại thời điểm đó sẽ làm tăng hiệu suất sử dụng CPU Đa chương trình ban đầu được phát triển vào cuối những năm 1950 như một tính năng của hệ điều hành và lần đầu tiên được sử dụng trong máy tính máy tính lớn Với sự ra đời của bộ nhớ ảo và công nghệ máy ảo, việc sử dụng đa chương trình đã được tăng cường

3.2 Hệ thống chia sẻ thời gian là gì?

Chia sẻ thời gian, được giới thiệu vào năm 1960, là sự chia sẻ tài nguyên máy tính giữa một số người dùng cùng một lúc Trong hệ thống chia sẻ thời gian, một số thiết bị đầu cuối được gắn vào một máy chủ chuyên dụng duy nhất có CPU riêng của nó Các hành động / lệnh được thực thi bởi hệ điều hành của hệ thống chia sẻ thời gian có khoảng thời gian rất ngắn Do đó, CPU được chỉ định cho người dùng tại các thiết bị đầu cuối trong một khoảng thời gian ngắn, do đó người dùng trong thiết bị đầu cuối có cảm giác rằng cô ấy có một CPU dành riêng cho mình phía sau thiết bị đầu cuối của mình Khoảng thời gian ngắn mà một lệnh được thực hiện trên

hệ thống chia sẻ thời gian được gọi là lát thời gian hoặc lượng tử thời gian Với sự phát triển của internet, các hệ thống chia sẻ thời gian đã trở nên phổ biến hơn vì các trang trại máy chủ đắt tiền có thể chứa một lượng lớn khách hàng chia sẻ cùng

một tài nguyên Vì các trang web hoạt động chủ yếu theo từng đợt hoạt động sau

đó là khoảng thời gian không hoạt động, thời gian không hoạt động của một khách hàng có thể được sử dụng hiệu quả bởi khách hàng kia mà không ai trong số họ nhận thấy sự chậm trễ

3.3Đa chương trình so với Hệ thống chia sẻ thời gian

Đa chương trình là phân bổ nhiều hơn một chương trình đồng thời trên một hệ thống máy tính và các tài nguyên của nó Đa chương trình cho phép sử dụng CPU một cách hiệu quả bằng cách cho phép nhiều người dùng khác nhau sử dụng CPU

và các thiết bị I / O một cách hiệu quả Đa chương trình đảm bảo rằng CPU luôn có thứ gì đó để thực thi, do đó làm tăng hiệu suất sử dụng CPU Mặt khác, Chia sẻ thời gian là việc chia sẻ tài nguyên máy tính giữa một số người dùng cùng một lúc

Vì điều này sẽ cho phép một số lượng lớn người dùng làm việc trong một hệ thống máy tính duy nhất cùng một lúc, nó sẽ giảm chi phí cung cấp khả năng tính toán

III.Interlude: API memory

1 Các loại bộ nhớ

Khi chạy chương trình C, có hai loại bộ nhớ được cấp phát Đầu tiên được gọi

là bộ nhớ ngăn xếp, và các phân bổ và phân bổ của nó được quản lý ngầm bởi trình biên dịch cho bạn, người lập trình; vì lý do này đôi khi nó được gọi là bộ nhớ tự động

Khai báo bộ nhớ trên ngăn xếp trong C rất dễ dàng Ví dụ: giả sử bạn cần một

số khoảng trống trong hàm func () cho một số nguyên, được gọi là x Để khai báo một phần bộ nhớ như vậy, bạn chỉ cần làm như sau:

void func () {

int x; // khai báo một số nguyên trên ngăn xếp

}

Trình biên dịch thực hiện phần còn lại, đảm bảo tạo khoảng trống trên ngăn xếp khi bạn gọi vào func () Khi bạn trở về từ hàm, trình biên dịch sẽ phân bổ bộ nhớ cho bạn; do đó, nếu bạn muốn một số thông tin tồn tại bên ngoài lệnh gọi, tốt hơn hết bạn không nên để thông tin đó trên ngăn xếp

Chính nhu cầu về bộ nhớ tồn tại lâu dài này đã đưa chúng ta đến loại bộ nhớ thứ hai, được gọi là bộ nhớ heap, nơi tất cả các phân bổ và phân bổ được xử lý rõ ràng Dưới đây là một ví dụ về cách người ta có thể phân bổ một số nguyên trên heap: void func () {

int * x = (int *) malloc (sizeof (int));

}

Do bản chất rõ ràng của nó và vì cách sử dụng đa dạng hơn, bộ nhớ heap đặt ra nhiều thách thức hơn cho cả người dùng và hệ thống

2 The malloc () Call

Lệnh malloc () call khá đơn giản: bạn chuyển nó vào một kích thước yêu cầu một số phòng trên heap, và nó thành công và trả lại cho bạn một con trỏ đến không gian mới được cấp phát, hoặc không thành công và trả về NULL

Trang hướng dẫn cho thấy những gì bạn cần làm để sử dụng malloc; gõ man malloc tại dòng lệnh và bạn sẽ thấy:

#include <stdlib.h>

void *malloc (size_t size);

Từ thông tin này, bạn có thể thấy rằng tất cả những gì bạn cần làm là bao gồm tệp tiêu đề stdlib.h để sử dụng malloc

Tham số đơn malloc () nhận có kiểu size_t, nó chỉ đơn giản mô tả bạn cần bao nhiêu byte Các quy trình và macro khác nhau được sử dụng Ví dụ: để phân bổ không gian cho giá trị dấu phẩy động có độ chính xác kép, bạn chỉ cần thực hiện như sau:

double * d = (double *) malloc (sizeof (double));

3 The free () Call

Hóa ra, phân bổ bộ nhớ là một phần dễ dàng của phương trình; biết khi nào, bằng cách nào và thậm chí nếu để giải phóng bộ nhớ mới là phần khó Để giải phóng bộ nhớ heap không còn được sử dụng, lập trình viên chỉ cần gọi free (): int *x = malloc (10 * sizeof (int));

free (x);

Quy trình nhận một đối số, một con trỏ được trả về bởi malloc () Do đó, ta có thể nhận thấy, kích thước của vùng được cấp phát không được người dùng chuyển vào và phải được theo dõi bởi chính thư viện cấp phát bộ nhớ

4 Các lỗi phổ biến

Quên phân bổ bộ nhớ

Nhiều quy trình mong đợi bộ nhớ được cấp phát trước khi bạn gọi chúng Ví dụ: strcpy thường trình (dst, src) sao chép một chuỗi từ con trỏ nguồn sang con trỏ đích Tuy nhiên, nếu không cẩn thận, bạn có thể làm như sau:

char * src = "xin chào";

char * dst;

strcpy (dst, src);

Khi bạn chạy mã này, nó có thể dẫn đến lỗi phân đoạn

Không phân bổ đủ bộ nhớ

Một lỗi liên quan là không cấp đủ bộ nhớ, đôi khi được gọi là lỗi tràn bộ đệm Trong ví dụ trên, một lỗi phổ biến là tạo gần như đủ chỗ cho bộ đệm đích char * src = "xin chào";

char * dst = (char *) malloc (strlen (src)); // quá nhỏ!

strcpy (dst, src); // hoạt động bình thường

Mặc dù nó chạy đúng một lần nhưng không có nghĩa là nó chính xác Vì nó có thể xảy ra nhiều trường hợp khác nhau như chương trình bị lỗi và sập, …

Quên khởi tạo bộ nhớ được phân bổ

Với lỗi này, bạn gọi malloc () đúng cách, nhưng quên điền một số giá trị vào kiểu dữ liệu mới được cấp phát của bạn Nếu bạn quên, chương trình sẽ gặp phải một lần đọc chưa được khởi tạo, nơi nó đọc từ đống dữ liệu có giá trị không xác định May mắn thì chương trình vẫn sẽ hoạt động còn không thì có thể sẽ có hại cho chương trình

Quên để giải phóng bộ nhớ

Một lỗi phổ biến khác được gọi là rò rỉ bộ nhớ và nó xảy ra khi bạn quên giải phóng bộ nhớ Trong các ứng dụng hoặc hệ thống chạy lâu (chẳng hạn như chính

hệ điều hành), đây là một vấn đề lớn, vì chậm việc tạo bộ nhớ cuối cùng dẫn đến việc hết bộ nhớ, tại thời điểm đó, khởi động lại là bắt buộc Vì vậy, nói chung, khi bạn sử dụng xong một phần bộ nhớ, bạn nên giải phóng nó

Giải phóng bộ nhớ trước khi bạn hoàn tất

Đôi khi một chương trình sẽ giải phóng bộ nhớ trước khi nó được sử dụng xong; một lỗi như vậy được gọi là con trỏ treo lơ lửng, và nó, như bạn có thể đoán, cũng là một điều tồi tệ Việc sử dụng tiếp theo có thể làm hỏng chương trình hoặc ghi đè bộ nhớ hợp lệ (ví dụ: bạn đã gọi là free (), nhưng sau đó lại gọi là malloc ()

để cấp phát một thứ khác, sau đó sẽ tái chế bộ nhớ được giải phóng một cách sai lầm)

Giải phóng bộ nhớ lặp đi lặp lại

Các chương trình cũng đôi khi giải phóng bộ nhớ nhiều hơn một lần; cái này được gọi là miễn phí gấp đôi Kết quả của việc làm như vậy là không xác định Như bạn có thể tưởng tượng, thư viện cấp phát bộ nhớ có thể bị nhầm lẫn và làm

đủ thứ chuyện kỳ lạ; sự cố là một kết quả phổ biến

Calling free () không chính xác

Một vấn đề cuối cùng mà chúng ta thảo luận là việc gọi free () không chính xác Rốt cuộc, free () mong rằng bạn chỉ chuyển tới nó một trong những con trỏ mà bạn

đã nhận được từ malloc () trước đó Khi bạn vượt qua một số giá trị khác, những điều tồi tệ có thể xảy ra Vì vậy, những giải phóng không hợp lệ như vậy rất nguy hiểm và tất nhiên cũng nên tránh

5 Các lệnh Call khác

Có một số lệnh gọi khác mà thư viện cấp phát bộ nhớ hỗ trợ Ví dụ, calloc () cấp phát bộ nhớ và cũng làm cho nó bằng không trước khi trả về; điều này ngăn ngừa một số lỗi trong đó bạn cho rằng bộ nhớ bị xóa và quên tự khởi tạo bộ nhớ đó (xem đoạn văn về “các lần đọc chưa được khởi tạo” ở trên) Quy trình realloc () cũng có thể hữu ích, khi bạn đã cấp phát không gian cho một thứ gì đó (ví dụ, một mảng), và sau đó cần thêm thứ gì đó vào nó: realloc () tạo một vùng bộ nhớ mới lớn hơn, sao chép vùng cũ vào nó và trả lại con trỏ đến vùng mới

III Dịch địa chỉ

1.Khái niệm

Một trong những hướng tiếp cận trung tâm nhằm tổ chức quản lý bộ nhớ một cách hiệu quả là đưa ra không gian địa chỉ được xây dựng trên không gian nhớ vật lí qua

cơ chế dịch địa chỉ

Với dịch địa chỉ, phần cứng sẽ biến đổi từng lần truy cập bộ nhớ (ví dụ: tìm nạp, tải hoặc lưu trữ lệnh), thay đổi địa chỉ ảo do lệnh cung cấp thành địa chỉ vật lý nơi thực sự có thông tin mong muốn Do đó, trên mỗi và mọi tham chiếu bộ nhớ, một bản dịch địa chỉ được phần cứng thực hiện để chuyển hướng các tham chiếu bộ nhớ ứng dụng đến vị trí thực tế của chúng trong bộ nhớ

Tất nhiên, phần cứng một mình không thể ảo hóa bộ nhớ, vì nó chỉ cung cấp cơ chế cấp thấp để thực hiện việc đó một cách hiệu quả Hệ điều hành phải tham gia vào các điểm chính để thiết lập phần cứng sao cho các bản dịch chính xác diễn ra; do

đó, nó phải quản lý bộ nhớ, theo dõi vị trí nào trống và vị trí nào đang được sử dụng, đồng thời can thiệp một cách thận trọng để duy trì quyền kiểm soát cách sử dụng bộ nhớ

Ví dụ: Một chuỗi mã ngắn tải một giá trị từ bộ nhớ, tang giá trị đó lên 3 lần rồi lưu lại giá trị đó trở lại bộ nhớ (theo ngôn ngữ C)

void func() {

int x = 3000;

Perry x = x + 3;

…