Ôn tập cuối kì OS - OS Finals

#schoolwork
May 29th 2026 15 Min.
Ôn tập cuối kì môn nguyên lí hệ điều hành - OS principles finals revision
Written by: Yuk

Table of Content

Block

Tiếng Việt

Câu 1: Đồng bộ hóa tiến trình (Process Synchronization) (2.5 điểm)

Một hang động du lịch có quy định để đảm bảo an toàn: chỉ cho phép tối đa 5 du khách được ở trong hang cùng một lúc. Lối vào và ra khỏi hang chung nhau một khe hẹp chỉ vừa đúng cho 1 người đi qua tại một thời điểm.

Hãy viết pseudo-code sử dụng cấu trúc Semaphore (các thao tác up() và down()) để đồng bộ hóa các tiến trình mô phỏng hành vi của các du khách bao gồm các bước: Lấy vé, qua lối hẹp vào hang, thưởng ngoạn, qua lối hẹp ra khỏi hang, trả vé.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
semaphore slot_hang = 5;  // Cho phép max 5 người
semaphore khe_hep = 1;    // Chỉ 1 người được qua khe cửa (Mutex)

void du_khach() {
    // VÀO HANG
    down(&slot_hang);     // Xếp hàng chờ lấy slot vào hang (đủ 5 thì phải đợi)
    down(&khe_hep);       // Xin quyền chui qua khe hẹp
    // (Đi qua khe hẹp)
    up(&khe_hep);         // Đi xong, nhả khe hẹp cho người khác

    // (Đang ở trong hang thưởng ngoạn...)

    // RA KHỎI HANG
    down(&khe_hep);       // Xin quyền chui qua khe hẹp để ra
    // (Đi qua khe hẹp)
    up(&khe_hep);         // Ra xong, nhả khe hẹp
    up(&slot_hang);       // Nhả slot trong hang cho khách mới vào
}
C
Mọi bài toán “Giới hạn N tài nguyên +1 con đường độc quyền” (như thư viện có N ghế, bãi đỗ xe có N chỗ…) đều dùng chung format này. Nguyên tắc: Luôn down cái giới hạn (N) trước, rồi mới down cái độc quyền / khóa Mutex (1). Làm ngược lại hệ thống sẽ bị Deadlock.

Câu 2: Quản lý bộ nhớ ảo (Virtual Memory) (2.5 điểm)

Một máy tính có không gian bộ nhớ ảo là 64KB, không gian bộ nhớ vật lý là 32KB. Kích thước mỗi trang bộ nhớ (Page Size) là 4KB.

  • a. Tính số bit dùng cho địa chỉ ảo, địa chỉ vật lý, và phần offset. Tính tổng số trang ảo (Virtual Pages) và số khung trang (Frames) của hệ thống.

  • b. Giả sử bộ nhớ vật lý cung cấp 4 khung trang (từ Frame 0 đến Frame 3) và đang áp dụng thuật toán thay thế trang FIFO. Bảng trang ban đầu trống. Hãy theo dõi sự thay đổi của bộ nhớ vật lý qua chuỗi chỉ thị CPU sau đây, chỉ rõ khi nào xảy ra lỗi trang (Page Fault) và trang ảo nào bị loại:

1
2
3
4
5
6
1. LOAD  R0  0x001
2. LOAD  R1  0x100
3. LOAD  R2  0x200
4. LOAD  R3  0x300
5. STORE R0  0x205
6. LOAD  R0  0x400
Text

  • a. Lời giải Tính toán bit:

    • Không gian ảo 64KB (2^16) => Địa chỉ ảo dài 16 bit.
    • Không gian vật lý 32KB (2^15) => Địa chỉ vật lý dài 15 bit.
    • Page size 4KB (2^12) => Phần Offset dài 12 bit.
    • Tổng số trang ảo (Pages) = Tổng dung lượng / Kích thước trang = 64KB / 4KB = 16 Virtual pages.
    • Số khung trang (Frames) = 32KB / 4KB = 8 Frames.

  • b. Lời giải Truy vết (Trace) FIFO:

    • Chú ý: Page size là 4KB (địa chỉ từ 0x000 đến 0xFFF đều cùng nằm trong Trang 0). Tất cả các địa chỉ đề cho (0x001, 0x100, 0x200, 0x300, 0x205, 0x400) đều bé hơn 0xFFF. Vậy tất cả chỉ lệnh này đều gọi tới Virtual Page 0.
    • Kết quả Trace:
      • Lệnh 1: LOAD 0x001 -> Nạp Trang 0 vào Frame 0 -> Xảy ra lỗi trang (Page Fault).
      • Lệnh 2 đến 6: Các địa chỉ đều nằm trong Trang 0 (đã nạp sẵn ở Frame 0) -> Đều HIT (không xảy ra lỗi trang, không bị loại trang nào). Bảng FIFO Queue không đổi.
Nếu như kích thước trang nhỏ hơn, ví dụ 256 Bytes (0x100). Nếu Page size = 256B, thì 0x001 là Trang 0, 0x100 là Trang 1, 0x200 là Trang 2… Lúc đó cứ nạp mới là phải xếp hàng vào Queue. Khung nào nạp vào đầu tiên (Head của Queue) sẽ bị đẩy ra (Evict) khi bộ nhớ đầy. Hãy nhớ chia địa chỉ ảo cho Page Size trước khi kết luận nó nằm ở trang nào, đừng chỉ nhìn vào chữ Hexadecimal.

Câu 3: Hệ thống tệp (File System) (2.5 điểm)

  • a. Phân biệt cách tổ chức móc nối của Hard Link (liên kết cứng) và Symbolic Link (liên kết mềm). Chuyện gì sẽ xảy ra đối với tệp liên kết nếu tệp gốc bị xóa?

  • b. Trình kiểm tra tính nhất quán hệ thống tệp phát hiện các lỗi sau trong bảng quản lý khối đĩa:

  • Khối 12: Bị đánh dấu là 0 ở cả bảng “khối đang dùng” và bảng “khối rỗi” (Orphan Block).
  • Khối 45: Được đánh dấu là đang dùng bởi một tệp, nhưng lại đồng thời xuất hiện trong danh sách khối rỗi (Inconsistent State).
  • Khối 88: Bị ghi nhận là đang dùng 2 lần, tức là có 2 tệp cùng trỏ tới (Cross-Link giữa 2 tệp).

Hãy đề xuất phương pháp hệ điều hành cần dùng để khắc phục 3 lỗi trên.

  • a. Lời giải Hard link vs Symbolic link:
    • Hard link (Liên kết cứng): Trỏ trực tiếp đến cùng một i-node với tệp gốc. Nếu tệp gốc bị xóa, dữ liệu vẫn còn và vẫn mở được bằng file Hard link (do biến đếm link count trong i-node vẫn lớn hơn 0).
    • Symbolic link (Liên kết mềm): Có một i-node riêng, dữ liệu bên trong chỉ chứa chuỗi đường dẫn văn bản trỏ tới tệp gốc. Nếu tệp gốc bị xóa, file soft link sẽ bị “mù” (lỗi find not found / dangling link).
  • b. Lời giải Block lỗi:
    • Orphan block (Khối 12): Khối bị thất lạc. Khắc phục: Đưa nó vào danh sách “khối rỗi” (Free blocks).
    • Inconsistent state (Khối 45): Vừa dùng vừa rỗi. Khắc phục: Xóa nó khỏi danh sách “khối rỗi”.
    • Cross-link (Khối 88): 2 file đang tranh giành 1 khối đĩa. Khắc phục: OS cấp phát một khối rỗi mới, copy dữ liệu từ khối 88 sang khối mới, rồi cập nhật i-node của 1 trong 2 file để nó trỏ sang khối mới.
Lỗi ổ đĩa chắc chắn chỉ xoay quanh 4 trường hợp. Trường hợp thứ 4 chưa có trong đề này là Duplicated free block (1 khối rỗi bị ghi 2 lần trong danh sách rỗi) -> Khắc phục: Xóa bớt 1 bản ghi dư thừa trong danh sách rỗi.

Câu 4: Bế tắc (Deadlock) (2.5 điểm)

  • a. Trong bài toán Dining Philosophers, hãy nêu cách bẻ gãy điều kiện Circular Wait (chờ vòng tròn) để ngăn chặn Deadlock. Phương pháp này có tính khả thi trong các hệ thống cơ sở dữ liệu thực tế không? Tại sao?

  • b. Một hệ thống có 3 tiến trình (A, B, C) sử dụng chung một loại tài nguyên. Tại một thời điểm, trạng thái hệ thống được ghi nhận như sau:

1
2
3
4
5
Tiến trình A: Allocation = 3, Max = 9
Tiến trình B: Allocation = 2, Max = 4
Tiến trình C: Allocation = 2, Max = 7

Available = 3
Text

Sử dụng thuật toán Banker's Algorithm, hãy lập ma trận Need và xác định xem hệ thống có đang ở trạng thái an toàn (Safe State) không bằng cách chỉ ra một chuỗi thực thi an toàn.

  • a. Lời giải Bữa ăn hiền triết (Circular Wait):

    • Giải pháp: Bẻ gãy chờ vòng tròn bằng cách đánh số các chiếc đũa. Bắt buộc các nhà hiền triết phải xin đũa theo thứ tự số tăng dần. Ví dụ: Các triết gia 1-4 lấy đũa trái trước, đũa phải sau; riêng triết gia thứ 5 phải lấy đũa phải trước, đũa trái sau để không tạo thành vòng tròn.
    • Tính khả thi: Cực kỳ hiệu quả với bài toán này, nhưng không khả thi trong hệ thống thực tế. Lý do là tài nguyên trong OS luôn thay đổi, ta không thể đánh số và sắp xếp thứ tự mọi tài nguyên trong hệ thống từ trước được.
Phần lý thuyết này rơi vào 1 trong 4 cách phá Deadlock. Nhớ 3 cách còn lại:
  • Hold & Wait: Lấy 2 đũa cùng lúc (kém hiệu quả, tốn tài nguyên).
  • Mutual Exclusion: Dùng trọng tài (Arbiter) điều phối (dễ gây nghẽn cổ chai).
  • No Preemption: Cấp quyền ưu tiên để ép nhả đũa (gây lỗi toàn vẹn dữ liệu).
  • Lời giải Thuật toán nhà băng (Banker’s Algorithm):

Tính ma trận Need (Nhu cầu = Max - Allocation):

1
2
3
4
Tiến trình A: Need = 9 - 3 = 6
Tiến trình B: Need = 4 - 2 = 2
Tiến trình C: Need = 7 - 2 = 5
Trình tự an toàn: Số Available hiện tại là 3.
Plaintext
  • B có Need(2) <= Available(3) -> Cho B chạy. B chạy xong trả lại 2 -> Available mới = 3 + 2 = 5.
  • C có Need(5) <= Available(5) -> Cho C chạy. C chạy xong trả lại 2 -> Available mới = 5 + 2 = 7.
  • A có Need(6) <= Available(7) -> Cho A chạy. A chạy xong trả lại 3 -> Available mới = 7 + 3 = 10.

Kết luận: Hệ thống đang ở trạng thái an toàn (Safe state).

Chuỗi an toàn là: B -> C -> A.

English

Question 1: Process Synchronization (2.5 points)

A tourist cave has a safety regulation: at most 5 visitors are allowed inside the cave at the same time. The entrance and exit share the same narrow passage, which can only accommodate 1 person passing through at a time.

Write pseudo-code using Semaphore constructs (the up() and down() operations) to synchronize processes that simulate the behavior of visitors, including the following steps: Obtaining a ticket, passing through the narrow passage into the cave, sightseeing, passing through the narrow passage out of the cave, and returning the ticket.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
semaphore cave_slots = 5;      // Allow at most 5 visitors
semaphore narrow_passage = 1;  // Only 1 visitor may pass through the passage (Mutex)

void visitor() {
    // ENTER THE CAVE
    down(&cave_slots);         // Wait for an available slot inside the cave
    down(&narrow_passage);     // Request permission to pass through the narrow passage
    // (Pass through the narrow passage)
    up(&narrow_passage);       // Release the passage for the next visitor

    // (Sightseeing inside the cave...)

    // EXIT THE CAVE
    down(&narrow_passage);     // Request permission to pass through the passage when exiting
    // (Pass through the narrow passage)
    up(&narrow_passage);       // Release the passage
    up(&cave_slots);           // Release a slot in the cave for a new visitor
}
C
Every problem involving “a limit of N resources plus one exclusive pathway” (such as a library with N seats or a parking lot with N spaces) follows the same pattern. The rule is: always perform down() on the limiting resource (N) before performing down() on the exclusive resource / Mutex (1). Reversing the order may lead to Deadlock.

Question 2: Virtual Memory Management (2.5 points)

A computer system has a virtual memory space of 64KB, a physical memory space of 32KB, and a page size (Page Size) of 4KB.

  • a. Calculate the number of bits used for the virtual address, physical address, and the offset. Also calculate the total number of virtual pages (Virtual Pages) and page frames (Frames) in the system.

  • b. Assume that physical memory provides 4 page frames (from Frame 0 to Frame 3) and uses the FIFO page replacement algorithm. The page table is initially empty. Track the changes in physical memory for the following sequence of CPU instructions, indicating when a Page Fault occurs and which virtual page is removed:

1
2
3
4
5
6
1. LOAD  R0  0x001
2. LOAD  R1  0x100
3. LOAD  R2  0x200
4. LOAD  R3  0x300
5. STORE R0  0x205
6. LOAD  R0  0x400
Text

  • a. Address Bit Calculation Solution:

    • Virtual memory space is 64KB (2^16) => Virtual addresses are 16 bits long.
    • Physical memory space is 32KB (2^15) => Physical addresses are 15 bits long.
    • Page size is 4KB (2^12) => The Offset field is 12 bits long.
    • Total virtual pages (Pages) = Total memory size / Page size = 64KB / 4KB = 16 Virtual Pages.
    • Number of page frames (Frames) = 32KB / 4KB = 8 Frames.

  • b. FIFO Trace Solution:

    • Note: The page size is 4KB (addresses from 0x000 to 0xFFF all belong to Page 0). All addresses given in the problem (0x001, 0x100, 0x200, 0x300, 0x205, 0x400) are less than 0xFFF. Therefore, all of these instructions access Virtual Page 0.
    • Trace result:
      • Instruction 1: LOAD 0x001 -> Load Page 0 into Frame 0 -> A Page Fault occurs.
      • Instructions 2 through 6: All addresses belong to Page 0 (already loaded in Frame 0) -> All are HITS (no Page Faults occur, and no page is removed). The FIFO queue remains unchanged.
If the page size were smaller, for example 256 Bytes (0x100), then 0x001 would belong to Page 0, 0x100 to Page 1, 0x200 to Page 2, and so on. In that case, each new page would have to be inserted into the FIFO queue. The page that entered first (the head of the queue) would be evicted when memory becomes full. Always divide the virtual address by the Page Size before determining which page it belongs to; do not rely solely on the hexadecimal representation.

Question 3: File System (2.5 points)

  • a. Differentiate between the linking mechanisms of a Hard Link and a Symbolic Link (soft link). What happens to the linked file if the original file is deleted?

  • b. A file system consistency checker detects the following errors in the disk block management tables:

  • Block 12: Marked as 0 in both the “allocated blocks” table and the “free blocks” table (Orphan Block).
  • Block 45: Marked as being used by a file, but also appears in the free block list (Inconsistent State).
  • Block 88: Recorded as being allocated twice, meaning two files point to the same block (Cross-Link between two files).

Propose the method the operating system should use to correct these three errors.

  • a. Hard Link vs Symbolic Link Solution:
    • Hard Link: Points directly to the same inode as the original file. If the original file is deleted, the data still exists and can still be accessed through the Hard Link (because the inode’s link count remains greater than 0).
    • Symbolic Link: Has its own inode, and its contents contain only a pathname pointing to the original file. If the original file is deleted, the symbolic link becomes “blind” (file not found / dangling link).
  • b. Disk Block Error Solution:
    • Orphan Block (Block 12): The block is lost. Fix: Add it to the “free block” list.
    • Inconsistent State (Block 45): The block is marked as both used and free. Fix: Remove it from the “free block” list.
    • Cross-Link (Block 88): Two files are competing for the same disk block. Fix: The OS allocates a new free block, copies the data from Block 88 into the new block, and updates the inode of one of the files so that it points to the new block.
Disk consistency problems generally fall into four common categories. The fourth category, not included in this problem, is a Duplicated Free Block (a free block recorded twice in the free list). Fix: Remove one of the duplicate entries from the free list.

Question 4: Deadlock (2.5 points)

  • a. In the Dining Philosophers problem, describe a way to break the Circular Wait condition in order to prevent Deadlock. Is this method practical in real-world database systems? Why?

  • b. A system has 3 processes (A, B, C) sharing a single type of resource. At a certain moment, the system state is recorded as follows:

1
2
3
4
5
Process A: Allocation = 3, Max = 9
Process B: Allocation = 2, Max = 4
Process C: Allocation = 2, Max = 7

Available = 3
Text

Using the Banker's Algorithm, construct the Need matrix and determine whether the system is in a Safe State by identifying a safe execution sequence.

  • a. Dining Philosophers (Circular Wait) Solution:

    • Solution: Break the circular wait condition by numbering the chopsticks. Philosophers must acquire chopsticks in increasing numerical order. For example, Philosophers 1-4 pick up the left chopstick first and then the right one; Philosopher 5 picks up the right chopstick first and then the left one, preventing a circular dependency from forming.
    • Practicality: This method is highly effective for this problem, but generally impractical in real-world systems. The reason is that resources in an OS are dynamic, and it is impossible to assign and enforce a global ordering for every resource in advance.
This theory question belongs to one of the four classical Deadlock prevention methods. Remember the other three:
  • Hold & Wait: Acquire both chopsticks at the same time (inefficient and resource-intensive).
  • Mutual Exclusion: Use an arbiter to coordinate access (can create a bottleneck).
  • No Preemption: Force resource release through priority mechanisms (may compromise data integrity).
  • Banker’s Algorithm Solution:

Calculate the Need matrix (Need = Max - Allocation):

1
2
3
4
5
Process A: Need = 9 - 3 = 6
Process B: Need = 4 - 2 = 2
Process C: Need = 7 - 2 = 5

Current Available = 3
Plaintext
  • B has Need(2) <= Available(3) -> Allow B to run. After B finishes, it releases its 2 allocated resources -> New Available = 3 + 2 = 5.
  • C has Need(5) <= Available(5) -> Allow C to run. After C finishes, it releases its 2 allocated resources -> New Available = 5 + 2 = 7.
  • A has Need(6) <= Available(7) -> Allow A to run. After A finishes, it releases its 3 allocated resources -> New Available = 7 + 3 = 10.

Conclusion: The system is in a Safe State. The safe sequence is:

B -> C -> A