Department
of Computer Science| Instructor: | Prof. S. Chaiken
LI-67A, 442-4282 sdc@cs.albany.edu |
M, W, F: 11:15AM-1:00PM
and by appointment or if not busy |
| Teaching Assistant: | Xiaoyu Zheng
LI-96P, 442-4285 xz7223@albany.edu |
T, Th: 10:30AM-12:30PM
and by appointment |
Textbooks:
Policies(pdf) (.ps) Programming Project Guidelines(.pdf)(.ps) How to Use Turnin (.pdf) (.ps) Project 1(.pdf) (.ps) Project 2(Simulating a scheduler in Java) Project 3 (the pthread "Threader" exercise) Project 4(Simulation of Paging Algorithms)(.pdf)(ps) Tracer data and other information Homework 1(.pdf) (.ps) Homework 2 Homework 3(.pdf) (.ps) Homework 4(.pdf) (.ps) Homework 5 Homework 6(.pdf) (.ps)
Course Policy, Syllabus, Readings, etc handout(.pdf) (.ps) Programming Project 1 Due Wednesday, Sept 10 (.pdf) (.ps) Goals: Provide experiences with concurrency including interprocess communication; introduce programming with system calls. Process, concurrency, system structure, design compared to analysis, hardware/software (fuzzy boundary), operating system versus application software, users/environment. A process is one run of one program. Analogous concepts about teachings of course meetings.
Handout: Guidelines and Rules for Programming Project 1 and others (.pdf) (.ps) Handout: How to Use turnin to submit project work electronically (.pdf) (.ps) Each C/C++ automatic variable is allocated in the execution stack of the current process. The memory belonging to one process is typically composed of regions with disjoint intervals of addresses. Each region is called a segment. One segment is used to store the stack, another for static variable, yet another for program (machine language) code. Intro. to using the read() system call. Pitfalls and directions for coding the address of the destination variable in argument 2 and the maximum number of bytes to read in argument 3. The return value indicates the number of characters actually read; the return value of 0 indicates "end of file" which means there is no more data. See Haviland chap. 1-2. One view of what a computer does is the interactions of I/O devices with users or other things in the environment. (cute cartoon of an elephant, see also Bovet and Cesati's Basic OS Concepts section, p.8, for a more serious styled explanation.). Another view is the loading and running of programs. The computer has randomly addressible memory to store the program code (in machine language) and CPU composed of an arithmetic/logic unit plus registersincluding a stack pointer and a program counter. Among the (assembly language) instructions from MIPS/spim simulator of Albany's CSI333, the syscall instruction is different because it does I/O instead of just manipulating memory and data values. In real systems, system call type instructions act very differently from ordinary instructions: A system call instruction causes an event in the CPU called (variously, according to vendor) a trap, exception, interrupt, or fault. What and where is the operating system kernel. When a trap, etc. occurs, the data in the registers is copied to a part of memory belonging to the kernel, the interpretation of addresses changes so kernel code and data is now referred to by addresses, and the computer begins to run code from the kernel. The kernel's scheduler (a software system) decides which process to return to when the kernel code finishes. Timesharingis implemented by a hardware clock generating interrupts frequently, which enables the kernel to reschedule processes in an interleaved fashion. The clock interrupts enable the kernel to run interleaved with the current process so it can determine when to run the scheduler. The maximum period of time that can elapse between activations of the scheduler is called the quantum. The quantum is generally around 0.1 to 0.01 second (these figures are corrections from what I said in class.)
Tips for Project 1: All 256 numeric values 0-255 for possible input characters must be accomodated. Use unsigned char C/C++ type for each variable that should hold an 8-bit value and interpret it as an integer (number) in the 0-255 range according to the plain binary number system. Your design must handle the requirement that the character with value 0 must not get the special treatment it gets in C strings. (A C-string is a string of characters terminated by the "NULL" character that has value 0.) Sequence diagram used to discuss details of key-presses, echos of characters and new-lines, and transmission of a character to the buffer holding the data for read(). (To answer questions about Project1 investigations.l) Process Control Block, process scheduling states, study Bovet's task_struct material alongside AOS's PCB material. Sequence Diagram slide 4.7 showing history in time of several processes and of their interactions. Sequence Diagrams See pages 102-105 of this document Unified Modeling Language(UML)--http://www.omg.org/uml/ A process's virtual memory is one of that process's resources. Each open file of the process is another resource belonging to that process. Each open file is implemented by a data structure (logically) stored in the process control block. (slide 4.7). Each system call done by a given process for a given open file refers to that open file by a file descriptor (Unix terminology) or handle (Windows and generic terminology). In Unix, a file descriptor is an unsigned integer and file descriptors are created as sequential numbers 0, 1, 2, ... . In Unix, each file descriptor is an index of an entry in the array of open file data structure (pointers). An open file traditionally was a file on a disk but in modern Unix, an open file descriptor describes a wide variety of data sources and destinations, including network connections. The socket() system call returns an open file descriptor to be used in read()/write() in much the same way as for a disk file opened by open(). Process scheduler queues are data structures used by the scheduler to keep track of the processes. In Linux, wait queues are used. When a Linux process changes state from ready or running to waiting, a record is inserted in one of the wait queues. Long and short term scheduling: Long is meaningful in batch systems. Today, users, more precisely, processes running client software, connect to servers across networks to obtain computer service. "Long term scheduling" is performed by server subsystems that manages connections or do load balancing among multiple server hosts. I/O bound, CPU bound, Interactive, prioritization: These are characteristics of a process that a schedule might use in its algorithmfor deciding which process to run.
Digression on why we had to wait for the Linux startup operations to do fsck. A (disk) file system is a data structure (that exists on a disk, floppy, hard, or optical) that can store filenames, directories of filenames, data files, and associations of filenames to directories or data files. When a file system is mounted , a copy of some of its information is made in a different kind of data structure that resides in kernel memory. Kernel memory resides in randomly accessible memory which is much faster (by factors of millions) than disk memory. If a system is turned off with the current memory data in and about files not written back on the disk, the disk data will be inconsistant or incorrect. The fsck utility takes advantage of redundancies in disk file system data structures to restore consistancy if possible. Blocking system calls: (SEE AOS pages 417-418)A system call blocks when the call makes the OS put the calling process into the waiting (sometimes called blocked orsleeping) state. When a process is waiting, it is made ready, it is scheduled, and the system call returns when the process is run only after the requested operation completes or fails with an error indication. You experienced the effect of blocking when you used your first interactive C/C++ program like: #include <iostream>
using namespace std;
int main()
{
int X;
cin >> X; //BLOCKS until input is typed in.// This means cin.operator>>(X);
// This FUNCTION CALL STATEMENT doesn't finish
// UNTIL input data is stored in X.
// (assuming a corrctly formatted decimal integer was typed.)cout << "your number multiplied by 52 equals " << X*52 << "." << endl;
return 0;
}Examples of non-blocking system calls: read(fd,0/*bytes*/,0); gettimeofday(); etc. Might vary with system and situations. "Non-preemptive" or "cooperative" multiprogramming: A running process CONTINUES TO RUN until either it makes a blocking system call, or it makes a special system call to voluntarily "yield" the CPU so other ready processes might run. A process running this program will make a non-preemptive system HANG:main(){ while(true) ;/*do nothing*/ } Almost all processes in time-sharing systems are in the waiting state, blocked on some system call such as read. You can see this by running ps aux | less on Linux. HOMEWORK: On ITS Solaris, run the command "ps -Afl | less", then find out the significance of the one-letter process state codes by finding that info in the output of "man ps". Then do ps -Afl again now that you know the significance of some of the columns. A server network TCP application (such as a Web server) programmed in the sockets interface is usually blocked on the accept()system call, waiting for a client to initiate a network connection. HOMEWORK: Draw with pencil or graphics software two neat sequence diagrams like Figure 4.3 in AOS to illustrate each history:
- One process makes a non-blocking system call to the operating system. The operating system returns directly to that process after handling the system call.
- One process makes a blocking system call. The OS runs a second (ready) process. This second process is interrupted by the event caused by the I/O device where this event enables the blocked system call to complete. (You must show a column for the I/O device and indicate when the I/O device sends an interrupt that interrupts the second process.) The OS reschedules the interrupted 2nd process because it has high priority. After a timer interrupt, the OS makes the second process be idle (in the ready state) and makes the previously blocked system call return to the original process.
- I will try to do and explain this on the blackboard, and your job is to draw it neatly and correct any mistakes or ambiguities! You must supply all the labels to indicate that you understand what is happening.
Introduction to Unix Pipes A pipeline is a shell command: It directs the computer to run two programs with the standard output from the process running the first (on the left to the pipe symbol | ) serving as the standard input of the process running the second process (on the right.) Unix pipes solve the producer-consumer problem for sequences of bytes. The kernel's pipe facility provides the necessary synchronization of the producer and consumer processes: (1) The consumer cannot operate on data until the data has been communicated to it (2) Until the consumer reads it, data from the producer must be either be saved in a buffer or the producer's write operation must block. The Unix pipe() system call creates a pipe. The pipe is described by file descriptors. New processes created by the process that called pipe() share these file descriptors to use to read and write to the pipe. Desription of shell pipeline: The shell calls the pipe()system call. The shell then calls system calls to make two new processes to run the programs named on the left and right sides of | . These two processes respectively have their standard output and standard input file descriptors describing the pipe. The right hand process blocks on reading the data if data is not available; the left hand process blocks on writing the data if the buffer is full. AOS slides edited and intended for this lecture
The two homework exercises assigned above will be due in class on Monday..Plus an exercise on the Java solution to the Bounded Buffer Problem presented in AOS chapter 4. These will be officially assigned on Wednesday. Some Q/A about what the OS is doing when a process is running, etc. Introduction to threads. Bounded Buffer Producer-Consumer Draft impl. in Java (From Chapter 4 of AOS) Java Sources Server.java BoundedBuffer.java Producer.java Consumer.java Data Structures after memory allocation but before constructors have been run(.png) (.pdf)(.ps) Data Structures after all the constructors have been run(.png) (.pdf)(.ps) Result: The Producer and Consumer objects SHARE the common BounderBuffer object.. We "talked through" some of the Java code and what it did...Homework: figure out how it all works completely!
How people time-share in life: Pay attention to different activities at once. It doesn't really save time except if you would otherwise wait, while doing nothing, for something to be finished or to happen. Notice how the professor slowed down when he time-shared! How people parallelize their life work: It takes less time when many people work simultaneously on a job that can be split up into independant tasks. Summary: Process signifies the virtual memory configuration and contents belonging to a running program, and thread signifies the sequence of instructions referrring to data and program code in the virtual memory. Modern application software often is organized with multiple threads. Invitation to scientific lecture right after class by Andrew Lumsdaine about The Matrix Template Library (http://www.osl.iu.edu/research/mtl/) Synchronization and Buffering Definitions and examples of concurrency, synchronization, (non-blocking I/O quick intro.), buffering, caching Remark on how swapping is kind of opposite to caching Buffering examples: (1) in-kernel buffers for disk I/O, (2) application program char array or string for reading an entire input line, (3) buffer used by Unix terminal drivers, see Haviland's chapter 9 (also line discipline and device driver separation)
Homework 2 and Project 2 ASSIGNED, Due first on Oct 3. Get it NOW. AOS Chapter 6 slides see Java Threads in them A scheduler IMPLEMENTED with theads in Java
Demo of the M-x . (Meta-X period) or "find tag" function in EMACS::YOU MUST RUN THE etags program first to create the TAGS file..Read the Makefile in ~acsi400/Proj2 on itsunix Start with TestScheduler.java. Java program execution starts by calling main. A Java class is a programmer defined data-type, like a C/C++ struct (or class) . It is critical to distinguish, comceptually, between a class and instance or object. What Java and C++ classes add to C structs is (instance) member functions or methods: These are procedures, functions, subroutines, etc., which when they are called, their bodies can conveniently access the data inside the particular object or instance whose reference is given in the call. Thread is a class that is part of the Java Library. currentThread() is a class method that returns a reference to the particular object of type Thread that represents the thread that called this method. Thread.MAX_PRIORITY is a class constant belonging to the Thread class. setPriority is a method belonging to the Thread class--it is an instance method, so it is called FOR the Thread object whose reference was returned by Thread.currentThread(). The first line of main calls the setPriority this way, with the parameter Thread.MAX_PRIORITY. CPUScheduler is a "local variable" that can hold a reference (think "pointer") to an instance or object of type Scheduler . We now look at the class definition for the Scheduler class in file Scheduler.java First, a Scheduler has the variable fields named queue, timeslice. It also has class constant DEFAULT_TIME_SLICE, which symbolizes constant value 1000. Observe how the constructor function initializes the two instance variable queue and timeslice. CircularList is a class whose instances implement a kind of data structure. Your authors implemented CircularList using Java Library class Vector. A Vector is like an array except it can shrink on command and grow when new highest subscript values are used. Your authors' wrote their Scheduler class to extend Java library's Thread class. This means any Scheduler has, in addition to the data fields and methods declared by your authors', the data fields and methods inherited from its base class Thread. Every method or data field in a Thread can be used by code in a Scheduler. The Thread class has a method named start. When the start method is called, the Java Virtual Machine activates and schedules a new thread. What code does this new thread run? The specification of the Thread class says that the code the new thread runs is the body of the method named run() in the derived class. Therefore, your authors coded what their scheduler should do in the run() method body you see in the Scheduler class deifiniton in file Scheduler.java
CPUScheduler.start();
CPUScheduler.run();
Completion of walkthrough of AOS TestScheduler Java Code for use in Project 2.
Handout of sections 6.7.2-3 on Win2000 and Linux scheduling from Operating Systems Principles new edition..Reading assignment: finish Chapter 6, read this, read Chapter 11 in Bovet's Linux Kernel book, and begin Chapter 7 of AOS. How to browse Linux Kernel Sources--various ways. Detailed Explantion of section 7.1 of AOS. Representation invariants for the circular list bounded buffer implementation were written on the blackboard. Detailed execution of the code by 2 concurrent threads was demonstrated. When we simulate a thread not-running, there is a well-defined resumption point where that thread's execution will resume when that thread is scheduled to run again. The Critical Section Problem: The problem is to invent hardware features, programming tricks, and/or operating system features implemented in software, hardware or both, so that regions of code (called "critical sections") may be protected so that if one thread is running code in a critical section, no other thread will concurrently be running code in the same or a different critical section. One of several solutions is "disable interrupts" It is not universally satisfactory for reasons we will cover later.
- Priority Scheduling Fair Share (not AOS).
- Real time:hard and soft.
- Principle of separation of Policy and Mechanism.
- Other OS Chapter 6 slides
- Examples of Gantt chart analysis of various scheduling strategies
- Multiple Processor Scheduling--see slide, but note that processor "affinity" scheduling is used to offset poor cache behavior effects due to pure load sharing...affinity tries to keep each process in one particular processor.
- Hard and soft real time.
The POSIX definitions for process and thread local versus global are alternative kinds of scope of variable names: The scope of a variable's name is the region of the code in which that name refers to the same variable.) compared to lifetimes. static, automatic, and dynamic are the three alternative kinds of varible lifetimes available in C/C++. The term for lifetime in C/C++ language descriptions is storage class. Static means the variable is allocted once and it persists, retaining its value and any value changes, to the end of the whole process's livetime. Automatic means the variable is allocated when the block is entered (or function is called) where it is declared is entered, and deallocated (made into garbage) when that block exits (or that function returns) . Automatic variables are allocated (typically) in the thread's exection stack, in the activation record for the activation of the function containing the block or declaring the variable. Students and others often use the word "local" when they mean automatic. In C/C++, according the the POSIX definition, ALL variables are shared among threads because every variable has an address, an address is an integer, and any thread can cast an integer to the variable's type of pointer and use that pointer to refer to the variable. Automatic variables belonging to the executions stack of one thread CAN be accessed by any other thread that gets a pointer to that automatic variable. Java prevents all access to variables without a reference to the variable being explicitly available to the method code making the access. Java does not implement the casting of integers to Java references, which are really pointers! Atomic actions in concurrency modeling. An example of interleavings of atomic actions was given in the last lecture and appears at the beginning of AOCS Chapter 7.
Various definitions of "Critical Section or Region" Definition of the Mutual Exclusion Problem by the criteria any solution must follow Store Sychronous shared variables Disabling of Interrupts Analysis of Race situations by listing all INTERLEAVINGS
mutex_unlock:
MOVE MUTEX,#0
RETURN
- The Java/C/C++ type modifier "volatile" and why the shared variables participating in these algorithms must be declared volatile
http://www.cs.albany.edu/~sdc/CSI400/Fal02/Sec2.3images/PriorityInversion.png
Solution of the Bounded Buffer Problem using Semaphores Definition of the Readers and Writers Problem and a glance at its solution with semaphores.
The Readers and Writers Problem, solved with semaphores and explained in detail Introduction to waiting mutex's and Monitors
- M.wakeup() effect is LOST if no thread is blocked (sleeping) in an M.sleep() call
- Each S.up() [in other words, S.V()] either wakes one thread blocked in a S.down() call OR increments S.count so that some future S.down() will decrement S.count and not block.
Explanation of the time analysis of grade school integer multiplication, and how factoring is a problem in the class of Non-deterministic Polynomial time (NP) problems. It is a mystery to computer scientists whether factoring is NP-complete or not. (leadup to Hal Abelson's lecture on cryptography: Cryptography is a key technology operating systems might use for security.)
Continuation of Lecture 24(html page linked to slide images) Safety and Liveness Coffman's 4 conditions; 3-4 strategies for dealing with deadlock Deadlock detection and recovery Deadlock (dynamic avoidance)--concept of safe state (of resource allocation) Linear (and partial) order of resouces used to prevent deadlock by preventing cyclic dependencies from occurring.
Database-style concurrency control Operating Systems view of critical sections used to maintain data consistency compared with the Data Base view of concurrent serializable transactions: A transaction is a sequence of atomic, shared memory operations, and a set of interleaved operations is serializable if it has the same effect as the serial exeution of the transactions without interleaving in some order (i.e. permutation). Why it's preferred to roll-back or cancel a transaction in progress rather than force the starting of transactions to wait. New Edition Section 7.10(.pdf)
- Some questions:
- Explain precisely, in term of the "wait-for" graph on page 245 of AOS, exactly why deadlocks are prevented if all the resources or locks were listed in a priority order 1, 2, ..., n and every time a thread requests or holds two or more resources or locks simultaneously, any lower numbered resources or locks is always requested before each higher numbered resource or lock. Hint: Associate the resource numbers with the nodes of the wait-for graph and explain why this rule for ordering the requests contradicts the formation a directed cycle in the wait-for graph.
- Explain, preferably in your own words, why two-phase locking and the timestamp locking protocol require transactions to be rolled back in order to be useful. Explain why at log based data base is essential for this, and why checkpointing is beneficial.
- Find and copy from your textbooks or notes the two definitions for the two senses of the term "critical section". Find and copy the definition of the term "transaction". of Explain, preferably in your own words, why transaction based concurrency control can allow more concurrency than locking of critical sections. Think up and try to justify (1) advantages of critical sections and (2) advantages of transactions compared to one another.
Protection Hardware protection features: User/priviliged mode bit in the PSW of the CPU controls whether certain instructions perform certain "system" operations (like change the base address for the page tables or disable maskable interrupts) or cause "illegal instruction execution" interrupts. Software protection features: (Basic Unix user privilege model)Each process has a userid attribute stored in its process control block. If userid=0 we say the process is running as "root". Certain system calls, like setuid(..) which change the userid value, are effective only when the process calling them has userid=0.
The next Homework will include the questions under Lecture 26 plus 2 more: (4) The sentence "Memory consists of a large array of words or bytes, each with its own address." is a simplefication. After reading most of Chapters 9 and 10 in AOSC, explain, in as many specific ways as you can, how memory on realistic systems is more complicated, and the advantages of each complication. List any disadvantages you think of too. Distinguish between virtual memory, randomly accessible physical memory and cache memory. (PS. In some 1960's mainframes and 1970's minicomputers, memory really was merely an array.) (5) On Solaris or Linux: Read the man page for malloc(). Read the man page for mmap(). Observe that with mmap() you can allocate a memory segment initialized to zero by requesting a private mapping of the file /dev/zero. Design, write, compile, debug, test and demonstrate a short C program that demonstrates typical use of malloc(). Design, ....etc.... demonstrate .... etc... that demonstrates how to use mmap() for the same usage that is typical for malloc(). What is the difference between what the system (library plus operating system kernel) does when a process uses malloc() compared to mmap() to allocate memory? Prepare a directory named Hw5Part5 that contains your programs, a Makefile to compile them so the TA can test them, and a report (written in English) that will indicate to the TA how well you were able to demonstrate and explain the difference between using malloc() and mmap() to allocate memory for use within one process. Submit your directory to project Hw5Part5 using turnin-csi400 as previously instructed.
Programming Project 2: Read the file threader.C available here and on itsunix in directory ~acsi400/public/Threader. Follow the instructions therein. Turnin your modified code and report to project Pr2 using turnin-csi400 as previously instructed. You may do this is project on Solaris or Linux. See me for access to a Linux system if you don't have one. Depth-first-search Algorithm definition from Corman, Leiserson and Rivest's book used in CSI403.
- Dea11dfs1.png Depth-first-search first slide.
- Dea12dfs2.png A remarkable feature of depth-first-search: It detects cycles efficiently.
- Dea13dfs3bfsBad.png Why a reasonable alternative to DFS does not help detect cycles.
Dea10DetRecoverFlow.png Role of the deadlock detection and recovery strategy in system operation explained with a flowchart.
Introduction to Memory Management First 6 slides from this batch(.ps) (.pdf) Why the Translation Lookaside Buffer is critical for virtual memory to be practical. Page replacement problem; dirty and clean pages; more generally, dirty and clean cache blocks. AOS Chapter 9 (Memory Mgt)(.pdf) (PowerPoint) AOS Chapter 10 (Virtual Memory )(.pdf)(PowerPoint) Input queues are not used in current general purpose systems. Binding steps needed for program execution. Richard R. Levine, Linkers and Loaders, Morgan-Kauffman 2000 Unix System/V ELF object/library/executable standard supports both programmer controlled "dynamic loading" and automatic "dynamic linking". Overlays are obsolete in modern large memory systems; maybe they are still used in (1) kernel booting or (2) embedded applicaitons. Virtual or "logical" addresses are determined by the linker which creates the executable files, in ELF. You can view the section map of an ELF executable with objdump or Solaris dump utilities. Microsoft Quickview has similar functionality. Paging removes the need for contiguous allocation of physical memory for ordinary process memory. Where contiguous allocation is necessary: Physical memory I/O buffers Efficient large files on disk hardware Allocation using say malloc or new of memory WITHIN the virtual memory of a process
Topics of homework problems: Actions when a page fault occurs; how the page number is determined from the virtual address, the page reference string and its role in analyzing page replacement algorithms, FIFO algorithm demonstrated. Topics in notes and text mentioned throughtout discussion: (slide 14) External fragmentation: Occurs when contiguous allocation is necessary: There is not a large enough contiguous area even though the sum of free area sizes is greater than the requested allocation size. "Dynamic relocation" means the entire address range of each contiguous allocation can be shifted by a fixed number. Internal fragmention: Occurs when allocations are done in units of fixed size blocks; the blocks need not be contiguous: Not all the allocated memory is used because the application only uses parts of each allocated block. 15-19 fast. (slide 20) : Translation Lookaside buffer hardware: similar to other cache hardware. (slide 21) The "effective access time formula" actually the average access time formula is very important! (Will be on the final exam :) It includes the hit ratio. 22, 23, 24, 25 fast. 26: Another example of the effective access time formula. (slide 27-28); Inverted page tables: An example of hash search built into hardware!! 29-30 shared pages: used for frequently used DLLs. 31-40 segmentation (review) (historic systems used non-paged segments, so they suffered from external fragmentation) Chapter 10: Please study the list of 12 steps that can occur following a page fault. slide 12 reference string
Page replacement problem; optimal off-line solution and various practical on-line solutions; off-line and on-line problem variants in general. Dirgression about the undecidability of the halting problem in terms of an "ideal software testing program". Locality of reference (AOS figure 10.15); Working set discussion and example of its calculation; how working set size varies with time; when thrashing occurs (AOS figure 10.14) Expected cached memory access time. Typical hit ratios for (1) pages in virtual memory and (2) blocks for 1st and 2nd level hardware caches. Not enough time for detailed review of page replacement algorithms..see remaining slides for alternative notes on them.
"Unix" compared to session semantics for shared open files; relationship with distrubuted computing: "Beowulf Clusters" Various file realted system calls, renaming and unlinking. Virtual functions and file operation motivation of them: Common application code for reading from a disk file and network connection (socket); declaring, defining and calling through function pointers in C/C++; using "virtual functions" with (1) function pointers in C/C++ or (2) Java or C++ virtual method support. Declarations of Linux struct file and struct file_operations in the /usr/src/linux/include/linux/fs.h. Extra remark: Notice each function pointer member in struct file_operations has a struct file * as its first function operand. Member functions are "called with" a pointer to the object for which they are called as an operarand!
More on virtual functions, virtual file system in Linux data stuctures. File types Separate issues -- see slides Summary of magnetic disk hardware features
Allocation Methods Free Space Management Directory Implementation are the key issues in the architecture of file systems (ie. disk-based data structures) AOSC Slides for Chapter 11(pdf) AOSC Slides for Chapter 12(pdf) AOSC Slides for Chapter 13(.pdf)
