Q1: Link the following and give me the memory map and symbol table of the executable.
2 bab 3 aba 4 1 cd 3 -1 6 I 1004 A 5678 R 2002 E 8002 R 2001 R 2003 0 2 bab 1 -1 cd 3 2 -1 6 R 8002 E 1000 E 1000 E 3000 R 1002 A 1010 1 cd 3 3 bab 2 -1 cd 1 -1 aba 4 -1 5 A 8000 E 1001 E 2000 I 2000 E 7004 0 2 cd 1 -1 aba 4 -1 7 A 8000 E 1001 A 2000 I 2000 E 7004 R 1002 R 1003
Q2: Consider the following snapshot of a system:
Alloc Max Avail. P1 0 0 0 2 4 5 6 2 1 3 2 2 P2 1 1 2 0 4 5 6 2 P3 1 1 2 0 2 4 3 2 P4 1 0 0 0 3 4 3 1
The system is in a safe state. Prove this by giving a sequence where everybody's max needs are satisfied. Do this by showing Available and Event columns.
Q3: Explain the difference between deadlock prevention, avoidance, and detection.
Q4: Banker's algorithm is for
(a) deadlock
prevention
(b) deadlock avoidance
(c) deadlock detection
(d) deadlock
resolution
(e) resource locking
Q5: What are the shared variables needed to implement a FIFO between a writer process and a reader process without using semaphores?
Q6: The only way to implement semaphores with user-level code in the lack of OS functions is an IPC server daemon. True or false?
Q7: In Windows let's say I just wrote and compiled a program in C:\myprogs\mynewprog\bindir directory. I want to be able to run this program from a cmd window while in other directories without typing the path to the executable. How do I do this?
Q8: Consider the following snapshot of a system:
Alloc Max Avail. P1 0 0 0 2 4 5 6 2 1 3 2 2 P2 1 1 2 0 4 5 6 2 P3 1 1 2 0 2 4 3 2 P4 1 0 0 0 3 4 3 1
The system is in a safe state. Prove this by giving a sequence where everybody's max needs are satisfied. Do this by showing Available and Event columns.
Q9: Consider 5 dining philosophers in a circle -- numbered 4 through 0 from left to right. We will coordinate their eating with an arbiter. Each philosopher eats for 2 mins non-stop when he eats. The arbiter uses a mix of a queue scheme and a fixed-priority (FP) scheme. 0 has the highest priority and the rest are arbitrated based on a "queue". Philosopher 4 and 3 immediately get hungry after they finish eating. Philosopher 0 stays 3 minute not-hungry between each feast. 1 stays not-hungry for 2 mins. 2 stays not-hungry for 1 min. The arbiter checks and decides who will eat next in the middle of every minute. When the arbiter gives them a go-ahead at the beginning, assume that they all came to the table from a restaurant. Show the progression of events for 12 minutes. H stands for hungry and waiting. e for 1st min and E for 2nd min eating. [1-3] for not-hungry. Assume that the queue is 4321 initially.
Q10: Link the following and give me the memory map and symbol table of the executable.
0 2 bab 1 -1 cd 3 2 -1 6 R 8002 E 1000 E 1000 E 3000 R 1002 A 1010 1 cd 3 3 bab 2 -1 cd 1 -1 aba 4 -1 5 A 8000 E 1001 E 2000 I 2000 E 7004 0 2 cd 1 -1 aba 4 -1 7 A 8000 E 1001 A 2000 I 2000 E 7004 R 1002 R 1003 2 bab 3 aba 4 1 cd 3 -1 6 I 1004 A 5678 R 2002 E 8002 R 2001 R 2003
Q11: Link the following and give me the memory map and symbol table of the executable.
2 ba 3 ab 2 1 z 2 3 -1 4 I 1004 A 5678 E 2000 E 8002 0 2 ba 1 -1 z 3 2 -1 6 R 8002 E 1000 E 1000 E 3000 R 1002 A 1010 1 z 3 3 ba 2 -1 z 1 -1 ab 4 -1 5 A 8000 E 1001 E 2000 I 2000 E7004
Q12: Consider 5 dining philosophers in a circle -- numbered 4 through 0 from left to right. We will coordinate their eating with an arbiter. They all eat for 2 mins at a time. The arbiter uses a mix of a round-robin (RR) scheme and a fixed-priority (FP) scheme. The priorities go as follows: 2 is the highest, then comes 1, then 0; philosophers 4 and 3 are equal priority and the lowest of all. The arbiter does an RR between 4 and 3. Philosopher 4 and 3 immediately get hungry after they finish eating. Philosopher 0 stays 1 minute not-hungry between each feast. 1 stays not-hungry for 2 mins. 2 stays not-hungry for 3 mins. The arbiter checks and decides who will eat next in the middle of every minute. When the arbiter gives them a go-ahead at the beginning, assume that they all came to the table from a restaurant. Show the progression of events for 10 minutes. H stands for hungry and waiting. e for 1st min eating and E for 2nd min eating. [1-3] for not-hungry. P stands for ptr. G for grant. Assume that P=4 initially.
Q13: Consider the following snapshot of a system:
Alloc Max Avail. P1 0 0 0 4 5 6 1 3 2 P2 1 1 2 4 5 6 P3 1 0 0 3 4 3 P4 1 1 2 2 4 3
The system is in a safe state. Prove this by giving a sequence where everybody's max needs are satisfied. Do this by showing Available and Event columns.
Q14: A FIFO can only be written with non-binary semaphores. True or false?
Q15: If there is no IPC implemented in an OS, processes cannot exchange data. True or false?
Q16: Consider 5 dining philosophers in a circle -- numbered 4 through 0 from RIGHT to LEFT. We will coordinate their eating with an arbiter. They all eat for 2 mins. The arbiter uses a mix of a round-robin (RR) scheme and a fixed-priority (FP) scheme. The priorities go as follows: 0 is the highest, then comes 1, then 2. Phil. 3 and 4 are equal priority and the lowest of all. The arbiter does an RR between 3 and 4. Philosophers 3 and 4 immediately get hungry after they finish eating. Philosopher 0, stays 3 minutes not-hungry between each feast. 1 stays not-hungry for 1 min. 2 stays not-hungry for 1 min as well. The arbiter checks and decides who will eat next in the middle of every minute. When the arbiter gives them a go-ahead at the beginning, assume that they all came to the table from a restaurant. Show the progression of events for 10 minutes. H stands for hungry and waiting. e for 1st min E for 2nd min eating. [1-3] for not-hungry. P stands for ptr. G for grant. Assume that P=3 initially.
Q17: Link the following and give me the memory map and symbol table of the executable.
1 yz 4 3 ba 2 -1 yz 1 -1 ab 4 -1 5 A 8010 E 2001 E 2000 I 2000 E 7004 2 ba 3 ab 2 1 yz 2 3 -1 4 I 1004 A 5678 E 2000 E 8002 0 2 ba 1 -1 yz 3 2 -1 6 R 8002 E 5000 E 1000 E 3000 R 1002 A 1010
Q18: Consider the following snapshot of a system:
Alloc Max Avail. P0 0 0 0 4 5 6 1 3 2 P1 1 0 0 3 4 3 P2 1 1 2 2 4 3 P3 1 1 2 3 5 6
The system is in a safe state. Prove this by giving a sequence where everybody's max needs are satisfied. Do this by showing Available and Event columns.
Q19: DMA means Direct Memory Access. What is it that accesses
memory directly?
(a) Cache
(b) Peripherals
(c) Hard disk
(d)
CPU
(e) Graphics adapter
Q20: A queue can only be written with binary semaphores. True or false?
Q21: Consider 6 dining philosophers in a circle. Here are the key parameters of the problem:
- philosophers numbered as 543210 - 0 eats for 1 min while rest eat for 2 mins - priority: 543 then queue - queue: 210 at t=0 - arbitrate in the middle of a min - 200022 are mins not-hungry - initially all are * hungry *
Show the progression of events for 12 minutes. H stands for hungry and waiting. e for 1st min eating and E for 2nd min eating. [1-2] for not-hungry.
Q22: Link the following and give me the memory map and symbol table of the executable.
2 foo 3 fn 1 1 foo 3 -1 6 I 2014 R 2002 A 3333 E 7003 R 1001 R 3003 0 2 fn 4 -1 foo 3 2 -1 5 R 8002 R 8002 E 2111 E 1000 E 4002 1 main 4 3 foo 1 2 -1 main 3 -1 fn 4 -1 5 R 8004 E 1011 E 4000 E 2000 E 7004 0 2 fn 1 -1 foo 4 -1 7 A 8000 E 1001 A 2000 I 2000 E 7004 R 1002 R 1003
Q23: Consider the following snapshot of a system:
Alloc Max Avail
A B C D A B C D A B C D
------- ------- -------
P0 2 0 0 2 5 5 4 3 1 1 2 4
P1 1 0 2 0 2 2 2 2
P2 1 1 0 0 3 4 5 6
P3 1 3 2 0 3 5 6 2
(a) The system is in an unsafe state. Explain why. (b) What is the min number extra resources we need to add to Avail to make the system safe. (c) Add that many resources and then show that the system is now in a safe state by giving a sequence where everybody's max needs are satisfied. Do this by showing Avail and Event columns.
Q24: How do we implement a semaphore mechanism with user-level code if the OS has no semaphore implementation. Explain why.
Q25: What are the two steps a compiler performs? And what is the advantage of separating the two steps?
Q26: There are 2 processes that process packets: process A and B. Every once in a while, process A receives a burst of N packets from outside and it has a buffer for exactly N packets. Process A either receives the N packets as a whole or declines the transfer. For efficency purposes, the 2 processes process packets in groups of multiple packets. Process A processes 2 packets at a time and produces 2 packets and sends them to process B. Process B processes 3 packets at a time and sends 2 result packets to process A. Process B has a considerably large buffer. (a) If N=5, there would be deadlock after a while. Show the sequence which leads to deadlock. (b) Trace the sequence of events, for N=1 thru 4 and see for each N, if a deadlock occurs.
Q27: See here for linker inputs and outputs (hence solutions). See the link on our YahooGroup titled "A simple linker from NYU".
Q28: Consider 4 dining philosophers in a circle -- numbered 3, 2, 1, 0. We will coordinate their eating with a referee (ie. hakem). The referee uses a round-robin (RR) scheme as follows (see here for general info). He has a pointer that points to the VIP (Very Important Philosopher) of the moment. If ptr=2 for ex., then 2 gets to eat in the next min if he is hungry (H). If not, the ref. checks to see 1 is H, if not 0 is H, if not 3 is H. Consider a clock that advances one minute at a time. Every philosopher eats for 2 minutes when he eats. Philosopher 0 stays full (ie. not-hungry) for 0 minutes. That is, as soon as he finishes eating, he immediately gets hungry. Philosopher 1, stays 1 minute not-hungry between each feast. 2 stays not-hungry for 2 mins. 3 stays not-hungry 3 mins. The ref. checks and decides who will eat next in the middle of every minute. When the ref. gives them a go-ahead at the beginning, assume that they all came to the table from a restaurant. Show the progression of events. H stands for hungry and waiting. E for eating. [1-3] for not-hungry. P stands for ptr. G for grant. Assume that P=3 initially.
Q29: Consider the above problem with the above RR scheme but assume all philosophers get hungry immediately. Can you come up with a state such that when the RR scheme gets into that state, it will go into such a vicious cycle that half of the philosophers would starve.
Q30: Consider the problem in Q5 with the same eating habits there. However, modify the RR scheme as follows. The ref executes RR scheme at the beginning of every minute in the blink of an eye. Show the sequence of events and look at effiviency and fairness isues.
Q31: Consider Q5. Show me the sequence in the case where a "Queue" based scheduling is used. As we discussed in class, the queue method is as follows. Instead of maintain just a pointer, we maintain a complete queue. Every cycle, we scan the queue starting from the topmost entry in the queue, we schedule all the philosophers who can eat to the following cycle, and move them to the end of the queue in the order they are scheduled. While the queue is always in a 3210 order or its rotated versions in RR arbitration, in the queue method, the philosophers may have any order. Therefore, in RR there are 4 different possible orders, in the queue method, there are 4! orders, ie. 24.
Q32: Solve MHW1-Q1 such that no buffer slots are wasted. You are allowed to use two additional shared variables but still no semaphores.
Q33: Writes to shared memory from parallel processes require serialization. What are the different ways of achieving serialization?
Q34: What is cooperative multitasking? And how is it different from preemptive (ie. regular) multitasking?
Q35: Exercise 8-13 in the 6th edition of Silberschatz. (Just to make sure we are looking at the same problem, Available = [1 5 2 0]).
Q36: What is .o file? What is .a file in UNIX?
Q37: How do I control whether I run a process in the background when issued from a command window in UNIX? DO I have a similar control mechanism in Windows?
Q38: What is the name of the first PC-UNIX? Which company developed it and which company funded the development?
Q39: For what reasons early mainframes used magnetic tapes as main memory?
Q40: Silberschatz 6th edition, exercise 7.9 (Cigarette-Smokers Problem).
Q41: Consider 5 dining philosophers in a circle -- numbered 4 through 0 from left to right. We will coordinate their eating with an arbiter. Each eats for 2 mins when he eats. The arbiter uses a mix of a queue scheme and a fixed-priority (FP) scheme. 0 has the highest priority and the rest are arbitrated based on a "queue". Philosophers 4 and 3 immediately get hungry after they finish eating. Philosopher 0 stays 4 minute not-hungry between each feast. 1 stays not-hungry for 2 mins. 2 stays not-hungry for 1 min. The arbiter checks and decides who will eat next in the middle of every minute. When the arbiter gives them a go-ahead at the beginning, assume that they all came to the table from a restaurant. Show the progression of events for 12 minutes. H stands for hungry and waiting. e for 1st min eating and E for 2nd min eating. [1-4] for not-hungry. Assume that the queue is 4321 initially.
Q42: What is BIOS? Give me a short description.