Up to now you have implemented several synchronization mechanisms: locks, mutexes, semaphores, monitors, condition variables (used inside a monitor). Each of those mechanisms aim at achieving either 1) mutual exclusiveness by locks, mutexes or 2) sequencing of execution by semaphores, monitors. Example to (2): if process A produces data and process B prints them, B has to wait until A has produced some data before starting to print.
These two classes of mechanisms is based on some shared state between the processes. In locks, access to the lock state is a shared state, hence should be done in mutex. In semaphores the semaphore value is shared, etc. In previous project you achieved this mutex by disabling interrupts. What we want is that the code to be preemptable as much as possible since this is an important principle for concurrency of processes.
The other two methods that can achieve mutex are 1) hardware support (MOS, Tanenbaum, Section 2.3, The Test and Set Lock (TSL) Instruction) 2) Peterson's Solution (MOS, Tanenbaum, Section 2.3, Peterson's Solution). In this project you will use first method, that is, make use of the TSL instruction in hardware.
thread.c:spinlock_init/acquire/release are implementations that are provided to you that make use of TSL in entering/leaving a critical section. Although the name tells it is a spinlock, it is not. If the mutex is occupied, the calling process yields. We keep this name because of the analogy of this lock to its spinlock version counterpart which makes its understanding more intuitive. This yielding based implementation is basically same as the mutex example in textbook section 2.3.6 Mutexes (pg 113).
You will re-implement the lock and condition variable primitives that you developed in last project, this time by using spinlock. Initial code for primitives resides in thread.c. Check thread.h to see that the lock_t and condition_t data structures are changed. First, there is a spinlock element in each which needs to be initialized by spinlock_init at each of lock_init and condition_init so that they can be used inside lock_acquire/release and condition_wait/signal/broadcast. Second, the waiting queue implementation is changed from node_t structure to (pcb_t *). This minor change should affect only the initialization of the queue; "queue_init(&l->wait_queue)" changes to "l->waiting=NULL".
Hint: The scheduler code still needs to be executed free of interrupts since it changes the global system data structures. Check scheduler.c:block function to see it changes from spinlock to interrupt disabling.
In this part you will implement a mailbox mechanism where different processes send arbitrary sized messages to the mailboxes and other processes read those messages. There are going to be 5 fixed mailboxes created at system start, and those will be used for processes' communication with each other.
As an implementation, you can think those mail boxes as FIFO queues, so this is actually solving the bounded buffer problem that you saw in class. The sender should block if the queue is full and receiver should block if the queue is empty. You will use Mesa style monitor, and your implementation will be very similar to the monitor implementation in textbook in Figure 2-27.
Check the mbox.h to see the mbox_t data structure. Basically it keeps an array to store messages, head and tail to keep track of the queue start and end, a lock_t structure to be used in monitor function calls, and some other accounting data for the mailbox.
The primitives that you will implement in mbox.c are:
- mbox_init: Initialize all the mailboxes in kernel. This is an internal routine called by only the kernel.c:_start
- mbox_open: Open the specified mbox for use of mbox_send/recv, increment used count. It returns the number of the opened mailbox.
- mbox_close: Close a mailbox, decrement used count. There can be many processes or threads that opened the mailbox. When all of them close, the mbox's data structures should be cleared.
- mbox_send: Send a message by writing to head of the queue, message can be variable length.
- mbox_recv: Receive a message by reading from the tail of the queue.
- mbox_stat: Return the number of messages in the queue.
All except the first one are system calls. User processes call them by including syslib.h and kernel uses them by including mbox.h directly. (Examples: process2.c and keyboard.c.) All system calls take the mailbox number as argument. For example, mbox_recv accesses the specified mailbox in array mbox.c:Q, writes the incoming message to its buffer. You can check the prototype descriptions in mbox.h for more about mbox primitives. Messages are of type common.h:msg_t which includes a header "int size" and body "char *body". Messages should be stored with both parts inside the queue.
Hint: When a process reads from a mailbox, it may free up enough space for multiple messages. (The converse is not true).You need to handle this situation by implementing the mbox_send and mbox_recv different in some points from the bounded buffer implementation given in textbook.
This part is related to the IPC part in that, the keyboard will act as a producer; input obtained from the user will be delivered to the keyboard mailbox (queue 0) using the mbox_send function. Also, the system call which reads from the keyboard will use mbox_recv to get characters from that queue. In our project a process called "shell" is responsible for calling the system call. If the keyboard buffer is full the producer cannot block so it has to discard keys.
The part that you will be writing is reached by the system after a series of steps: kernel.c:init_idt creates the gate for the interrupt descriptor table at entry 33 with the keyboard interrupt (IRQ1) with the handler entry.s:irq1_entry. Then it calls keyboard.c:keyboard_init to initialize keyboard subsystem. When a user presses the keyboard, the CPU gives control to irq1_entry which in turn calls keyboard.c:keyboard_interrupt. According to what character was types, one of the handler methods in the same file is called. If it is not a control character, normal_handler is called which in turn calls keyboard.c:putchar. You will implement:
- keyboard_init: Prepare the data structures that the keyboard uses.
- getchar: Gets the next keyboard character. This is a system call.
- putchar: Called by the keyboard interrupt handler to put a character in the keyboard buffer.
Hint: In putchar, you need to be sure there is enough space in keyboard buffer first. Both the getchar and putchar are interruptable (you can check entry.s:irq1_entry that it calls leave_critical before calling the keyboard_interrupt, and getchar is a system call). Think about what problems IRQ1(keyboard) and IRQ0(timer) interrupts can cause inside getchar and putchar (consider first hint, too).
This part is not distinct from the IPC part, therefore can be developed independently. We provide a possible scheduling of the development in Hints on Testing and Scheduling. The aim here is to load a program from USB flash disk dynamically.
The createimage that we provide to you produces an image containing the kernel and 5 user processes; shell, process1, process2, process3 and process4. The bootblock loads only the kernel. One of the kernel threads (loader_thread) take care of loading the shell first. Then, as you issue commands in the shell the other processes(1-4) will be loaded by the shell (check shell.c to see the available commands). So, the image we use to boot kernel acts as a program disk as well. In addition to those 5 processes, you will be able to load other programs as well by first creating standalone program disks which are non-bootable images. Details will be given in Hints on Testing and Scheduling.
You will write two functions inside kernel.c:
- readdir: Reads the process directory into a given buffer (just read a whole sector).
- loadproc: Loads the ith program on the program disk, creates a new PCB entry and inserts it into the ready list.
In readdir, you can make use of usb.c:read() function which just reads the specified block from disk to a buffer. util:bcopy is just a utility for copying between two buffers which can make your life easier.
In loadproc, you are already given the location and size of the program as parameters. You will need to use memory.c:alloc_memory to allocate enough space (consider also the stack size) in the memory for the process, usb.c:read to read blocks from disk and util:bcopy to copy it to the allocated memory. Once the new process has been loaded, you will use the kernel.c:create_process so that PCB for the process is created, it is added to the ready queue. Read the code of the functions that you are supposed to use.
The process directory is a simple directory showing the placement of the processes in the program disk. You can check how shell.c (line 142) traverses the directory to find a specific program in disk (in response to your load command), and calls loadproc with parameters start address and size.