Transcript How Computers Work: Operating Systems, Memory

Foundations of Software Design
Fall 2002
Marti Hearst
Lecture 5: Operating Systems, continued
1
Today
• Operating System Scheduling
– Resource Allocation
– Synchonization
– Deadlock
• Memory Management
– Address Spaces
– Memory Allocation Strategies
• Virtual Memory
• Thrashing
– Allocating memory for a java program
– The Java Virtual Machine
2
Scheduling
• Concepts you should know
– Time Slices
– Context switches / Process switches
– Strategies
• Preemptive vs. Non-preemptive
• Round-robin (with time slices), First-come-first-serve
(FCFS), Shortest Process Next
Image from http://courses.cs.vt.edu/~csonline/OS/Lessons/Processes/index.html
3
Resource Allocation
• Allocation of files,
printers, main
memory, and other
shared resources.
Image from http://courses.cs.vt.edu/~csonline/OS/Lessons/Resources/index.html
4
Synchronization
• Relevant concepts you should know
–
–
–
–
Critical section
Critical resource
Mutual exclusion
Semaphors
• Mutex semaphors
• Count semaphors
• Test-and-Set
Images from http://courses.cs.vt.edu/~csonline/OS/Lessons/Synchronization/index.html
5
Deadlock
• Like Gridlock: everyone is stuck waiting for other peole
to get out of the way
– The 3 conditions for deadlock (necessary but not sufficient)
from Brookshear
• There is competition for nonshareable resources
• The resources are requested on a partial basis
– (having received some resource, a process will ask for
another later)
• Once a resource is allocated, it cannot be “forcibly” retrieved
– Another way to say these:
• Mutex (mutual exclusion)
• Hold-and-wait
• No preemption
Image from http://courses.cs.vt.edu/~csonline/OS/Lessons/Deadlock/index.html
6
Deadlock
• Example:
• Two processes running; both require the printer and the
CD drive
• Process A has the CD drive, but is waiting for the
printer; process B has the printer but is waiting for the
CD drive.
– Have to “break the deadlock” via preemption
– Instead: don’t allow it to happen in the first place
• Don’t ever allow all three conditions to hold
• e.g., make processes “spool” their print jobs
Image from http://courses.cs.vt.edu/~csonline/OS/Lessons/Deadlock/index.html
7
Deadlock
– Another famous example: Dining Philosophers
• Three states:
– Eating
– Thinking
– Hungry
• Meets the three deadlock conditions:
– Resource contention on the dining implements
(have to share each one with one neighbor)
– Need two implements to eat
– Too polite to steal each others’ tools (nonpreemptive)
• The online readings present an interesting solution …
Image from http://courses.cs.vt.edu/~csonline/OS/Lessons/Deadlock/index.html
8
Memory Management:
User vs. System Address Spaces
• The OS manages memory for all the user
processes running on the machine.
– Each user process runs in its own address space.
• User processes have to handle their own
memory management.
– The C language makes the user do this explicitly
– Java does it for you
• Every time you do a “new” you get a new object
• If you stop using the object, you don’t say “remove”
• Cleanup is done for you by the java Garbage
Collection system
9
Address Space
• The range of bytes in memory that are
assigned to a process.
• Often will locate the OS address space in low
memory addresses, and user programs in high
0
memory addresses.
OS
• Example:
– OS needs 24 Kbytes
– User needs 12 Kbytes
24K
1012K
User
1024K
10
Address Space
• The address space can begin anywhere in memory.
• Example:
– Say your program requires 2K for instructions and 30K for
data.
– If stored starting at position 0, then the address space
ranges from 0 to 32K-1
– If stored starting at position 12K, then the address space
ranges from 12K to 44K-1.
– That means the first instruction starts at location 12K.
(This is where the Program Counter starts.)
• How does the Program Counter know what to do?
– The OS automatically adds 12K to every address in the
program.
11
Memory Allocation Policies
• The OS tries to accommodate as many user processes
as possible.
• Problem: where to put which process in memory?
• Strategies:
– Best fit: smallest possible free block
– Worst fit: largest possible free block
– First fit: first free block that fits
• Occasionally “house cleans” (reorganizes everything).
Image from: http://courses.cs.vt.edu/~csonline/OS/Lessons
12
Virtual Memory
• Allows a process to run even if the full amount of
needed memory is not currently available.
– Pages:
• The memory needed by a program is divided up into 4K
blocks
• This allows the process to run in non-continguous blocks of
memory
– Page table
• Shows which pages are in RAM and which on disk.
– Page Fault
• Happens when the process tries to access a page that is
not currently in RAM.
VM simulation: http://courses.cs.vt.edu/~csonline/OS/Lessons/VirtualMemory/index.html
13
Page Table Maps Pages in Virtual
Memory to Main Memory or Disk
Image from http://www.ece.arizona.edu/~ece369/lec10S01/sld058.htm
14
Virtual Memory
• Allows a process to run even if the full amount of needed
memory is not currently available.
– Swapping
• Moving a page from memory to disk, and vice versa
• Can also refer to moving an entire process into or out of RAM
memory
• A page fault has to be handled by the Scheduler – so slow
(accessing the disk resource; can cause a context switch)
– Thrashing
• When there isn’t enough room in main memory for all the pages
that the process needs at the same time
• The process spends all its time page faulting, swapping processes
into and out of memory, and gets little work done.
VM simulation: http://courses.cs.vt.edu/~csonline/OS/Lessons/VirtualMemory/index.html
15
Page Replacement Policies
• To decide which page to throw out of RAM
–
–
–
–
–
Least Recently Used (LRU)
Least Frequently Used (LFU) LRU with counts
First In First Out
(FIFO) Remove oldest
Random
Many others
16
Locality
– In a fairly large program, only small portions are
ever used at any one time.
– A set of pages which tend to be used together.
• Something that has been used recently is more likely
to be used again than something that has not been
used recently.
– Surprisingly, this holds true quite often.
– Processes tends to move from locality to locality.
• Makes FIFO problematic
• Makes LRU look good
17
Caches
• Idea: due to the principle of locality, some variables are
used in the CPU quite often without changing.
– These are stored in very fast memory hardware called a
cache.
• Operation: accessing a variable v:
– Check: is it in the cache?
• Yes: use the value (A Cache Hit)
• No: is the cache full? (A Cache Miss)
– Yes: remove out the least recently used value from the
cache
» Has that value changed?
» Yes: write the value into RAM
» No: do nothing; it just gets overwritten
– Read the value of v from RAM into the cache.
• There is special hardware to support all this
– TLB (translation lookaside buffer)
18
The Java Runtime Environment
• Runtime is contrasted with Compile time
– Like an OS for your java program
– The Virtual Machine is run at runtime
• Takes care of
– Memory management
– Resolving class inheritance decisions
– Allows your java program to run on any machine for
which a VM has been compiled.
• Applets are a special case
– They use a special runtime environment that is
integrated into the web browser.
19
Garbage Collection
• An object retains its space in the user address
space until there is no longer a variable
referencing (pointing to) that object.
• If there are lots of large, unused objects in the
process, this eats up the user’s address space.
• The Garbage Collector
– Runs periodically while the process is running.
– Reorganizes the user’s address space, freeing the
memory allocated to unused objects, and grouping
larger blocks of memory together.
20
The Java Virtual Machine (VM)
• When you compile a java program, javac
produces byte codes (stored in the class file).
• The byte codes are not converted to machine
code.
• Instead, they are interpreted in the VM when
you run the program called java.
– Loose Analogy: like a child standing on her parent’s
feet to dance – she does the movements but her feet
don’t touch the floor.
21
C code
Translated
by the C
compiler
(gcc or cc)
Assembly Language
Machine Code
The OS loads the
machine code into the
CPU, and handles
system calls, allocates
memory, etc
22
Translated
by the java
compiler
(javac or jit)
Java code
Byte code (class file)
The byte codes are loaded into
the java Virtual Machine.
The Virtual Machine
is a regular program
that is run in the
standard way by the
OS.
(You invoke it with the “java.exe”
command.)
The VM interprets the codes, does
memory management, makes
class inheritance decisions, etc
23
Programs vs. Processes
• Program
– The code, both in human and machine-readable form
• Process
– A running program is a process.
– It is allocated a number of resources:
• Registers in the CPU
• Some part of the CPU’s RAM
• I/O devices (the monitor, files in the file system)
• Several copies of the same program can be
running as different processes.
– But data values, current Program Counter location,
etc., will differ among the different processes.
24
Programs vs. Processes
• How does this relate to Object Oriented Programming?
• An important difference:
– Class definition vs.
– Object creation / instantiation
• Class definitions are created at compile time.
• Objects don’t really get created until the program is
running as a process.
– The “new” command in java tells the operating system to
allocate some memory and put the new object in that space.
• When the process ends,
– the class definitions do not disappear, but
– the objects disappear.
meaning that the memory allocated to the objects gets
reallocated for some other purpose.
25
Class Definition vs. Object Instantiation
/* the class definition */
public class Fish {
private int age;
private int size;
private String color;
/* the class constructor */
Fish (String col) {
age = 1;
size = 4;
color = col;
}
/* a method */
public void setColor
(String col) {
color = col;
}
/* Create and use some objects */
public static void main (String[] args)
{
// instantiate the object –
// allocate memory for it
Fish charlie = new Fish(“pink”);
Fish freddy = new Fish(“yellow”);
//
//
//
//
//
we have to tell the program
which object instantation to
modify – that’s why we say
charlie.setColor(), not just
setColor()
charlie.setColor(“red”);
}
}
26
Class Definition vs. Object Instantiation
0
int
1
int
4
str
4
“p”
4
8
“i”
“n”
The compiler knows the
“shape” of the class from
the class definition and the
definition of the constructor.
“k”
int
1
int
4
str
6
“y”
Each instantiation of an
object gets its own space in
memory. This space is
allocated when the process
space for charlie executes a “new”.
space for freddy
“e”
“l”
“l”
“o”
“w”
Each integer gets one word
of memory (2 bytes here).
The string starts with an int
showing the length of the
string. Each character
requires only one byte.
Memory addresses
Note: this is the general idea; many details are simplified
27