Homework 1

INSTRUCTIONS

Out: August 29, 2005.
Due: At the start of lecture, September 9 (Friday), 2005. We will accept only solutions that are typed-up and printed out (figures and tables may be drawn by hand). No written solutions or online handins.
Resources you are allowed to use: Unless otherwise mentioned, the only resources you can use are the lectures slides, your notes, the Tanenbaum textbook, and any other textbook on OS's, architecture, data structures or previous CS material. You cannot refer to any online resources (unless otherwise mentioned). You cannot use ready-made solutions under any circumstances..
 Relevant Lectures: 1-4 AND 5-6.
 Points: Each problem below is worth 5 points, for a total of 40 points. If a question has multiple parts, the 5 points are split equally among the parts.
 Warning: Homeworks are individual efforts. Although you are allowed to discuss HWs with your fellow students, you are expected to solve them yourself and type up the solution yourself. For detailed information on penalties, cheating and playing it safe, see this page.

PROBLEMS

  1. Problem 1.11 from text, with some numbers replaced - use a textbook of 1024 pages, with each page consisting of 40 lines of 60 characters each. For disk devices, the access time given is per block of 4096 characters. The remaining part of the problem and the remaining numbers stay the same as in the textbook.
  2. (100 words max.) Describe the main difference between a TRAP and an INTERRUPT? Describe the main similarity between the two? Give one example of the use of each of the two.
  3. (75 words max.) What are L1 and L2 caches? Since caches improve performance, why not just make them as large as the main memory (say, 1 GB large)?
  4. Operating systems use "protected" instructions that are allowed to be executed only by some (special) processes or by OS-based processes. At the same time, reducing the number of protected instructions is important for improving user flexibility and performance. The following is a list of operations that is normally protected. What is the minimal (absolutely necessary) set of instructions among these that must be protected? The instructions: (1) change to user mode, (2) change to monitor mode, (3) read from OS memory, (4) write to OS memory, (5) fetch instruction from OS memory, (6) turn on timer interrupt, (7) turn off timer interrupt. Explain your answer(s).
  5. Describe the actions taken by a kernel to context switch between:
    1. (100 words max.) Two kernel-level threads that belong to the same process.
    2. (50 words max.) Two user-level threads that belong to the same process.
  6. (100 words) In class, we've seen that a Web Server process is best designed multi-threaded. Given a choice between user-level threads and kernel-level threads for a Web Server, which option would you choose? Why?
  7. The Linux operating system does not distinguish between processes and threads, but instead deals with entities known as "tasks." So, in a sense, Linux does not support threads. However, Linux offers kernel-level-like threads through a system call "clone()". clone() is used to create a new task from a given task so that the new task ("thread") can share certain components with the parent task ("thread"). A part of task_struct, the Linux-equivalent of the Process Control Block, is defined below. For each field-type in this structure below, specify for a clone() call: (a)  whether the child task will eventually receive a completely new value for the field from the parent task, or (b) whether the child task always retains the same field value as the parent, or (c) whether this depends on the specific Linux implementation. For each field-type, provide a 1 sentence justification for your choice. To start off, the child task has the same pid as the parent task (ah, Linux has peculiarities too!).

    struct task_struct {
      int pid; // id of this task
      volatile long state; // current process state - running, etc.
      long priority; // process priority
      unsigned long policy; // scheduling policy for this task
      unsigned long start_time; // time at which current task was generated
      unsigned short uid, gid; // userid and groupid of this task
      struct thread_struct tss; // pointer to save state of task (used for context switching)
      struct files_struct *files; // pointer to open file descriptors
      struct mm_struct *mm; // pointer to code and data segments

      ....
    };

  8. The jobs in the ready queue of a system have the following actual running times in seconds (from head to tail): 3, 50, 12, 39, 20, 21, 1, 4. All CPUs in this system follow the FCFS scheduling strategy, and use (share) the same ready queue. Calculate the average waiting time and  the average turnaround time if:
    1. (2 points) the system has 1 CPU;
    2. (2 points) the system has 2 CPUs.

    (1 point) Is the average turnaround time in (2) above exactly half of the average turnaround time in (1) above? Why or why not?

Updated: Aug. 29, 2005. (c) Indranil Gupta.