Đề cương ôn tập giữa kỳ Môn Hệ điều hành | Đại học Bách Khoa Hà Nội

lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
ĐỀ CƯƠNG ÔN TẬP GIỮA KỲ MÔN HỆ ĐIỀU HÀNH A. TIẾN TRÌNH
1. Khái niệm về tiến trình – process, các trạng thái cơ bản của tiến trình
1.1. Khái niệm về tiến trình – process
- Tiến trình – một chương trình đang thực thi, việc thực thi tiến trình phải tiến triển một
cách tuần tự. Không thực hiện song song nhiều lệnh của cùng một tiến trình.
- Chương trình là một thể bị động lưu trên ổ đĩa ngoài (executable file), tiến trình là thực thể chủ động.
+ Chương trình trở thành tiến trình khi một file thực thi được nạp vào bộ nhớ trong.
- Chương trình được thực thi khi click chuột với GUI, gọi trên giao diện CLI.
- Một chương trình có thể trở thành nhiều tiến trình
+ Các người dùng khác nhau cùng thực thi một chương trình.
1.2. Các trạng thái cơ bản của tiến trình
Tiến trình thực thi có thể chuyển đổi trạng thái cơ bản state:
- New: Tiến trình được khởi tạo.
- Ready: Tiến trình sẵn sàng thực thi chờ bộ xử lí khi: số lượng bộ xử lí < số lượng tiến trình
Quản lí bằng ready process list, có quan tâm thứ tự.
- Running: Các mã lệnh đang được thực thi.
- Waiting/ Block: Tiến trình chờ một sự kiện nào đó hoặc chờ cấp phát tài nguyên thêm -
Terminated: Tiến trình kết thúc.
2. Sự biến đổi trạng thái của tiến trình
Cung 1: Tiến trình khởi tạo, nếu còn bộ nhớ trống, sẽ được đưa vào bộ nhớ và sẵn sàng nhận
CPU, khi đó tiến trình từ trạng thái New được chuyển sang trạng thái Ready lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
Cung 2:Bộ điều phối cấp phát cho tiến trình một khoảng thời gian sử dụng CPU và cho tiến
trình thực hiện, khi đó tiến trình từ trạng thái Ready được chuyển sang trạng thái Running
Cung 3: Khi tiến trình kết thúc việc thực hiện, khi đó tiến trình ở trạng thái Running được
chuyển san trạng thái End
Cung 4: Khi tiến trình yêu cầu một tài nguyên nhưng chưa được đáp ứng vì tài nguyên chưa
sẵn sàng hoặc tiến trình từ trạng thái Runnin sang trạng thái Blocked
Cung 5: Khi tiến trình tạm dừng vì hết thời gian sử dụng CPU, bộ điều phối sẽ chọn tiến trnhf
khác để xử lí, khi đó tiến trình được chuyển sang trạng thái Running sang trạng thái Ready
Cung 6: Khi tài nguyên mà tiến trình yêu cầu trở nên sẵn sàng để cấp phát; hay sự kiện hoặc
thao tác nhập/ xuất mà tiến trình đang đợi đã hoàn tất, khi đó bộ tiến trình được chuyển từ
trạng thái Blocked sang trạng thái Ready
3. Sự tạm dừng và kích hoạt, biến đổi trạng thái khi có tạm dừng, kích hoạt
- Sự tạm dừng (suspend): Khi tiến trình không thể tiếp tục thực thi đến khi có một tiến
trình khác kích hoạt nó.
- Sự kích hoạt (activate): Là thao tác chuẩn bị để tiến trình có thể tiếp tục thực thi kể từ
trạng thái dừng trước đó.
- Biến đổi trạng thái khi có tạm dừng, kích hoạt: Khi bộ xử lý đang thực thi tiến trình, có
sự kiện dừng thì sẽ dừng tiến trình và xử lý yêu cầu. Sau khi xử lý xong, có yêu cầu kích
hoạt sẽ tiếp tục thực thi từ thời điểm ngắt quãng. lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
4. Xử lý ngắt, cơ chế chuyển đổi ngữ cảnh
- Ngắt: Là sự kiện dừng công việc hiện tại của Bộ xử lý (CPU). - Các loại ngắt: + SVC;
+ I/O: ngắt liên quan đến thiết bị vào ra; + External: ngắt ngoài;
+ Restart: ngắt khởi động hệ thống (có báo trước cho các tiến trình biết);
+ Program check: ngắt lỗi phần mềm; +
Machine check: ngắt lỗi phần cứng. - Xử lý ngắt : + Điều khiển HĐH;
+ HĐH lưu lại trạng thái của tiến trình hiện tại;
+ HĐH xử lý và phân loại ngắt cho bộ xử lý ngắt tương ứng.
- Cơ chế chuyển đổi ngữ cảnh
+ Chuyển đổi ngữ cảnh (Context switch) xảy ra khi CPU thay đổi từ một tiến trình sang tiến trình khác. lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
+ Khi chuyển CPU sang tiến trình khác, hệ thống phải lưu lại trạng thái của tiến trình đang
thực hiện và tải trạng thái đã được lưu của tiến trình mới.
+ Ngữ cảnh – Context của một tiến trình thể hiện trong PCB.
+ Thời gian chuyển đổi phát sinh tải CPU; hệ thống không được thực thi tác vụ của người
dùng: HĐH và PCB càng phức tạp  chuyển đổi càng lâu + Thời gian phụ thuộc vào phần cứng hỗ trợ.
5. Hạt nhân của Hệ điều hành. Hai mô hình của HĐH: Monolithic và Micro Kernel
5.1. Hạt nhân của Hệ điều hành
- Tất cả các thao tác liên quan đến process được thực hiện bởi một phần của Hệ điều hành
gọi là hạt nhân – Kernel.
- Thành phần thực thi các chức vụ cơ bản nhất: + Xử lý ngắt.
+ Tạo và xoá các process.
+ Đổi trạng thái của process. + Dispatching.
+ Suspend and activate process.
+ Đồng bộ (synchronize) các process.
+ Xử lý, tổ chức mối quan hệ giữa các process. + Điều khiển PCBs. + Quản lý bộ nhớ.
+ Hỗ trợ làm việc hệ thống file. - Cơ chế:
+ User mode: app: cơ chế ưu tiên thấp lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
+ Kernel mode: HĐH: cơ chế ưu tiên cao
 Chế độ User >< Kernel
5.2. Hai mô hình của Hệ điều hành: Monolithic và Micro Kernel 5.2.1. Monolithic - Trong OS: + Giao tiếp: Inteprocess; + Local procedure call; + Địa chỉ. - Tính chất:
+ Kích thước kernel lớn, tốc độ nhanh;
+ Khi một process bị crash, kéo theo cả hệ thống bị crash theo, tính ổn định thấp, khó mở rộng;
+ Khó debug, kém an toàn và bảo trì mất nhiều thời gian.
5.2.2. Micro Kernel
- Chuyển nhiều chức năng của Hệ điều hành sang chế độ client.
- Trao đổi thông tin giữa các cấu phần: message passing. - Ưu điểm: + Kích thước Kernel bé
+ Dễ dàng mở rộng, cấu hình; + Dễ bảo trì, debug
+ Dễ dàng chuyển đổi nâng cấp; + Ổn định hơn; + An toàn, bảo mật hơn;
- Nhược điểm: Ảnh hưởng đến tốc độ lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
B. TIẾN TRÌNH TƯƠNG TRANH KHÔNG ĐỒNG BỘ
1. Khái niệm loại trừ (mutual exclusion), ví dụ
- Khi một process truy nhập đến dữ liệu chung thì cần cấm tất cả các process khác truy
nhập đến cùng dữ liệu vào thời điểm đó. Điều đó gọi là mutual exclusion (loại trừ lẫn nhau). - VD:
+ Các cửa hàng bán vẽ: Các tiến trình
+ Kho vé: Dữ liệu + Logic:
• Đọc X (số chỗ trống)
• Bán vé – Trừ số lượng vé
• Cập nhập số lượng vé + Lệnh : a X= a a n= − X a=
2. Thuật toán Dekker cài đặt loại trừ cho 2 tiến trình Version 1 Version 2 lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370 Version 3 P1, f1 P2, f2 lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370 While true While true; f 1 = true ; while f 2 = true f2 = true do: if s while f1 = true do: = 2 do: f1 = if s = 1 do false while s = f2 = false 2 do; while s = 1 do; f1 = true f2 = end; end; true end; end; f1 = false f2 = false s = 2 s = 1 end; end;
3. Thực hiện loại trừ bằng lệnh TestAndSet
3.1. Lệnh TestAndSet - Định nghĩa - Tính chất:
+ Cơ chế thực hiện: Nguyên tử
+ Trả lại giá trị gốc của tham số đầu vào
+ Đặt giá trị mới cho tham số đầu thành true
3.2. Thuật toán TestAndSet
Biến chia sẻ chung lock, khởi tạo là false
Thuật toán TestandSet: a: Boolean P1, f1 P2, f2 lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370 While true While true; p1 = true ; p2 = true while p1 = true do: while p2 = true do: testAndset (p1, a) testAndset (p2, a) a = false end; a = false end;
Trong đó testAndset (a,b): a = b; b = true;
4. Khái niệm Semaphore, ứng dụng của Semaphore
4.1. Khái niệm Semaphore - Là biển được bảo vệ tạo thành phương pháp hạn chế
truy cập tới tài nguyên dùng chung trong môi trường đa chương. Giá trị của nó
chỉ được đọc , ghi thông qua các biến q , v , biến khởi tạo - + init(s,v) : Gán s=v;
- + p(s) : .Nếu s>0 : s=s-1; - . Ngược lại chờ s
- + v(s) : . Nếu chờ s thì chọn 1 tiến trình để tiếp tục - . Ngược lại s=s+1;
- Với giả định: hàng đợi V(s) theo nguyên lý FIFO - Lệnh: P(s) V(s)
4.2. Ứng dụng của Semaphore - Cấp phát tài nguyên pool: tài nguyên - Đồng bộ tiến trình C. TẮC NGHẼN (DEADLOCK)
1. Khái niệm Deadlock, ví dụ tình trạng Deadlock
- Khái niệm: là trạng thái xảy ra trong quá trình môi trường đa chương, khi hai hay nhiều
tiến trình đi vào vòng lặp chờ tài nguyên mãi mãi. lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
- Ví dụ: Cấp phát tài nguyên Tiến trình A: + Đang sử dụng R1 + Yêu cầu thêm R2 Tiến trình B: + Đang sử dụng R2 + Yêu cầu thêm R1
2. Các điều kiện xuất hiện Deadlock
Theo Coffman, Elphick: Deadlock xảy ra khi có cả đồng thời 4 điều kiện
- Loại trừ lẫn nhau: tại một thời điểm chỉ có tiến trình được sử dụng tài nguyên.
- Giữ và chờ: một tiến trình đang giữ ít nhất một tài nguyên yêu cầu thêm tài nguyên được
giữ bởi tiến trình khác
- Không trưng dụng: một tài nguyên chỉ có thể được giải phóng bởi chính tiến trình đang
nắm giữ, sau khi tiến trình đó kết thúc việc sử dụng
- Chờ đợi vòng tròn: tồn tại một tập tiến trình {P0, P1, ..., Pn} đợi tài nguyên theo nguyên
tắc P0 chờ tài nguyên giữ bởi P1, P1 chờ tài nguyên giữ bởi P2, ..., Pn-1 chờ tài nguyên giữ
bởi Pn và Pn chờ tài nguyên giữ bởi P0.
3. Ngăn chặn Deadlock theo các chiến lược của Havender, ưu/ nhược điểm.
3.1. Chiến lược ngăn chặn Deadlock của Havender
- Tiến trình phải yêu cầu tất cả tài nguyên cần thiết ngay từ đầu
- Tiến trình yêu cầu thêm tài nguyên mà chưa được đáp ứng thì giải phóng tài nguyên đã
được cấp phát và chờ được cấp phát lại.
- Đánh số thứ tự tài nguyên (tiến trình sử dụng tài nguyên theo số thứ tự tăng dần)
3.2. Ưu/ nhược điểm - Ưu điểm
+ Loại bỏ được điều kiện “Chờ tài nguyên bổ sung”
+ Loại bỏ được điều kiện “Không phân bố lại”
+ Loại bỏ được điều kiện “Chờ vòng quanh” - Nhược điểm :
+ Sử dụng tài nguyên không hiệu quả
+ Làm mất các kết quả làm việc đến thời điểm giải phóng
+ Khi có thêm tài nguyên mới có thể gây ra ra tình huống phải thiết kế lại hệ thống. lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
4. Thuật toán Banker, trạng thái của hệ thống 4.1. Thuật toán Banker
Điều kiện: Hệ thống biết trước một số thông tin
- Mô hình đơn giản và khả dụng nhất yêu cầu mỗi tiến trình khai báo số lượng tài nguyên
tối đa có thể yêu cầu.
- Thuật toán phòng tránh tự động kiểm tra trạng thái cung cấp tài nguyên để đảm bảo
không thể xảy ra chờ đợi vòng tròn.
- Trạng thái cung cấp tài nguyên được xác định dựa trên số lượng tài nguyên sẵn sàng, số
lượng tài nguyên đã phân bổ và nhu cầu tối đa của các tiến trình. 4.1.1. Tính chất
- Hệ thống ở trạng thái an toàn  bế tắc không xảy ra
- Hệ thống ở trạng thái không an toàn  bế tắc có thể xảy ra
- Phòng tránh  đảm bảo hệ thống không bao giờ ở trạng thái không an toàn. 4.1.2. Điều kiện
- Tài nguyên có nhiều đơn vị
- Mỗi tiến trình phải khai báo số đơn vị lớn nhất của mỗi loại tài nguyên sẽ có thể sử dụng
- Khi một tiến trình yêu cầu tài nguyên, có thể phải đợi
- Khi một tiến trình sử dụng tài nguyên, tiến trình phải giải phóng sau một khoảng thời gian hữu hạn
4.1.3. Cấu trúc dữ liệu
Với n= số lượng tiến trình và m= số loại tài nguyên
- Available: Vector độ dài m. Nếu available  j = k , có k đơn vị tài nguyên Rj sẵn sàng.
- Max: ma trận n m . Nếu Max i j,  = k , tiến trình Pi có thể yêu cầu nhiều nhất k đơn vị tài nguyên Rj.
- Allocation: ma trận n m . Nếu Allocation i j,  = k thì Pi đang được cấp phát k đơn vị Rj.
- Need: Ma trận n m . Nếu Need i j,  = k , thì Pi có thể yêu cầu thêm k đơn vị Rj để có thể kết thúc.
Need i j,  = Max i j,  − Allocation i j, 
4.2. Trạng thái của hệ thống
4.2.1. Trạng thái an toàn lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
- Khi một tiến trình yêu cầu một tài nguyên đang sẵn sàng, hệ thống phải kiểm tra nếu
việc cấp phát dẫn tới trạng thái an toàn.
- Hệ thống ở trạng thái an toàn – safe state nếu tồn tại một chuỗi  P P 1, 2, ..., Pn  của tất
cả các tiến trình trong hệ thống mà với mỗi Pi , các tài nguyên Pi có thể yêu cầu có thể
được cung cấp dựa trên tài nguyên hiện có và tài nguyên đang được sử dụng bởi các tiến
trình Pj , với j  i. - Nghĩa là:
+ Nếu Pi yêu cầu tài nguyên đang không sẵn sàng, Pi có thể chờ đến khi tất cả tiến trình Pj kết thúc.
+ Khi Pj kết thúc, Pi có thể được cấp tài nguyên, thực thi, trả lại tài nguyên đã được cấp phát và kết thúc.
+ Khi Pi kết thúc, Pi+1 có thể được cấp phát tài nguyên và cứ tiếp tục như thế.
4.2.2. Điều kiện - Mỗi tiến trình:
+ Đưa ra số lượng tài nguyên lớn nhất có thể cần
+ Nếu được cấp phát, tiến trình phải trả lại tài nguyên sau thời gian hữu hạn nào đó
+ 1 yêu cầu => cấp phát 1 tài nguyên - Hệ thống sẽ đảm bảo:
+ Yêu cầu => sẽ được cấp phát sau thời gian hữu hạn
4.2.3. Ví dụ: Trạng thái an toàn >< Không an toàn
Hệ thống: có 12 tài nguyên, 3 tiến trình
Số thiết bị đang được cấp phát Số thiết bị lớn nhất có thể cần P1 1 4 P2 4 6 P3 5 8 Dự trữ còn lại 2
Nếu P1 yêu cầu và Hệ thống cấp cho P1: 1 tài nguyên => đi đến trạng thái
Số thiết bị đang được cấp phát Số thiết bị lớn nhất có thể cần P1 2 4 P2 4 6 P3 5 8 Dự trữ còn lại 1 lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
5. Phát hiện Deadlock qua đồ thị phân bố tài nguyên Rút
gọn đồ thị để phát hiện Deadlock:
- Khi tiến trình kết thúc công việc và trả lại các tài nguyên cho hệ thống thì ngắt bỏ cung
từ process đó đến tài nguyên và từ tài nguyên đến process đó.
- Khi tài nguyên chỉ cấp phát cho 1 tiến trình và tiến trình đó không yêu cầu cấp thêm tài
nguyên hoặc yêu cầu cấp thêm tài nguyên còn trống.
⇨ Không còn cung nào thì sẽ không tắc nghẽn.
D. BỘ NHỚ 1. Bộ nhớ thực: Tổ chức bộ nhớ thực, địa chỉ phẳng và địa chỉ phân cấp
1.1. Tổ chức bộ nhớ thực
- 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ất kỳ.
1.2. Địa chỉ phẳng và địa chỉ phân cấp
-Địa chỉ phẳng(tuyệt đối)
+ Gắn địa chỉ cho ô nhớ thấp nhất với lần lượt tăng dần
+Xử lí thao tác đơn giản nhưng không linh hoạt
-Địa chỉ phân cấp( tương đối)
+Có 2 thành phần base(địa chỉ cơ sở), offset(phần tương đối)
+Có thể dịch chuyển được
2. Bộ nhớ thực: Bộ nhớ trong hệ điều hành đơn tiến trình, cơ chế overlay
2.1. Bộ nhớ trong hệ điều hành đơn tiến trình
-Bộ nhớ trong hệ điều hành đơn tiến trình
+Hệ điều hành nằm ở vùng địa chỉ thấp
+Tiến trình người dùng nằm ở vùng địa chỉ cao
+Mỗi tiến trình nằm trong 1 vùng bộ nhớ liên tục lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
2.2. Cơ chế Overlay
- Tại mỗi thời điểm, chỉ giữ lại trong bộ nhớ những lệnh hoặc dữ liệu cần thiết, giải phóng
các lệnh/dữ liệu chưa hoặc không cần dùng đến.
- Cơ chế này rất hữu dụng khi kích thước một process lớn hơn không gian bộ nhớ cấp cho process đó.
- Cơ chế này được điều khiển bởi người sử dụng (thông qua sự hỗ trợ của các thư viện lập
trình) chứ không cần sự hỗ trợ của hệ điều hành.
3. Bộ nhớ thực: Bộ nhớ trong hệ điều hành đa tiến trình, cơ chế swap
3.1. Bộ nhớ trong hệ điều hành đa tiến trình
-Bộ nhớ phân chương cố định
+Bộ nhó được thành 1 số vùng có kích thước cố định, gọi là chương, đoạn.Mỗi chương có thể chứa nhiều thư viện
-Bộ nhớ phân chương động
+Tăng độ linh hoạt bằng kích thước chương thay đổi khi có tiến trình yêu cầu=> cấp phát bộ
nhớ từ 1 vùng trống kích thước đủ để đáp ứng yêu cầu 3.2. Cơ chế Swap 3.2.1. Swapping
- Một tiến trình có thể được hoán đổi swapped tạm thời từ bộ nhớ chính ra bộ nhớ thứ cấp
và chuyển lại bổ nhớ chính để tiếp tục thực thi.
- Tổng không gian bộ nhớ cho tiến trình có thể lớn hơn lượng bộ nhớ vật lý.
- Bộ nhớ thứ cấp – Backing store – ổ đĩa tốc độ cao kích thước đủ lớn để chứa tất cả các
tiến trình người dùng, có khả năng truy cập trực tiếp. lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370 3.2.2. Cơ chế - Tác vụ:
+ Swap in: Đưa từ bộ nhớ ngoài vào bộ nhớ thực.
+ Swap out: Đưa từ bộ nhớ thực ra bộ nhớ ngoài.
- Ưu điểm: Giải quyết được vấn đề giới hạn, kích thước.
- Nhược điểm: Thao tác swap in/swap out gắn với thao tác vào/ra và tốc độ của nó là rất
chấm. Nếu sử dụng thường xuyên thì hệ thống sẽ hoạt động rất chậm.
4. Bộ nhớ ảo: Khái niệm, bộ nhớ theo trang, bộ nhớ theo đoạn 4.1. Khái niệm
- Bộ nhớ ảo là một kĩ thuật quản lý bộ nhớ được giả lập bởi HĐH , nó liên kết với địa chỉ
ô nhớ bởi địa chỉ ảo. Nó không tương ứng 1-1 (nó lớn hơn) với bộ nhớ thực và có không
gian bộ nhớ lớn , giúp chương trình không bị giới hạn bộ nhớ (địa chỉ tiến trình truy cập
không trùng với địa chỉ vật lý).
- Được ứng dụng đầu những năm 1960.
- Đánh địa chỉ không gian lớn hơn bộ nhớ thực.
- Địa chỉ tiến trình truy cập không trùng với địa chỉ vật lý.
- Quá trình phát triển kiến trúc bộ nhớ Bộ nhớ vật lý Bộ nhớ ảo Hệ thống đơn nhiệm
Hệ đa nhiệm, bộ nhớ vật lý
Hệ đa nhiệm, bộ nhớ ảo Tổ chức Tổ chức theo Tổ chức Phân đoạn cố định Phân đoạn thay đổi theo trang segment kết hợp Địa chỉ Địa chủ tuyệt đối thay đổi - Ưu điểm : lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
+ Có thể chạy nhiều chương trình một lúc, kích thước chương trình có thể lớn hơn kích thước bộ nhớ chính.
+ Cho phép chia sẽ mã và dữ liệu , số lượng đa chương trình không giới hạn.
+ Khắc phục và hạn chế việc phân mảnh.
+ Giữ cho chương trình an toàn. - Nhược điểm :
+ Tăng chi phí để xử lí ngắt phân trang, độ phức tạp của phần mềm và chi phí phần cứng.
+ Tốc độ giảm, ứng dụng chạy chậm hơn.
4.2. Bộ nhớ theo trang
4.2.1. Mô hình phân trang
- Bộ nhớ ảo chia thành trang có kích thước cố định.
- Địa chỉ ảo trong hệ thống theo trang được thể hiện bằng cặp v = (p,d), p_ thứ tự trang, d_offset trong trang p. 4.2.2. Phân trang
- Không gian địa chỉ vật lý của tiến trình có thể không liên tục; tiến trình được cấp phát
bộ nhớ ngay khi tài nguyên sẵn sàng.
+ Tránh được phân mảnh (fragmentation) ngoài.
+ Tránh được vấn đề kích thước các khối bộ nhớ thay đổi.
- Chia bộ nhớ vật lý thành các khối các kích thước xác định gọi là khung – frames.
- Lũy thừa của 2, giữa 512 bytes và 16 Mbytes.
- Chia bộ nhớ logic thành các khối cùng kích thước gọi là trang – pages.
4.2.3. Quản lý của HĐH trong phân trang -
Theo dõi các khung trang tự do/còn trống.
- Để thực thi chương trình kích thước N trang, cần tìm ra N khung tự do và tải chương trình.
- Thiết lập bảng phân trang page table để biến đổi địa chỉ logic sang địa chỉ vật lý.
- Vùng nhớ ngoài cũng chia thành các trang.
- Vẫn có hiện tượng phân mảnh trong trang.
4.2.4. Cơ chế chuyển đổi địa chỉ
- Địa chỉ sử dụng bởi CPU được chia thành:
+ Page number (p) – sử dụng như 1 chỉ mục trong bảng phân trang – page table chứa địa
chỉ vật lý bắt đầu của mỗi trang.
+ Page offset (d) – kết hợp với địa chỉ bắt đầu trang để xác định địa chỉ vật lý cần gửi tới MMU. lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370 page number page offset p d m - n n
+ Không gian địa chỉ 2m và kích thước trang 2n. + Phép ghép địa chỉ.
4.2.5. Biến đổi địa chỉ trong tổ chức theo trang
- Các bước biến đổi địa chỉ trực tiếp Địa chỉ ảo v = (p,d)
Địa chỉ thực r = (p',d) + Bước 1: p+a + Bước 2: đọc ô nhớ + Bước 3: tính r
4.3. Bộ nhớ theo đoạn
4.3.1. Chiến lược phân đoạn (Segmentation)
- Chương trình chia thành các module: + Chương trình chính. + Các chương trình con.
+ Các biến, cấu trúc dữ liệu: tĩnh, cấp phát động.
- Các module, đối tượng được xác định bằng tên
- Các phần tử trong module xác định thông qua độ lệch với vị trí ban đầu
4.3.2. Cấu trúc phân đoạn
- Chương trình gồm 1 tập các đoạn (segment)
- Bảng quản lý đoạn SCB
+ Cờ f: đánh dấu segment đã tồn tại trong bộ nhớ
+ Base: địa chỉ bắt đầu + Length: độ dài đoạn
- Khả năng dùng chung đoạn lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
4.3.3. Biến đổi địa chỉ trong phân đoạn
- Địa chỉ ảo: v = (s,d) - Địa chỉ thực: r - Thông tin ánh xạ
- Cơ chế chuyển đổi địa chỉ (s, d): s’ + d
+ Bước 1: s + b (b: địa chỉ đầu của bảng ánh xạ) + Bước 2: đọc ô nhớ
+ Bước 3: s’ + offset d => r lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
Cả semảphore vả monitor đe u đượ c du ng như lả mo t co ng cu đe đo ng bo hoả . Cả 2 đe u co the thư c
hie n co ng vie c như nhảu vả thảy the đượ c cho nhảu de dả ng.
Đie m khả c bie t co the thả y ro nhả t, như đả no i ợ bả ng tre n, đo lả monitor de sư du ng hợn
semảphore. Semảphore gio ng như con tro trong C++, mả nh me vả low-level nhưng lả i ye u cả u sư
cả n thả n, chu đả o tư ngượ i sư du ng no .
Ne u bả n wảit() mả que n releảse() tre n semảphore, bả n se rả t co the gả p phả i trượ ng hợ p
deảdlock, hoả c như ng bug kho phả t hie n. Monitor, ngượ c lả i, đả giu p bả n giả i quye t vả n đe tre n
bả ng cả ch go i hả m thảy vì phả i tư kie m soả t signảl() vả wảit().
Câu 8 : Trì nh bả y giả i thuả t ye u cả u tả i nguye n ?
Request(i) lả mo t vector request cu ả process P(i).
Request(i)[j] = k o P(i) cả n k thư c the (instảnce) cu ả tả i nguye n Rj. 1.
Ne u Request(i) <= Need(i) thì đe n bượ c 2. Ne u kho ng, bả o lo i vì tie n trì nh đả vượ t ye u cả u to i đả. 2.
Ne u Request(i) <= Avảilảble thì quả bượ c 3. Ne u kho ng, P(i) phả i chợ vì tả i nguye n kho ng co n đu đe cả p phả t. 3.
Giả định cấp phát tài nguyên đáp ứng yêu cầu của P(i) bằng cách cập nhật trạng thái
hệ thống như sau : •
Avảilảble = Avảilảble – Request(i). •
Allocảtion(i) = Allocảtion(i) + Request(i). •
Need(i) = Need(i) – Request(i).
A p du ng giả i thuả t Bảnker le n he tho ng mợ i. •
Nếu hệ thống giả định trên an toàn thì tiến hành cấp phát thực. •
Ne u trả ng thả i lả kho ng ản toả n thì Pi phả i đợ i vả phu c ho i trả ng thả i :
o Available = Available + Request(i). o Allocation(i) = Allocation(i) – Request(i).
o Need(i) = Need(i) + Request(i).
Vì du ye u cả u đượ c chả p nhả n vả cả p phả t thư c te : lOMoAR cPSD| 61552860
HỆ ĐIỀU HÀNH_MI3370
Vì du ye u cả u cả p phả t tả i nguye n đượ c chả p nhả n.
Vì du ye u cả u kho ng đượ c chả p nhả n vả kho ng đượ c cả p phả t :
Vì du ye u cả u cả p phả t tả i nguye n kho ng đượ c cả p phả t. Bài tập chương 6.
Bài 1 : Cho 1 he tho ng có 4 tie n trình P1 đe n P4 và 3 loả i tài nguyên R1 (3), R2(2),
R3(2). P1 giư 1 R1 và yêu cả u 1 R2, P2 giư 2 R2 và yêu cả u 1 R1 và 1 R3, P3 giư 1 R1 và
yêu cả u 1 R2, P4 giư 2 R3 và yêu cả u 1 R1. •
Ve đo thi tài nguyên cho he tho ng này ? • Deadlock ?