CS计算机代考程序代写 x86 chain compiler • System software serves three purposes

• System software serves three purposes
– virtualization
– protection
– abstraction (particularly hiding asynchrony)

• virtualization:
– the illusion of multiple/practically unlimited resources

• protection:
– reduce/eliminate the chance of accidental and/or malicious

destruction of data/results by another program

Role of System Software (1)

• abstraction:
– hide fundamentally asynchronous nature of processor/device

interaction
– provide simpler and more powerful interfaces (integrated

w/protection)

Role of System Software (2)

ETH

someone
else’s codeyour code

buf buf buf

neither can cross
protection boundary

• recall that subroutines allow a programmer
to encapsulate common operations

• the operating system
– want to provide an interface including

common operations
– BUT don’t want to re-link programs
– NOR rely on everyone having exactly

the same OS version

System Calls, Interrupts, and Exceptions (1)

CALL

CALL

26

4
1

3

5

7

• solution
– add a level of indirection!

• with indirection
– to rewrite OS, just change the table
– application code does not change

System Calls, Interrupts, and Exceptions (2)

CALL #1
0
1
2
3
4

called
“handlers”
or “handler
procedures”

table of
function
pointers

• in LC-3, we used the TRAP instruction; in x86, it’s the
INT instruction:
INT 8-bit imm. # (PUSH EIP), EIP ¬ table[imm8]

– the RTL is actually a little more complicated, as you’ll see
later in course

– called a trap (after instruction, or trap door through protection
boundary)

– also called a system call (for operating system)

System Calls, Interrupts, and Exceptions (3)

• vector tables/jump tables
– i.e., tables of function pointers
– convenient abstraction for many procedure-like activities

• Question:
– What happens if software does something wrong, e.g.,

• accesses a non-existent memory location?
• issues an illegal/undefined instruction? divides by 0?

• What do we do to handle problems?
– state machine that you design for processor may have don’t cares
– state machine that you build will do something (may be unknown)
– so just let it run! (e.g., 6502 did so… and programmers used!)

System Calls, Interrupts, and Exceptions (4)

• a better solution: exceptions!
– processor maps each problem to a vector #
– calls procedure in vector table by #

• Where else might we use vector tables?

• Consider processor interactions with devices
– a disk access takes about 10 milliseconds
– new machines in lab: 10 ms = 32 million cycles

• should processor sit around asking, “Are my data here yet?”

System Calls, Interrupts, and Exceptions (5)

– analogous to posting a letter to a friend in Europe
– and checking your mailbox every minute for a reply
– instead, have your mail carrier ring your doorbell when it arrives
– in a processor, we call that an interrupt

• How can we use a vector table for interrupts?
– each device has a vector #
– call corresponding procedure in vector table when device generates

• x86 ISA
– uses one table for all three kinds
– called the Interrupt Descriptor Table (IDT)

System Calls, Interrupts, and Exceptions (6)

• How does a processor support interrupts?

• Logically…

N=8 on x86 (and LC-3)

• How should we change a processor’s state machine
to incorporate interrupts?

Processor Support for Interrupts (1)

INTR

N which one?

Z. Kalbarczyk ECE391

LC-3 state machine
interrupt support

• x86 allows software to block interrupts with a status
flag (in EFLAGS)

• normal interrupts occur only when the interrupt
enable flag (IF) is set

• some interrupts are too important
– e.g., memory errors, power warnings, etc.
– these are NOT maskable, and use a separate input to

processor
– called non-maskable interrupts (NMI)

Processor Support for Interrupts (2)

INTR

8 which (uses data bus)
NMIx86

• as mentioned earlier
– x86 uses a single vector table
– the Interrupt Descriptor Table (IDT)
– hold vectors for interrupts, exceptions, and system calls

• note that this picture is partly OS-specific
– the exception vector numbers are specified by Intel – Why?

• A: generated directly by processor’s state machine

– programmable interrupt controller (PIC) will be discussed later;
• range of vectors generated is programmable, and is shown for

Linux 2.4

– note that a single entry is used for all system calls in Linux

Interrupt Descriptor Table

Interrupt
Descriptor Table

(cascade to secondary)

primary

secondary

• The question
– interrupt handlers and programs share

resources
• What resources are shared between them?
• How might interactions cause problems?
• What can we do to fix those problems?

Shared Data and Resources (1)

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• Obvious things
– registers

• solution? save them to the stack

– memory
• solution? privatize

• will still need to share some things; discussed later

Thought Problem on Shared Resources (2)

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• Less obvious
– condition codes

• solution? again, save them to the stack

– shared data

• More subtle
– external state (e.g., on devices)
– compiler optimization (e.g., volatility)
– security leaks

• e.g., application waits for interrupt, then observes values written
by OS to stack

• solution? use separate stack for kernel

Thought Problem on Shared Resources (3)

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

step 1: old_head = head;

step 2: head = new_elt;

Oops! an interrupt!
step 3: new_elt->next = old_head;

Examples of Shared Resources:
Example #1: a shared linked list

?

old_head

head

new_elt

1

2

3

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• The problem?
– linked list structure has invariant
– head points to first, chained through last via next field, ends

with NULL
– complete operation maintains invariant
– partial operation does not – need atomic update

Examples of Shared Resources:
Example #1: a shared linked list

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• The core problem
– devices have state
– processors interact with devices using specific protocols
– protocol often requires several steps (e.g., I/O instructions)
– device cannot differentiate which piece of code performed an

operation
• Example:

– VGA controller operations for scrolling window with color
modulation

– interrupt handler drives color manipulations
– program handles scrolling using pixel shift
– both use VGA attribute register (port 0x3C0)

Examples of Shared Resources:
Example #2: external state

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• Protocol for attribute control register
– 22 different attributes accessed via this register
– first send index
– then send data
– VGA tracks whether next byte sent is index or data

• Problem: processor can’t know which one is
expected

• Solution: reading from port 0x3DA forces VGA to
expect index next

Examples of Shared Resources:
Example #2: external state

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• Consider the program code
– the horizontal pixel panning register is register 0x13
– assume that the code should write the value 0x03 to it

(discard) ¬ P[0x3DA] MOVW $0x3DA, %DX
INB (%DX),%AL

0x13 ® P[0x3C0] MOVW $0x3C0, %DX
MOVB $0x13, %AL
OUTB %AL, (%DX)

0x03 ® P[0x3C0] MOVB $0x03, %AL
OUTB %AL, (%DX)

Examples of Shared Resources:
Example #2: external state

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• What happens if the interrupt occurs after the first
write to 0x3C0?
– the interrupt handler is executing basically the same code
– leaves the VGA expecting an index

• What is the solution?

Examples of Shared Resources:
Example #2: external state

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• A device generates an interrupt after it finishes
executing a command

• Consider the following attempt to synchronize

the shared variable…
int device_is_busy = 0;

the interrupt handler…
device_is_busy = 0;

Examples of Shared Resources:
Example #3: handshake synchronization

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

The program function used to send a command to the
device…

while (device_is_busy);/* wait until device is free */

device_is_busy = 1;
/* send new command to device */

• Q: Does the loop work?
• No.

– Compiler assumes sequential program.
– Variables can’t change without code that changes them.

Examples of Shared Resources:
Example #3: handshake synchronization

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

LOOP: MOVL device_is_busy, %EAX

CMPL $0, %EAX

JNE LOOP

• Nothing can change variable, so no need to reload (move
LOOP down a line).

• Now nothing can change EAX, so move it down another line
(to branch!).

• Will interrupt handler break you out of the resulting infinite
loop?

Examples of Shared Resources:
Example #3: handshake synchronization

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• Solution
– mark variable as volatile
– tells compiler to never assume that it hasn’t changed between uses

• Why not mark everything volatile?
– forces compiler to always re-load variables
– more memory operations = slower program

Examples of Shared Resources:
Example #3: handshake synchronization

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• Is it ok to swap setting the variable and sending the
command?

• No.
– introduces a race condition:

/* send new command to device */

—- INTERRUPT OCCURS HERE —-

device_is_busy = 1;

• Next command call blocks (forever) for device to be free.

Examples of Shared Resources:
Example #3: handshake synchronization

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• Unfortunately, writing your code correctly is not enough.
– compiler optimization allowed to reorder

• so long as code is equivalent
• assuming sequential program

– also (and much more subtly!)
• ISA implementation is allowed to reorder

• Message
– important to think about reordering possibilities by compiler and ISA

and to prevent bad reorderings

Examples of Shared Resources:
Example #3: handshake synchronization

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• Some parts of program need to appear to execute
atomically, i.e., without interruption

• Full version: atomic with respect to code in interrupt
handler
– for now, the clause is implied i.e., only interrupt handlers can

operate during our programs
– however, multiprocessors may have >1 program executing at

same time

Critical Sections

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• Solution?
– IF (the interrupt enable flag)

critical section start (CLI)

(the code to be executed atomically)
critical section end (STI)

• What else must be prevented?
– no moving memory ops into or out of critical section!

Critical Sections

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• Example #2: external state

MOVW $0x3DA, %DX

INB (%DX),%AL

MOVW $0x3C0, %DX
MOVB $0x13, %AL

OUTB %AL, (%DX)
MOVB $0x03, %AL
OUTB %AL, (%DX)

Critical Sections in Examples

CLI

STI

the critical section
should be as short

as possible

© Steven Lumetta, Zbigniew Kalbarczyk ECE391

• Why should critical sections be short?
– avoid delaying device service by interrupt handler
– long delays can even crash system (e.g., swap disk driver timeout)

• Example #1: a shared linked list
old_head = head;

head = new_elt;

new_elt->next = old_head;

• If interrupt handler can change list, too, leaving out first
inst. creates race

• Example #3: handshake synchronization—volatile suffices
for this example

Critical Sections in Examples

CLI

could skip first statement,
but including is safer

STI

© Steven Lumetta, Zbigniew Kalbarczyk ECE391