CS423 Homework 1 - SolutionProcesses and Threads1. Processes may be in one of three states: Running, Ready, or Blocked. However, not all sequences of these three states are possible. In the list below, identify the sequence of states that is possible. (a) Blocked  Ready  Running  Blocked(b) Running  Ready  Blocked  Running(c) Running  Ready  Blocked  Ready(d) Blocked  Running  Ready  Blocked(e) None of the aboveSolution: (a)Blocked can only be followed by Ready, and Ready can only be followed by Running. Thus, any sequence in which Blocked is followed immediately by Running is wrong, and so is any sequence where Ready is followed immediatelyby Blocked.2. A producer P and consumer C communicate by means of three semaphores and a buffer that has a capacity of 10. - Semaphore M enforces mutual exclusion; it is initially 1, is decremented by whichever process wants to enter its critical region (the code that adds or removes items from the buffer), and incremented back to 1 after leaving the critical region. - Semaphore F counts the number of full slots in the buffer. It is initially 0, is decremented by C before entering its critical region, and incremented by P after leaving its critical region. - Semaphore E counts the number of empty slots in the buffer. It is initially 10, is decremented by P before entering its critical region, and incremented by C after leaving its critical region. Before entering a critical region, a process first tries to decrement E or F, and then tries to decrement M. On leaving a critical region, a process first raises M and then E or F. Under these assumptions, what are the possible combinations of values of E, F, and M that can exist? Identify,in the list below, the combination that cannot exist. (a) M = 0, E = 5, F = 3(b) M = 0, E = 8, F = 0(c) M = 0, E = 7, F = 1(d) M = 1, E = 7, F = 0(e) M = 1, E = 9, F = 1CS423 Homework 1 - SolutionSolution: (d)When neither P nor C is in its critical region or attempting to enter its critical region, F+E=10 and M=1. If one tries to enter its critical region, it decrements E or F, in which case E+F=9, while M is still 1. It is possible that, at the sametime, the other process also tries to enter its critical region, and decrements the other of E and F, resulting in E+F=8with M=1. Then, one of these processes must set M=0 and enter its critical region. On exiting the critical region, M becomes 1 again, while E and F are unchanged; their sum is either 8 or 9. However, the process exiting the critical region will increment one of E or F, resulting in M=1 and E+F=9 or 10. If E+F=9, the other process may set M=0 and enter its critical region. If E+F=10, then M will stay 1 until P or C decrements E or F. The only other constraints are that neither E, F, nor M can be negative. The conclusion is that if M=0, then E+F = 8 or 9, and if M=1, then E+F = 8, 9 or 10. Since executing P increments F and decrements E, while executing C does the opposite, we conclude that any of these combinations of M, E, and F described above are possible, subject only to the constraints of no negative values. Paging:3. Consider a memory-management system based on paging. Let the total size of the physical memory be 2GB, laid out over pages of size 4KB. Let the logical address space of each process be limited to 128MB. Based on the information above, determine the physical address layout in the system (i.e., the total number of bits in a physical address, the number of bits specifying the physical frame number, and the number of bits specifying the page displacement). How many physical frames are there in the system? Determine the logical address layout in a similar way. How many pages are there in the logical address space of each process? Finally, compute the number of entries in each page table and the size of each page table entry. Based on the computation above, identify the TRUE statement from among those below. (a) 1 Each page table entry has 13 bits (including 1 valid/invalid bit).(b) Each logical address has a total of 27 bits, with 17 bits for the page number and 10 bits for displacement.(c) Each logical address has a total of 27 bits, with 13 bits for the page number and 14 bits for displacement.(d) Each physical address has a total of 31 bits, with 19 bits for the page frame number and 12 bits for the displacement.(e) There are a total of 32,768 frames in the system.CS423 Homework 1 - SolutionSolution: (d)The total physical memory size is 2GB, so each physical address requires 31 bits. The page size is 4KB, requiring 12 bits of displacement in each address. Thus, the physical address layout is 31 bits, including 19 bits for the page frame number and 12 bits of displacement. Note that there are 512K page frames in the system. The logical address space for each process is 128MB, requiring a total of 27 bits. The page size is the same as that ofthe physical pages (i.e., 4KB). Therefore the logical address layout is 27 bits, with 15 bits for page number and 12 bits for displacement. Note that there are 32K pages in the address space of each process. Each page table should contain as many entries as there are logical pages in the address space of each process. Therefore, there are 32K entries in each page table. Each entry in a page table contains a valid/invalid bit and a page frame number. Since the page frame number has 19 bits, the length of each entry in the page table is 20 bits. Please refer to Section 3.3.1 (p. 189) for a discussion of Paging.4. Consider a system with 16MB of physical memory laid out over pages of 8KB size. Let P1 be a processin this system with the following page table: Valid Bit Frame Number1 2051 1091 3040 00 00 00 00 0Let P2 be another process in this system with the following page table: Valid Bit Frame Number1 2451 3781 1841 642CS423 Homework 1 - Solution1 5251 7121 4350 0Consider the logical addresses 0x26ca and 0x54b9 of process P1. Note that the addresses are represented in hexadecimal notation (e.g., 0x26ca refers to 0010 0110 1100 1010). Also, considerthe logical addresses 0x56d8 and 0xd695 of process P2. For these four logical addresses, determine the corresponding physical addresses. Note that the frame numbers in the page tables are given in decimal notation. In the following answer choices, let (A, L, P) denote that the logical address L of process A translates to the physical address P. Identify the triple that denotes a correct address