CS372: Homework 4

Problem 1:

Which of the following components is responsible for loading the initial value in the program counter for an application program before it starts running:

        * Compiler
        * Linker
        * Loader
        * Boot module or boot ROM

Problem 2:

Given the following program that uses three  memory segments in an address space as described in class (code segment, data segment ,and stack segment):

char a[100];
main(int argc, char ** argv)
{
    int d;
    staticdouble b;
    char *s = "boo", * p;

    p = malloc(300);
    return 0;
}

Identify the segment in which each variable resides and indicate if the variable is private to the thread or is shared among threads.
Be careful.

Problem 3

A hardware designer argues that there are enough transistors on the chip to provide 1024 integer registers and 512 floating point registers. You have been invited as the operating system guru to give opinion about the new design.

        1. What is the effect of having such a large number of registers on the operating system?
        2. What additional hardware features you would recommend added to the design above.
        3. What happens if the hardware designer also wants to add a 16-station pipeline into the CPU. How would that affect the context
            switching overhead?

Problem 4

Given the following piece of code:
    main(int argc, char ** argv)
    { }
     
How many different copies of the variable c are there? What are their values?

Problem 5

Given the following piece of code How many processes are created if the above piece of code is run? Hint: It may be easier to solve this problem by induction.

Problem 6

What is the output of the following programs (inspect the manual for the system calls if you need more information, but please solve the problem without compiling and running the program).

Program 1:
main()
{
    val = 5;
    if(fork())
        wait(&val);
    val++;
    printf("%d\n", val);
    return val;
}

Program 2:
main()
{
    val = 5;
    if(fork())
        wait(&val);
    else
        exit(val);
    val++;
    printf("%d\n", val);
    return val;
}
 

Problem 7

Suppose a program references pages in the following sequence:
ACBDBAEFBFAGEFA
Suppose the computer on which this program is running has 4 pages of physical memory.
  1. Show how LRU-based demand paging would fault pages into the four frames of physical memory.
  2. Show how OPT (or MIN) based demand paging would fault pages into the four frames of physical memory.
  3. Show how clock-based demand paging would fault pages into the four frames of physical memory.

Problem 8

Assume that you have a page reference string for a process. Let the page reference string have length p with n distinct page numbers occurring in it. Let m be the number of page frames that are allocated to the process (all the page frames are initially empty). Let n > m.
  1. What is the lower bound on the number of page faults?
  2. What is the upper bound on the number of page faults?
Hint: Your answer is independent of the page replacement scheme that you use.
 

Problem 9

Belady's anomaly: Intuitively, it seems that the more frames the memory has, the fewer page faults a program will get. Surprisingly enough, this is not always true. Belady (1969) discovered an example in which FIFO page replacement causes more faults with four page frames than with three. This strange situation has become known as Belady's anomaly. To illustrate, a program with five virtual pages numbered from 0 to 4 references its pages in the order:
0 1 2 3 0 1 4 0 1 2 3 4
  1. Using FIFO replacement, compute the number of page faults with 3 frames. Repeat for 4 frames.
  2. Compute the number of page faults under LRU, NRU, the clock algorithm, and the optimal algorithm.