CSE 121 Spring 2003 Homework 1 Solutions

CSE 121 Spring 2003 Homework 1
Solutions

Problem 1

Write a Java monitor that prints a message under the following circumstances:

A thread t is blocked on a wait invocation in a monitor.
Another thread q is blocked waiting to enter the monitor by calling a synchronized method.
A third thread r is in the monitor and calls notify.
The thread q enters the monitor before t regains the monitor lock.

You will need to be able to create Java threads to do this. You do so by extending Thread. Here's an example Java program that takes as an argument a number of threads to create. All the threads run the same code, defined by the method run. The thread starts running when its start method is called.

Each thread goes into an infinite loop calling a single method Test on a static object tm. In your program, TM would be a class with a synchronized method Test (that is, a monitor with a single entry procedure Test) :

public class montest {

    static int N;
    static TM tm;

    static class Driver extends Thread {
        public void run () {
            int i = 0;
            while (true) tm.Test();
        }
    }

    public static void main(String[] args) {
        int i;
        try { N = Integer.parseInt(args[0]); }
        catch (java.lang.NumberFormatException e) {N = 0;};
        if (N <= 0) {
            System.out.println(N + " is not at least one.");
            return; }
        Driver d[] = new Driver[N];
        tm = new TM();
        for (i = 0; i < N; i++) {
            d[i] = new Driver();
            d[i].start();
        }
    }
}

You can do this several ways. Here's my monitor. The first N-1 threads wait, and the N'th thread notifies all of them. When a thread waits, it increments w. When the N+1st thread enters, it knows what has transpired, and so simply sees if w is greater than zero. If so, then it notes the priority violation before waiting itself.

public class TM {
    int c, w, N;

    public TM (int N) {
        this.N = N;
        w = 0;
        c = 0;
    }

    public synchronized void Test () {
        int me = c % N;
        c = c + 1;
        if (me == 0 && w > 0)
            System.out.println("Priority violation: w = " + w + ", c = "+ c);
        if (me < N - 1) {
            w++;
            try { wait(); }
            catch (java.lang.InterruptedException e) { };
            w--;
        }
        else notifyAll();
    }
}

Problem 2

Using (strong general) semaphores, give a pseudocode semaphore implementation of a Java monitor. You will need to give the code that is executed when calling a synchronized method, when returning from a synchronized method, and the code for wait, notify, and notifyall.

One uses two semaphores per object.

struct Monitor [ sem mlock = 1; sem cond = 0; int waiting = 0;
];

Wrap each synchronized method invocation with P(m.mlock); ... V(m.mlock).

wait() == m.waiting++; V(m.mlock); P(m.cond); P(m.mlock); notify() == if (m.waiting > 0) { m.waiting--; V(m.cond); } notifyAll() == while (m.waiting > 0) { m.waiting--; V(m.cond); }

Problem 3

Write a C program that takes the name of a file as a single argument. The program should rewrite the file to be the reverse of the original contents. For example, if the file contains the three characters ABC, then it will rewrite the file as CBA.

Use mmap and munmap for file access. You will also need the following system calls (for which you can find documentation for by using the man command).

stat for finding the length, in bytes, of the file.
open for opening the file.
close for closing the file.

Here's one solution:

/* --- reverse.c; Wed, Apr 09 2003 14:32:22 --- */
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>
#include <sys/mman.h>

/* Obtain length of file (-1 if fails) */
int flength(int fildes) {
struct stat buf;
int rc;
rc = fstat(fildes, &buf);
return (rc == 0) ? (int) buf.st_size : -1;
}

int main (int argc, char **argv) {
char *file = argv[1];
char *f;
int fdes, flen, i;
if (argc != 2) {printf("Need the name of a file.\n"); exit(1);}
fdes = open(file, O_RDWR);
if (fdes == -1) {printf("Could not open %s r/w.\n", file); exit(1);}
flen = flength(fdes);
if (flen == -1) {printf("Could not stat %s.\n", file); exit(1); }
f = (char *) mmap(0, flen, PROT_READ | PROT_WRITE, MAP_SHARED, fdes, 0);
if (f == MAP_FAILED) {printf("Map of %s failed.\n", file); exit(1);}
for (i = 0; i < flen/2; i++) {
    char c = f[i];
    f[i] = f[flen - i - 1];
    f[flen - i - 1] = c;
}
if (munmap(f, flen) == -1) {printf("Unmap of %s failed.\n", file); exit(1);}
close(fdes);
}

last edited by Keith Marzullo on 25 April, 2003