When accessing the logical address at , 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 0x0000F1AE (in
hexadecimal) with a page size of 256 bytes, what is the page offset?
A) 0xAE
B) 0xF1
C) 0xA
D) 0xF100
10) A computer based on dynamic storage memory allocation has a main memory with
the capacity of 55MB (initially empty). A sequence of operations including main
memory allocation and release is as follows: 1. allocate 15MB; 2. allocate 30MB; 3.
release 15MB; 4. allocate 8MB; 5. allocate 6MB. Using the best-fit algorithm, what is the
size of the largest leftover hole in the main memory after the above five operations?
A) 7MB
B) 9MB
C) 10MB
D) 15MB
2. [20 points] Synchronization
You are asked to implement the second reader-writer solution, in which once a writer
is ready, it needs to perform update as soon as possible. There are two classes of
processes accessing shared data, readers and writers. Readers never modify data, thus
multiple readers can access the shared data simultaneously. Writers modify shared
data, so at most one writer can access data (no other writers or readers). This solution
gives priority to writers in the following manner: when a reader tries to access shared
data, if there is a writer accessing the data or if there are any writer(s) waiting to access
shared data, the reader must wait. In another word, readers must wait for all writer(s),
if any, to update shared data, or a reader can access shared data, only when there is no
writer either accessing or waiting.
The following variables will be used:
semaphore mutex =1; /* lock for accessing shared variables */
semaphore readerlock=0; /* readers waiting queue */
semaphore writerlock=0; /* writers waiting queue */
int R_count = 0; /* number of readers accessing data */
int W_count = 0; /* number of writer accessing data */
int WR_count = 0; /* number of readers waiting */
int WW_count = 0; /* number of writers waiting*/
TA Yixin YANG ( yyangfe@cse.ust.hk ) is responsible for questions before the deadline
TA Peng YE ( pyeac@cse.ust.hk ) is responsible for grading and appeal handling after the deadline
Please fill in the blanks to design Writer s and Reader s code.
Writer() {
// Writer tries to enter
wait(mutex);
while (BLANK1) { // Is it safe to write?
WW_count++;
BLANK2
WW_count--;
}
W_count++; // Writer inside
signal(mutex);
// Perform actual read/write access
// Writer finishes update
BLANK3
W_count--; // No longer active
if (BLANK4){ // Give priority to writers
signal(writerlock); // Wake up one writer
} else if (WR_count > 0) { // Otherwise, wake reader
BLANK5
}
signal(mutex);
}
Reader() {
// Reader tries to enter
wait(mutex);
while (BLANK6) { // writer inside or waiting?
BLANK7
wait(readerlock); // reader waits on readerlock
BLANK8
}
Rcount++; // Reader inside!
signal(mutex);
// Perform actual read-only access
// Reader finishes accessing
wait(mutex);
R_count--; // No longer active
if (BLANK9) // No other active readers
BLANK10
signal(mutex);
}
3. [30 points] Deadlocks
Consider the following snapshot of a system:
TA Yixin YANG ( yyangfe@cse.ust.hk ) is responsible for questions before the deadline
TA Peng YE ( pyeac@cse.ust.hk ) is responsible for grading and appeal handling after the deadline
Allocation Max Available
A B C D A B C D A B C D
P0 2 0 0 1 4 2 3 4 3 3 2 1
P1 3 1 2 1 5 2 3 2
P2 2 1 0 3 2 3 1 6
P3 1 3 1 2 1 4 2 4
P4 1 4 3 2 3 6 6 5
Please answer the following questions using the banker s algorithm:
1) (5 points) What is the content of the matrix Need denoting the number of resources
needed by each process?
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, 0), can the request be
4) (10 points) If a request from process P4 arrives for (0, 0, 2, 0), can the request be
granted immediately? Why?
TA Yixin YANG ( yyangfe@cse.ust.hk ) is responsible for questions before the deadline
TA Peng YE ( pyeac@cse.ust.hk ) is responsible for grading and appeal handling after the deadline
4. [30 points] Memory Management
1) (15 points) 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 420
1 144
2 198
3 296
4 50
5 32
2) (15 points) Consider a virtual memory system providing 128 pages for each user
program; the size of each page is 8KB. 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
TA Yixin YANG ( yyangfe@cse.ust.hk ) is responsible for questions before the deadline
TA Peng YE ( pyeac@cse.ust.hk ) is responsible for grading and appeal handling after the deadline
Assume there are three requests on logical address 040AFH, 140AFH, 240AFH. First
please describe the format of the logical address and the physical address. Then please
illustrate how the virtual memory system will deal with these requests.