Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

(1) Which of the following statements is TRUE about Race Condition? A) Race Condition…

  1. User

    (1) Which of the following statements is TRUE about Race Condition? A) Race Condition can cause potential data inconsistency B) The outcome of the executions depends on the particular order C) Even race condition exists, the outcome of the executions can be correct D) All of the above (2) Which of the following statements is TRUE about Mutex Lock? A) Calling acquire() of a mutex lock can be interrupted B) Calling release() of a mutex lock can be interrupted C) Mutex lock is often implemented as a spinlock D) All of the above (3) Which of the following statements is FALSE about Semaphore? A) Improper usage of semaphore can cause deadlock B) Semaphore can be used as a mutex lock C) Semaphore values cannot become negative D) Semaphore has busy waiting and non-busy waiting versions (4) Which of the following statements is TRUE about Reader-Writer Problems? A) Multiple readers cannot read the shared data simultaneously B) We should always prioritize readers in reader-writer problem C) OS usually provides a reader-writer lock to mitigate the starvation problem D) None of the above (5) Which of the following statements is TRUE about Deadlock? A) Deadlock prevention and avoidance guarantee that deadlock will never happen B) Circular wait always leads to deadlock C) The number of resource instances has no impact on whether the deadlock will happen D) None of the above (6) Which of the following statement is TRUE about the Bankers’ Algorithm? A) Bankers’ algorithm does not need to know the maximum resource usage for each process B) The Safety Algorithm is only invoked once at the beginning of the algorithm C) After resource is allocated using Resource-Request Algorithm, we never restore the state of resource allocation D) None of the above (7) Which of the following statement is FALSE about the Deadlock Detection Algorithm? A) The deadlock detection algorithm is identical to the safety algorithm B) Using deadlock detection algorithm for each resource allocation request causes large overhead C) The deadlock detection algorithm can tell which process cause the deadlock D) All of the above (8) Consider a segment table of one process: Segment # Segment length Starting address Permission Status 0 100 6000 Read-only In memory 1 150 5500 Read/Write In memory 2 350 4000 Read/Write In memory When accessing the logical address at <segment # = 2, offset = 400>, the results after address translation is: A) No such segment B) Return address 4400 C) Invalid permission D) Address out of range (9) In a system with 32-bit address, given the logical address 0x0000F1BC (in hexadecimal) with a page size of 256 bytes, what is the page offset? A) 0xBC B) 0xF1 C) 0xC D) 0xF100 (10) Which of the following statement is FALSE when comparing Segmentation and Paging Schemes? A) The number of entries in a page table is usually smaller than the number of entries in a segmentation table B) Paging scheme results in better memory utilization than segmentation scheme C) Sharing a segment is easier that sharing a page, as each segment represents a logical entity in a program D) Paging scheme does not suffer from external fragmentation

    1. (20 points) Process Synchronization This problem involves multiple readers and one writer accessing a shared resource. When the writer wants to write, readers must wait, ensuring the writer gets priority. We will use a new API pthread_cond_broadcast(&cond) to wake up all waiting threads on the conditional variable cond. Please fill in 10 blanks to correctly implement synchronization using mutex locks and condition variables. #include <pthread.h> #include <stdio.h> #include <unistd.h> int read_count = 0; // Number of active readers int writer_waiting = 0; // Is the writer waiting? pthread_mutex_t read_count_mutex; // Protects the read_count variable pthread_mutex_t writer_mutex; // Controls writer's priority and access pthread_cond_t reader_cond; // Condition variable for readers pthread_cond_t writer_cond; // Condition variable for the writer void* reader(void* arg) { // Lock to modify read_count pthread_mutex_lock(); // (1) Lock read_count_mutex to access read_count // Wait if the writer is waiting while () { // (2) Check if the writer is waiting pthread_cond_wait(, &read_count_mutex); // (3) Wait for the writer } read_count++; // Increment reader count pthread_mutex_unlock(&read_count_mutex); // Unlock read_count_mutex // Reading section printf("Reader %d is reading.\n", id); // Lock to decrement read_count pthread_mutex_lock(&read_count_mutex); // Lock read_count_mutex read_count--; // Decrement reader count // If no readers are active, signal the writer if () { // (4) Check if no readers are active pthread_cond_signal(); // (5) Signal the writer } pthread_mutex_unlock(&read_count_mutex); // Unlock read_count_mutex return NULL; } void* writer(void* arg) { // Lock to manage writer state and access pthread_mutex_lock(); // (6) Lock writer_mutex to access writer state writer_waiting = 1; // Mark the writer as waiting // Wait until all readers are done pthread_mutex_lock(&read_count_mutex); // Lock read_count_mutex while () { // (7) Check if any readers are active pthread_cond_wait(, &read_count_mutex); // (8) Wait for readers to finish } pthread_mutex_unlock(&read_count_mutex); // Unlock read_count_mutex // Writing section printf("Writer %d is writing.\n", id); writer_waiting = 0; // Mark the writer as not waiting // Signal waiting readers to proceed pthread_cond_broadcast(); // (9) Broadcast to readers pthread_mutex_unlock(); // (10) Unlock writer_mutex return NULL; }

    2. (30 points) Deadlocks Consider the following snapshot of a system: Allocation Max Available A B C D A B C D A B C D P0 2 0 0 1 4 2 3 3 2 3 2 1 P1 4 1 2 1 6 1 3 2 P2 1 1 0 3 2 4 1 6 P3 1 2 1 2 1 3 2 4 P4 1 4 5 1 3 4 6 1 (1) (5 points) What is the content of the Need matrix? (2) (10 points) Is the system in a safe state? Why? (3) (5 points) If a request from process P1 arrives for (1, 1, 0, 2), can the request be granted? Why? (4) (10 points) If a request from process P0 arrives for (1, 1, 2, 1), can the request be granted? Why?

    3. (20 points) Memory Management Consider the segment table shown in Table A. Translate each of the virtual addresses in Table B into physical addresses. Indicate errors (out of range, no such segment) if an address cannot be translated. Table A Segment number Starting address Segment length 0 260 90 1 1466 160 2 2656 130 3 146 50 4 2064 370 Table B Segment number Offset 0 10 1 180 2 100 3 80 4 50 5 32

    What is the Physical address of each Segment number and Offset Segment number Offset Physical address 0 10 1 180 2 100 3 80 4 50 5 32

    1. (12 points) Paging Consider a virtual memory system providing 256 pages for each user program; the size of each page is 4KB. The size of main memory is 256KB. Consider one user program occupied 4 pages, and the page table of this program is shown as below: Logical page number Physical block number 0 9 1 6 2 7 3 3 Assume there are two requests on logical address (in hexadecimal number) 010AF, 100AF. (1) (4 points) Please describe how many bits the virtual page number and the page offset contain, respectively. (2) (8 points) Please illustrate how the virtual memory system will deal with these requests. (Please indicate if there will be a page fault. If there is no page fault, please give the corresponding physical address.)
  2. Assistant

    Problem 1

    (1) Answer: D) All of the above

    All the statements A, B, and C about race conditions are true:

    • A) Race conditions can cause potential data inconsistency.
    • B) The outcome of the executions depends on the particular order.
    • C) Even if a race condition exists, the outcome of the executions can be correct (though not guaranteed).

    Therefore, the correct answer is D) All of the above.


    (2) Answer: D) All of the above

    Regarding mutex locks:

    • A) Calling acquire() of a mutex lock can be interrupted.
    • B) Calling release() of a mutex lock can be interrupted.
    • C) Mutex locks are often implemented as spinlocks in low-level programming (e.g., kernel code) to improve performance.

    All these statements are generally true, so the correct answer is D) All of the above.


    (3) Answer: C) Semaphore values cannot become negative

    This statement is FALSE because semaphore values can become negative in some implementations, indicating the number of processes waiting.


    (4) Answer: D) None of the above

    • A) FALSE: Multiple readers can read the shared data simultaneously.
    • B) FALSE: Prioritizing readers can lead to writer starvation; we should balance priority.
    • C) FALSE: The OS may provide reader-writer locks, but they don't inherently mitigate starvation without proper implementation.

    Therefore, the correct answer is D) None of the above.


    (5) Answer: A) Deadlock prevention and avoidance guarantee that deadlock will never happen

    This statement is TRUE. Proper deadlock prevention and avoidance techniques ensure that deadlocks do not occur.


    (6) Answer: D) None of the above

    All statements A, B, and C are FALSE:

    • A) The Banker's Algorithm requires knowledge of the maximum resource usage for each process.
    • B) The Safety Algorithm is invoked whenever a resource allocation request is made.
    • C) If a requested allocation leads to an unsafe state, the system must restore the previous state.

    Therefore, the correct answer is D) None of the above.


    (7) Answer: A) The deadlock detection algorithm is identical to the safety algorithm

    This statement is FALSE. While the deadlock detection algorithm and the safety algorithm are similar, they serve different purposes and are not identical.


    (8) Answer: D) Address out of range

    The offset 400 exceeds the segment length of 350 for segment 2, resulting in an address out of range.


    (9) Answer: A) 0xBC

    With a page size of 256 bytes (2^8), the page offset is the lower 8 bits of the address:

    • Offset = 0x0000F1BC (hexadecimal) ⇒ Offset = 0xBC

    (10) Answer: A) The number of entries in a page table is usually smaller than the number of entries in a segmentation table

    This statement is FALSE. The page table typically has more entries than the segment table because pages are fixed-size blocks dividing the entire address space, whereas segments are variable-sized and fewer in number.


    Problem 2

    Here are the correct entries for the blanks in the code:

    1. pthread_mutex_lock(&read_count_mutex);
    2. while (writer_waiting) {
    3. pthread_cond_wait(&reader_cond, &read_count_mutex);
    4. if (read_count == 0) {
    5. pthread_cond_signal(&writer_cond);
    6. pthread_mutex_lock(&writer_mutex);
    7. while (read_count > 0) {
    8. pthread_cond_wait(&writer_cond, &read_count_mutex);
    9. pthread_cond_broadcast(&reader_cond);
    10. pthread_mutex_unlock(&writer_mutex);

    Problem 3

    (1) Need Matrix:

    ProcessNeed ANeed BNeed CNeed D
    P02232
    P12011
    P21313
    P30112
    P42010

    (2) Answer:

    Yes, the system is in a safe state. A possible safe sequence is P1 → P0 → P2 → P3 → P4.

    (3) Answer:

    No, the request from P1 cannot be granted because it exceeds its maximum need in resource B.

    (4) Answer:

    No, the request from P0 cannot be granted because granting it would lead the system into an unsafe state.


    Problem 4

    Segment numberOffsetPhysical address
    010270
    1180Error – Offset out of range
    21002756
    380Error – Offset out of range
    4502114
    532Error – No such segment

    Problem 5

    (1) Answer:

    • Virtual page number bits: 8 bits (since there are 256 pages).
    • Page offset bits: 12 bits (since page size is 4KB).

    (2) Answer:

    • For logical address 010AF:
      • No page fault occurs.
      • Physical address is calculated as (Physical block number * page size) + offset = (6 * 4096) + 175 = 24751.
    • For logical address 100AF:
      • A page fault occurs because logical page number 16 is not mapped in the page table.