Programming Assignment 3 - Synchronization

Table of Contents

• Due Date
• Prerequisites
• Introduction
• The Batch Disk
• System Calls
• Test Batch Disks

Due Date

Prerequisites

Introduction

A critical section is a bounded contiguous region of code in which the operating system guarantees that only one process is executing; see Silberschatz, Glavin and Gagne, section 6.2. A process’s code may have several critical sections, and critical sections may appear in several processes. Whatever their configuration, the operating system must guarantee that at most one process is executing in all critical sections at any time.

This assignment extends the the simple batch-oriented operating system created for the previous assignment to provide tagged critical sections, a generalization of critical sections. A tagged critical section is a critical section with an integer tag. All critical sections with the same tag in all processes are part of the same critical section. The operating system should guarantee that at most one process ever executes code from any critical section with the same tag. However, critical sections with different tags are different critical sections, and there may be processes executing concurrently in different critical sections, as long as there is at most one process executing in each critical section.

The operating system is extended with two new system calls: csin and csout described below.

The Batch Disk

There is no change to the structure and use of the batch disks described in the previous assignment. This assignment adds new batch disks, described below, for the operating system to execute. The batch disks from previous assignments should continue to work with the revised operating system.

System Calls

The new system calls provide a region of mutual exclusion among executing processes.

critical-section enter system call (OperatingSystem.SystemCall.csin)

The calling process requests entry into a critical section. Register 1 contains the tag of the critical section it’s trying to enter.

The calling process blocks until no process is executing in the tagged critical section given in the system call. If there are several processes waiting to enter the same tagged critical section, one is chosen to enter the tagged critical section. Waiting processes can be chosen in any order, but the choice should be eventually fair: a process waiting long enough will eventually enter the tagged critical section. After the exec system call returns, the caller’s register 0 contains the system call status, which should always be Hardware.Status.ok.

critical-section exit system call (OperatingSystem.SystemCall.csout)

The calling process exits the critical section it occupies.

The csout system call returns immediately; register 0 contains the system-call status:

Hardware.Status.ok	command completed successfully
Hardware.Status.noResource	the critical-section tag given in register 1 doesn’t match the critical-section tag occupied by the calling process

Test Batch Disks

pa3-2pme.dsk - A disk containing two programs. Each associated process tries to repeatedly enter the same critical section. After a while the processes get tired of this little game and exit.

pa3-bad.dsk - A disk containing a program that does bad things. Despite all the bad things that are going on, there should be no output other than the usual end of execution information.

It’s important that batch disks from different assignment aren’t mixed. Batch disk from earlier assignments won’t work with this assignment, and vice versa.

$ time java -cp pa3/arcsim.jar:. main os pa3/pa1-empty

The system is halted.
Total execution time:  10 ticks, idle time: 9 ticks (90%).

real	0m0.252s
user	0m0.218s
sys	0m0.035s

$ time java -cp pa3/arcsim.jar:. main os pa3/pa1-solo

The system is halted.
Total execution time:  429 ticks, idle time: 99 ticks (23%).

real	0m0.240s
user	0m0.215s
sys	0m0.038s

$ time java -cp pa3/arcsim.jar:. main os pa3/pa2-bad

The system is halted.
Total execution time:  62 ticks, idle time: 45 ticks (72%).

real	0m0.243s
user	0m0.226s
sys	0m0.024s

$ time java -cp pa3/arcsim.jar:. main os pa3/pa2-dcs

The system is halted.
Total execution time:  149 ticks, idle time: 72 ticks (48%).

real	0m0.249s
user	0m0.226s
sys	0m0.032s

$ time java -cp pa3/arcsim.jar:. main os pa3/pa2-execs

The system is halted.
Total execution time:  187 ticks, idle time: 72 ticks (38%).

real	0m0.246s
user	0m0.211s
sys	0m0.050s

$ time java -cp pa3/arcsim.jar:. main os pa3/pa2-tree

The system is halted.
Total execution time:  441 ticks, idle time: 129 ticks (29%).

real	0m0.255s
user	0m0.242s
sys	0m0.024s

$ time java -cp pa3/arcsim.jar:. main os pa3/pa2-ydcs

The system is halted.
Total execution time:  141 ticks, idle time: 72 ticks (51%).

real	0m0.367s
user	0m0.222s
sys	0m0.033s

$ time java -cp pa3/arcsim.jar:. main os pa3/pa2-ytree

The system is halted.
Total execution time:  443 ticks, idle time: 129 ticks (29%).

real	0m0.264s
user	0m0.237s
sys	0m0.032s

$ time java -cp pa3/arcsim.jar:. main os pa3/pa3-2pme

The system is halted.
Total execution time:  371 ticks, idle time: 54 ticks (14%).

real	0m0.265s
user	0m0.246s
sys	0m0.034s

$ time java -cp pa3/arcsim.jar:. main os pa3/pa3-bad

The system is halted.
Total execution time:  62 ticks, idle time: 45 ticks (72%).

real	0m0.242s
user	0m0.213s
sys	0m0.041s

$

As long as your operating system runs correctly the numbers produced by your operating system don’t matter. As a sanity check, however, the numbers produced should be within 50% of the numbers shown above.

If you’re looking for a way to proceed, you might want to consider the following steps:

1. Get your os to work with pa3-2pme.dsk, which requires implementing the csin system call.
2. Make sure pa3-bad.dsk runs without incident.
3. Make sure the older batch disks run successfully.