compsci2(2008)
Tue 03/25/08
ls -l |
redirects keyboard input .. going to come from the pipe now
create an unnamed pipe
(named pipes use a create function)
int pdt[2] (pipe descripter table)
pdt
[] read end
[] write end
pdt[0] read end
pdt[1] write end
that doesn't give you a pipe but an index for one
if (pipe(pdt) = -1)
{
perror("bad pipe");
exit(0);
}
fdt
0stdin
1stdout
2stderr
3read end
4write end
pipes (unnamed) are one-directional
named pipes are two unnamed pipes duck taped together
we read and write to a pipe as if it were a file
write(pdt[1],buff,sizeof(buff));
read blocks on a pipe if nothing is in there
pipes are invisible .. they look like buffers
the kernal keeps the data somewhere in case you're not ready for it
unlike a file, when you read from a pipe, you remove it from the pipe
the buffer itself is invisible to us
read(pdt[0],buff,n);
what happens if i keep writing to the pipe and don't get around to reading it?
the write is blocked when the pipe is filled
ex: parent reads from a file,
echos to stdout and pipes to a child
child reads from the pipe and writes to stdout
int pdt[2];
pipe(pdt);
(pid = fork())
// parent with fdt
//child with same fdt
//pdt[0] and pdt[1] in fdt
we want to close the pipe connections that we aren't going to use
close(pdt[0]);
child:
close(pdt[1});
parent: df = open(a file);
parent: n= read(df,buff,20);
parent: write(pdt[1],buff,20);
.. and loop
child: n = read(pdt[0],buff,5);
write(1,buff,n):
parent loop - done when we hit the EOF
how does child know to stop?
when the write end of the pipe is closed, the kernal sends the signal sigpipe to all the readers (children)
in this case, read returns a 0. So n=0 in this case.
so parent needs to close(pdt[1]);
both parent and child have to close the end for it to be closed .. so close your unneeded ends immediately
exec executes a process from within a process
(different from system)
reference: Wang 353-356, 394-395
exec overlays the callers memory space
calling process is destroyed
the process that you're executing could use the files that you had open for it
what good is that? that's why you have children .. child can do the exec .. so main program is still alive
execl (list entire path or in current directory)
execlp (uses your PATH variable)
int pid;
id status;
pid = fork();
if(pid == 0)
{
execl("/usr/bin/ls","ls", "-l", NULL);
.. that's the command tail
path must include the ls
with we use exelp, then we could have gotten by with just ls instead of /usr/bin/ls
perror("canot exec"); //should not get here
exit(0);
else
{
/*parent*/
lives on;
/*could wait for the child here*/
}
execv(path as a string, array of strings for the command);
str
0 ls
1 -l
3 NULL
then tht would execute the same away
so if you don't know or will have a variable amount of paramenters, then set up as an array rather than lots of strings
execvp works too
system
------
int system(str);
//str = ls -l;
system executes in a new shell
uses the SHELL environment variable .. usually set to sh
main program blocks and waits until it finishes
should not use it if you use threaded processes .. sharing signals .. the shell would get the signal and not the ls
systems returns an error code .. you can find out why it exited
ls -l | short +4
Parent
create a pipe and then fork
child1
child2
at this point, all three can read and write to the pipe
parent should close both ends of the pipe
child1 should keep pdt[1] but close pdt[0]
child2 should keep pdt[0] but close pdt[1]
child1 ls -l
child2 sort +4 (sort on column 4)
when i do ls -1, it goes to stdout .. but we want it to go to the pipe
when you don't have what to sort, it sorts from stdin
==========(Note Break)==========>>
Thu 03/27/08
scheduling and batch processing
first come first served .. easy .. whoever comes first goes first
not preemptive .. example: people getting concert tickets
mouse movement wouldn't get to happen with first come first served
shortest job first .. always tkaes the shortest job first .. so you can have more processes get done
.. problem for longer processes .. they wouldn't get to go
10 s , 5, 7 4 4 second jobs = 30
10 15 22 26 30 = 103/5 = 20.6 .. takes on average 20.6 for each process to finish
4 4 5 7 10
4 8 13 20 30 = 75/5 = 15 .. less average time
shortest remaining time next .. when a process comes in, if you're running a 4 second process and a 3 second process comes in .. it'll take the 3 second process
.. but you can't always estimate run time
have to take into consideration the time it takes to switch processs
another alg - round robin .. everyone gets to go at some point
old scheduling algorithm .. pretty fair .. no processes are starved .
simple and widely used
when a process is interrupted it gets put at the bottom of the list
but, how long do we want to make the quantum .. how long does a p-switch take
take into account the amount of time used (percentage) vs processing time
if you make the quantum too big .. itakes awhile for other processes to go
quantum usually 20 to 50 ms
what else: lottery scheduling, priority scheduling
Disk formatting and disk arm scheduling
low level formatting
preamble - tells about the start of the secotor
Data
Ecc - info for error recovery
issues with low level formatting .. when the disk is created .. the time of rotation of the actual disk and the movement of the arm have to be in sync .. cyllinder screw -- takes into account the time it takes for the tarm to move to the next track .. offset depending on how long it taaes the arm
also a head screw .. but not as big
low level formatting reduces the capacity by about 20%
also software gigabyte vs math gigabyte
2^30 vs 10^9
large data transfers need large buffer
by the time the buffer hits the ecc , the next secotor has passed by .. has to rotate around
algorithms for the low level formatting to do interleaving .. alternates .. single and double interleaving
always take time to copy the buffer to memory .. controller should be able to buffer an entire plan vs track.
on most pentium computers, sectory 0 contains the master boot record .. some boot code and the partition table (starting secords and partitions)
disk arm scheduling
seek time
rotational delay
actual data transfer time
alg
first come first served .. can only improve on seek time
11,1,36,16,1,34, ..
you'd bounce all over the place
shortest seek first
starts at 11 and then sees which is the next closest
puts data in table according to sector
but you have a tendency to stay in the middle .. extremes never get touched
next thought .. elevator .. keep moving in the samme direction until all requests in that direction .. but that requires software to maintain.
another way to improve this .. wraparound .. considers 0 to be 41 hits all of them and goes all the way back
if seek time is faster than rotational time, the requests should be sorted by sector number .. so it just switches tracks when it hits a sector
reading one or two sectors is inefficient .. so reads most, if not all, of the cache .. reads more than it was told to with the idea that it'll be needed eventually
OS cache vs disk cache
vista scheduling
why does the scheduler get called
1. if the thread gets blocked on a semaphore or mutex
reason: thread cant do anything until up is issued
2. thread signals an object called because when the thread is given an up , it may have an opportunity to run so let it.
3. quantum expires .. lowers the priority of the thread
4. i/o completes
5. a timed wait expires .. example: sleep command
what does the scheduler do?
assigns a priority to each process
levels of clasificatin
real time
high
above normal
normal
below normal
idle
goes highest priority down.
when a trhead is created within a process, the thread gets the default for that process
once the processes have their priorities, it then assigns priorities on every thread
time critical
highest
above normal
normal
below normal
idle
based on the two priorities it creates a number value for the priority .. goes from 31 to 0
goes down the table to run the threads
four different levels of the threads .. 31 to 16 .. maintained by the os .. they need higher priority
user threads are from 15 to 1
say a user creates a thread that defaults to 12 .. that tthreadcan get boosted or lovwer but never boosted above 15 .. that's os threads
four different levels
realtime
user
at the zero level .. the zero thread
idle is -1
zero threads convert free pages into pages of zero
thread can either get boosted or lowered in priority
raised ..
i/o completes .. different for different i/o
released by semaphore (2 levels)
whichever window's in the foreground
quantum expires .. gets lowered by 1 level .. can go all the way down to zero
seems like its impossible to get to the bottom threads
if there's a certain thread hat exceeds a threashold, it gest to go to 15 and if it still doesn't complete its mission it goes back down to where it was
choose which trhead to run based on the chart .. not hte process
smart enough to schedule certain threads on certain processors
vista home 20ms
vista business 180ms
windows in the foreground have a longer quantum
.. you can change it manually
file placement for multimedia
large files
write once, read many
mostly sqeuntial
strict QoS
ingle disk
- cannot have jitter
- minimize disk seeking
keep files contiguous - but they're long!
but .. have video, audio, and subtitle tracks
suggestion
interleave video, audio, and text so that you dontt have to keep seeking to different areas
alternatives
disk block < frame size
one frame takes multiple blocks
frame index
frame contains video/audio/subtites
disk block > frame size
multiple frames fit in each disk blook
block index
block contains multiple frames of video/audio/text
<
1 frame per disk read
. double buffer .. one ahead in read
>
multiple frames per read
double buffer
one thing on screen start loading the next frame
then you make that one on the screen and load the next frame
larger disk blocks .. may have a circular buffer of sorts
7.7.3 near video on demand
- showings rather than watch it now
finite number of showings at a time ("this movie starts at 8, 8:30, and 9:00)
90 minute movie with three streams
8:00 ? Only 1 stream. contingous reading
8:30? next showing starts
8:30 showing must seek to beginng
9:00 .. next showing
lots of seeking
we can interleave the frams nto the file
multipe files
zipfs law
- 2nndd most popular movie 1/2 as demanded as first
3rd most popullar movie 1/3 as demanded as the first
1000 movies, top five 30% of the time
raids vs disk farms
disk farm : just abbunch of disks
stripe movies across multiple disks
stagger start frames to keep first disk from being over utilized
stripe by lbock
cable company does this alot
disk scheduling for multimedia ..
static vs dynamic
round .. 33.3 msec
advantage of multimedia .. predictabillty
static .. elevator algorithm .. just move accross the disk and get everyone
diagram 514
move right across .. hit 'em as you go.
but nothing's ever static
look at different frame rates -- different encoding qualities etc
placement on the disk and deadline
ou could do the scheduling in ourder, but what if you have a shorter deadline at the top floor of the bulidng .. but the those don't get hit
he recommends
the scan edf (earliest deadline first) algorithm
take jobs that have deadlines close together and hit them with the elevator
how many streams can we keep adding
varies by system performance .. and movie type .. war vs romance
clcuaate the requirements for a normal movie .. if it fits in , then do it
multiprocessor scheduling
-------------------------
542
what tasks
what do we have avialbe to use
processes with multiple threads and multiple cpus
scheduling single processes accross multiple cores
8-12
share a single queue
but the queue gets blocked ...
cpu affinity .. when a process is reopned .. it'll go back to the cpu if it can
affinity runs with two levels
1 .. each cpu has it's own list of processes that it can schdule to itself
2. alg to take care of scheduling on each cpu
space sharing
tries to schedule all threads of a ppocess into individual cores at the same time .. 8-14 .. can be a time waister
advantage .. don't have to worry about caches, etc
gang scheduling ..
threads switched out with rpocess?
runs on a speciffic timeslice ..
algorithms become more ifficient with many cores
exam: scheduled for 15th
deadlocking
memory management
senior presentations .. tuesday of wk 13 .. 3pm
==========(Note Break)==========>>
Wed 04/02/08
Chap 6 Deadlock
a set of processes is deadlocked if each is waiting for an event that only another process in the st can cause
nobodys moving .. somebody got what i need and i got what somebody needs
and it can be between several processes
deadlock: a set of processes is deadlocked if each process is waiting for an event that only another process in the set can cause
we'll be waiting for resources alothough its more general than that
a resource might be a printer or a cd or some kind of device .. not going to be memory .. memory is shareable .. but could be memory if we're after the same portion of memory
so were talking about if you gt the resource you own it
Coffman proved 4 conditions are necessary for deadlock
1. mutual exculsion ie, only one process at a time can use a resource
ownership .. the os .. processes don't grab resources they do back in dos days whe the os didn't care but now that you have more than one process, what a process does is ask for the resource .. open statement for a file .. the process doesn't opeh thr file, the os does .. the os assigns the file to that process .. so only one process per resource at a time.
so if you open a file for multiple readers, we're not talking about that situation here.
if you try to get at a resorce , you'll be blocked
you can set things that say "just nevermind then" but usually you want the file
2. hold and wait .. this condition says a process must be holding a resource and waiting for another one that's currently held by another process
3. no preemption .. nohthing can rip a resource away
4. circular waiting .. that means that we're involved in a chain that comes back to the start.
four indirectly implies 2 but we'll keep it separate
if dead then 4 conditions .. necessary
if 4 conditions then dead --- sufficient (so not necessarily sufficient)
if ! 4 conditions then not dead.
so if you're missing one of the four conditions then you know it won't deadlock
how do you handle deadlock?
hard to easy
A. prevention -- make sure one of te four conditions doesn't happen .. then deadlock can't happen. .. expensive and not easy to do .. usually built into the os
b. avoidance .. software oriented and less drastic .. what you do there is you avoid unsafe conditions ..need a way of monitoring the system .. if I give that resource, I am potentially in trouble .. instead of giving it to you right now, i'll put you to sleep and we'll wait until the situation is safe .. so not prevented but kind of a look ahead. avoidance .. means it might happen .. we guess that we're getting close to a circular wait .. so you get less work done that way
c. Detection --> it's already too late.. if you take away a resource .. caa you back the process out of the situation? but it's easier to not be guessing but rather detect that its happening .. but the problem is to recover is usually drastic.
D. Ignore the problem .. ostrich method .. deadlock won't happen to me
a mathematician would run out of the room .. an engineer says how often will it happen .. 1%? then screw it ..
depends on the system .. if it's a heart machine then please don't screw it
linux and unix use the ostrich approach alot
linux uses array .. fixed size and they fill .. when they , chances are they deadlock the system.
can deadlock linux, unix
detection:
(p) -> [R]
process requesting a resource
uses ordered pairs (P,R)
[S]-->(Q)
the resource S belongs to Q .. holding
example in book
the OS knows the graph
G wants U and it also owns V
B wants T, D wants T, but T is owned bby E, so they're blocked at this point
Do a depth first search from each node .. if a tree, then !dead locked
a cycle will indicate deadlock
start with R
[R,A,S and we're done so back up
R,A .. no other options, so backup
R
that's the end of that
so far so good
but we have to starrt at every node and go to every other place
B,T,E,V,G,U,D,S block
B,T,E,V,G,U,D,T ** cycle .. that's deadlock
system is deadlocked .. well not all of it just those from T to T.
the other processes may be locked but not particupating in the deadlock.
deadlock does not mean your system gets torn down .. but a set o f processes that gets blocked and will never finish by themselves.
how dd you detect ? see how's been there for along time .. could mean that you'r just starving that process.
probably don't want to do it too foten because it's time consuming .. but the mot often you'd do it if it really mattered would be granting a resource. but you shouldn't have granted it.
recovery:
so deadlock is happened .. whatcya going to do?
cann work with
1. process
2. resource
usually remove them or try to remove the resource from the process.. this inst pretty stuff.
one ofption .. destroy all the processes in deadlock
or you could kill a process and then check the deadlock. .. good, but which one are you going to pick?
no one good strategy
could also pick on a resource.
processes have resources and
rollback .. saved snapshot that you can roll back to safely
detection isn't recovery usally means not good results
Banking Alg for detection
multiple instances of each resource
there might be more than one printer, CD-ROM, etc
n = processes
m = types of resources
p = (p[1],p[2] .. p[n])
E = existing resources .. how many you have of each resource (e[1],e[2],e[m])
c = current allocation matrix
resource distribution among processes
row - all the resources a process uses
column - all the processes connected to a resource .. less than or equal to to the available resources
A matrix .. available matrix
[ A[1], A[2],
column plus A[2] should be E[2]
R matrix -- requested
R[1][1] R[1][2]
......
why bankers algorithm?
they may be asking for mor than they actually have .. banks do taat all the time .. they give you credit.
not every process can come in at the same time and get all the resources, but if you do it in an orderly fassion
maybe as it runs, the avail list gets bigger and we can do business
if something needs too much, then i'm deadlocked
example
E = (7,2,6)
printer, CD, Disk Drives
m = 3
at time T[0]
C
010
200
303
211
002
n=5
so column 1 better not be bigger than 7 .. can't have more than you've got on the ssytem
A = (0, 0, 0)
Requested
000
202
000
100
002
Finish
F P[1]
F P[2]
F P[3]
F P[4]
F p[5]
we could do P[2] asl long as it doesn't make a request. it might not be interested in the two printers it will want at this time
but we know it cant run to finish because there are not enough resources for him.
can anything run? if not, then deadlocked
so maybe P[2] is scheduled and then gets blocked
consider that they've all run up to the stage where they want someting
we look frr soeething that can run to finish
Run to finish?
P[1], P[3] .. why? they don't need anything more.
we can chose either one.
lets pick P[3]
when it finishes, avail becomes
(3,0,3)
so P[3] is not deadlocked
but the rest fo the system could be
so now everything can run .. we're doingg well .. not deadlocked
deadlock .. is it impossible to run?
...
no deadlock
so we let it run 'cuz it's not deadlocked
so i let P[3] run and it's multi tasking away and it makes a request for an additional disk drive
new request matrix
can run P[1], but the rest deadlock
those that have F's .. not finished .. are participating in deadlock
avoidance part .. giving that extra resource to P[3} was not a good thing to do. .. so you should hold off on that.
lab from 1-2pm .. meet at back door of pack
trains are going to have and need resources
==========(Note Break)==========>>
Tue 04/08/08
Deadlock
--------
ecessary conditions
1. circular wait
2. mutual exclusion
3. no preemptions .. once you have a resource, you can't have it taken away .. have to be finished with it
4. hold and wait .. every process that's particupating in the deadlock has a resource and it's waiting for a resource that anohter process has
1 and 4 go together
4 ways of handling deadlock (in order)
easy --> hardest
1. ignore the problem - how important ? how often will it happen?
2. detect it/ recovery - how ? remove processes, remove resources -- backing up to a condition before ... every time a photo cell was covered, the dection alg was run
3. avoid unsafe conditions4. prevention
with detection, we assumed that when a process request, it is granted the resource immediately
so when the train covered the photo cell and asked for the cell ahead, if it was available, it was given.
in reality, the os could decide whether granting this was safe or not and make the process wait if unsafe.
safe sequence of processescould all finish if granted all necessary resources
unsafe - some of the processes might not bet all the way to the end .. possible that they might get caught .. possible that deadlock could occur up the road. doesn't say you can execute however you want .. you could get caught .. 2d array that allowed us to execute the next process.
there is a way to execute to the end that's safe .. will it execute that way? we don't know .. so safe may turn into unsafe.
so the situation can change from a safe situation to an unsafe over time, so just because you're safe, doesn't mean you'll be safe forever
unsafe is a caution ..
so if we looked at all processes here
so you don't have to deadlock to be unsafe.
an example
suppose processes A, B, And C
//no good way to know max .. except if batch job -- Job control language (jcl)
P Has(t0) Max Needs
A 3 9 6
B 2 4 2
C 2 7 5
avl3
total of 10 printers
promise of 20
banker's algorithm (don't have a run on the bank!)
at this point the system is not deadlocked .. we have a way for them all to execute .. but there are ways for it to jam up if A asks for three more, for example
but if we try B first .. then we can get to then end.
but not deadlocked because there is a way that they all can finish
B goes first .. gets 2, if it runs to done, then it will release tohose resources and we'll have 5 in avail.
now we can schedule C to the end, adds another 2, so we'll havee7 and now a can run
so if there's a run on the resources, you could get into trouble
nice in theory, but how do you know max??
diekstra is full of crap
so that was safe and not deadlocked
but suppose at t[1], A has the cpu and it requests 1 of another resource .. needs 6, asking for 1. (not a pig)
then A will have four and needs 5 more
but now avail is 2.
B can go to then end and then we have 4 avail, but each of the other processes need 5
so, just because you ask for it, doesn't mean you get it
--> unsafe condition
might make A wait
block A and schedule B or C for awhile
B might release a resource.
yellow light condition .. look ahead on the track .. is somebody interested in the one after than. if somebody is, block to see if that person will take a side track instead of shooting up and budding heads.
train gets next resource and puts a yellow light on the one after. if he sees all yellow light, he should block
so if you're close to a tourn out , it waits for a train to make a turn out first -- it blocks you.
but if yo're headed towards each other anyway, they're going to deadlock
how to handle deadlock
----------------------
prevent deadlock from happening by building a protocal into the os. easiest way to do that is to pick on those 4 coniditions
Make sure that one of the 4 necessary conditions cannot happen
read about it.
if you allow preemeion , doesn't that cause problems allot -- if you could just rip a printer away from a process.
.. spoolers are the answer
and then the spooler owns the device
but they might fill the sppool and get deadlocked there.
can talk about prevention but usually not a good thing to be doing that in the OS
hold and wait -- if you want something, you gotta put everything back in the pool and then see if you can get what you need -- but you can't put the printer back if you're in the middle.
circular wait seems to have promise ..
everybody gets an id --1,2,3 .. printer #1 , disk drive #2
everybody (resource) has a number .. and a process can only request resources i increasing order of the ID number. otherwise, it has to let go first.
then every process is only being granted resources i increasing order.
.. won't have a circular way because you wont want something smaller than what i have.
exam review on G:
pipes
unnamed pipes - parent and child
pipe();
fork();
parent has read end and write end.
child inerhits that
essentially are bidirectional .. child and parent can read and write from pipe. but very inconvenient .. hard to multitask.
pipe is actually a buffer in shared memory.
no pipe code. questions bout setup .. usually used with children, so know what forking a child means.
schedulers
short term
long term
medium term
know how they work and the queues involved, types of jobs
-- essay question/
when is the short term scheduler called into action? short term feeds the cpu.
long term scheduler tends to run highly intensive i/o jobs .. they're more batch jobs.
OS could know much more about the resource needs of the long term jobs .. tend to run the same way each time.
medium term scheduler .. throttling down on memory usage .. if weehave too many oprocesses in memory/read queue and the systee is starting to thrash .. just overloaded .. so swapping a process out for awhile and bringing it back in.
.. different than paging .. can use swapped out to disk.
our topics -- question in review .. pick one of the talks that we did not do and describe the scheduling in there. describe it weel enough that he knows that you know, but not a disertation .. page too long
signals - know what the are, what are the actions that you can take when signaled?
dft
ign
custom handler
can change these dynamically.
SIGALRM set by alarm(n); where n is in seconds.
know what setenv() and longjump() .. know purpose and usage. .. allow you to come out of a funciion without the return statement. .. come out of a stack and not have to pop the values off.
cant catch a signal while you're handling that signal.
execlp() .. execute a command in the same space as the calling process. see inotes.
cmd line arguments
argc, argv[]
ls -a -l
argc = 3
ls
-a
-l
and the system has put \0's at the end of the strings.
pointers to where they start.
sigfill, setaction -- don't have to remember that.
if you do have a handler, show it someplace!
deadlock
--------
racing
blocked vs dead
4 necessary conditions
4 ways to handle
CCR example
.. apply these using CCR example
four questions with parts
==========(Note Break)==========>>
Tue 04/15/08
sockets
-------
can offload the work to another computer
in order to do that, we'll use network protocal and assume a lot
two kinds of network TCP (tream communication) treat things like a file .. write and read
another form is with datagrams .. you basically package things in packets and send them out .. faster .. but you're not guarrenteed that you're gonna get it.
communication of info
client/server
server process
client process
client contacts the server and tries to connect and the server would be listening for connections .. so blocked and waiting for contact.
listening founction
when the conttact is made, then the server will go into action
often info/data servers
may be a database involved. client gotten from databae and sent to client
client consumes it
so consumer/producer in a sense.
if this were a web server, then it's serving out web pages if this is the server at harley davidson when the springsteen tickets go for sale .. would clog up pretty quickly
so if a second client comes in, we get blocked at the listening queue .. posix says you can have up to five waiting.
most srvers aren't designed this way.
HOw about handling several clients ?
unix is based on the client server model .. so internal , you on't need the internat to work with client server .. several servers that run just booting unix.
could have the server listen and when a client comes in, it would accept the client and fork off a child process and have a private conversation with the client.
and the listening server doesn't do much .. just loops and listens.
sockets are two way pipes .. two one-directional pipes duck taped together
sometimes the server swans off another thread for receving and one for sending
that way you can talk over each other
unix is built on this model (client/server).
login server
these servers are called daemons .. stays slient and sleeps until a client requests service
and then it waes up and handles the clients
usually there's no tty (terminal) associated with them
so if you launch one of these, you need to alunch them in the background with nohup
so simpbiff was kinda a daemon .. but it was timer based.
login is a daemon .. will respond when we connect and log me in
telnet is a daemon .. stayls sleeping .. awoken when contacted and basically is a walkie-talkie .. a shell is associated with this .. will spawn off a shell and execute the answer
you are sitting at a client .. you basically contact the server with say "ls -l" .. the client could be on the same machine or another.
in our labs , the server is compsci , we're on a pc
takes output and puts it back in the socket
takes stdin and what comes back goes on stdout
telnet makes my PC a dumb terminal
PC cpu wasted .. we're just doing I/O
init .. looks for zombies
ftp- sends info back and forth.
http - web server
cron - schedule something to run
snc.edu
domain .. names for numbers
once you get to us, we can then name other hosts
compsci 138.74.x.x
pankdc
ip addresses .. they uniquely identify the host on the internet
anything on the internet has an ip
all lab computers, printers.
cof112.snc.edu
name server
ip is unique world wide
so I can get to server that's running http on compsci.
but there are multiple servers on the host.
so how to we talk to one server
need to identify a server .. can't use the pid because every reboot gets it a different pid .. so need
host (ip)
where you're going
id for the server (port)
can think of it as a pointer to the server
telnet 23
a function called a bind will take the number and associate it with the program running
ssh 22
ftp 20 for connection 21 for data
nobody decided the right ports -- the internet came out of universities .. they just asked each other which number they should use
there is no standard written down on that's how to di it.
80 http
stay away from numbers under 1000 because they may be used.
capitalizer
3900
telnet .. usually has some handshaking, but DCPs program does not
what makes a connection unique are the two endpoints.
client and server
dcp.snc.edu
client1
-----------
doorpi.net
client2
between the two is the internet .. we're both going to go to compsci.snc.edu
port 80.
you issue a connect dcp.snc.edu, any port
every program to get out on the internet has what computer and the port number.
listening on 80.
when compsci gets a request, it forks off a child.
doorpi.net, any port connects to compsci on port 80 and it forks off another cild.
now both the children are the same, but the other endpoints make it unique
can we connect twice on the same machine? sure .. same computer, but different port. any port but the first one we connect with.
OS is smart enough to pick a different port.
can use the same port number if it's different computers.
netstat -an .. server info.
watch netstat to see if a process has been cleaned up .. so we can connect again.
compsci.snc.edu .. how to make a boot disk
fuji.snc.edu
pc
mac.snc.edu
mac
write a client and server and try to connect to the other person's
these linux boxes mount compsci home area
can't compile on the linux box and then run on compsci
==========(Note Break)==========>>
Wed 04/16/08
go to presentatin and tell what it has to do with operating systems
memory management:
processes sharing thh cpu
- increases utilization we sawy taat with the dac lab
soething waits for i/o, its good to schedule something else to keep the cpu busy
- possible (pswitch)
- scheduling
- problems and issues with sharing resources . racing conditions, the dreaded dead lock, and starvation.
- memory management issues
from 225, i stressed that processes in the ready queue must be in primary memory at least most of the time
the thing is that memory then is a resource
execept that memory is just one contigous 1d array and so must be shared
only one that really needs to be shared .. more than one prcess needs to be in meory at the same time or we can't do multitasking nicely
so ere's where the memor manager comes in -- needs to protect the memory asssgned to a process from other processes .. and that's not easy
a lllk about here is similar to cs220 .. file and dat structures where you tak about disk and how you protect fiels on disk form interfering with each other.
so id like to set the stage today
so cpu executes instruciions and basically it is very intimate (sleeps with) memory)
here's the cs225 part,
0) handle interrupt
1) fetch instruction
2) decode instruction and compute memory addresses
3) fetch data
4) bump the program counter
5) execute
6) store result
7) goto zero
can't do a p-switch on steps 1-6 .. zero is a hardware pswitch
now we say that for its own sake but where do you fectch the sntruction foom .. form memory
decoe - in cpu but addresses are in memory
step 3 -- most ly from memory
pc++ says that memory is sequential and contiguous .. 1d array at elast virtually it seems that way so addresses start at zero and go 1,2,3,4, pc++
cpu lives in its world , memory lives in its world
there's a control line, address line, and a data line between the two. .. that's call a memory bus
5 is internal .. it doesn't use memory, it's inside itself
the cpu will communicte to the memory unit .. either read or write and an address
so memory is a passive resource .. that means: it sits there and something tells it what to do .. the cpu basically is using it
6 - into memory!
last semester we looked at addresses somewhat and we were looking at how an address was made .. there was a base register called the cs .. the start of hhis segment .. block of memory .. .. we're not interested in that this emester
we're inerested in wheree we go in memory
we're interested in the addresses
our interest .. where is the stuff --> Address
cpu thinks its a 1d array
compiler & linker .. assume that memory starts at zero
and it'll have commands in there .. might call a function
and that funcion might be further down .. so when it calls the function, it basically is jumping to 8.
but we know we're not actually at 0 in actual memory.
0 is occupied by another program ...
but it finds that adddress 100 is available and there's enough room from there on that the whole program fits.
so the loader (part of the OS) is going to have to take the comiler stuff and renumer all the addresses
numbering --> base number + compiler number
so compilers think of memroy as the cpu thinks of memory
writing a memory manager
- partition memory
- fixed partition
memory
------
| |12k
----
| | 6k
----
| | 2k
----
| | kernal
----
so if you have a process that's 10k, then the 12k area would have to have it.
system administrator makes the aprtitions
2k partitions make sense when we have a lot of processes that are tiny
potential of internal fragmentation - wasted space
so if I had a 10k process, I'd have a 2k internal fragmentation
extternal fragmentation - partitions that you're not using.
so, how do you feed something like this?
you might have 3 queues
Q[12] [8k|11k|7k]
Q [6] queue for the 6k
like grocery store lines
what if we do one queue
so what are some issues here?
the next person in line comes oup and he'll go in the 12k slot
where does the 1k program go? in 6k or 2k?
we should probably do a best fit kind of thing
bigger processes will block smaller processes that could have snuck in the smaller partitions
so fixed partions are easy but the multitasking slows down.
job swapping
------------
uses the disk .. kinda like the medium term scheduler -- it is.
you are taking a lot of time, mr process .. you're i/o bound . you're taking memory and I could be scheduling other processes and you're in memory but blocked
what you could do is swap it out to disk and scheudle something in its place.
swapped out .. when you're brought back in, you might not be put in the same memory location .. the quickest way is to save the bytes -- if you do that, you'll want to bring it back to the same partition because of the addresses
and you'll want to protect that area on the disk so that ttravis doesn't monkey around with it
a job can request more money when it's running
if you've put a process in that doesn't take the full pprtituion, you have exttra .. otherwise, there has to be an area -- a heap .. doesn't work well with fixed partitions 'cuz if i'm given a pprtition for my heap and i don't want any, then we have external fragmentation etc.
so . so what.
so why not make them variable?
memory manager then will need mor ecpu time computing where all these things end up
but cpus are a lot faster .. let them do that
Variable partitions
-------------------
since the size of programs vary, and they gotta fit in he memroy, why makes the partitions fixed .. make them as big as they need to be.
and since you dontt have the same number of processes in memrry, then dont have a fixed number of places where they go.
but protecion becomes much more complicated.
//partition will have a base and a size .. how big it is.
even if i have variable partitum .. i need ___ and how big it is .. you caa find out how big the program is easily enough.
data int m; char a; ..etc
protection is an issue on variable partitions
.. so that you don't get outside your partition
Def: a hole is a continuous block of memory
so a proces comes in and finds an available hole
suppose k comes along and its a 5k process.
then B comes along .10k
C - also a 10k process
firstfit .. we woul puu it where A was .. first available.
c is a 3k, so I am occupied here and here and I siill have tow hole.s
compress the holes
what's wrong with this? tendency to get in he tiny holes .. maybe you need a bestfit .. find the bets fitting hole
the problem is that yo might find a 4 byte hole at some pont .. can't do anytiing with it.
coud also do worse fit. .. take the biggest hole and put it in there .. because then it'll leave a usefull hole.
we could start where we left off .
Tannenbaum says they're alll crappy, so bestfit is easiest on the cpu
Implimentation for the hole manager (READ IT!)
- bit map
- linked list
[C|3k]->[hole|4k]
need to be able to colapts into one hole
maybe you have one list for processees and one for holes.
maybe you double link them.
so the fragmentation is what kills you
so what oses like linux and windows use
thye compromize between fixed and variable
what they'll do is that they'l devide memory into chuncks -- clusters .. small enough but fied size, so if I have a program that's like yay big, it would take say 3 clusters. .. can't allocate any less than a cluster
but if they're small enough, we're kinda getting the idea of variable partitions .. at least it s taking into acooutt that not all pocesses are created the same size.
so we have some waste .. some fragmentation
then next process can start in the 4th cluster
how big do yo make the cluster? ho much fragmentation you want
the bigger yo mmke them , then the more fragment, the smaller you make them, the more overhead.
why can't we fill those holes .. beecause the cpu has been designed to think of the program sequentiially -- assuming the addresses start at zero .. so we can't take part the code unless you have someting that remembers wherre the suuff is -- you need a table to look up where the actual stuff is becaae it isn't continuous
.. and that's what virtual memory is all about .. its all busted up if yo actually look at it
programs are bigger than memory -- so you can keep parts on disk .. until you need that part.
==========(Note Break)==========>>
Tue 04/22/08
memory management for multi-prog
ready q --> cpu
when the cpu does a fetch of an instruction, it fetches it from memory -- primary memory, not disk .. but a cache could be involved, but we don't care
so the ready q would need to be in primary memory, not disk .. 'cuz if you're ready to run, the scheduler outght to pick you out and give you the cpu .. which means you really ought to be there.
so you want lots of memory so you can do multitasking
many programs sharing memory
so the memory manager , part of the OS must assign and protect memory spaces, the places where it puts the processes
processa
---------
pprocess b
memory manager first of has to find an empty spot in memory for it (we didn't go there) but we talked about that .. find a spot and tht goes into the assignment part , has to remember where it is and has to protect one process from aonother so that they don't interfere with each other..
every time there's a memory access, which menas jumping to a function or changing an address, like with a goto, every time there's an if statement in there, the memory manager says "is that in bounds" .. and that's part of what protected mode means
question and answer
what else did we talk about with memory?
partiting memory .. why? how dd you put more than one thing in memory .. need to know where you put it base and how big is it (limit)
fixed partitions, the size isn't so hard .. a lot easier to do the prottection and find where there's a whole with this schemem, so we could write the memory manager for this.
if they're fixed, then you don't have to keep track of how much the process used, just say that i have a process here that's 750 address that it uses .. we can't put t in the 500 addresses spot but we can put it in the 1000 addresses block. ... internal fragmentation 750 into 1000 .. 250 mb of intenal fragmentation .. can't put a base there, so waisted.
problems -- could be too big for the partitions ..
or we want to run a lot of little ones
on a dedicted machine that might be in charge of a robot, you might be able to do that a lot easier than on a general purpose machine .. but you are constrained here -- almost too much
so we went to variable partitions
so now size needs to be monitored .. so where you started and how big is it neeeds to be maintained
and the concept of the hole manager
now we can put the bases anywhere and the size can be up to the size of memory .. so now, our manager is a little more complicated.
some uissue with this.. external fragmentation
can combine ajacent holes for one big hole. .. in your best interest
best way to
//what if: final .. throuhg processes at us and we come up with the issues.
best fit
worst fit - idea that you'll still have something useable when you put a process in a hole.
bitmap method
first we pick a size for a hole and make it small.
so, 8 equal sized partitions somewhat small in size.
each base must start at a hole
hunk of memory (hole) = cluster ..
compromize .. make them small enough so that we don't have a lot of internal fragmentation, but big enough to make it easier on the memory manager.
suppose A takes two clusters.
smaller cluster, the less internal fragmentaton but more boundries.
another process B and C at the top
we have some holes
how to maintain the holes ? maybe take a byte and use it as an index.
we used 1 byte to describe 8 clusters worth of memory.
cluster generally about 4k.
4096 addresses!
how do you find a hole here? shifts and rotates!
consecutive holes -- .. need three consective zeros .. and that algorithm is not efficient.
search algorithm is hard
can search for a 0 with shifts
but what about consecutive holes?
linux uses 4k as its cluster size .. windows has since windows 98 3.1's cluster size was a segment size
compaction
like defragmenting a hard drive
seggmentation
hardware solution -- cpu based .. uses segment reggisters
stack
data
code
in separate locations
-- relative addressing needed
so you'd have the segment register in the cpu that has the datasagment address stored .. needs to know where it put the data and the code.
stack pointer is another good place.
th3e cpu is in on this .. compiler needs to be in on it as well.
that's how architectures have gotten by solving the problem of segmentation .. but you still have areas where you'll get holes.
heap - can put that in a sagment, too
dlls can be put in a neutral segment so we can share it
some editors work that way .. get different local variables but the same code. .
but what if the code's too big ...
programmers write code for the cpu and assume thht all code, all data, and the stack is contiguous .. idea that instructions follow each other in memory .. to get to another place, you change the value of the porgram counter because it'll go tot he next instruction otherwise..
that's what makes this really hard .. if we don't have contiguous memory free, then we can't execute sequentially like that.
idea of virtual memory
we're not goin to change how the cpu runs -- starts at 0 and goes to some big number. but the memory manager plugs chuncks of code in holes. .. what chuncks? only those chucks you are currently using (cpu-ing)
we think we're executing 0 1,2,3 ..
memory manager has code in two places .. but the cpu has no clue that that happens .. so the request for the next line of code goes through the memory manager and remaps it
so virtually, i think my program is linear .. in reality, it's broken up. .. so the memory manager just got much more complex.
also has to do swaps when you run out of memory
but we can have huge programs now .. bigger than i have physical memory for.
goes under the premise that we're not going to use all of our code (or memory) at the same time)
so we don't want a bunch of jumping around.
modules that are seldom used.
so things execute modularly.
==========(Note Break)==========>>
Thu 04/24/08
virtual memory
classical - memory is a large 1d array
compilers assume that layout .. that things go sequentially
if 0 is instruction 1, then 1 is instruction 2
programmers think in terms of virtual memory
and the cpu executes virtual memorygrabs an instruction .. treats it all as right next to each other .. program counter .. almost every machine uses one .. years ago , embeded in the instruction was an address as to where you went next .. but that just got so bulky
we get no where if we go on this side and look at physical memory .. the whole conecpt of holes is that you're probably not goin to find one big enough to fit .. and you have more than onne program in memory . you probably don't have enough physical memory as ist is
so paging is the idea that you usually don't use it all at the same time
so all that we really need to keep in memory is wha we areeusing currently
usually in programming you program addresses next to each other .. loops are small
you might go to a funcion ..
so code and functin .. two chuncks of memory that you're actuall usuing
if we could just put those two chuchks that would be great
we need a converter to convert the way we think to whte way it actuaaly is
paging.
motherboard
- cpu
this assumes virtual addresses
memory banks
------------
.
.
mem controller
bus between cpu and memory banks
cpu talks in terms of a virtual address .. that hs to be converted somewhere.
the cnversion can take place in software or hardware .. more and more its a piece of firmware
the cpu will take an address and hand it to the memory manager and out will come a physical address
so when the memory unit gets it, it has no idea about what it is .. he just wants to know where, so the converter will be very helpful
we talked about keeping parts of the program out on disk .. and we'll have to bring them in eventually and sometimes swap what we are using out to make room
cool thing about this DMA (direct memory access) the disk controller has enough smarts that it can use the memroy buws without he cpu having to interfere
MMU - memory management unit
not just get a byte write a bit ..
physical memory divided into frames .. a chunck of addresses (cluster)
virtual memory is devided into pages - also a cluster
so we're not going to lead just an address into memroy .. we're goin to leoad a page at a time
so as long as we're grabbing we grab several byte
and in physical memory, we'll put that in a frame
now that's just a bunch of terms .. its in the oses best interest to make the frame size the same as the page size
so, best if the size of the frame matches size of page --> 2^x
suppose i take vritual memory and i have 32 addresses. we don't care if that's coee or data .. we're interested in working iwth addresses
i have 32 addresses. supose that a frame size is a page size is 4.
how many pages do we have? 8.
pages 0,1,2,3,4,5,6,7
addresses 0,1,2,3 .. up to 31
now lets look a physical memory .. it's 1/2 as big for our show today
frame numbers 0,1,2,3
and we can get four addresses in each frame
interested in a mapping
page 4 to frame 3
page 0 to frame 1
page 2 to frame 0
so how do you do the map? usually you use a cs110 technique .. a table or an array
oses love to do that ..
so there'd be a page table involved.
and how big is the page table?
where is this cluster mapped?
so the page number maps page numbers to frame number.
there'll be 8 areas in the page table.
let's index on page number.
and inside the table we'll put the frame number
so zero is mapped to 1, 1 isn't mapped . . .
the problem with is .. there's always numbers in memory
so if we say where's 5 mapped to .. we can read that and think its something
so we have another field with info .. presence or absense bit.
presence or absense field .. yeah it's in memory I can go there
virtual address goes to the page table and computes a physical address
5 bit virtual address
virtual address is a page number plus an offset
offset has four addresses per page -- so you'd need two bits for that
page number = virtual address divided by page size (four in our case)
11/4 = 2
offset = virtual address % page size = 3.
since it's base 2 .. 3 bits represent page and 2 reprsent offset .. together they're the address.
Physical address . 16 physical addresses so 2^4
do the same thing
frame number, offset
keep the offset the same -- 3rd one up is the 3rd one up on physical
so we scramble *chuncks* of memory
so 2 bits for frame number and 2 bits for offset
MMU takes a virtual address which has the page number and an offset
phsyical address
offset gets copied, page number goes through the page table .. that's a lookup.
cpu think's it at all but really at 3
word size in cpu determines the virtual memory
every process has it's own page table
that's a lot of virtual memory!
program
-------
virtual
x++ --> gcc --> inc [3]
virtual address = 3 = 0*4+3
--> page table --> out pops physical address = 1*4+3
physical address is at 7 .. so it goes to memroy cell 7 and fetches it in
so what it really does is it increments cell 7
but when it goes back to store it .. will it still be there
it would be good if you couldn't bust things up mid-cycle .. but it could happen.
the data might be gone .. it might have to go get it again and put it in a different address .. so nothing is messed up .. just slow.
move b into a.
mov a,b;
gcc
move [
virtual address is 9 .. 2*4+1
physical address = frame * 4 + offset
and to find the frame number you go through the apge table
really at address 1.
really going to move something into 1.
va --> 4*4+3
physcial 3*4+3 = 15
y++ -> imcrement 27
virtual address = 27 = 6*4+3.
physical addresss = frame *4 +3
o page 6 has a zero i the presence address bit .. well go get it!!
6 not in page table
so the os creates what's called a page fault.
the programer has just started using memory that she hasn't used before
you oould be so unlcuky that you have a loop that goes between pages
what would happen on a page fault .. we're going to trap to the OS
go to disk and grab page 6 .. that would be four addresses .. the whole page
call the decider .. where do you put it?
choose a frame .. 2 loooks available .. but that might be used by another process. chose a victim
let's pick frame 1. was that a good choice? we'll see
we want frame 1 to go .. we gotta swap it out because it was modified
how does the mmu know that it was modified? add another entry in the page table called modified .. will all start out zero
.. also called the dirty bit. .. so that might be something that we look at when choosing a victim
so then we'll mark the P/A bit in the page table for page 2 as absent
bring in page 6 and put at frame 0.
six gets mapped to zero and it's present
then we trap back (von trap?) and increment cell 3.
so please don't make me do that a lot .. that's the expensive part.
other things you might keep in the page table entry
all this sits in the mmu
every process that's running needs a page table
usually your word size is long enouhg that you have a few extra bits
frame number, present/absent, dirty, permissions (3 bits) - r w or x, reference bit . when chooinsg a victim for faulting .. aren't you kninda intersted in if you'll come back soon .. so you want some kind of a mechanism that says when i was last here or when i'll be there next but hhat's harder
so, page tables are big .. 2^32 = 4 gig
page size is around 2^12 - 4k
page table entries will be much smaller than 4 billion -- 2^32/2^12 = so that's "only" 1000000 -- 1000000 entries
where do we put that? you're in the page table all the time .. always need it..
paging is expensive .. some OSes let you turn virtual memory off .. but it won't be as convenient
==========(Note Break)==========>>
Tue 04/29/08
exams due monday
gone over at 2:15 exam time on wed.
Quiz
0. F/T A page table maps virtual memory addresses to physical addresses. True.
1. T/F it's best to keep the page table in memory. True
2. T/F every process has a unique pt.
3. T/F a page fault happens when the MMU can't find a reference page in physical memory.
4. T/F frame size determines internal fragementation. TRUE
5. T/F the dirty bit indicates the page is used often. FALSE
6. T/F the pt depends o the size of memory. buy more memory chips, page table increases. false -- you can just map more pages in mem at once
size is an issue. we also need fast lookup
can put page table in MMU processor -- fast lookup .. but slow p-switch
could keep page table in memory at all times and the mmu could have pointers to the page tables.
usually a combination of the two happens
if we have a 32 bit machine and the cpu indicates wwere in memory you want to fectch, then the most you can do is 2^32 different addresses.
.. 4 gig
the page table isn't quite that big .. it ponts to a frame .. and so a frame size .. a hunk of memory
and usually, most of today's pages are 2^12 addresses - 4096
so page table size = 2^20 or 1 million addresses
2^64/2^12 = 4500 trillion in ONE pt.
but you uslally don't use all that
usually reference a few pages in a program .. data, stack, code
theorum: many references to a few pages.
permissions with each of these entries
so if you don't map a page, then you can't use it even though it's not outside of your virtual page table.
levels -
32 bit virtual address
4206599 .. dec.
part of it is ppge number and part is offset.
let's have two levels
table 1 table 2 offset
10 10 12 bits.
Page table 1 can have 2^10 entries
and that page table has pointers and that ponts to the next page table.
so if page table 2 is also 10 bits, then we can pont to 1024 different page tables.
so table 1 just tells which page table to use
page table 2 -- offset in the second table.
second table has frame numbers, like what we talked about last thursday
we don't need them all at once
keep first page table in memory
but not the other tables
divided up ... some of them are not used at all.
this is all just for one process.
frame offset ponts to specific memory cell.
so this works for the many references to just a few pages theorum.
but we have 3 memory lookups for every instruction
so that deals with size
what about speed?
we may need four pages but only one page loaded .. if they're not kept in memory, they're in the swap space.
need fast lookup:
most OSes today use somthing called associative memory.
OR TLB (translation lookaside buffer)
in MMU (registers 8-64 of them)
inside mmu is a piece of hardware that contains pages .. entries from the page table.
has: page number, frame number, and dirty bit
when the cpu loooks at an address, it sees page table number and offset
hardware is setup so that it can look at any entry in parallel -- not a linear search and if it has a hit, it immediately has a frrame number and didn't look at page table at all.
offset is copied, frame number many come from the TLB.
used a lot .. not many of them but fits the theorum.
when is that built? on demand.
so if you're just starting out, it'll go load it out of the page table. if you referenced it onece, you're probably going to reference it again .. associative registers .. buffer.
this is a soft miss
a hard miss would be if it's not present at all in memory .. needs to do page fault.
can't get rid of the page table because this is so small, but in terms of speed, we put them in hardware registers.
one more on speed and size:page tables are large, so there's lots of pages. .. not as much physical memory or frames.
some installations work with a table of phsyical memory or frame table
.. one entry per frame, indexed by frame number.
stored we'll have the page number, present absent bit
search here is a pain.
so a solution to that is to use associative memory. so go there first and then if you don't get a hit, go to the frame table.
cpu gets a virtual address .. page number 5 and offset. loooking for a 5 .. sequential frame table search. so we find a five .. it'll come down and say well your physcial address is say 3 and copy offset.
two processes may each have their page 5 in there. so you need some way of saying who's the process, too.
is a linear search, butt the associative table can help.
could build a hash table of page numbers. . find all page 5's etc.
so a combination of those two are commonly used.
tlb fills fast .. have to knock out processes.
need more frames
who do you pick to get rid of?
reference defined but not mapped.
what do you do ? go out to disk, get that page, and put it into physical memory
do you get to pick a frame that some one else is using? maybe you don't get to.
at any rate, if they're all being used, somebody hast go . pick a frame to take over. how do you pick? need an algorithm to choose.
when you do pick one, say 3, you have to save what's in there if it's dirty
if not durty just load the new one, else save the frame first
page replacement algorithms .. strategies
look at the history .. stale pages make good victims .. not recently used.
old pages go first -- FIFO. - but old doesn't mean you're not going to use it again .. could be my menu manager.
not modified recently - less time in swapping it out.
optimal .. looks into the future -- page that isn't going to be used for a long time -- impossible to determine.
Least Recently Used is the best future predictor .. can't necessarily determine that easily .. need a counter and clock.
implement least recently used - could use timestamp or counter .. maybe we have a feild that we init to zero and a counter register that clicks on each memory access. and store current counter value with the page table entry accessed.
kinda expensive but not a clock .. finding the smallest .. expensive
Alg for LRU
build a square matrix rows and columns represent pages.
0 1 2 3
0
1
2
3
start with all zeros
if you reference page i , make its row 1's and its column zeros
the page with the smallest row value is the lru
1. show the alg fo r
0 1 2 1
2. how does the alg age pages.
3. why does a refereced page make it's entry 0?
why does it age itself? no one else can do it.
another technique
get yourself a register and zero it. have one per page. then use the reference bit
all do a shift right .. brings in the process that was used.
smallest number is the oldest.
flaw - you can only save so much history .. registers too small.
but you want something simple
==========(Note Break)==========>>
05/01/08
balady's anomaly
the theory is that if you give the program more frames, you would think the number of ppge faults would go down .. but he cameeup with an example that contradicts that .. actually went up
so it's not only how muhh memory you can assign but its your scheduling algorithm .. how you pick the victim
stack algorithms -
LRU algorithm .. idea that most rferences are to very few pages
gong to use two frames . memory's not too big here
frame size =8
int = 2,
instr = 4;
cpu = 16 bits - 2^16 virtual accresses
IP =800
stack ponter is at 1600
and the stack decreases because that's what we're used to.
going to call a functin with a reference argulemtn .. so it pushes thhe argument on to the stack 0
you gotta know that it uses the stack to call functions.
push ...
page table
present abset bit and a modifieed but and a clean builds.
two frames .. 0 and 1
reference string
- pages in memory ... we can only have two considereing we have two frames
MMU -
in charnge of addresses .. so we start executing code .. and it fetches a questoion foom memory
fetch --- VA 800
in there's there 's an imcrement ...
look up in the page table where to go
and where to we go? well where's 100 .. hat's mapped to ...
put it in frame .. say yzero . say that the perons's precedent
data is zero .. page zero and offset zero
not there .. absent .. so we do a page fauolt .
go get it, map it to zero
you already have soethig there .. you cul get rid of that bbut yo don't want to.
so probably map it to 1
so wehn we execute , the modified bit goes to 10 .. becomes dirty.)
supposed to increment ceel 32
-----
push zero .. at 084 = 8*100 +4
so we're on page 1000 yet but fort down. each of the inntrucins take
next referencde is at 100 again, but do we have to trapp.
stack algorithm
page 100 in memory .. don't have to do anyiing .. no page fault;
push 0; does not need you to go to 333 for this program tongiht
808 = PUSL (push
sp = 16,000 = 8*200+0
soo i neeed page 200
so I go looking for page 200 and of course that's not mapped .. so i need to go get it and load it into a frame
so 2000 is gong to cause a page fault.
out goes the least recently used.
so new page comes in .. with stack.
page zero gets pushed out
and 200 will get mapped to frame number 1 .. so that's where my stack is
the push pushed a zero onto the stack.
note: because M=1 .. frame 1 goes to disk.
pikced page 100 to go on its way out
was 100 modified? not .. ss frame zero is goin to get replaced ..
101 had a zero .. now it's frame 0.
sp 1598 = 8*199+6
don't have it .. ppge fault
a lot going on .. eveery time youaccess memory, you have to go trough all this.
more time consuming when it's durty
you can see taat funciion calls might take you to a different page just because they're jumps and when you come back foom them, yo're typically coming back to the page where you did the jump .. what would be infortionate is if the jump ois at the end of the page.
2. the stack .. we typically don't like programs where we use the stack implicitly .. but we rite a lot of fumctions
the heap is expensive .. not always on the page.
reference arguments can be expensive in terms of virtual memory .. often on a different page.
you are slowing up by using paging .. tha'ts the point
most OSes you can turn paging off. so if efficency matters,
coming back from a functio is costly too .. invloves a return statement ..