Operating Systems

• As you know, you don't have to work in teams, and can work at home if you installed Minix. I'll assume in what follows though that you're working in Sheppard.
• We decided that I'll let you log in as root, even when using hd1. You won't need to worry about passwords. But please be careful with hd1. Don't change its kernel.
• In Part 2, it suggests that I gave you a DOS disk. I did not. I only gave you a Minix boot disk. I'm sure you can get your own DOS-formatted diskette.
• The phrase "can be found here" in Part 2 means that if you go on-line and read this assignment there, you can click on the word "here" to get the C program I mention.
• Notice in part 3, you'll need yet another diskette, which I didn't provide.
• IGNORE what it says about being OK to leave some of your files on hd1. Please don't leave any of your files on the Sheppard Lab computer.
• In part 5, you might not need to use make clean each time. Things go quicker if you don't do this. However, two years ago, we discovered that it was sometimes necessary. I forget why.
• As I said in class, if the computer in the Sheppard Lab should crash in a non-recoverable way, get in touch with me right away. If necessary I'll let you use my laptop. Also, if the monitor should blow out, then feel free swap in the monitor right next to it. Just let me know of course.
• Oops: I forgot to tell you how to transfer a file from Minix to a DOS diskette. For example, suppose you're in a directory containing a file named life.c, and you want to copy it to a diskette, but have it named liberty.txt on the diskette. To do this, give the following command:

          doswrite -a /dev/fd0 liberty.txt < life.c
          

1. When say a keyboard interrupt occurs, interrupting (let's assume) some process, some hardware and BIOS software manage to automatically change SS and SP so that the active stack becomes a very small stack located in the entry of the process table corresponding to the interrupted process. Onto this stack are pushed the values of some of the registers at the time when the interrupt occurred including SS, SP, CS, IP(at which time SS:SP pointed into the process's (big) stack in its memory space, and CS:IP pointed into the process's code segment.)
2. Then execution (in kernel mode with interrupts currently disabled) is directed to line 06168 on page 595, ie to _hwint01. Here the assembler really substitutes the code at the top of page 593 using 1 in place of irq. This code makes a call to save, on page 595.
3. At the moment when save executes line 06274, the active stack will again change, becoming the kernel stack. The address of _restart (on page 596) is then pushed onto this stack, and later will be treated as a return address (via ret instruction. After pushing this, save executes an xor instruction (ignore) and then a jmp instruction. This jmp instruction magically causes a return back the instruction in hwint_master(0) that follows the call to save. It does this without popping off a return address. Note that the return address from this call was pushed onto a stack that is no longer active, namely the small stack in the process table.
4. The next few lines of hwint_master(1) cause interrupts to be enabled again, excep[t for the type of interrupt that is currently being handled. Then a call is made to the appropriate C code interrupt handler by looking for its address in a table named irq_table. Note that the irq number is pushed onto the stack just before calling the C code in order to pass it an argument.
5. The name of the C code interrupt handler for a keyboard interrupt is kbd_hw_int() and this is on page 701. We won't consider this code until later. (There is similarly some C code for handling a real-time clock interrupt called clock_handler() on page 673 that we'll discuss later. )
6. When we finally return from the keyboard interrupt handler, hwint_master(1) disables interrupts again to get ready for some critical final details. It also changes a mask so that when interrupts are later reenabled, this will include interrupts of the type currently being handled. Then it executes the ret instruction at the bottom which causes the execution to continue at restart on page 596.
7. restart first checks to see if any interrupts were held up because of the current interrupt handling not having completed yet. If so, it arranges for these to be dealt with next. (We'll discuss this later.)
8. It then changes the active stack again to a small stack inside the process table, but not necessarily the one that was used earlier! This is because the scheduler might have decided to change processes during the interrupt handling. Note that _proc_ptr points inside the process table to an entry corresponding to the process that is now in the running state, and so should be executed when interrupt handling is completed.
9. The registers are now popped off this short stack, and a "return from interrupt" iret instruction is executed, allowing a process to execute now. (But not necessarily the one that was interrupted!)

• main.c (pages 601-603) is responsible for initializing the Minix system. It must create tasks and server processes, put these in the process table, and put them in the ready queue.
• At some moment, the clock task executes for the first time (code is on pages 666-675), and this results in a call of the function init_clock(). This executes the following instruction (see page 674, line 11481):
  
  put_irq_handler(CLOCK_IRQ, clock_handler)
  
  
• clock_handler is a function found on page 672. Even though this code is inside the file clock.c, this function is called by the kernel during interrupt handling, while the rest of the code in clock.c is executed by the clock task.
• CLOCK_IRQ is defined to be zero (not eight) in a header file on page 157.
• As you can guess, put_irq_handler sets an entry in the irq_table array that we encountered in the assembly code we examined (page 593, line 6152).

• In restart, at line 6333, the contents of proc_ptr are moved into the esp register. This makes one of the tiny stacks in the process table the active stack. But following the way I described it, you might think it is pointing to the beginning of the stack, although it needs to point to the end of the stack (i.e. to last thing pushed on it). It's my fault. My diagramming may have misoriented you. The tiny stack is as I suggested in the lowest part of of a struct proc. (You should definitely take a look at page 581 to see how struct proc is defined. You'll see many familiar goodies, and some badies.) But here's a sneaky fact that you should recall. Stacks build downward in main memory. So when the tiny stack becomes active, the SP is actually pointing some place in the middle of the proc struct. After all the registers get pushed via save, the stack pointer will be pointing to the lowest memory location in the struct proc. This is where proc_ptr also points. (The tiny stack is just big enough to hold all the info it's required to save.)
  
  
• If you carefully checked the ready function, you may have noticed that tasks and server processes are put on the tails of their respective queue, but that user processes are instead put at the head of their ready queue. What?! This seems very unfair. Why should a user process cut ahead of every other user process in line? It shouldn't. This is just an annoying and ugly technical fix. Tannenbaum uses the function sched when it's time to preempt a process. This moves the guy at the head of the user processes' ready queue to the tail. It turns out that whenever ready is invoked to put a user process in the ready queue, it is followed by a call to sched. So the process that was just put in at the head will now have been rotated to the tail where it belongs. Yuk!
  
  

• Sections 1.1 and 1.2 (we didn't discuss too much of it, but you were asked to read this)
• Section 1.3
• Subsection 1.4.1 (not all system calls, but know fork^* well)
• Subsection 1.4.3 and 1.4.4
• Subsection 1.5.1 and 1.5.2 (get a basic sense at least)
• Subsection 1.5.4 (an easy read)
• Section 2.1
• Section 2.5
• Subsections 2.6.7, 2.6.8, 2.6.9

• Please drop the HW in my 3rd floor box or under my office door by Friday. Sorry I forgot to pick it up.
• I'll post solutions to the first exam before I go home. Feel free to discuss it with me.
• I'll also post the original solution to the first part of Project Two. Notice that in the supplement I handed out, I said we would discuss this, and you should then alter the problem slightly and work on that instead.

• As David said in class "Sleep and Wakeup" is not a correct solution.
• David also pointed out something nice about the three semaphores used in the producer-consumer example: each is keeping count of the number of available instances of some resource:
  • empty - how many empty slots are available to write to
  • full - how many filled slots are available to "eat" (read from)
  • mutex - how many available circular buffers (either zero or one) to read from or write to.
  In other words, the cicular buffer is treated as a resource and there's only one instance of it, which is why mutex is always either one (circular buffer is available) or zero (circular buffer is unavailable).
• Two of the Chapter Two HW problems deal with the "Dining Philosophers Problem" problem, but you should be able to read this on your own. Let me know if you have questions.
• Remember that you only need to turn in the Ch. 2 part of the HW on Wednesday. You will be responsible for the Ch. 3 part on the exam though.
  
  

DRAKE UNIVERSITY CONFERENCE ON UNDERGRADUATE RESEARCH IN THE SCIENCES

Drake University science and mathematics students and their faculty
mentors are making significant contributions in many different fields
of scientific inquiry.  To celebrate this, a conference showcasing the
results of scientific research at Drake will be held on Friday April 9
in Olmsted Parents Hall on the Drake University Campus.  The
conference will allow students and faculty to communicate their
results to other researchers in the Drake community.  This is part of
a broader effort to develop a culture of research that will foster
opportunities for students and faculty to engage in new and more
ambitious projects.

The conference will feature student oral presentations (15 minutes
each) and student and faculty poster presentations on current research
projects. There will also be a chance for students to show off their
knowledge of science and mathematics in the form of a quiz-bowl style
competition.

A schedule for the meeting is given below:

8:00 - 8:30  Poster Set-up
8:15 - 8:45  Registration
8:45         Welcome
8:55         Dean John Burney, Arts and Sciences
9:15         Oral Presentation:  Luke Freml
9:30         Oral Presentation:  Drew Fustin
9:45         Oral Presentation: Brian Rinner
10:00        Oral Presentation: Andy Windsperger
10:15-11:30  Poster Session 1*
11:30-12:15  Lunch (provided for authors)
12:15-1:00   Poster Session 2*
1:00         Oral Presentation:  Eric Gorman
1:15         Oral Presentation:  Kavitha Pundi
1:30         Oral Presentation:  Elizabeth Carr
1:45         Oral Presentation:  Nathan Walters
2:00 - 2:15  Break
2:15 - 2:45  Science/Math Quiz Bowl
2:45 - 2:55  Awards and Closing Remarks

Notice the use of mem_vid_copy and vid_vid_copy in the console.c code. There are several instances of these. Use

mem_vid_copy(BLANK_MEM, ..... )

to blank out one of the console buffer spaces (c_ramqueue). Use

vid_vid_copy( ... , ... , ... )

to copy a portion of one buffer to another buffer. The parameters are start of source, start of destination, number of characters to copy.

• How big can a file be?
  
  Let's count the maximum number of file data blocks. Can have 64 blocks corresponding to 64 direct pointers. Can have 64 * 256 = 2¹⁴ = 16K blocks corresponding to 64 singly indirect pointers. Can have 32 * 256 * 256 = 2²¹ = 2M blocks corresponding to the 32 doubly indirect pointers. Can have 32 * 256 * 256 * 256 = 2²⁹ = (1/2)G blocks corresponding to 32 triply indirect pointers. So the total number of possible data blocks for the file is (1/2)G + 2M + 16K + 64. This is approximately (1/2)G blocks = (1/2)G times 1024 bytes = 2²⁹ time 2¹⁰ = 2³⁹ = (1/2)T bytes. Well, we don't even have enough disk space for such a file, but OK!
  
  
• How could a program quickly do a random access into the file in order to get the byte at logical address 1,234,567,890 in the file? (I'm here counting bytes in their logical order in the file).
  
  Well, first of all which block is this in? 1234567890 divided by 1024 equals 1205632.705. So we need to look in block number 1205632. Note that 1234567890 - 1205632*1024 = 722, so we need to look at byte number 722 in this block. Now let's find block number 1205632. Subtract 64 corresponding to the first 64 blocks, the ones with direct pointers from the i-node. This equals 1205568. Now 16K = 16384. Subtract this off (corresponding to blocks that have singly indirect pointers from the i-node) to get 1189184. It is now more or less clear that the block we seek has a doubly indirect pointer in the i-node. Which one is it? Each of these is responsible for 256*256 = 65536. Now 1189184/65536 = 18.15, so need to use the nineteenth doubly indirect pointer ("doubly indirect pointer number eighteen" if you prefer). This leads us to another block of pointers. Now 1189184 - 18 * 65536 = 9536. Since each of the pointers in the present block is responsible for 256 blocks of data, and since 9536/256 = 37.25, we need to use the thirty-eighth pointer here ("pointer number thirty seven" if you prefer). Follow this to another block of pointers. Since 9536 - 37*256 = 64, we need to use the sixty-fifth pointer here ("pointer number sixty four" if you prefer). This pointer will lead us straight to the data block we seek. As already mentioned, we want to look at the 723rd byte (byte number 722) in this block.
  
  

• There will be something that requires an understanding of forking.
• There will be something involving semaphores.
• There will be something concerning Minix code.
• There will be something involving virtual memory.
• There will be something very much like the above i-node example.

• First Exam
• Second Exam
• Third Exam