Tóm tắt lý thuyết môn Hệ điều hành | Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh

lOMoARcPSD| 36443508
Kiến thức nền (thuật ngữ): -
Kernel: Nơi mà chương trình hoạt động trên máy tính - System program - Application program -
Buffer: Vùng lưu trữ dữ liệu tạm thời, thường được lưu trữ trong bộ nhớ tạm (RAM). -
Device controller: Đảm nhiệm việc chuyển dữ liệu giữa thiết bị ngoại vi mà nó
điều khiển và bộ nhớ đệm -
Device driver: Chương trình điều khiển thiết bị ngoại vi - Operation (Hoạt động):
Chương 1: INTRODUCTION 1. Tổng quan HĐH: - Vai trò: -
Đóng vai trò trung gian giữa người dùng và phần cứng máy tính -
Điều phối nhiều ứng dùng cho nhiều người dùng, tận dụng được tối đa phần cứng máy tính. -
Đối với người dùng (User view): HĐH chỉ cần thuận tiện, dễ dàng sử
dụng và có hiệu suất tốt -
Đối với hệ thống (System view): HĐH kiểm soát việc chia sẻ của máy
tính nhằm thỏa mãn người dùng. - Mục tiêu: -
Thực thi các tác vụ của người dùng dễ dàng hơn. -
Giúp hệ thống máy tính dễ sử dụng hơn. -
Tận dụng hiệu quả phần cứng máy tính hơn.
2. Cấu trúc máy tính gồm 4 phần - Phần cứng: -
Cung cấp các tài nguyên: CPU, memory, I/O devices. - HĐH: -
Kiểm soát và điều phối việc sử dụng phần cứng giữa nhiều phần mềm và người dùng. -
Application programs (trình ứng dụng): -
Đưa ra cách thức sử dụng các nguồn tài nguyên sử dụng để giải quyết
một vấn đề nào đó của người dùng. - Người dùng: -
Con người, máy móc, hoặc máy tính khác.
3. Tổ chức máy tính -
Tổ chức máy tính tập chung vào: Interrupt, storage và Cấu trúc I/O -
Thiết I/O và CPU có thể thực hiện đồng thời: -
Các thiết bị cụ thể được kiểm soát với device controller - Device controller: -
Có bộ nhớ đệm cục bộ (local buffer storage) -
Đưa dữ liệu giữa thiết bị ngoại vi và local buffer storage. -
HĐH có mỗi device driver cho mỗi device controller. -
Hoạt động (CPU và device controller có thể thực hiện đồng thời): lOMoARcPSD| 36443508 -
CPU di chuyển dữ liệu giữa main memory và local buffer -
I/O từ device đến local buffer của controller -
Device controller thông báo cho CPU khi xong hành động của mình qua interrupt (Ngắt). 4. Interrupt (Ngắt): - Chức năng:
- Device controller dùng để thông báo cho device driver sau khi thực hiện xong
- Nó phải thực được giải quyết nhanh vì được xảy ra rất thường xuyên.
- Chuyển giao việc điều khiển cho trình điều khiển ngắt, qua interrupt
vector (Chứa địa chỉ của tiến trình dịch vụ) - Nó chứa địa chỉ của
câu lệnh đã được ngắt. - Trap hay exception là ngắt của phần mềm.
- HĐH chính là hệ thống điều khiển ngắt - Các loại ngắt: - Overload - Timer - I/O - Hardware failure - Trap 5. Cấu trúc lưu trữ - Main memory - Hard Disk Drives (HDD) -
Chương 2: Quản lý tiến trình I. Process
1. Khái niệm: Tiến trình là chương trình đang chạy, mỗi tiến trình sở hữu một con trỏ lệnh (program
counter), tập thanh ghi và các biến cần sử dụng một số tài nguyên như CPU, bộ nhớ chính, các tập tin,
các thiết bị nhập xuất
-Mỗi thời điểm CPU chỉ chạy đc 1 chương trình nhưng có nhu cầu chạy nhiều chương trình cùng lúc,
để đáp ứng cần có 1 bộ điều phối(schedule)
2. Trạng thái của tiến trình: ●
Mới tạo (new): tiến trình mới được đưa vào hệ thống ●
Đang chạy (running): CPU đang thực thi các chỉ thị của tiến trình ●
Chờ (waiting): tiến trình đang đợi cấp phát tài nguyên hoặc 1 sự kiện và chưa sẵn sàng chạy ●
Sẵn sàng(ready): tiến trình chờ cấp phát CPU để xử lý ●
Kết thúc(terminate): tiến trình hoàn tất
Mỗi thời điểm chỉ có 1 tiến trình ở trạng thái running, khi tiến trình đó không còn ở trạng thái running,
1 tiến trình ở trạng thái ready được lấy ra và chạy(công việc của scheduler)
3. Khối điều khiển tiến trình(Process control block): Mỗi tiến trình được hiện diện trong hệ điều hành bới
một khối điều khiển tiến trình (PCB) còn gọi là điều khiển tác vụ
4. Thread: Mỗi tiến trình có nhiều dòng xử lý(Thread), chia sẻ cùng không gian địa chỉ, mỗi tiến trình có
thể tạo nhiều Thread đồng hành, tài nguyên của tiến trình gọi là tài nguyên cục bộ
Thread dùng chung không gian địa chỉ, dùng chung biến toàn cục II.
Process Scheduling: Ngắt tiến trình running và chọn 1 tiến trình trong danh sách ready để chạy tiếp,
dispatcher chuyển ngữ cảnh, CPU cho tiến trình được chọn 1.
Hàng đợi tiến trình(Ready and Wait Queues): Tiến trình được đưa vào hàng đợi, lOMoARcPSD| 36443508
Ready: Các tiến trình sẵn sàng nằm trong hàng đợi(ready), ở đầu hàng đợi có 2 con trỏ một trỏ đến
PCB đầu tiên và PCB cuối cùng, trong mỗi PCB có 1 con trỏ đến PCB kế tiếp
Waiting: Khi tiến trình running bị ngắt khi đang running thì được đưa vào thiết bị tương ứng 2.
FCFS: first come, first served: Khi 1 tiến trình đi vào nó sẽ vào cuối hàng đợi, khi tiến trình
running bị ngắt, tiến trình đầu hàng đợi sẽ được lấy ra => thời gian chờ đợi trung bình khá dài
Tiến trình Thời gian xử lý Thời gian vào P1 24 0 P2 3 1 P3 4 2 P4 9 3 P5 2 4 P1 P2 P3 P4 P5 24 27 31 40 42
Thời gian chờ của P1: 0s
Thời gian chờ của P2: 24 - 1 = 23s
Thời gian chờ của P3: 24 + 3 - 2 = 25s
Thời gian chờ của P4: 24 + 3 + 4 - 3 = 28s
Thời gian chờ của P5: 24 + 3 + 4 + 9 - 4 = 36s
Thời gian chờ trung bình: (0 + 23 + 25 +28 +36) / 4 = 28s
=> Không phù hợp với hệ thống chia sẻ thời gian
3. RR: Round - Robin: Định mức thời gian cho mỗi tiến trình, các tiến trình trong hàng đợi theo cơ chế
vòng, sau khi hết thời gian quantum, tiến trình tự động ngắt
Tiến trình Thời gian xử lý Thời gian vào P1 24 0 P2 3 1 P3 4 2 P4 9 3 P5 2 4 Quantium = 4ms P1 P2 P3 P4 P5 P1 P4 P1 P4 P1 4 7 11 15 17 21 25 29 30 42
Thời gian chờ của P1: 0s + (17 - 4)s + (25 - 21)s + (30-29)s = 18s
Thời gian chờ của P2: (4 - 1)s = 3s
Thời gian chờ của P3: (7 - 2)s = 5s
Thời gian chờ của P4: (11 - 3)s + (21 - 15)s + (29 - 25)s = 18s
Thời gian chờ của P5: (15 - 4)s = 11s
Thời gian chờ trung bình: (18 + 3 + 5 + 18+11) / 5 = 11s
=> Năng lực của RR phụ thuộc vào Quantium, nếu Quantium quá lớn thì thuật toán trở thành
FCFS, nếu Quantium nhỏ quá -> chia sẻ bộ xử lý(không tốt)
4. SJF(non preempt): Short Job First: Thực hiện công việc ngắn nhất trước, nếu cùng chiều dài thì FCFS
Tiến trình Thời gian xử lý Thời gian đến P1 6 0 P2 8 2 P3 7 4 P4 3 5 P5 2 7 P5 P4 P1 P3 P2 lOMoARcPSD| 36443508 0 2 5 11 18
Thời gian chờ của P1: 5s
Thời gian chờ của P2: 18 - 2 = 16s
Thời gian chờ của P3: 11 - 4 = 7s
Thời gian chờ của P4: 0s
Thời gian chờ của P5: 0s
Thời gian chờ trung bình (5 + 16 + 7)/5 = 5.6s
=> SJF tối ưu thời gian chờ 5. SJF(preempt):
Tiến trình Thời gian xử lý Thời gian đến P1 8 0 P2 5 2 P3 1 4 P1 P2 P3 P2 P1 0 2 4 5 8
Thời gian chờ của P1: 8 - 2 = 6s
Thời gian chờ của P2: 0 + 5 - 4 = 1s
Thời gian chờ của P3: 0s
Thời gian chờ trung bình (6 + 1) / 3 = 2.333s III. Process Synchronization:
Đôi khi có những tiến trình cần độc quyền truy xuất tài nguyên trong một khoảng thời gian, phát sinh nhu
cầu cần đồng bộ hóa hoạt động của chúng.
Bài toán đồng bộ hóa(Critical Section Problem): Khi một tiến trình đang chạy không có 1 tiến trình nào gián đoạn tiến trình này
Để giải quyết bài toán miền găng có thể dùng: semaphore, monitors… Yêu cầu:
●Không có 2 tiến trình ở trong cùng 1 CS (Mutual Exclusion)
●Tiến trình ngoài miền găng không ngăn cản tiến trình vào CS (Progress)
●Không có tiến trình nào phải chờ vô hạn để được vào CS (Bound Waiting) Giải pháp:
Interrupt - based Solution: Giải quyết với môi trường đơn lõi, vô hiệu hóa interrupt khi một
tiến trình đang trong vùng CS, nếu thực thi xong mở lại interrupt => khi 1 tiến trình chạy quá lâu các tiến trình
khác phải chờ vô hạn -> starvation, chỉ sử lý ở môi trường đơn lõi, ở môi trường khác vẫn vào CS được -> ít dùng
Software Solution: -Two process solution: biến turn cho biết có được vào tiến trình hay
không => Chỉ thỏa mãn yêu cầu 1
-Peterson solution: có thêm biến bool flag => Thỏa mãn 3 yêu cầu những vần gây lãng phí CPU
Hardware support for synchronization:
Memory Barriers: Đảm bảo Load và Store trước được hoàn thành trước khi có lệnh
tiếp theo, các => đảm bảo sự nhất quán dữ liệu phần cứng
Test and Set, Compare and Swap: Lười quá k ghi
Mutex Lock: Công cụ phần mềm giải quyết bài toán CS, yêu cầu khóa(acquire()) khi vào
CS, giải phóng khóa(release()) khi thoát khỏi CS -> khóa xoay vòng(spinlock)
Semaphore(quan trọng): Công cụ đồng bộ cung cấp bởi hđh, cung cấp nhiều cách thức phức
tạp hơn Mutex Lock, có 1 biến số nguyên S, được truy xuất bởi wait() và signal() lOMoARcPSD| 36443508
Cách sử dụng: có 2 dạng Semaphore: Counting(S không hạn chế): Đếm semaphore Binary(S 0 hoặc 1) IV.
DeadLock: Một tập hợp tiến trình ở trạng thái DeadLock khi mỗi tiền trình đều chờ một sự kiện mà chỉ
có một tiến trình trong tập hợp mới có thể phát sinh. Nói cách khác mỗi tiến trình đều chờ 1 tài nguyên đang bị
tiến trình khác ở trạng thái Blocked chiếm giữ => không có tiến trình nào tiếp tục xử lý -> không có tiến trình nào
giải phóng tài nguyên cho tiến trình khác -> các tiến trình này bị khóa vĩnh viễn Sources types R
1 … RN có tài nguyên W1,…WN + 4 Điều kiện cần để phát sinh DeadLock: -
Có tài nguyên không thể chia sẻ(Mutal exclusion) -
Sự chiếm giữ và yêu cầu thêm tài nguyên: Tiến trình chiếm giữ tài nguyên được cấp trong khi
chờ tài nguyên mới(Hold and Wait) -
Không thu hồi tài nguyên đang bị chiếm giữ: Tài nguyên không thể được thu hồi từ tiến trình
đang chiếmgiữ cho đến khi tiến trình sử dụng xong (No preemption) -
Tồn tại chu kỳ trong đồ thị cấp phát tài nguyên (Circular wait)
Mô tả Deadlock bằng đồ thị có các đỉnh V và cạnh E
V được chia thành 2 loại:
P = {P1, P2,…PN}: Mô tả tiến trình (hình tròn)
R = {R1, R2, …RN}: Mô tả tài nguyên hệ thống (hình vuông) E gồm 2 loại: Request edge: Pi -> Rj Assignment edge: Rj -> Pi
+ Prevent DeadLock: (lắm vl, tóm tắt thôi)
C1: Không cho phép 1 trong 4 điều kiện trên xảy ra + Mutual Exclusion:
+ Hold and waiting: Đảm bảo khi nào tiến trình yêu cầu tài nguyên thì k giữ tài nguyên nào
khác, mỗi tiến trình yêu cầu tài nguyên 1 lần, các tài nguyên yêu cầu phải trả lại tài nguyên trước khi nhận =>
giảm khả năng sử dụng tài nguyên, có thể dẫn tới starvation
+ No Preemption: Tài nguyên phải do tiến trình tự giải phóng
+ Circular way: áp dụng thứ tự của tài nguyên và tiến trình, thực hiện theo thứ tự
+ Safe state: Kiểm tra trạng thái cấp phát tài nguyên:
Need[i,j] = Max[i,j] - Allocation[i,j]
Available = Available + Allocation[i,j]
+ Banker Algorithms: Dùng cho multiple instances Alloca 琀椀 on Request Available Need R1 R2 R3 R4 R5 R1 R2 R3 R4 R5 R1 R2 R3 R4 R5 R1 R2 R3 R4 R5 lOMoARcPSD| 36443508 P1 1 1 1 1 1 4 2 2 3 3 5 8 4 4 5 3 1 1 2 2 p2 1 1 0 1 1 2 2 2 2 3 3 5 2 2 4 1 1 2 1 2 P3 0 0 0 1 1 3 1 1 4 1 5 8 4 5 6 3 1 1 3 0 P4 1 2 1 1 0 2 4 4 3 2 4 7 3 3 4 1 2 3 2 2 P5 1 0 0 0 1 2 1 1 1 1 2 2 1 1 2 1 1 1 1 0 P6 0 2 1 0 1 2 3 2 1 2 2 4 2 1 3 2 1 1 1 1 Available: 1 2 1 1 1
P5 -> P6 -> P2 -> P4 -> P1-> P3 lOMoARcPSD| 36443508 Chương 3: Memory management 1.
Khái niệm: Quản lý bộ nhớ là công việc của hệ điều hành với sự hỗ trợ của phần cứng
nhằm phân phối, sắp xếp các process trong bộ nhớ sao cho hiệu quả.
-Mục tiêu cần đạt được là nạp càng nhiều process vào bộ nhớ càng tốt (gia tăng mức độ đa chương)
-Trong hầu hết các hệ thống, kernel sẽ chiếm một phần cố định của bộ nhớ; phần còn
lại phân phối cho các process. 2.
Địa chỉ vật lý (physical address) (địa chỉ thực) là một vị trí thực trong bộ nhớ chính 3.
Địa chỉ luận lý (logical address) là một vị trí nhớ được diễn tả trong một chương trình
(còn gọi là địa chỉ ảo virtual address).
● Các trình biên dịch (compiler) tạo ra mã lệnh chương trình mà trong đó mọi tham
chiếu bộ nhớ đều là địa chỉ luận lý
● Địa chỉ tương đối (relative address) (địa chỉ khả tái định vị, relocatable address) là
một kiểu địa chỉ luận lý trong đó các địa chỉ được biểu diễn tương đối so với một vị
trí xác định nào đó trong chương trình.
● Địa chỉ tuyệt đối (absolute address): địa chỉ tương đương với địa chỉ thực. 4.
Chuyển đổi địa chỉ: quá trình ánh xạ một địa chỉ từ không gian địa chỉ này sang
không gian địa chỉ khác. Phân mảnh: 5.
Phân mảnh ngoại (external fragmentation): Kích thước không gian nhớ còn trống đủ
để thỏa mãn một yêu cầu cấp phát, tuy nhiên không gian nhớ này không liên tục ⇒ có
thể dùng cơ chế kết khối (compaction) để gom lại thành vùng nhớ liên tục. 6.
Phân mảnh nội (internal fragmentation): Kích thước vùng nhớ được cấp phát có thể
hơi lớn hơn vùng nhớ yêu cầu. 7. Cách chia:
Fixed partitioning: vùng nhớ có kích thước cố định, process có kích thước nhỏ hơn
hoặc bằng kích thước partition thì được nạp => phân mảnh nội
Dynamic partitioning: Số lượng partition không cố định và partition có thể có kích
thước khác nhau => phân mảnh ngoại 8.
Chiến lược: Best-fix: Chọn khối nhớ trống nhỏ nhất phù hợp First-fix: Chọn khối
trống phù hợp đầu tiên từ bộ nhớ
Next-fix: Chọn khối trống phù hợp đầu tiên từ vị trí cấp phát cuối cùng Worst-
fix: Chọn khối nhớ trống lớn nhất
Phân trang: Bộ nhớ vật lý -> khung trang (frame), Bảng phân trang (page table) để ánh xạ
địa chỉ luận lý thành địa chỉ thực lOMoARcPSD| 36443508 9.
Chuyển đổi địa chỉ trong paging: Địa chỉ luận lý gồm có:
Số hiệu trang (Page number) p
Địa chỉ tương đối trong trang (Page offset) d lOMoARcPSD| 36443508 10. Effective access time (EAT) 11.
Tổ chức bảng trang: Bảng trang 2 cấp… 12. Thay thế trang nhớ
FIFO, OPT(nhìn về trước),LRU(nhìn về sau), Clock(Second Chance) 13. Bộ nhớ ảo:
HĐH lấy 1 phần thiết bị lưu trữ (đĩa cứng) mô phỏng như là bộ nhớ, gọi là bộ nhớ phụ.
Bộ nhớ ảo bao gồm bộ nhớ và bộ nhớ phụ.
Hiện nay HĐH chỉ tổ chức bộ nhớ ảo trong kỹ thuật phân trang và phân đoạn kết hợp. Tất cả
các trang của 1 tiến trình được nạp vào các khung trang của bộ nhớ ảo. Phụ thuộc vào HĐH,
có thể các trang tích cực (hoạt động) được chuyển vào bộ nhớ để thực thi, các trang không
tích cực sẽ được chuyển ra bộ nhớ phụ. Có thể sử dụng thuật Swapping để chuyển các khung
trang giữa bộ nhớ và bộ nhớ phụ.
Ưu điểm của bộ nhớ ảo
+ Số lượng process trong bộ nhớ nhiều hơn
+ Một process có thể thực thi ngay cả khi kích thước của nó
+ lớn hơn bộ nhớ thực lOMoARcPSD| 36443508
+ Giảm nhẹ công việc của lập trình viên Có hai kỹ thuật:
+ Phân trang theo yêu cầu (Demand Paging)
+ Phân đoạn theo yêu cầu (Demand Segmentation) lOMoARcPSD| 36443508
—-------------------------------------------------------------------------------------------------------------
- Lập lịch đặc quyền: tiến trình sẽ giành lấy CPU cho đến khi thực hiện xong
- Lập lịch không đặc quyền: tiến trình sẽ phân phát tài nguyên cho tiến trình khác
trong lúc không sửa dụng
- Các tiêu chí đánh giá lập lịch: CPU utilization Throughtput Turnaround Time Waiting Time Respond time:
- FCFS: Bài toán kẹt xe : Convoy Effect
* CRITICAL-SECTION PROBLEM (CSP)
- Loại trừ tương hỗ (Mutual Exclusion): Không có 2 tiến trình cùng ở trong miền găngcùng lúc
- Process: 1 tiến trình tạm dừng bên ngoài miền găng không được ngăn cản các tiến
trình khác vào miền găng
- Bounded Waiting: Không có tiến trình nào phải chờ vô hạn để được vào miền găng
-- Mutex Lock: Sử dụng acquire và Release
-- Semaphore: sử dụng wait và signal -- DeadLock:
- Mutual Exclusion (Có sử dụng tài nguyên không thể chia sẻ): Chỉ 1 ctrinh được sử
dụng tài nguyên ở 1 thời điểm
- Hold and wait (Chiếm giữ và yêu cầu thêm tài nguyên): 1 ctrinh sẽ giữ ít nhất 1
nguồn tnguyen rồi đợi để nhận thêm nguồn tài nguyên từ ctrinh khác
- No preemption (Không thu hồi tài nguyên từ tiến trình đang giữ chúng): Tài
nguyênkhông thể thu hồi từ tiến trình đang chiếm giữ chúng trước khi tiến trình này sử dụng chúng xong lOMoARcPSD| 36443508
- Circular wait (Tồn tại 1 chu trình trong đồ thị cấp phát TN): Có ít nhất 2 tiến trình
chờ đợi lẫn nhau. Tức là ttrinh này chờ được cấp phát TN đang bị ttrinh kia chiếm giữ và ngược lại
-- Cách ngăn chặn deadlock: Chỉ cần vô hiệu hóa 1 trong 4 tính chất trên. lOMoARcPSD| 36443508
LÝ THUYẾT ĐỂ LÀM BÀI
------------------------------------------------- * GIẢI THUẬT BANKER
------------------------------------------------Need = Request (Max) - Allocation
Tiến trình an toàn nếu: Avalable >= Need
(Avalable phải >= Need từng bit 1 => Avalable += Allocation)
-------------------------------------------------
* CÁC TIÊU CHÍ ĐIỀU ĐỘ CHO TIẾN TRÌNH - CHƯƠNG 3
-------------------------------------------------
-- Thuật toán FCFS (First Come First Served): Đến trước thực hiện trước
+ Tiến trình nào yêu cầu CPU trước sẽ được cấp CPU trước
+ HDH xếp tiến trình vào hàng đợi FIFO, tiến trình mới được xếp vào cuối hàng đợi
+ Đảm bảo tính công bằng, tuy nhiên FCFS có thời gian chờ đợi trung bình của tiến
trình lớn do phải chờ đợi tiến trình có chu kỳ CPU dài
Vd: tiến trình P1 : 10, P2: 4, P3: 2
=> Thời gian chờ lần lượt 0 -> 10 -> 14
(TimeP1=0 do thực hiện ngay, TimeP2=10 do chờ P1 thực hiện xong, TimeP3=14 do chờ P1 và P2)
=> Nếu có thời gian đến: Thời gian chờ của mỗi tiến trình = thời gian bắt đầu
thực hiện - thời gian đến
-- Thuật toán Round Robin (RR): Điều độ quay vòng
+ Cách tính thời gian chờ của một tiến trình bất kỳ: Tổng của các (thời gian bắt đầu
thực thi - thời gian bắt đầu chờ của chương trình đó)
-- Thuật toán SJF (Shortest Job First): Điều độ ưu tiên tiến trình ngắn nhất
+ SJF đặc quyền: Thực hiện tiến trình có thời gian nhỏ nhất
+B1: Xét theo thời gian đến: Ban đầu thực hiện P0
+B2: thực hiện xong thì xét xem những tiến trình nào đã xuất hiện trong quá
trình thực hiện P0, rồi chọn tiến trình nhỏ nhất để thực hiện +B3: Quay lại B2 đến khi xong -- Thuật toán SRTF
+ Ban đầu thực hiện P0
+ Trong lúc thực hiện nếu có tiến trình khác
=> Xét thời gian thực hiện còn lại của P0 với P1, ưu tiên thực hiện nhỏ
hơn, tiến trình còn lại cho vào hàng đợi lOMoARcPSD| 36443508 + Làm liên tục
. Tính thời gian chờ của mỗi tiến trình:
Thời gian bắt đầu đợt 2 - thời gian kết thúc đợt 1 + (Thời gian bắt đầu thực hiện - thời gian đến)
Nếu chỉ thực hiện đúng 1 lần, thì:
Thời gian = Thời gian bắt đầu thực hiện - thời gian đến
-------------------------------------------------
* CÁC GIẢI THUẬT PHÂN TRANG PHÂN ĐOẠN VÀ THAY TRANG - CHƯƠNG 4
-------------------------------------------------
-- CÁC GIẢI THUẬT PHÂN CHIA: - Kỹ thuật phân trang:
- Các khối có KT bằng nhau, vị trí cố định- Các bảng quản lý cấp phát:
+ JT (Job Table): Chứa thông tin về các tiến trình đang hoạt động
________ _______________ _________
| TTrinh | Kích thước TT | Đ/c PMT |
+ PMT (Page Map Table): Ánh xạ trang - Bảng trang
___________________ ___________ _________________________
| Số hiệu trang (p) | ... | Số hiệu khung trang (f) |
+ MMT (Memory Map Table): Quản lý khung trang
_________________________ _______ __________________
| Số hiệu khung trang (f) | Đ/c | Trạng thái (F/B) | F: Free, B: Busy
- Biến đổi địa chỉ: ___ ___
+ Địa chỉ logic có dạng: | p | d | p : Số hiệu
trang, d: độ dời (độ lệch) trang
=> Biến đổi địa chỉ: tra p trong PMT -> f
=> ĐCVL = f * kích thước trang + d + Địa chỉ vật lý:
d = (ĐCVL) % (KT trang), f = ĐCVL / KT trang;
tra f trong bảng PMT -> p => ĐC logic : ___ ___ | p | d | - Kỹ thuật phân đoạn: lOMoARcPSD| 36443508
- Tổ chức không gian địa chỉ: + Kích thước khác nhau
+ đ/c đầu -> số hiệu phân đoạn + qhe logic vs nhau
- Các bảng quản lý cấp phát:
+ JT (Job Table): Chứa thông tin về các tiến trình đang hoạt động
________ _______________ _________
| TTrinh | Kích thước TT | Đ/c SMT |
+ SMT (Segment Map Table): Ánh xạ phân đoạn - Bảng phân đoạn
_______________________ ____________
_______________________________
| Số hiệu phân đoạn (p) | Kích thước | Đ/c bắt đầu cấp phát (Bộ nhớ) |
+ MMT (Memory Map Table): Quản lý tương tự kỹ thuật phân vùng động
- Biến đổi địa chỉ: ___ ___
+ Địa chỉ logic có dạng: | s | d | s : Số hiệu phân đoạn, d: độ dời
(độ lệch) trong phân đoạn Tra s,d trong bảng SMT:
+ Nếu không có s => Phân đoạn chưa cấp phát -> Dừng
+ Nếu d >= kích thước của s -> Lỗi địa chỉ
+ Nếu đúng: từ s -> đc => ĐCVL = đc + d
+ Địa chỉ vật lý -> ĐC logic (cần biết đc phân đoạn) tìm những phân đoạn
có đc logic gần với ĐCVL, Tính d = ĐCVL - ĐC logic
Chọn nếu d < Kích thước của phân đoạn trong bảng SMT
- Kỹ thuật phân đoạn kết hợp:
- Tổ chức không gian địa chỉ: + Kích thước khác nhau
+ đ/c đầu -> số hiệu phân đoạn + qhe logic vs nhau
+ Mỗi phân đoạn -> Các trang, có KT = Khung trang
- Các bảng quản lý cấp phát:
+ JT (Job Table): Chứa thông tin về các tiến trình đang hoạt động
________ _______________ _________
| TTrinh | Kích thước TT | Đ/c SMT |
+ SMT (Segment Map Table): Ánh xạ phân đoạn - Bảng phân đoạn
_______________________ ____________ _________________
| Số hiệu phân đoạn (p) | Kích thước | Con trỏ đến PMT | lOMoARcPSD| 36443508
+ Mỗi bảng pđ có 1 bảng trang (PMT) riêng: Ánh xạ trang - bảng trang
______________________ ___________ _________________________
| Sh trang(p) trong pđ | ... | Số hiệu khung trang (f) |
+ MMT (Memory Map Table): Quản lý khung trang
_________________________ _______ __________________
| Số hiệu khung trang (f) | Đ/c | Trạng thái (F/B) | F: Free, B: Busy
- Biến đổi địa chỉ: ___ ___
+ Địa chỉ logic có dạng: | s | d |
+ s : Số hiệu phân đoạn, d: độ dời (độ lệch) trong phân đoạn
+ Tra s trong PMT của tất cả tiến trình chứa s -> Kích
thước + Nếu d >= KT -> Sai + Ngược lại: d' = d % (KT trang)
p = d / (KT trang) (cột bên
trái) Từ bảng PMT (s) và p -> f =>
ĐCVL = f * KT trang + d' + Địa chỉ
vly -> Logic: d' = ĐCVL % (KT trang) f = ĐCVL / (KT trang)
Tra bảng PMT cột trái => Cột phải (tìm được p) => d = p * (KT Trang) + d'
-- CÁC GIẢI THUẬT THAY TRANG - FIFO:
+ nếu không tìm thấy, thay tại vị trí couter lớn nhất, đặt counter = 1, các couter khác tăng 1 đơn vị
+ Nếu tìm thấy, thì không thay trang, nhưng vẫn tăng couter tất cả lên 1 đơn vị - TỐI ƯU:
+ Nếu không tìm thấy, thì nạp trang đó vào khung trang trống, đồng thời thấy
số thứ tự tiếp theo của trang đó làm couter. Khi khung trang đầy, thì tìm trang trong bộ
nhớ có counter lớn nhất sẽ bị thay (do lâu dùng nhất trong tương lai)
+ Nếu tìm thấy, thì không thay, nhưng đổi counter = số thứ tự trang đó tiếp theo
+ Khi không tìm thấy số thứ tự trang tương lai (trang cuối) thì couter của trang đó = tổng số trang + 1
+ Nếu có 2 trang có cùng counter, thì chọn thay theo chiều nào cũng được. Sẽ
phải chọn chiều đó làm tương tự đến khi nào xong => Lỗi trang khi: Không tìm thấy trang - LRU: lOMoARcPSD| 36443508 . Counter:
+ nếu không tìm thấy, thay tại vị trí couter lớn nhất, đặt counter = 1, các couter khác tăng 1 đơn vị
+ Nếu tìm thấy, thì không thay trang, nhưng counter của trang tìm thấy = 1, vẫn
tăng couter còn lại lên 1 đơn vị (Điểm khác so với FIFO, do counter = 1 khó bị thay nhất) . Stack:
+ Nếu tìm không thấy, thì nạp vào khung trang trống, và điền nó vào đỉnh
stack. Nếu stack đầy, thì đẩy trang ở đỉnh stack ra, và đẩy tất cả đỉnh trang xuống, và
trang không tìm thấy đó sẽ nạp vào cuối stack.
+ Nếu tìm thấy, bất kể nằm đâu thì phải để trang đó vào cuối stack, giữ nguyên
thứ tự của cách trang còn lại.
- Thuật toán CƠ HỘI LẦN 2 (bit = 1 truy xuất trang, con trỏ di chuyển tất cả trường hợp)
Sử dụng bảng bit đánh dấu, Nếu bit bằng 1 thì truy xuất trang và cho bit bằng
0. Nếu tìm thấy bit 0 trang đó lần nữa thì mới bị thay
+ Nếu tìm không thấy, đưa trang đó vào khung trang trống, cho bit bằng 0 và
chuyển đến bit tiếp theo
Nếu bảng bit đi đến cuối, thì quay trở lại
Nếu không tìm thấy, và bit = 1, thì cho bit = 0 và không thay trang, di chuyển tiếp
+ Nếu tìm thấy, đổi bit trạng thái = 1, con trỏ chuyển đến trang tiếp
------------------------------------------------Bài tập chỉ số khối:
- Chỉ số khối chứa trong Directory Entry:
- Chỉ số khối chưa trong FAT
+ Dùng bảng FAT để quản lý khối:
Trong Root Directory: Chỉ ghi chỉ số khối bắt đầu => Truy xuất chỉ số khối
trong bảng FAT để tìm chỉ số khối tiếp theo - Cấu trúc I - node:
+ Bắt đầu bằng i-node num & file + Cách lưu trữ: Nếu dữ liệu nhỏ
Nếu dữ liệu lớn: Direct Blocks chia làm nhiều phần, mỗi phần trỏ đến 1 data block ...
(Cấu trúc trong bảng i-node)
—---------------------------------------------------------------------------------------- lOMoARcPSD| 36443508
EAT = @(TLB + X) + (1-@)(TLB + 2X) = TLB + 2X - @X @ : hit ratio sử dụng TLB
EAT: Thời gian truy xuất bộ nhớ trong hệ thống (Effective access time)
TLB: thời gian để tìm trong TLB
X: thời gian chu kỳ truy xuất bộ nhớ