Windows File System

File Systems

A file system enables applications to store and retrieve files on storage devices. Files are placed in a hierarchical structure. The file system specifies naming conventions for files and the format for specifying the path to a file in the tree structure.

Each file system consists of one or more drivers and dynamic-link libraries that define the data formats and features of the file system. File systems can exist on many different types of storage devices, including hard disks, jukeboxes, removable optical disks, tape back-up units, and memory cards.

All file systems supported by Windows have the following storage components:

• Volumes. A volume is a collection of directories and files.
• Directories. A directory is a hierarchical collection of directories and files.
• Files. A file is a logical grouping of related data.

Directory Management

A directory is a hierarchical collection of directories and files. The only constraint on the number of files that can be contained in a single directory is the physical size of the disk on which the directory is located.

http://msdn2.microsoft.com/en-us/library/aa364407(VS.85).aspx

Spinlock

spin lock: busy waiting
semaphore: sleep and wake-up
spin lock 适用于切换快的场合, 否则会浪费大量cpu时间

a spinlock is a lock where the thread simply waits in a loop ("spins") repeatedly checking until the lock becomes available. As the thread remains active but isn't performing a useful task, the use of such a lock is a kind of busy waiting. Once acquired, spinlocks will usually be held until they are explicitly released, although in some implementations they may be automatically released if the thread blocks (aka "goes to sleep").

Spinlocks are efficient if threads are only likely to be blocked for a short period of time, as they avoid overhead from operating system process re-scheduling or context switching. For this reason, spinlocks are often used inside operating system kernels. However, spinlocks become wasteful if held for longer, both preventing other threads from running and requiring re-scheduling. The longer you hold the lock, the greater the risk that you will be interrupted by the O/S scheduler while holding it. If this happens, other threads will be left spinning on the lock, despite the fact that you are not making progress towards releasing it. This is especially true on a single-processor system, where each waiting thread of the same priority is likely to waste its full quantum spinning until the thread that holds the lock is finally re-scheduled.

Implementing spinlocks is difficult, because one must take account of the possibility of simultaneous access to the lock to prevent race conditions. Generally this is only possible with special assembly language instructions, such as atomic test-and-set operations, and cannot be implemented from high level languages like C.[1] On architectures without such operations, or if high-level language implementation is required, a non-atomic locking algorithm may be used, e.g. Peterson's algorithm. But note that such an implementation may require more memory than a spinlock, be slower to allow progress after unlocking, and may not be implementable in a high-level language if out-of-order execution is in use.

Measuring Program Execution Time

Two basic mechanisms to record the passage of time:

• Interval Counting, which is based on a low frequency time that periodically interrupts the procesor. The operating system uses the time to record the cumulative time used by each process and maintains counts of the amount of user time and the amount of system time used by each process. There are libraries functions for this time (linux) and clock (time.h, ANSI C). We can compute the total time between two different points in a program execution by making two calls to times and computing the difference of the return values. Disadvantage: The interval accounting scheme makes no attempt to resolve time more finely than the time interval. Interval counting is only useful for measuring relatively long computations-- 100,000,000 clock cycles or more and is too coarse-grained to use for any measurement having duration of less than 100 ms.
• Cycle Counters, which is based on a counter that is incremented every clock cycle. The timer is a special register that gets incremented every single clock cycle. Special machine instructions (rdtsc for "read time stamp counter") can be used to read the value of the counter. Cycle counters provide a very precise tool for measuring the time that elapses between two different points in the execution of a program. The disadvantage is that they do not keep track of which process uses those cycles or whether the procesor is operating in kernel or user mode. Context switching and cache operations cause extreme variation in execution time. To overcome this, K-best measurement scheme is proposed but it is reasonably robust for measuring durations shorter than the timer interval.

Process Scheduling and Timer Interrupts: computers have an external timer that periodically generates an interrupt signal to the processor. The spacing between these interrupt signals is called the interval time. When a timer interrupt occurs, the operating system scheduler can choose to either resume the currently executing process or to switch to a different process. This interval time must be set short enough to ensure that the processor will switch between tasks often enough to provide the illusion of performing many tasks simutaneously. Typical timer intervals range between 1 and 10 milliseconds.

Kernel operation (in kernel mode) such as handling page faults, input, or output is considered part of each regular process rather than a separate process. When the scheduler switches from process A to process B, it must enter kernel mode to save the state of process A (still considered part of process A) and to restore the state of proces B (considered part of proces B).

Looking into the future:

• Process-specific cycle timing. All that required is to store the count as part of the process' state.
• Variable Rate Clocks. Power consumption is directly proportional to the clock rate,and to reduce power consumption, future systems will vary the clock rate.

Garbage Collection

A garbage collector is a dynamic storage allocator that automatically frees allocated blocks that are no longer needed by the program. Such blocks are known as garbage and hence the term garbage collector. The process of automatically reclaiming heap storage is known as garbage collection.

A garbage collector views memory as a directed reachability graph. The nodes of the graph are partitioned into a set of root nodes and a set of heap nodes. Each heap node corresponds to an allocated block in the heap. Root nodes correspond to locations not in the heap that contain pointers into the heap. Those locations can be registers, variables on the stack, or global variables in the read-write data area of virtual memory. The role of a garbage collector is to maintain some representation of the reachability graph and periodically reclaim the unreachable nodes by freeing them and returning them to the free list.

Mark & Sweep algorithm (by McCarthy): A Mark&Sweep Garbage Collector consists of a mark phase, which marks all reachable and allocated descendants of the root nodes, followed by a sweep phase, which frees each unmarked allocated block by iterating over each block in the heap and freeing any unmarked allocated blocks that it encounters.

Dynamic memory allocation

Computer Systems

10.9.5 Implementation issues

A practical allocator that strikes a better balance between throughput and utilization must consider the following issues:

• Free block organization: how do we keep track of free blocks?
• Placement: How do we choose an appropriate free block in which to place a newly allocated block?
• Splitting: After we place a newly allocated block in some free block, what do we do with the remainder of the free block?
• Coalescing: What do we do with a block that has just been freed?

10.9.6 Implicit Free Lists

Any practical allocator needs some data structure that allows it to distinguish block boundaries and to distinguish between allocated and free blocks. Most allocators embed this information in the block themselves. An example is as follow.

A block consists of a one-word (4 bytes) header, the payload, and possibly some additional padding. The header encodes the block size as well as whether the block is allocated or free. If we impose a double-word alignment constraint, then the block size is always a multiple of eight and the three low-order bits of the block size are always zero.

This organization is called implicit free list because the free blocks are linked implicitly by the size fields in the headers. The allocator can indirectly traverse the entire set of free blocks by traversing all of the blocks in the heap. We also need some kind of specially marked end block. The advantage of an implicit free list is simplicity. A significant disadvantage is the cost of any operation, such as placing allocated blocks, requires a search of the free list will be linear in the total number of allocated and free blocks in the heap.

10.9.7 Placing Allocated Blocks

Three common placement policies are: first fit, next fit and best fit. All of them have advantages and disadvantages.

10.9.8 Splitting Free Blocks

If the fit is not good, then the allocator will usually opt to split the free block into two parts. The first part becomes the allocated block, and the remainder becomes a new free block.

10.9.9 Getting Additional Heap Memory

If the allocator is unable to find a fit for the requested block, it will ask the kernel for additional memory, either by calling the mmap or sbrk functions.

10.9.10 Coalescing Free Blocks

There are free blocks adjacent to the newly freed block, which is known as false fragmentation. Coalescing comes in to rescue this phenomenon by merge adjacent free blocks. When to perform such operations??? Immediate coalescing Vs Defer coalescing. The former could introduce a form of thrashing, where a block is repeatedly coalesced and then split soon thereafter.. Fast allocators often opt for some form of deferred coalescing.

10.9.11 Coalescing with Boundary Tags

Coalescing the next free block is straightforward and efficient. How would we coalesce the previous block? Knuth developed boundary tags, which allows for constant-time coalescing of the previous block. The idea is to add a footer (the boundary tag) at the end of each block, where the footer is a replica of the header. If each block includes such a footer, then the allocator can determine the starting location and status of the previous block by inspecting its footer, which is always one word away from the start of the current block.

10.9.14 Segregated Free Lists (A popular choice with production-quality allocators such as GNU malloc)

Segregated storage: maintain multiple free lists, where each list holds blocks that are roughly the same size. Two basic approaches: simple segregated storage and segregated fits.

Simple segregated storage: the free list for each size class contains same-sized blocks, each the size of the largest element of the size class.

Segregated Fits: Each list contains potentially different-sized blocks whose sizes are members of the size class.

Alignment

excerpted from 3.10 Computer Systems

Reason: Many computer systems place restrictions on the allowable addresses for the primitive data types, requiring that the address for some type of object must be a multiple of some value k (typically 2, 4, or 8). Such alignment restrictions simplify the design of the hardware forming the interface between the processor and the memory system.

Note: the IA32 hardware will work correctly regardless of the alignment of data. However, Intel recommends that data be aligned to improve memory system performance.

Alignment with Linux: Linux follows an alignment policy where 2-byte data types (e.g., short) must have an address that is a multiple of 2, while any larger data types (e.g., int, int *, float, and double) must have an address that is a multiple of 4.

Note: a multiple of 2 means the least significant bit of the address of an object of type short must equal 0. Similarly, any object of type int, or any pointer, must be at an address having the low-order two bits equal to 0.

Alignment with Microsoft Windows: Microsoft requires a stronger alignment requirement - any k-byte (primitive) object must have an address that is a multiple of k. In particular, it requires that the address of a double be a multiple of 8.

Note: malloc must be designed so that they return a pointer that satisfied the worst-case alignment restriction for the machine it is running on, typically 4 or 8.

For structures, the compiler may need to insert gaps in the field allocation to ensure that each structure element satisfies its alignment requirement. The compiler must also ensure that the structure has some required alignment for its starting address. In addition, the compiler may need to add padding to the end of the structure so that each element in an array of structures will satisfy its alignment requirement.

Chapter 1. Introduction

Direct memory access (DMA) : the data travels directly from disk to main memory, without passing through the processor.

Virtual Memory

excerpted from chapter 10, Computer Systems

Modern systems provide an abstraction of main memory known as virtual memory (VM), which provides each process with a large, uniform and private address space. VM uses main memory efficiently by treating it as a cache for an address space stored on the disk, keeping only the active areas in main memory, and transferring data back and forth between disk and memory as needed.

10.1 Physical and Virtual Addressing

The main memory of a computer system is organized as an array of M contiguous byte-sized cells. Each byte has a unique pyhsical address (PA). {0, 1, 2, ,,, , M-1}

With virtual addressing, the CPU accesses main memory by generating a virtual address, which is converted to the appropriate physical address before being sent to the memory. Memory Management Unit (MMU) on the CPU chip translates virtual addresses on the fly, using a look-up table stored in main memory whose contents are managed by the operating system.

10.2 Address Spaces

An address space is an ordered set of nonnegative integer addresses {0,1,2,...}. If the integers in the address space are consecutive, then we say that it is a linear address space.

The concept of an address space is important because it make a clean distinction between data objects (bytes) and their attributes (addresses). This is the basic idea of virtual memory. Each byte of main memory has a virtual address chosen from the virtual address space, and a physical address chosen from the physical address space.

10.3 VM as a tool for caching

Conceptually, a virtual memory is organized as an arry of N contiguous byte-sized cells stored on disk. VM partitions the virtual memory into fixed-size blocks called virtual pages (VPs). Similarly, physical memory is partitioned into physical pages (PPs), the same szie.

The set of virtual pages in partitioned into three disjoint subsets:
1.Unallocated. Unallocated blocks do not have any data associated with them, and thus do not occupy any space on disk.
2.Cached
3.Uncached

10.3.1 DRAM Cache Organization

Due to the large miss penalty, virtual pages tend to be large, typically 4 to 8 KB. DRAM caches are fully associative, that is, any virtual page can be placed in any physical page.

10.3.2 Page Tables

a data structure stored in physical memory known as a page table that maps virtual pages to physical pages. The address translation hardware reads the page table each time it converts a virtual address to a physical address. The operating system is responsible for maintaining the contents of the page table and transferring pages back and forth between disk and DRAM.

A page table is an array of page table entries (PTEs). Each page in the virtual address has a PTE at a fixed offset in the page table.

10.3.3 Page Hits

10.3.4 Page Faults

A DRAM cache miss is known as a page fault, which will triggers a page fault exception. The page fault exception will invoke a page fault excpetion handler in the kernel, which select a victim page, copy that page back if it has been modified and modify the page table entry. After that, restarting the previous faulting instruction.

Demand paging: the stratery of waiting until the last moment to swap in a page, when a miss occurs.

10.3.5 Allocating Pages

10.3.6 Locality to the Resue Again

The principle of locality promises that at any point in time they will tend to work on a smaller set of active pages known as the working set or resident set.

As long as our programs have good temporal localtiy, virtual memory systems work quite well.

10.4 VM as a Tool for Memory Management

Operating Systems Provide a separate page table, and thus a separate virtual address space, for each process. Multiple virtual pages can be mapped to the same shared physical page.

10.4.1 Simplifying Linking

A separate address space allows each process to use the same basic format for its memory image, regardless of where the code and data actually reside in physical memory.

10.4.2 Simplifying Sharing

In general, each process has its own private code, data, heap, and stack areas that are not shared with any other process. However, in some instances it is desirable for processes to share code and data. the operation system can arrange for multiple processes to share a single copy of this code by mapping the appropirate virtual pages in different processes to the same physical pages.

10.4.3 Simplifying Memory Allocation

Operating system allocates an appropriate number, say k, of contiguous virtual memory pages, and maps them to k arbitrary physical pages located anywhere in physical memory. Because of the way page tables work, there is no need for the operating system to locate k continuous pages of physical memory. The pages can be scattered randomly in physical memory.

10.4.4 Simplifying Loading

The .text and .data sections in ELF executables are continuous. To load these sections into a newly created process, the Linux loader allocates a continuous chunk of virtual pages starting at address 0x08048000, marks them as invalid, and points their page table entries to the appropriate locations in the object file.

The loader NEVER actually copies any data from disk into memory. The data is paged in automatically and on demand by the virtual memory system the first time each page is referenced.

This notation of mapping a set of continuous virtual pages to an arbitrary location in an arbitrary file is known as memory mapping.

10.5 VM as a Tool for Memory Protection

Since the address translation hardware reads a PTE each time the CPU generates an address,, it is straightforward to control access to the contents of a virtual page by adding some additional permission bits to the PTE.

If an instruction violates these permissions, then the CPU triggers a general protection fault that transfers control to an exception handler in the kernel. Unix shells typically report this exception as a "segmentation fault".

10.6 Address Translation