Assignment 0. Welcome to CSC 7103

Swapping in the state from your undergraduate OS course

This assignment is meant to quickly and thoroughly restore your existing understanding of undergraduate OS course material. It may require review on your part, which is an appropriate action for the first week of class. You may discuss this homework with anyone.

This assignment is due on September 2, 2025 before the lecture. It will not be turned in. Instead, there will be a short quiz consisting of exactly one question from this assignment. Note that if you miss class that day, this quiz cannot be made up.

Ask on our online Discord discussion forum and/or attend office hours. The forum is open 24/7 for discussion with your peers, and quick (though not 24/7, we do sleep!) answers from course staff. The instructor and TAs are available to answer questions after lecture and in weekly office hours.

Definitions

Define the following terms:

  • Internal and external fragmentation. Also, which of them can occur in a paging system? A system with pure segmentation?
  • Translation look-aside buffer (TLB)
  • Interrupt
  • Distributed shared memory
  • Stateful and stateless servers. Also, list two file systems, one that is stateful and one that is stateless, and explain how having or not having state affects file service
  • Swapping
  • Inverted page table
  • Disk sector, track, and cylinder
  • Thrashing

Short answers

Provide a short answer to each of the following questions:

  • Give a reason why virtual memory address translation is useful even if the total size of virtual memory (summed over all programs) is guaranteed to be smaller than physical memory.
  • Compare and contrast access control lists and capabilities.
  • The length of the time slice is a parameter to round robin CPU scheduling. What is the main problem that occurs if this length is too long? Too short?
  • List an advantage and a disadvantage to increasing the virtual memory page size.

Virtual memory addressing

Suppose we have a machine that uses a three-level page table system. A 32-bit virtual address is divided into four fields of widths a, b, c, and d bits from left to right. The first three are indices into the three levels of page table; the fourth, d, is the offset. Express the number of virtual pages available as a function of a, b, c, and d. Give one advantage and one disadvantage to multi-level page tables.

Page replacement

Suppose a machine with 4 physical pages starts running a program (in other words, the physical pages are initially empty). The program references the sequence of virtual pages as follows:

A B C D E D C B A E D C B A C E

For each of the following paging algorithms, replicate the reference pattern and underline each reference that causes a page fault (or make references that cause a page fault uppercase, and those that don’t lowercase):

  • LRU
  • FIFO
  • Optimum (MIN)

Multiprocessing

Suppose you have a large source program containing m files that you want to compile. You have a cluster of n “shared-nothing” workstations, where n > m, on which you may compile your files. At best you will get an m-fold speedup compared to a single processor. List at least three reasons as to why the actual speedup might be less than this.

Achieving fast file reads

  • Give at least three strategies that a file system can employ to reduce the time a program spends waiting for data reads to complete.
  • For each strategy you listed, describe a read pattern for which the strategy would do well, and one for which the strategy would do poorly.

Synchronization

Your OS has a set of queues, each of which is protected by a lock. To enqueue or dequeue an item, a thread must hold the lock associated with the queue. You need to implement anatomic transfer routine that dequeues an item from one queue and enqueues it on another. The transfer must appear to occur atomically.

This is your first attempt:

void transfer(Queue *queue1, Queue *queue2)
{
    /* the thing being transferred */
    Item thing;     

    queue1->lock.Acquire();
    thing = queue1->Dequeue();
    if(thing != NULL) {
        queue2->lock.Acquire();
        queue2->Enqueue(thing);
        queue2->lock.Release();
    }
    queue1->lock.Release();
}

You may assume that queue1 and queue2 never refer to the same queue. Also, assume that you have a function Queue::Address() which takes a queue and returns, as an unsigned integer, its address.

  • Explain how using this implementation of transfer() can lead to deadlock.
  • Write a modified version of transfer() that avoids deadlock and does the transfer atomically.
  • If the transfer does not need to be atomic, how might you change your solution to achieve a higher degree of concurrency? Justify why your modification increases concurrency.

Networking

You are developing a network protocol for the reliable delivery of fixed-sized messages over unreliable networks. You are using a sequence number in each message to allow the receiver to eliminate duplicates, but you still have three design alternatives to consider.

The design alternatives are: (1) the sender must receive an acknowledgement for the previously sent message before it can send the next message in the sequence, (2) the sender can transmit up to n unacknowledged messages, but the receiver will discard any messages that are received out of sequence (in other words, it will only acknowledge a message if it is received in sequence), and (3) the sender can transmit up to n unacknowledged messages, and the receiver will acknowledge each on receipt, even if they arrive out of order.

For each alternative, answer the following questions:

  • Explain what state the receiver must keep around to implement each of the three alternatives (remember, the receiver must be able to detect and discard duplicates).
  • Suppose two machines are communicating across a bi-directional network link with fixed-size messages.

Acknowledgement packets are also fixed-size. One machine, the sender, is transmitting a very large file to the other machine, the receiver. That is, the sender is transmitting a large number of messages that make up this file. Discuss briefly how each alternative’s data bandwidth is expected to vary given different underlying network characteristics.

Serving multiple clients

There are two main approaches to organizing a server daemon, such as a web server:

  • Create a new kernel thread for each client (for each web browser connection)
  • Use a single process responding to all clients

Compare and contrast these two approaches.