Note: midterm, Monday Oct.
29
Summary for Midterm: it’s open book, open notes, can bring posted solutions and your own hw.
Note practice midterm,
solutions on Saturday, linked to class web page.
Is there a theme connecting all
the things we’ve covered so far? I think so, as follows. We have
concentrated on the transitions, or handoffs, between the three major players,
the user code, kernel code, and hardware. A major concern is user-kernel
separation, needed to keep the system well-understood and secure. This
separation is implemented by being very careful about transitions. The
user code is kept “bottled up” in its virtual machine. System calls
communicate a small amount of information (the syscall
# and arguments, return value) across the user-kernel boundary and back.
Note that the CPU is running
in kernel mode or user mode at each point in time (or each CPU, for
multiprocessors). It will continue to run that way until a particular
event takes place: an interrupt, or execution of a system call, or execution of
iret (or equivalent), or some exception (including
page faults, which we will study later).
Hardware-user code
relationship
Hardware-kernel code
relationship
User-Kernel relationship
Hardware/Software terms
that sometimes cause confusion on exams
instruction: like mov, push, in,
out, etc., belong to “instruction set”, used in assembly language
register: array of hardware bits, part of CPU, memory,
i/o devices, holds a value in its bits
CPU register: like eax, ecx, esp, etc. for x86.
device register: like UART’s transmit register,
receiver reg, LSR
port or i/o port: 16-bit number providing an address for
various device registers, in x86 architecture. Ex: 0x2f8 for COM2’s transmit register.
memory address: 32-bit number of a byte of memory, in
separate space from i/o ports.
interrupt vector: the address of the interrupt handler, held in
IDT[nn], and specifying the entry point of the
assembler interrupt handler
command: string used to tell a program what to do, ex: “ls” is a shell command
system call: two meanings, system API call such as write(fd, buf, nbytes),
certain instruction execution (int, ta)
user stack: one for each thread, holds execution state of
user code.
kernel stack: one for each thread, holds execution state of
current system call execution, or is empty
interrupt stack: we assume this is built on top of the kernel
stack of the thread executing at the time of the int.
Midterm
Chap 2, Sections 2.1, 2.2: all to pg. 106, skip 2.2.4,
read 109-110, skip 2.2.6, .7, .8. read
114-end of 2.2.
Sec 2.3: everything through pg. 130, skip pg 131-134
(user-level threads, mutexes in Pthreads
(we can always use semaphores for mutex), condition
variables)
Read Sec. 2.3.7 Monitors to the point it mentions
condition variables.We are using semaphores,
not the more primitive condition variables, for blocking, and we don’t need to
block inside a monitor with
semaphores, since they themselves are monitors.
We have replaced the ProducerConsumer code on pg. 141 with the code on the
handout “Example of Monitor in Java, using the synchronized keyword”, which
does producer-consumer with two semaphores for blocking and a monitor for the
needed mutex to protect the integrity of the LinkedList used for the shared buffer.
Read Sec. 2.3.8, Message Passing. Skip 2.3.9 Barriers
Read Sec. 2.4 to pg. 148: basics of timesharing, which
we have discussed.
Chap. 5 to pg. 336. We are using i/o
instructions, not memory-mapped i/o.
Skip Sec. 5.1.4, DMA
Read Sec. 5.1.5. Correct the
typo on pg. 339 referring back to Chap. 1: should be 1.3.5, not 1.4.5.
Read Sec. 5.2 except the part
on DMA. Note that the code uses memory-mapped i/o, so where you see “*printer_status_register != READY”, replace it with an inb
to the printer status register, followed by testing the resulting value in EAX.
Read 5.3.1, Interrupt
handlers
Read 5.3.2, Device drivers.
We have a tty device driver
in hw2. Don’t worry about block devices
yet. Our tty driver is a
character device.
Read 5.3.3,
Device-independent I/O Software: our setup for hw1-hw2 is a device-independent i/o package, usable for both serial and parallel ports as
shown in hw1.
Chap. 10 Linux
Sec 10.3.2, 10.3.3 to pg 747. Processes in Linux.
Lecture notes through today.
hw1 ideas:
hw2 ideas: ideas only, not code details
Message Passing
Tan, pg. 140:
send(dest, &message);
receive(source, &message);
It isn’t really clear what
kind of id’s dest and source are—thread ids? or message-queue ids? Probably
the latter, because one thread might want to communicate with several other
threads in various message formats.
Producer-consumer
using messages. Idea here is
to set up a flow of data messages from producer to consumer. Normally a
receiver waits (blocked) if there are no messages to receive. How do we
prevent the sender from getting way ahead of the receiver? Recall that
the producer is supposed to be blocked when the queue is “full” in some bounded
way.
To prevent the producer from
run-away production, we require it to receive an “empty” message from the
consumer before it can produce a full one. We prime the system by
producing N empty messages to start with. After that, there are always
nearly N messages total in the system, some empty, some full.
Pg. 143—another somewhat
magic program, using the empty messages for flow control as outlined
above. Again, let’s show how the system objects are set up by the
top-level thread and used by the worker threads.
At the OS level, UNIX/Linux
has TCP and UDP networking and System V IPC message queues. Windows has TCP and
UDP and message queues.
In Java, with threads, we
don’t typically use messages because it’s so easy to share data in memory, so
the code we already have studied shows how to do this. When we communicate between systems, we
usually use the networking support, i.e., TCP, which means we need to talk
about network host addresses and then within hosts, the ports that are used to
define communication endpoints. There is a part of JEE called JMS, for reliable
and transactional messaging. These are
both “heavyweight” services. Java seems to be lacking in “lightweight” message
mechanisms for activities on the same system.
In Android, however, the
architecture favors messages for communication, because it works just as well
between processes, and lots of functionality in Android is implemented in
servers, separate processes from the app processes.
So for Android, Apple has
implemented a new form of Linux IPC, having apparently rejected as too slow TCP
and System V IPC, and certainly JMS.
The new service is called
“Android Binder”. It sends messages from one process to another by copying them
to kernel memory from one process and then out to the other process. The fact that this is not a data stream makes
it not properly fit into read/write Linux syscalls,
so it is actually an “ioctl”, the miscellaneous file syscall. This
service underlies broadcasts as well as calls to servers, including the Service
Manager that keeps track of all the servers and services.
See Academic
article (thesis) on Android Binder
Semaphores vs. Message Passing
Message passing can be done
across systems, whereas semaphore systems offered by
Mutex by message passing: put one message in a message queue. receive it to obtain the mutex, send it back in to release the mutex.
Message passing by semaphores? No way to move the data.
Message passing + shared memory can provide message passing
within one system.
Actual message services
System V msgget,
etc.: available on most UNIX systems. Provides message
passing between processes on one system.
Pipes, Network i/o: stream-oriented, but can subdivide stream into
messages.
Win32: pipes, network i/o
Something
portable between Windows and UNIX?
Answer: TCP network i/o, works between processes
on one machine as well as over the network.
Rest of IPC coverage in Tanenbaum:
pg. 123:barriers—can
skip.
Dining philosophers:
has easy solution with mutex: get mutex, pick up both forks, eat, release
mutex. But this allows only one eater at a
time. The challenge is to safely allow 2 eaters.
Readers and Writers: more
realistic problem. Allow N readers XOR 1 writer to each data item.
The solution uses two semaphores, one (db) to make sure the system is EITHER
doing reading or writing, the other (mutex) to guard rc, the reader count. Only the first reader does the
down on the “db” mutex, and subsequent readers get
blocked at the down on mutex, since the first reader
still holds that until it gets db. But that’s OK, since they need to
block. They get unblocked at the right time too.
Sleeping barber—skip.