Transcript Page table

In a nut shell
1







Goals
A little history
System components
Threads & CPU scheduling
Virtual memory
Environmental subsystems
File System: NTFS
2


Preemptive multitasking
Goals:
◦ Security, reliability, ease-of-use, Windows &
POSIX application compatibility, highperformance, extensibility, portability,
international language support
◦ Commercial

“the layered architecture of the system …
makes it so easy to use”
 Windows
NT
◦ Adopted Windows 95 user
interface and incorporated webserver & web-browser
◦ User-interface routines and all
graphics code were moved into the
kernel to improve performance
 Side effect: Decrease in system
reliability
4

Windows XP (Oct 2001)
◦ Successor to Windows NT/2000, replacement for
Windows 95/98
◦ Reliability requirement for Windows XP more
stringent than Windows 2000 (which was the
most reliable, stable system released by
Microsoft)
◦ “extensive manual and automatic code review to
identify over 63,000 lines in the source [code]
that might contain issues not detected by testing”
and then set about a review & correction process
5
System Components
6

Microkernel: Executes in protected mode
◦ HAL: Hardware abstraction layer
 Some hardware independence
 HAL provides memory mapping, configuring I/O buses,
setting up DMA, motherboard specific facilities
 Device drivers (I/O manager) can still work directly with
hardware
◦ Kernel
 thread scheduling, interrupt & exception handling, CPU
synchronization, power failure recovery
 Never paged out, never preempted

User mode processes
◦ Environmental subsystems
 User mode operating systems (e.g., MS-DOS, OS/2, Win32,
POSIX)
 Logon systems
◦ User applications
7

Processes

Threads
◦ Virtual memory address space
◦ Base priority
◦ “affinity” (assignment) to one or more
processors
◦ One or more threads
◦ Units of execution; dispatched by kernel
◦ States: ready, standby, running, waiting,
transition, terminated
8


Priority-based, preemptive scheduling
32 priority levels; each has a queue of
threads
◦ Variable class: 0-15
◦ Real-time: 16-31
◦ Higher numbers indicate higher priority

Scheduler traverses from highest to
lowest priority queues
◦ Round robin, combined with priority scheme
9


Variation on standard round-robin CPU
scheduling
When thread’s time quantum runs out
◦ Variable class: priority lowered
 unless already base priority
◦ Returned to relevant priority level in queue, in
ready state
◦ Why lower the thread priority? Are there
conditions under which a variable class thread will
not have its priority lowered?
10

When variable priority thread released from
wait state
◦ Dispatcher boosts priority, depending on type of
wait
◦ High boost:
 Waiting for keyboard I/O
 Thread associated with user’s active GUI window
◦ Low boost: waiting for disk I/O
11

32-bit processors
◦ 4K page size
 12 bit page offset
◦ 4GB virtual address space
◦ Upper 1-2 GB of all processes, used by
operating system in kernel mode

64 bit processors
◦ 8K page size
 13 bit page offset
◦ 8 TB virtual address space
12

Demand paging with clustering

Max/min working set size per process

If a process is at its working set maximum and a
page fault occurs
◦ Bring in neighboring pages on a page fault: “Prefetching”
◦ Processes have initial working set size of 50 frames
◦ Local page replacement

When number of free frames drops below a certain
value
◦ Automatic working-set trimming
◦ memory manager removes pages from processes until
processes at working set minimum
◦ FIFO or variation of clock algorithm depending on hardware
(p. 363)


2-level page tables
Each process has a page directory (outer page
table)
◦ 1024 page-directory entries (PDE’s)
◦ Size 4 bytes for each PDE
◦ Each PDE points to a page table

Page table (inner page table)
◦
◦
◦
◦

1024 page-table entries (PTE’s)
Size 4 bytes for each PTE
Each PTE points to a 4 KB frame of physical memory
Page tables are swapped out to disk when necessary
Total size of all page tables, per process: 4 MB
Logical
Address
structure
14
15


20 bits for frame number
12 bits remain to describe state of page
◦
◦
◦
◦
◦
Accessed or written
Caching attributes
Access mode
Global
PTE valid
16


Some implement user-level operating
systems
Some implement services crucial to all userlevel operating systems
◦ E.g., GUI, security management

Win32
◦ Executes in unprotected mode
◦ Provides all keyboard, mouse, graphical display
 Other environmental subsystems use this
◦ Separate processes with own input queues
◦ Window manager dispatches input to input queue
of appropriate process

A user-level operating system
◦ Executes in unprotected mode



Instruction execution unit: Emulates Intel
486 instructions
Routines to emulate DOS ROM BIOS & “Int
21” software interrupt services
Virtual device drivers: Screen, keyboard,
comm. Ports
◦ Partial support only: No direct h/w access
18






User-level operating systems considered
to be “clients”
Kernel considered to be “server”
Communication between client and
server provided by message passing
“Local procedure call” (LPC) facility
◦ like Remote Procedure Calls
Message passing within a single
computer
Used to implement system calls
19

Server (e.g., kernel)
◦ Publishes a globally visible connection port object

Client (e.g., Win32), to obtain services
provided by server
◦ Opens a handle to server connection port
 Sends connection request
◦ Server creates channel & returns handle to client
◦ Channel: pair of private communication ports
 Client-to-server messages
 Server-to-client messages

Some specifics dependent on message sizes
◦ Small messages (e.g., up to a few hundred bytes) are
copied from sender to receiver
◦ Shared memory is used for larger messages
20
 Goals
◦ data recovery, security, fault
tolerance, large file & file system
sizes, multiple data streams,
UNICODE names, compression

NTFS is a journaling file system
◦ It provides recovery of structure of file system
(metadata) should there be a system failure

NTFS volumes can occupy a portion of a
disk, an entire disk, or can span disks
21




In NTFS a file is not a simple stream of
bytes as it is in some operating systems
(e.g., Unix)
Rather, files are structured objects
comprised of typed attributes
Some types of attributes
◦ Conventional data of a file
◦ Standard attributes: name, creation time,
security descriptor
Examples of other uses of these typed
attributes
◦ Mac file resource fork on a Windows XP file
server
◦ Thumbnail of an image
22


Cluster: Unit of disk allocation
Allocates sectors on disk in contiguous
groups
◦ A number of 512 byte disk sectors (power of two
size)

Example
◦ Cluster size is 4096 bytes with disks > 4GB
◦ If the (block) sector size on disk is 512 bytes,
this means each cluster is going to be 8 (blocks)
sectors
23
“How NTFS Works”, www.microsoft.com
24

MFT (Master file table)


Partial copy of MFT
Log file

Volume file

Attribute-definition table




Root directory: top-level in hierarchy
Bitmap file: free/used clusters on disk
Boot file: startup code for Windows XP
Bad-cluster file: Bad areas on volume
◦ Describes all files; file control block information
(analogous to Unix inode information)
◦ Temporary record of all metadata updates
◦ Name of volume, NTFS version, consistency bit
◦ Types of attributes used in volume & operations on types
25

MFT: Master file table
◦
◦
◦
◦
One or more records per file
Each record is 1-4 KB in size
Describes attributes of file
Resident attributes: small sized
 data stored in MFT record
◦ Nonresident attributes: larger sized
 data stored in contiguous extents on disk


For small files, even the data of the file may be
stored in the MFT record
Each file in NTFS volume has an ID-- its file
reference
◦ 48 bit file number, 16 bit sequence number

Directories: particular kinds of files; B+ tree
rep’n

If a system failure (e.g., power failure)
occurs when a file system is being written,
can loose meta data (organization info)
and/or file data
◦ Metadata loss tends to be more difficult

In NTFS, all file-system data-structure
(metadata) updates are performed in log file
transactions
◦ Before a data-structure is altered, transaction first
writes a log record that contains redo and undo
information
◦ After the data structure has been changed,
transaction writes a commit record to log to
signify that transaction succeeded

After a crash, log file transactions that had
not been committed can be undone
27