Operating Systems ECS 150
Popular in Course
Popular in Engineering Computer Science
This 115 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 150 at University of California - Davis taught by Staff in Fall. Since its upload, it has received 28 views. For similar materials see /class/191705/ecs-150-university-of-california-davis in Engineering Computer Science at University of California - Davis.
Reviews for Operating Systems
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/08/15
ECS 150 Operating Systems Spring Quarter 2008 Classical Synchronization Problems Introduction This handout states three classical synchronization problems that are often used to compare language constructs that implement synchronization mechanisms and critical sections The ProducerConsumer Problem In this problem two processes one called the producer and the other called the consumer run concurrently and share a common buffer The producer generates items that it must pass to the consumer who is to consume them The producer passes items to the consumer through the buffer However the producer must be certain that it does not deposit an item into the buffer when the buffer is full and the consumer must not extract an item from an empty buffer The two processes also must not access the buffer at the same time for if the consumer tries to extract an item from the slot into which the producer is depositing an item the consumer might get only part of the item Any solution to this problem must ensure none of the above three events occur A practical example of this problem is electronic mail The process you use to send the mail must not insert the letter into a full mailbox otherwise the recipient will never see it similarly the recipient must not read a letter from an empty mailbox or he might obtain something meaningless but that looks like a letter Also the sender producer must not deposit a letter in the mailbox at the same time the recipient extracts a letter from the mailbox otherwise the state of the mailbox will be uncertain Because the buffer has a maximum size this problem is often called the bounded bu er problem A less common variant of it is the unbounded buffer problem which assumes the buffer is infinite This eliminates the problem of the producer having to worry about the buffer filling up but the other two concerns must be dealt with The ReadersWriters Problem In this problem a number of concurrent processes require access to some object such as a file Some processes extract information from the object and are called readers others change or insert information in the object and are called writers The Bernstein conditions state that man readers may access the ob39ect concurrently but if a writer is accessing the object no other processes readers or writers may access the object There are two possible policies for doing this 1 First Readers7Wr139ters Problem Readers have priority over writers that is unless a writer has permission to access the object any reader requesting access to the object will get it Note this may result in a writer waiting indefinitely to access the object Second Readers7Wrilers Problem Writers have priority over readers that is when a writer wishes to access the object only readers which have already obtained permission to access the object are allowed to complete their access any readers that request access after the writer has done so must wait until the writer is done Note this may result in readers waiting indefinitely to access the object N So there are two concerns first enforce the Bernstein conditions among the processes and secondly enforcing the appropriate policy of whether the readers or the writers have priority A typical example of this occurs with databases when several processes are accessing data some will want only to read the data others to change it The database must implement some mechanism that solves the readersiwriters problem The Dining Philosophers Problem In this problem five philosophers sit around a circular table eating spaghetti and thinking In front of each philosopher is a plate and to the left of each plate is a fork so there are five forks one to the ri ht and one to the left of each philosopher39s plate see the figure When a philosopher wishes to eat he picks up the forks to the right and to the left of his plate When done he puts both forks back on the table The problem is to ensure that no philosopher will be allowed to starve because he cannot ever pick up both forks There are two issues here first deadlock where each philosopher picks up one fork so none can get the second must never occur and second no set of philosophers should be able to act to prevent another philosopher from ever eating A solution must prevent both Version of April 17 2008 at 946 PM Page 1 0x0 4 O ampO rem 1 m mung Pmnmpm s 1m vemuf ym n mm mm sz ECS 150 Operating Systems Input and Output input and Output Goal To learn how input and output are done and how the medium being used affects the operations Spring Quarter 2008 1 ECS 150 Operating Systems Input and Output KernelLevel O Routines Moving data to or from secondary storage is done by kernel routiness called device drivers Each device driver is associated with one type of device and all processes access the same set of device drivers by making appropriate system calls This leads to the issue of how the processes view devices the most basic issue is transparency the processes don39t care about the manufacturer the model of the device and in some cases the type of the device ie whether it is a printer tape drive or another process example virtual devices these are devices simulated by the kernel with data kept either in the main store or elsewhere for example IBM39s VMCMS partitions the real disks into much smaller minidisks and stores data on those example a printing spooler system the program may think it is talking to a printer but in reality it is writing the data to a disk from which it will be sent to the printer We shall examine the issues involved in several steps 1 goals what should a good processdevice interface do 2 device hardware what does a device look like 3 device interface how are the devices connected to the computer 4 device drivers what do the kernel modules interacting with devices look like 5 process interface how do the processes access devices Goals of KernelLevel 0 Routines 1 Character code independence The kernel lO subsystem must translate character codes from various different devices to a uniform internal representation this is done by the kernel just after the characters arrive in memory and before they are passed to the process so that the programmer need not worry about it 0 internal codes may be ASCII EBCDIC UNICODE or something else Device Independence The process should not depend on one particular device the operating system should be free to assign any device of the right type as appropriate ie the process should not need to say lpO to get printer number 0 but should be able to say lp and let the kernel select the printer 0 It is very desireable that as far as possible programs should be independent of the type of the device ie it should not matter if input is taken from a tape a disk or a card reader 2 V Spring Quarter 2008 2 ECS 150 Operating Systems Input and Output 3 Efficiency lO operations are often a bottleneck this should be minimized 4 Uniform treatment of devices The intent is to keep device handling simple and errorfree but it may be difficult in practice to handle all devices alike Spring Quarter 2008 3 ECS 150 Operating Systems Input and Output Device Hardware Disks Disks are collected in a pack like stacked phonograph records head platter track ring sector portion top View of of track platter A cylinderis the same track on all disks in the pack think of chopping out one track on each of the platters by cutting straight down and you39ll see where the name comes from It is relevant because the arm moves all the heads over the tracks with the same number in the different platters Characteristics are data transfer rate 2 megabitssec data is transferred in blocks with between 256 and 4096 bytes typically data is always transferred in multiples of a block 0 the platters spin at 60 rotations per second 0 each platter typically has 1000 tracks 0 each track typically has 30 sectors Floppies consist of one removable platter and rotate more slowly than larger disks A sector contains 0 data 0 a bit indicating whether or not the sector is usable 0 error checking information 0 possibly the sector number A cylinderis simply the set of tracks with the same track number on all platters The operating system needs to know how the disk is formatted 0 the number of sectors per track 0 the number of bytes per sector The operating system may do formatting when the disk brought into service it can also discover bad sectors and mark them as unusable To read data the operating system first seeks for the data by positioning the disk arm on the track on which the data sits typically takes 2040 ms Hence there are three latencies delays relevant Spring Quarter 2008 4 ECS 150 Operating Systems Input and Output seek latency how long does it take the heads to get to the desired cylinder rotational latency once the heads are over the right track how long does it take the right sector to rotate under the heads transfer latency once the heads are over the right sector how long does it take to transfer data to or from the disk 1 2 VV 3 V Drums A drum is a cylinder divided into circular tracks it is just like a disk except that there is one head per track so the heads don39t move this eliminates seek latency When drums are used it is typically for swap space or as a backing store nowadays disks or banks of memory chips are used instead Magnetic tapes Magnetic tapes are used for archiving data transferring data between computers and for intermediate storage of large amounts of data They are usually m portable between different operating systems and machine architectures Some relevant characteristics there are 9 regions across the width of the tape hence the term ninetrack tape one bit is stored per region so you can store 8 bits for the character and l parity bit This is called a frame Tape density is the number of frames per inch usually 1600 or 6350 frames per inch Density is the same throughout the tape Frames are grouped into records and records are grouped into files interfile gap 7 4 file gt 1 a record record record record 7 m m interrecord gap Records may be of any size and successive records may have different lengths so when the tape is being reading there must be enough room in the buffer to hold entire records Note you can only write at the end of a tape safely because the inter record gaps are not of reproducible size So writing in the middle of the 01 Spring Quarter 2008 ECS 150 Operating Systems Input and Output tape overwrites a record followed by an interrecord gap the latter of which may overwrite part of the next record Tapes usually contain a label which is an initial record containing information that describes the tape39s contents its owner its serial number etc Similarly headers and trailers may surround files To read data the operating system first seeks for the data by winding the tape So there are two latencies delays relevant l Winding latency how long does it take to wind the tape to the desired place 2 transfer latency once the heads are over the right sector how long does it take to transfer data to or from the disk The times here are comparable to those of disks 2 megabits per second Communications lines There are three types of lines simpeXIines transmit data in only one direction halfduplex lines can transmit data in either direction but only one direction at a time and duplex lines can transmit data in both direcitons simultaneously Some relevant characteristics baudis the number of electrical transitions per second on the line which is usually but not always equivalent to bits per second typical baud rates are 0 for a terminal line 110300 1200 2400 4800 9600 19200 0 for a leased line computer to computer 56000 ASCII character codes take 7 or 8 bits the remaining 2 or 3 bits are used as parity checks and to synchronize the sender and receiver All conversing parties must agree on conventions called protocols for formatting information interpreting messages etc For synchronous transmissions the sender and receiver share a common clock and know when to sample the wire for transmission 0 Each transmission will be preceded by a header containing a prearranged pattern of bits which enables the receiver to adjust its clock to match that of the sender 0 Transmissions are split into frames each of which is preceded by a header 0 The header pattern cannot appear in the message so 0 if the transmission is bitoriented put an extra bit in this bit will be stripped when the message is read called buit stuf ng 0 if the transmission must have multiples of some byte size the transmission is characteroriented so stuff a byte called the escape character instead of a bit As an example the BISYNC protocol sends messages with the following format Spring Quarter 2008 6 ECS 150 Operating Systems Input and Output ltSYNgtltSYNgtltSOHgtheaderltSTXgtteXtltETXgtCheCksum The escape character is ltDLEgt hence if the character ltETXgt appears in the text it must be escaped by sending ltDLEgtltETXgt or else the receiver will mistake it for the end of the text and become confused when it interprets text as the checksum Spring Quarter 2008 7 ECS 150 Operating Systems Input and Output Device Interface The device interface is the lowest level of interaction between the machine and the lO device the device driver sits directly above it The interface mechanism is the device registers which are used for 0 transferring status information from the device to the CPU 0 transferring instructions from the CPU to the device 0 transferring data from the device to the CPU 0 transferring data from the CPU to the device Review the PDPl l polling and interruptdriven lO schemes quickly Complex devices are usually connected to a controller and the controller to the CPU The controller monitors the device status knows the format of the medium etc and accepts orders from the CPU as well as accepting or returning data Channels are subsidiary CPU39s that use a different machine language the instructions are commands and sequences of commands are channel programs which usually are stored in the main store as used by the CPU They typically use DMA Command chaining is the ability to send or take channel programs containing more than one command The term data chaining also called scattergather is the ability to gather output data from or scatter input data to many places A selector channel manages many devices of which only one may transfer data at a time A multiplier channemanages many devices all of which may transfer data simultaneously Spring Quarter 2008 8 ECS 150 Operating Systems Input and Output Device Drivers These serve three functions 0 they try to put a regular structure on those parts of the operating system that interact with devices they provide a standard interface to the rest of the kernel they serve the rest of the operating system and the device Think of a device driver as having two parts the lower part deals with the device itself and the upper part with the rest of the operating system 0 The upper part accepts requests from the operating system eg the storage manager asks it to write out a page to backing store this part then transforms these requests into entries in a pending work list for the lower part 0 The lower part wakes up when there is an interrupt or when new work is added to the pending work list When awakened it disables other interrupts from the same device Example Clock device driver There are two types of clock devices 1 1 line clocc generates an interrupt every tick E or a second 0 It may have a register that counts ticks since the last reset 0 It has a backup battery to handle shortterm power failures 0 It may have a register counting ticks missed if interrupts are not serviced by the CPU for priority reasons programmable clocc 0 a count register can be set by software 0 subtract 1 from the register per time interval say ms or tick 0 when the count register contains 0 an interrupt occurs When an interrupt occurs the following steps are done i the system39s software time structure is incremented 2 if the clock is used for scheduling decrement the remaining time field of the current job is decremented and if 0 the scheduler is invoked 3 accounting is done 4 if there is no programmable clock decrement a counter for the next alarm if this counter is 0 any kernel routine waiting for an alarm is invoked 5 if the current process is being profiled figure out where it is by looking at the program counter and update the appropriate counter 6 return to interrupted process Example Disk device driver Spring Quarter 2008 9 ECS 150 Operating Systems Input and Output These must provide the illusion of a virtual disk that is a linear array of sectors to do this the sectors are numbered like elements of an array Thus sector s on track t in cylinder c is numbered a c x trackscylinder t x sectorstrack s so other parts of the kernel can write to sector number a rather than sector number c t s The other requirement is that the disk driver reduce the effect of the latencies inherent in accessing the disk this is typically done by l overlapping lO and computation 2 storing large objects in contiguous regions on the disk so once the first seek is done no more seeks are needed to write out the object and 3 ordering outstanding disk requests The last is particularly important Assume only one disk drive if there are more schedule them separately all lO requests are for single equalsized blocks the requested blocks are distributed randomly over the disk pack the disk drive has only i moveable arm with all heads on it the seek latency is linear in the number of tracks crossed this is not true if the disk controller uses replaces bad sectors with those in tracks at the end of the disk the disk controller does not introduce appreciable delays and read and write requests are identically fast Evaluation of policies involves considering 0 how long requests must wait as a function of load ie the frequency of requests measured in requests per second 0 the mean and variance of the waiting time for each request for example a low mean but high variance means some requests will take a long time There are several common policies the handout gives an example of how they work 1 First Come First Served FCFS no starvation of requests possible all eventually get serviced It has a fairly low variance but becomes saturated easily saturation occurs when the load becomes greater than the driver can handle so there are always requests waiting Problems 0 every request is likely to require a seek 0 for low loads it works fine but for high loads the latencies increase the mean of the waiting time appreciably Pickup this is FCFS but on the way to the track where the next request lies any queued requests lying on an intermediate track are serviced For high loads this decreases the mean waiting time a bit 2 V Spring Quarter 2008 10 ECS 150 Operating Systems Input and Output 3 Shortest Seek Time First SSF SSTFService the request lying on the closest track It saturates at the highest load of any of these policies Problems 0 Starvation is possible but means that the disk can39t keep up with disk requests which usually indicates other more severe problems specifically thrashing 0 The innermost and outermost tracks are discriminated against leading to a variance larger than that of FCFS SCAM the head moves from the outermost track to the innermost one then back out then back in servicing requests on the way This variant of SSF reduces the problem of discrimination against the outermost and innermost tracks thereby lowering the variance Problems 0 It is still subject to starvation NSTEP SCANE like SCAN but only requests waiting when the disk heads begin a sweep are serviced all others wait until the next sweep This prevents starvation and lowers the variance even further C SCAM This is like SCAN except in one direction only hence the name Circular SCAN in it the head moves from the outermost track to the innermost and then jumps back to the outermost track This variant of SCAN eliminates the problem of discrimination against the outermost and innermost tracks and provides more uniform waiting times In practice the last three are implemented by having the head move only as far as there are outstanding requests in each direction so if the first request is at track 7 the second at track 9 and the arm is moving outward the arm will stop at track 7 and then change direction rather than continue to the outermost track and reverse direction there These variants are called LOOK NStep LOOK and C LOOK respectively At very heavy loads it is useful to use a scheduling policy to minimize rotational latency called sector queueing This involves ordering requests for the same track so all such requests can be written in a minimum number of rotations of the disk In practice each sector has its own queue and requests for a given sector are put into the appropriate queue when that sector rotates under the head the first request in its queue is serviced It is most often used with fixedarm devices such as drums 4 V 5 V 6 V Spring Quarter 2008 l l ECS 150 Operating Systems Input and Output Process Interface Underlying this interface is the concept of a file this concept usually does not exist at the lower level Files provide the means for processes to interact with devices and in some cases data structures such as kernel memory or a sink devnullin NIX Given this metaphor the system needs one extra system call to handle actions that can39t fit into the metaphor such as changing speed on a terminal line System Cals open the le device descriptor opendevice name intent 0 the descriptor can then be used in other references to the file 0 this call may block until the device is ready or return an error code 0 this call also checks privileges close the le closedevice descriptor 0 the device driver does any needed cleanup eg rewind tape position the le pointer positiondevice descriptor where 0 position the readwrite pointer associated with the device in a certain way eg skip over records on a tape or move to the end of a file read the le readdevice descriptor memory address amount 0 this call transfers data from the device to memory 0 it reads at most amount and may read less write the le writedevice descriptor memory address amount 0 this call transfers data from memory to the device miscellaneous control commands controldevice descriptor code 0 this is the call for all actions not fitting into the metaphor and is used to do devicespecific things The read and write commands have two forms blocking and nonblocking 0 a blocking transfer is synchronous when the next statement executes the data has been transferred yo or from memory 0 a nonblocking transfer is asynchronous the transfer may or may not be complete when the next statement is executed To determine when the transfer completes one cal use polling or a virtual interrupt With the latter the process requests an interrupt from the kernel when the transfer is finished This requires the system call handledevice descriptor routine Spring Quarter 2008 13 ECS 152B Computer Networks Spring 2004 Highhghts prerequisites ECSISO and ECSISZA mum merfypuhave mt cumpleled thepra39equisltes make sure to follow up the newsgroup messages miclasmec 52b mdclassecs1 521311 mg ijects 3n Dem Aksoy umewurks 1m WWWcsucdaviseduNaksoycoursel52b Fmal W39VD zzmnnAEcs rsza Demet Aksu ms rsza Demzt Aksa Road Ma Highhghts p r Imrummun Book mr ewmks vu39v 7 Computer Networking A Tnpanwn Approach Featurinng I D xf f Inmm u Appirmuunmya by Jim Kurose and Keth Ross Addisoanesley ISBN 07201976997 gsWm 42002 ws Of ce Hours 39 MMquot 7 TuesdayThursday 1 3072 10 m classoffice m T rspggf mmm m m TA Mohit Gupta EWltmBb smugwmaw uwcmal cmmcmr swammum Late policy regrading requests etc on the web page ECSISZB Demet may ms rsza Demzt Aksay Road Map Computer Networks Interconnected collection of autonomous computers attached to a host system l mm mum mum m m Am Network Adapter Network Adapter ECSlSZE DemetAksu Ecsisza mimosa 2 Protocols Protocols 0 A protocol defines 0 Why use a protocol 7 the format and the order ofthe messages exchanged 7 the actions on receipttransmission ofa message 7 to provide a common language There are so many protocolsl n51 0 Rules quot l 7 must be unambiguous and followed exactly e gTCPIP 1P IntemetProtocol Network Adapter Network Adapter ECSlSZE DemetAksuy Ecsisza DemztAksay Brunch request Ecsisza Protocol Example URL request 39hello yes got panc akes t TCP 174 c onnection request connection reply get httpwww umd eduindex htrnl yum omin up soon not necexmnlytypxml Demet New The Protocol Stack IP Suite 4 layers OSI 7 layers Applic ation Presentation Layers Application Session Transport Transport Network Network Link Link Physical in HTTP FTP TCP UDP IPv4 IPv6 Old Saying Ifyou lmow what you are doing four layers 15 enough ifyou don t seven won thelp 05 15213 DemztAksa Ecsisza The Internet Protocol Stack transmit individual bits within the frame Demet Aksuy 05 15213 gun re The Internet Protocol Stack original messag IIIIII e Dem Aksay The Internet Protocol Stack source original m ssa e g IIIII destination e Demet Aksu Ecsisza 05 15213 The Internet Protocol Stack Protocol Data Units PDW e message segment damgmm ame DemztAksa Implementation a wme a wme mxxed network Inter zce card Protocol Layers Summary Simpli es implementation segmentationreassembly error control ow control multiplexing connection setup in different layers El Application Link HostA App li V I Link HosLB m Link router W Link router There also are some potential disadvantages uplicate functionality may need info in a nonadjacent layer e g timestamp Demet Aksuy ClientServer Model A typical network has two cornponen client and server 05 15213 lent ehent hustthatlmtlatesthe sessmn e 9 server host that glVES the re queste d sewn asksfura Web page browser e same hast ean he bath a llentand a server fortune applicanun email Dem Aksay Application Layer 7 are only one piece 7 de ne messages exchan ed n ax semantics and actions 7 user services are provided by lower layer protoc ols ECSISZE Demet New Application Layer Protocols 0 example application layer protocols 7 HTTP Hypertext Transfer Protocol 7 FTP File Transfer Protocol 7 SMTP Simple Mail Transfer Protocol 7 DNS Domain Name System 505 1523 Demzt Aksa http hypertext transfer protocol WWW s application layer protocol chem client requests receryes WWW F image audio clip etc browser 7 server in response to requests sends objec s eh server enemz browser Uses TOP rehabe transport layerprotoco nanosnamg etc on port 80 ECSISZE Demet may World Wide Web the HTTP protocol HTTP example Suppose user enters URL VWWV cs undavts Edumstru mndefault html Emam host name 1a nttp ctrenrrnrtrates TCP connectron to http server process at lb nttp senerat host WW WWW CS ucda w cs u davls edu Port80 W5 edu wartrng is default for http server for TCP connectron atport 80 accepts connectron notifies 2 nttp clrent sends http request client message contarnrng URL rnto TCP connectron socket 3 http server recerves request message forms response mess e contarnrngre uested me Object rnsaurannueraurt ntrnr 5 nttp cuent recerves response sends message into socket message contarnrng html le 4 http server closes TCP drsp lays html Connect Ecsrsza DemztAksay HTTP HTTP message format request Stack Protocol Data Units PDU gplicztion message 0 http request message Transport segment 39 quot quot method URL Version requesf quot5 GET somedirpage html HTTP1 0 frame GET POST Connection close HEAD ETC header User agent Mozilla40 r r I I lines Accept texthim Lmagegif imagejpeg b l gt desnmltw Accept language fr IIIIIIIIIIIII lllllllll 39em wage he feed Carriage return source line fee indicates end of message ECSlSZB DemetAksoy ECSlSZB DemetAksoy HTTP request message general format HTTP message format reply sTaTLIs line protocol re ee status code HTTP11 200 OK sTaTLIs phrase Connection close Date Thu 06 Apr 2000 120015 GMT header Server Apache130 Unix lines Last Modified sat 1 Apr 2000 062319 EM Content Length 5021 Content Type texthtml En fy bodw data data data data data reques re h rml file Status code examples 200 OK success header lines lami ix 1510qu U39 0 39 HTTP Version Not Supported ECSISZB Demet Aksoy Demet Aksoy Ec5152B HTTP response message general format request line ECSISZB DemetAksoy try it out http client side 1 Telnet to UCD WWW server Open TCP connection To port 80 default http server port of wwwcsucdavis Anything Typed n Sent To port 80 of wwwcsucdavis telnet www cs ucdavis edu 80 2 Type in a GET http request GET indexhtm1 HTTP10 Host wwwcsucdavisedu hi carriage refurn fwicz 3 Look at response message sent by http server in response to your minimal but complete request Ec5152B Demet Aksoy HTTP two versions 0 HTTP 10 RFC 1945 0 HTTP 11 RFC 2068 default server keeps the connection open for successive request persistent default server closes connection after each object nonpersistent ECSISZB DemetAksoy Authentication and Cookies HTTP is stateless ask for the same object twice server sends it twice Authentication to control access to server documents authorization typically name and password 7 client must present authorization in each request 0 send Authorization header line in every request 7 ifcorrect server accepts access 7 else server refuses access 401 Authorization Authorization send with each message Ec5152B Demet Aksoy Authentication Cookies Cookies RFC 2109 Saves m a le e g netscapdcuukies li Cookie send with Each message ECSISZE Demet New Conditional GET client w Goal don t send object if client has uptodate stored cached version client specify date of cached copy in http request Ifmodifiedsince ltdategt object not modified server response contains no object if cached copy uptodate39 RTE10 304 not Modified 50515213 Dem Aksa object modified Conditional Get 0 ask to receive only if current object Stale m nucmmnaegemmm m39rw 1 mun m nx Dale mu 6 mn 2m 2nn m Sexvex Mania13quot mum sm1 n ma ns23is m snz concenceme ceman data data data data data 5m Inuslxmunnldzaullmml mun usexeaqem mullsdquot Accept texthum magequ nemruneaesme sat A Iran 2m ls2119 nmn m m unmixed Dale nu n 1m 2m 2nn5 5m Sexvex Manna13quot 1me 1am enmy may ECSISZE Demet Aksuy Web Caches Proxy Server Goal satisfy client request without involving origin server user sets browser WWW accesses via web cache client sends all http Q m mey We server 2 w requests to web cache wequot as ea Me W e ifobjectnot atweb rpm cache web cache 9 requests ob Jed from ongm server en retums http response to sheet 19 chem 50515213 Dem Aksay Web Caches Proxy Server Goal satisfy client request without involving origin server When another client rather than contacting the origin server Ecsisza Demet Aksu Web Caches Proxy Server Cache acts as both client and server 39 What ifIfimodlfledi Since HTTP header Prox 7 Issue should cache take Q hr my risk and deliver cached MN 7 objectwithoutchecking ey me 6 s f n Typically cache is r a we s a h 4 installed by ISP we my 9 x Mm residential ISP chem 55 15213 Demzt Am Suggested Reading 0 KuroseRoss 7 Chapter 2 upto section 2 3 Section 2 9 Ecsisza Demet Aksuy ECS 150 Operating Systems File Systems F e Systems Goal To learn how files are represented both in memory and on the secondary storage devices Spring Quarter 1999 1 ECS 150 Operating Systems File Systems File Systems A file is a collection of data There are two aspects of it virtual this is how the user process sees the file physical this is how the file is represented to the hardware and operating system file39s name often reflects something about the file example in TOPS20 file names are nameext where ext is a three character extension describing the file bas for BASIC for for FORTRAN bli for BLISS obj for object exe for executable txt for text and so forth On UNIXTM and MINIX the last letter may designate something for example C source files end in and PASCAL source files in gt Spring Quarter 1999 2 ECS 150 Operating Systems File Systems Directories Files can be organized into directories foldersquot to the Mac to make organizing them easier A directory contains pairs of name location The location may be a physical location disk address or an index into an array containing those locations or any other datum used to locate files There are several main types of directory organizations in historical order they are a onelevel flat directory in which all files are in the same single directory no two files can have the same name so to keep users having to worry about collisions the system could make the user name a component of each file name to find a file one must search the whole directory hierarchical directories impose a tree structure on directories typically there is a master directory and then user directories for each user do absolute and relative path names current working name graphstructured directory systems are basically hierarchical systems but with the ability to alias files direct aliasing occurs when one file location appears twice or more in directories often with different names indirectaliasing occurs when a special type of file containing a path name is created it is said to be an indirect alias for the file it names When you refer to the indirect alias the operating system interpolates the name of the file being aHased issues naming there is no such thing as a quottruequot name now deletion If a file is deleted under one alias is it inaccessible using the other aliases yes must find all other aliases and delete them expensive no don39t delete file until all aliases deleted use a link count to track how many aliases a file has accounting usually the owner of a file pays for storage and other related charges but if another user aliases to the file the owner might no longer be able to delete all references to it solution have each person owning a link to the file ie owning a directory containing a link to the file pay a percentage of the cost of the file Spring Quarter 1999 3 ECS 150 Operating Systems File Systems Information kept in a directory or indicated by it is the name file type etc example UNIX handout note the difference between incore representation and representation of information on disk Spring Quarter 1999 4 E08 150 Operating Systems File Systems Access Control Typical protection modes are read write append delete privilege allows modification of others39 rights owner indicates owner of file and search grants permission to search directory example UNIX note difference in meaning of execute for files and directories implementation describe access lists abbreviation association of rights are privileges associated with a name or a file That is ifX is an alias for y can a user have read permission on X but not on y Spring Quarter 1999 5 ECS 150 Operating Systems File Systems Process View of File Processes operate on files using the following commands create find space for the file allocate it and make an entry in the directory open begin operations on a file close end operations on a file read transfer information from the file write transfer information to the file rewind move to the beginning or a random point in the file delete remove the file Spring Quarter 1999 6 ECS 150 Operating Systems File Systems Access Methods How can processes access files sequential one block after the other The process keeps track of a readwrite pointer part of the PCB indicating where the next action is to be done the pointer always advances direct the readwrite pointer can move freely mapped map the file into a virtual segment and return the segment number rather than the file descriptor then treat thr file as part of the process39 virtual store On closing just release the storage example TOPS20 MULTICS structured the file consists of a sequence of records often the operating system knows about the file type example ISAM Indexed Sequential Access Method In this a small master index points to blocks in a secondary index which in turn point to real file blocks Thus it takes at most 2 reads to locate any record Spring Quarter 1999 7 E08 150 Operating Systems File Systems Information in disk directorv file A disk directory is like a directory for a disk it describes what blocks are in use and which are free This means it must keep track of what blocks are not in use such a list is a free list Several representations a bit map with 1 bit per block a linked list of blocks like linked list but in each block of size n on the free list store n1 numbers of free blocks the nth is the address of the next block making up the list pairs of block number number of free blocks from that block on if there is more than one contiguous block free this usually saves same space The latter three are often called file maps because each free block is represented by 1 word pointer Spring Quarter 1999 8 ECS 150 Operating Systems File Systems Aquot quot of Disk Blocks to Files This is done in one of three ways contiguous allocation here blocks are allocated sequentially contiguously advantages minimal head motion for sequential reading of file problems need to find space for it using the usual algorithms firstfit bestfit Compaction is possible but usually requires copying almost everything on the disk how much space should be allocated for the file grow beyond its initial allocation there may be room to increase the allocation the program may be terminated in this case people tend to ask for as much room as possible wasting space the file may be moved elsewhere very slow Note that files may grow for years so even if you know the maximum size a file will ever get you may waste lots of space for a long time linked allocation the directory contains pointers to the first and last blocks of the file and the last n bytes of each block in the file point to the next block in the file advantages this scheme eliminates the need to know the size of files in advance again it is great for files accessed sequentially disadvantages it is poor for direct access files as the operating system must follow links to get to the desired block it wastes n bytes of disk space per block it is unreliable if 1 pointer is deleted or changed the file is garbled a doublylinked list which would ameliorate this uses more memory indexed allocation this scheme brings all pointers together into one block advantages compact and easy to reference blocks disadvantages wastes more space as an entire block is pointers rather than just 1 word per block so a 511 block file and a 2 block file use the same number of pointers It might Spring Quarter 1999 9 ECS 150 Operating Systems File Systems implementation issue If you need more than 1 index block link them together Or use indirection if you can have 256 pointersblock 2 levels of indirection allows 2562 65536 blocks example UNIX scheme the first 12 blocks of a file are data the 13th is an index block the 14th is a doublyindexed block ie it contains pointers to index blocks and the 15th is a triply indexed block ie it contains pointers to doublyindexed blocks Spring Quarter 1999 10 ECS 150 Operating Systems Process Scheduling Process Scheduiing Goal What characterizes a fair internal policy Which process is given the CPU next This is the province of schedulers ECS 150 Operating Systems Process Scheduling MILE Three kinds longterm scheduler determines which jobs are admitted to the system for processing example in a batch system often more jobs are submitted than can be done at once so some are spooled out to a mass storage device the longterm scheduler selects the next one to be loaded into memory So it controls the degree of multiprogramming ie the number of processes in memory shortterm scheduler determines which job in memory ie in the ready queue goes next mediumterm scheduler at times jobs may have to be removed from the system temporarily that is too many jobs may be competing for memory The removed process will be restarted where it left off later called swapping This scheduler decides who gets swapped out and in The long term scheduler is invoked relatively infrequently but the short term one is invoked often whenever any process returns control to the operating system Hence the shortterm scheduler must be m E Context switching also must be very fast typically lOus to lOOus Many machines have specialpurpose instructions like the VAX LDCTX for just this reason The system should try to balance CPUbound and lObound jobs ECS 150 Operating Systems Process Scheduling 5 I I These choose which process goes next Which one is used depends on what is wanted from the system possible measures are In throughput get the most work done in a given time turnaround complete jobs as soon as possible after submission response minimize the amount of time from submission to the first response called the response time this interval does not include the time to output the response resource use keep each type of resource assigned to some process as much as possible but avoid waiting too long for certain resources waiting time minimize the amount of time the process sits in the ready queue consistency treat processes with given characteristics in a predictable manner that doesn39t vary greatly over time the process of scheduling the processes being considered must be distinguished upon many parameters among them priority anticipated resource need including running time running time resources used so far interactivenoninteractive frequency of lO requests time spent waiting for service To demonstrate how algorithms work we39ll use this set of jobs Service Time 10 29 3 7 12 Arrival Time I39I39IUOWJgt wN O and measure 3 quantities turnaround time time the process is present in the system T finish time arrival time waiting time time the process is present and not running W T service time response ratio sometimes called the penalty ratio the factor by which the processing rate is reduced from the user39s point of view 4 R service time ECS 150 Operating Systems Process Scheduling I HI H H I decision mode This is nonpreemptive if a process runs until it blocks or completes at no time during its run will the operating system replace it with another job It is preemptive if the operating system can interrupt the currently running process to start another one priority function This is a mathematical function which assigns a priority to the process the process with the highest numerical priority goes next The function usually involves the service time so far a the real time spent in the system so far r and the total required service time t arbitration rule If two processes have the same priority this rule states how one of them is selected to run ECS 150 Operating Systems Process Scheduling II 5 I I I I I I First Come First Served FCFS decision mode nonpreemptive priority function pa r t r arbitration rule random service arrival start finish T W R time time A 10 0 0 10 10 0 10 B 29 1 10 39 38 9 13 C 3 2 39 42 40 37 133 D 7 3 42 49 46 39 66 E 12 4 49 61 57 45 48 mean 382 26 54 A potential problem is when a short job follows a long one service arrival start finish T W R time time A39 1000 0 0 1000 1000 0 10 B39 1 1 1000 1001 1000 999 10000 Gantt Chart 0 1O 39 42 49 61 A l B C D l E Basically long processes love FCFS but short ones seem to be much slower ECS 150 Operating Systems Process Scheduling Shortest Job Next SJN Shortest Job First SJF Shortest Process Next SPN As an estimate of the total service time neded is required this algorithm is usually used in batch systems decision mode nonpreemptive priority function pa r t t arbitration rule chronological or random service arrival start finish T W R time time A 10 O O 10 10 O 10 B 29 1 32 61 6O 31 21 C 3 2 1O 13 1 1 8 37 D 7 3 13 20 17 39 24 E 12 4 20 32 28 10 23 mean 252 176 23 Claim Shortest Job First gives the smallest average turnaround time T out of all nonpreemptive priority functions Proof Suppose n jobs arrive at the same time with t1 S t2 S S tn Then Tt1 t1 Tt2 t1 t2 hence the average turnaround time is Tav 2 it Now suppose ta and tb a lt b are swapped The new average turnaround time is I 1 TaV n nt1n 1t2 n a1tb n b1ta tn SO I l TaV Tav n n a1tb n b1ta n a1ta n b1tb and 1 T av TaV F b atbta Z 0 because b Za Impl I es tb Z ta Probem need to know service times into the future so you can run the process with the shortest next CPU burst How does the shortterm scheduler choose the next process to run It can use a number of different ways 0 Most accurate is to run all ready processes time the CPU bursts and then schedule them snicker 0 Characterize each process as CPUbound or lObound and specify for each an average service time needed based upon timing processes over a period of time and averaging Note that characteristics might ECS 150 Operating Systems Process Scheduling change over a period of time that is a process might be CPUbound for a time then lO bound then CPU bound etc 0 Compute the expected time of the next CPUburst as an exponential average of previous CPUbursts of the process Let tn be the length of the nth CPU burst and tn1 the expected length of the next burst then tn1 atn l39 1 39atn where a is a parameter indicating how much to count past history usually chosen aroundl a l the estimate is simply the length of the last CPU burst a O the estimate is the initial estimate holds burst length 0 l 2 3 4 5 6 7 8 6 4 6 4 l3 l3 l3 13 10 8 6 6 5 9 ll 12 13 Comparing exponential estimation with actual values al2 SPN is better than FCFS for short jobs but long jobs may have to wait for some time for service The longterm scheduler can simply use the job39s time limit as specified by the user this motivates users to be realistic in their limits as 0 limits too low job aborts with a time limit exceeded 0 limits too high the turnaround time may be very long ECS 150 Operating Systems Process Scheduling Shortest Remaining Time SRT Preemptive Shortest Process Next PSPN This is like SPN but preemptive decision mode preemptive at arrival priority function pa r t a t arbitration rule chronological or random service arrival start finish T W R time time A 10 0 012 2 20 20 10 20 B 29 1 32 61 6O 31 21 C 3 2 2 5 3 O 10 D 7 3 5 12 9 2 13 E 12 4 20 32 28 16 23 mean 24 1 1 8 1 74 Miscellaneous 0 Whenever a new job comes in check the remaining service time on the current job For all but the longest jobs SRT better than SJF The response ratio is good low Waiting time is also quite low for most processes ECS 150 Operating Systems Process Scheduling Highest Response Ratio Next HRRN HRN This tries to level out bias towards long or short jobs decision mode nonpreemptive priority function pa r t ac arbitration rule random or FIFO service arrival start finish T W R time time A 10 O O 10 20 1O 2 O B 29 1 32 61 6O 31 2 1 C 3 2 2 5 3 O 10 D 7 3 5 12 9 2 13 E 12 4 20 32 28 16 2 3 mean 252 13 2 3 Why Here are the response ratios as each process completes time A B C E lo 13 3 37 g 20 15 13 292212 14 771o 11229 8 24 20 295919 1 121216 23 32 2931 2 21 The ratio used is actually estimated service time waiting time so far estimated service time The idea behind this method is to get the mean response ratio low so if a job has a high response ratio it should be run at once to reduce the mean ECS 150 Operating Systems Process Scheduling Round Robin RR With Quantum q This is especially designed for time sharing the quantum is typically 6l O S q S 1 seconds decision mode preemptive at quantum priority function pa r t c arbitration rule cyclic In this example the quantum is 5 service arrival start finish T W R time time A 10 O 28 28 18 28 B 29 1 61 6O 31 21 C 3 2 13 1 1 8 37 D 7 3 35 32 25 46 E 12 4 47 43 31 35 mean 348 226 33 Why Here is what things look like time 0 5 1013 18 23 28 33 35 4O 45 47 52 57 61 procABCDEABDEBEBBB rem52402701902140940 here proc is the process starting at the indicated time and rem the remaining time after the quantum is complete 0 As each process is preempted it moves to the rear of the queue 0 All new arrivals come in at the rear of the queue 0 As q 00 0 every process thinks it is getting constant service from a processor that is slower in proportion to the number of competing processes this is called processor sharing This scheme is used in hardware in CDC66OO to implement 1O peripheral processors with one set of hardware ie processor and 10 sets of registers the processor does 1 instruction for one set of registers then goes on to the next set This turns out to be not much slower than a real processor Variants 0 Round Robin but adjust quantum periodically example after every process switch the quantum becomes qn where n is the number of processes in the ready list 0 few ready processes means that each gets a long quantum minimizing process switches 0 a lot of ready processes means that this algorithm gives more processes a shot at the CPU over a fixed period of time at the price of more process switching 0 processes needing a small amount of CPU time get a quantum fairly soon and hence may finish sooner 10 ECS 150 Operating Systems Process Scheduling 0 Round Robin but give the current process an extra quantum when a new process arrives This reduces process switching in proportion to the number of processes arriving ECS 150 Operating Systems Process Scheduling Multilevel Feedback Queues MLF MLFB With n different priority levels each of priority Tp Processes start out in the uppermost level After getting To units of CPU time it drops to the next lower level and after units of CPU time at that level it drops down again until it reaches the lowest level If it blocks or otherwise leaves the scheduling system and later returns it may reenter the feedback queues at another queue for example the top one decision mode preemptive at quantum priority function pa n i where i satisfies both 0 S i lt n and To2i 1S a lt To2il 1 assuming that Tp szo arbitration rule cyclic or chronological within queues In this example the quantum is 1 n 3 To 2 and TD 2PTo service arrival start finish T W R time time A 10 O 38 28 38 B 29 1 6O 31 21 C 3 2 11 8 37 D 7 3 27 20 39 E 12 4 4O 28 33 mean 352 233 34 This algorithm favors short processes by giving them more of the CPU It is also adaptive in that it responds to the changing behavior of the system it controls Variants 0 MLFB with round robin for all but the lowest level and thatr first come first serve but preemption possible of course service arrival start finish T W R time time A 10 O 25 15 25 B 29 1 49 20 25 C 3 2 11 8 14 D 7 3 50 43 12 E 12 4 57 45 13 mean 384 262 18 ECS 150 Operating Systems Process Scheduling E IE These adjust priority based on some external factors and are quite common when users pay based upon their computer use Examples round robin where the quantum is set independently for each process based on the external priority of process ie the more you pay the bigger the quantum Worst Serw39ce Next after each quantum compute a suffering function based on how long the process had to wait how many times it has been preempted how much the user is paying andor the amount of time and resources used The process with the greatest suffering gets the next quantum The user buys a response ratio guarantee the suffering function used takes into account the difference between the guaranteed response ratio and the actual response ratio at the moment Deadline Scheduling each process specifies how much service it needs and by what real time it must be finished The algorithm tries not to run jobs that cannot meet their deadline FairShare Scheduling allocate blocks of CPU time to a particular set of processes usually by splitting user processes into groups within each group use a standard schedule but allocate the CPU proportionately to each group example All processes are infinite loops 1 process in group i 2 in group 2 3 in group 3 and 4 in group 4 regular scheduler each process gets 10 fair share scheduler each group gets 25 processes in sgroup share equally example This uses UNIX internal not external priorities Here 3 processes process A in one group processes B and C in another group The internal priority function is recent CPU usage group CPU usage 2 2 threshhold with the threshold being 60 for user processes A decay function decrements the current CPU usage of processes not run this has the effect of raising their priority The function is CPU usage 2 priority decay of CPU usage example of the UNIX Fair Share Scheduler Here the quantum is 1 second Note that the higher the priority the lower the integer representing that priority ECS 150 Operating Systems A gt 0 Process Scheduling runs for 1 second decay applied to CPU and group CPU usage A39s new priority is 60 30 2 2 say B goes next runs for 1 second decay applied to CPU and group CPU usage A39s new priority is 60 E l5 30 90 and C39s 90 As B and C now have higher priority one of them 2 7 74 B39s new priority is 60 7 30 new priority is 60 7 75 A has the highest priority so it runs next runs for 1 second decay applied to CPU and group CPU usage A39s new priority is 60 3T7 377 96 B39s new priority is 60 74 and C39s 1 new priority is 60 75 67 C has the highest priority so it runs next runs for 1 second decay applied to CPU and group CPU usage A39s new priority is 60 E E 96 B39s new priority is 60 377 81 and CS 2 2 new prIorIty Is 60 2 2 93 A has the hIghest prIorIty so it runs next Hence the order of running is A B A C A B A C with A getting 50 of the CPU and B and C together getting 50 example VAXVMS scheduler This scheduler has 32 priority levels levels 31 to 16 are for realtime processes and levels 15 to O for regular processes Real time processes have fixed priority throughout their lifetime but the priority of regular processes is dynamic at process creation a base priority assigned this is the process39 minimum priority the current priority of the process is altered by a system events each of which has an associated increment ie terminal read increment gt terminal write increment gt disk lO When awakened due to a system event the appropriate increment is added to the current priority value on preemption due to quantum expiration the current priority drops by 1 14 ECS 150 Operating Systems Process Scheduling preemption preemption preemption current priority time Processes are dispatched by their current priority This scheme is like a MLFB scheme with two differences 0 processes need not start at the highest level and 0 quanta are associated with each process not level Oracle 9i XML DB and XDK nm Wong Database and Information Systems Group Department creompmer Science Universit of California Davis Overview of Oracle 9i XML DB XML Storage Options VARCHARZ unstructured limited size CLOBs unstructured max file 26B XMLType structured associate with XDK and other XML opera ions XML DB Architecture 1 XML DB Repository 2 DOM delity SQL Loader Oracle 9i XML DB Overview of Oracle 9i XML DB XML Schema Validation Manually or automatically validate XML documents as they are inserted tothe Database XML Piecewise Update Update pari oithe xml document in the database speci ed by the XPath expression XML Document Generation Generate XML data from database using normal SQL query XSLT transformation Transform the XML document returned by the queryto another output format or XML document with different structures Using XMLType Creating XM LType Column or table with optional XML Schema suppo create table profie 39 m er pfile XMLType lt Declares XMLType Column create table pro le of XMLType Declares XMLType Table create table pro le of XMLType XiVI C HEMA http llbumbusucdavisedulschoarxsdquot ELEMENT UCLEADS Declares XMLType Table conformed to an XML Sc ema and speci c the root element of the xml 39 rted document to be Inse Using XMLType Storing XML document into the database insert into prome lt lnsert the whole leL document in valuesuoo XML e39 5039 query lt5cholarPro legt gt1 ltlIDgt tNamegtWongltlLaslNamegt ltFirstNarnegtTImltlFIrstNamegt gu avisedultlEmailgt ltMajorgtcomputer Soienceltlmajorgt ltMinorgtltlMinorgt ltGradegtJuniorltlGradegt ltIScholalPro legt Insert the leL document using PLSaL Insert into pro le function vall Inl1 rm I Sample XML document ltUCLEADSgt ltScholarPro legt Dgt1ltIIDgt ltLastNamegtWongltlLastNamegt ltFirstNamegtTimltlFirstNamegt ltEmailgtthwongucdavisedultlEmailgt ltMajorgtComputerSciencelt 39 ltGradegtJuniorltlGradegt ltlScholaProfilegt megtGaunaltlLastNamegt lFirstNamegt unaucdavisedultlEmailgt ltMajorgtPlant BiologyltlMajorgt lt radegt un ltlScholaProfilegt ltIUCLEADSgt IONBra egt Using XPath with XMLType Accessing XML data stored as XMLType instance ExtractVaIue access the value of an XML node ExistsNode check if a particular node existed Exact xtract a collection of XML nudes XMLSequence converts a fragment of XML into a collection a table of llllLType instances Using extract SELECT extractivalueiX39UcLEADSScholarFro lelMajor39 FROM pro le X EXTRACTVALUEX 39UCLEADSISCHOLARPROFILEIMAJOR39 Results are returned as a frag ment of XML Using existsNode SELECT existsNodevalueOO IUCLEADSISChoIarMajor FROM Profile x SELECT counti FROM Pro le X an i DELETE FROM Pro le X l lllt l Div I existsNodeo returns 1 if the node is found Using extract extractvalue SELECT extractValueivalueiw39lMajor39 FROM pro le X TABLE xmlsequencei extractvalueix 39IUCLEADSISchoIarPro lelMajor39m w EXTRACTVALUEVALUEW39IMAJOR39 Values are extracted from the nodes of Mechanical Engineering the GVlLType table generated using the Mathematics GWLSequenceo Ph ics Environmental Toxicology Biochem39stry Biochem39cal Engineering Biochem39cal Engineering Additional XMLType Functions s33 XML Piecewise Update UPDATE pro let I manmm mm WHERE existsNodevalueit 39IUCLEADSScholarPro leMajorquotComputer Sciencequot39 1 39 ii I I 39 Ir 39 YM39 getClthali converts the XMLType document into CLOB object getRootElementi get the root element of the XML document me mm document XML Schema Support XML Schema has to be first registered using PLSQL package DBMSXMLSCHEMA Once the XML Schema is registered XML documents will be automatically validated against the schema insertion Manually validate an XMLType instance using XMLlsValid Generate XML Schema based on object type using DBMSXMLSCHEMA Validating XMLType Instances XMLlsValid An SQL tor uses to validate an XMLType instance without changing its validation state SchemaValidate memberprocedure which validates an XMLType instance against its XML Schema Validation state will be changed arter validation lsSchemaValido VA PLISQL membermnctioh which checks the validation state of an XML instance setSchernaValidatedo A PLISQL memberfunctien which can set the validation state of an XML instance Registering an XML Schema egin dbmsxmlschemal39egisterSchema 39 t bumbusucdavisedutimScholarxsd39 getDocument39Scholarxsd39 end When an XML Schema is registered the Oracle 9i DB will 1 Create an appropriate SQL object type for the XML document based on the XML Schema 2 Create default XMLType tables for all the root elements 3 Create Java Bean for better XML manipulating performance Validation Examples Using XMLlsValid Ensures that the incoming X document is Valid CREATE TABLE Scholar of XMLT e CHECK XMLlsValidsys nc rowinfo 1 XMLSchema http Ilhumhusucdavisedultimlscholarxsdquot element UCLEADS Using lsSchemaValid declare xmldoc xmltype begin 39 quotup if xrrldochSchemaValid 1 then 53959 1 Perform different operations based on equot the validation state of the XML ent Validation Examples Using SchemaValidateO DECLARE xmldoc xmltype BEGIN xmldoc newsysncrowinfo xmltypeschelnavalidate xmldoc END39 Validate the incoming XML instance and change its Validation state Generate XML Schema chema can be generated AUTOMATICALLY from an objectrelational type using XMLtoObject Mapping TWo functions to use 1 generateSchemal ates an XMLType instance which contains the XML Schema 2 generateSchemas generates an XMLSequenceWpe of XML Schema and each of them is corresponded to a d erent namespace CREATE TYPE office as OBJECT SELECT d ms xmlschemagenemteschema address VARCHAR2200 k phone NUMBERUO CONNECTION OFFICE from Pro le Deleting Registered Schema drop table profile EXEC dbmsxmlschemadeleteSchema httplbumbusucdavisedutimscholarxsd dbmsxmlschemaDELETECASCADEFORCE Two delete modes T Cascade Mode delete all the XMLType tables SQL objects and Java Beans generated by the Schema registration Force Mode delete the schema even if it fails the dependency check Using XSLT with XMLType XMLTransform XMLType instance XS Tranforrn the result of the SQL query a 39 am my L from XML to other output format create table MyStyle Stores various stylesheets as GWLType i mm 1 Output as HTML style XMLType 2 Output as another GWL SELECT XMLTransforn1 xp le select style from Myster where id1 getStringVal AS result FROM pro le X ansfonn an GWLType instance usingst stored in the Myster table Oracle 9i XDK Oracle 9i XDK Main Utilities XML SQL Utility XSU provides XMLtoSQL and SOLto Mapping generates XML document from SQL quer with DTD and Schema extracts values from XML document and generates SQL query 0 XSQL Servlet uses XSLT with XML document or SQL query to publish dynamic content c TransX Utility loads XML document intothe database with additional SOL functionalities Oracle 9i XDK Main Utilities 33 XM L Parser creates and parses XML document using DOM or SAX XSLT Processor transforms parsed XML document using API for XML XML Schema Processor validate parsed XML document against XML Schema XML Class Generator for Java generates Java source les from DTD or XML Schema to build Java application as backbone to process XML document Using XML Parser Namespace support XML Compression for efficient storage Two different type of parsers 1 DOM parser tree based APL good for structure manipulations 2 SAX parser event based AFI good for event handling Main validation modes for XML Parser Nonvalidate only check if the XML document is wellformed DTDvalidate validate against DTD Schemavalidate validate against Schema Autovalidate validate automatically when DTD or Schema is presen ed fileName validate the inputXML le against a DTD schema fiIeName validate me inputXIliL le against an XML schema novalidate fileName checks if the inputXML le is well formed warning show warning log IogFiIe writes error to a log file Other DOM Parser methods SetPreserveWhiteSpace True or False SetDocType Document Type SetBaseURL DTD directory ShowWarnings True or False GetEIementTagName GetAttributes GetNodeName GetNodeValue Reset lean up any data structure generated in the parsing process XSLT Processor Example import oracIexmlparserv2XSLStyiesheet import oraclexmlparserv2XSLProcessor Import oracIexmlparserV2XMLDocumentFragment URL MyParserparse MyXMLFiIe XMLDocument XMLDoc MyParsergetDocument URL MyXSLFiIe createURuargsnn Parse the inputst le MyParserparse MyXSLFiIe XMLDocument XSLDoc MyParsergetDocument XSLT Processor Example XSLProcessor MyProcessor new XSLProcessorl MyProcessorsetBaseURL MyXSLFiIe lt Instantiate the XSLT Processor XSLStyleSheet MyXSL processornewXSLStylesheet XSLDoc lMyXSL XMLDoc L Process the XSL Transformation XML Schema Processor Import oraclexmlparserschema XSDBuilder MyBuilder new XSDBuilderl RL Myxsn createURLlargs0 XMLSchema MySchenu XMLSchema MyBuildeszuiltll Myxsn Process l aquot95m MYSOlIemal lt first param me file second param Xsd file Class process String xmlURl XMLSchema doc DOMParser p new DOMParserll URL url createURL xmlURl psetXMLSchema doc psetValidationMode XMLParser Schema VALIDATION pparse url XSLT Command Line Tool 3 General format oraxsl options source stylesheet result Exanple oraxsl pro lexml websitexsl tablehtml Ad onal command line options d directory transform al the xml les in the directmy i source 39 M speci c extension I l xml le list a list of xml les to be transformed s stylesheet uses with d or I option which speci cs the stylesheet to use in the transformation t num of t d 39 r of x source extension uses with d option which exclude les with speci c ext n ension from the transfol39matio XML Class Generator CG When to use XML Class Generator application based on DTDs or XMLSchema Namespace support 1 a package 2 Synbol space each target namespace specified in the XML Schema will have a distinct symbol space Two class generators 1 DTD Class generator 2 XML Schema Class generator root input is a DTD le or a DTDbased XML le outputDir spec es output directory for the Java source le package speci es the package name to use comment generates comment in thejava source le DTD CG Example in Java University UCD new Universityquot Scheduie s1 new Scimiqu lt7 Instantiate different nodes ourse new ourse ECS150quot Course C2 new Course ECS 165Aquot S1addNode c1 S1addNode c2 I Constructing the XML document UCDaddNode s1 UCDaddNode 52 II UCDValidateContent0 Vali39dati39ng the XML document against the DTD defined in the root node XML SQL Utility XSU Main features 1 Converts nonXML data from various databases Into XML format 2 Inserts XML data into nonXML table 3 Updates nonXML table from XML data 4 Generates DTD dynamically based on SQL query 5 Generates XML Schema dynamically based on SQL query 6 Transforms autogenerated XML document using XSLT 7 Provides mapping between SQL and XML Required components 1 JDBC Oracle JDBC is recommended 2 XML Parser XSU Example in Java Import oraclexmlsqlqueryoracleXMLQuery Import oracIexmlsqldml0racleXMLSave Register the JDBC driver and create connection Import oracledhcdrver i Connection MyConn rIverManagergetConnection jdhc oracle8quot tim 12345 II If the XSU application is running on the server uses II Connection MyConn new II OracIejdhcdriver0racleDriverdefaultconnectianl OracleXMLQuery Mery new OracleXMLGueryl MyConn select from pro lequot YMI YMI nnMu i Creates a Query instance and convert the query result into at XML form Sample XSU XML File SELECT from profile lt Xml version 10 gt ltRDWSETgt ltRDW num 1 gt ltnamegtTimltlnamegt ltmajorgtComputer Scienceltlmajorgt ltyeargtJuniorltlyeargt ltIRDWgt ltRDW num 2quotgt ltnamegtMichaeltlnamegt ltmajorgtComputer Engineeringltlmajorgt ltyeargtSeniorltlyeargt ltIRDWgt II ltIRDWSETgt XSU Example in Java First register the JDBC driver and creates connection DracleXMLSave MyXS new DracleXMLSave MyConn profile MyXSinsertXML MyXSgetURL XML FILE MyXScose Insert the whole XML document into the database String 1 KeyColumn ew String1 KeyColumn0 Major i H K9 Pnlllmn MyXSsetUpdateColuanistcolumn names Ilcolumn names0 lt Specifies the columns to update Ilcolumn names1 Major IXMI FILE lt Sample XSU XML File SELECT name major year yearquot from pro le lt Xml version 10 gt ltRDWSETgt ltRDW num 1 year Juniorquotgt ltnamegtTimltlnamegt ltmajorgtComputer Scienceltlmajorgt ltIRDWgt ltRDW num 7 year Seniorquotgt ltnamegtMichaelltlnamegt ltmajorgtComputer Engineeringltlmajorgt ltIRDWgt ltIRDWSETgt XSU Command Line Tool General format java OracleXML getXML options Example java OracleXML getXML user Hm12345 select from prorile xsu Command Line Tool Options user userpassword specifies login information conn JDBC connection stnng specifies the JDBC connection withDTD generates DTD along with the XML document withSchema generates an XML schema along with the XML document rowsetTag tag name specifies the ltRDWSETgt tag rowTag tag name specifies the ltROWgt tag rowldAttr attr name speci es the num attribute in the row tag styesheet stylesheet URI specir39 s the XSL to userortransrormation maxrows number speci es the maximum numper or rows returned skiprows number speci es the umber of rows to skip XSQL Servlet Main Feature Combines the power of SQL query XML document and XSLT to publish information in different formats including but not limited to HTML WML XMLFO for PDF and other text formats such as emails Required component Oracle 9i XML Parser Oracle 9i XSLT Processor Oracle 9i XML SQL Utl ty XSU Command Line Tool General format java OracleXML putXML options Example java DracleXML putXML user Hm12345 IileName profilexml tabeName profile xsu Command Line Tool Options user userpassword speci es login information conn JDBC connection string specifies the JDBC connection batchSize size speci es the batching size to use commitBatch size speci es the batching size before a commit is performed rowTag tag name specifies the ltROWgt tag eName name specifies the XML document to use tabeName name speci es the table name where the data will be inserted setXSLT Specifies the XSL to use before insertion Web Servers for XSQL Page Main servers which support XSQL Page Oracle 9i Internet Application server v1x and v2x Oracle 9i Oracle Servlet Engine Allaire JRun 233 and 300 Apache 139 or higher with JServ1011 or Tomcat 31 32 Servlet Engine Apache Tomcat 31 or 32 Web Server Servlet Engine Java Web Server 20 Sun JavaServer Wen Development Kit JSWDK 101 Web Server XSQL Query Example ll ClaSSSEamhqul Prede ned connection lt xml Version 10quot gt r APPIJ XSLT to XML document lt xmlstylesheet type te XSIquot href tablexslquot gt ltxsql query connection dbisquot hindparams Class xmlns xsq ucdavisquotgt SELECT Location Instructor Time FROM Class Pro le WHERE Name 4 Binding parameter ltlxsql querygt http XSQL Query Attributes hindparams param1 param2 quot ORDER matters idattrihute string speci es the num tag in the result 4 ta39g value I or Fquot GL u A maxrows integer max number of rows to fetch rowelement string speci es the ltrowgt tag rowsetelement string speci es the ltrowsetgt tag skiprows integer speci es the number of rows to skip I or Fquot at ului tagcase lower or upperquot speci es the case used in the output dateformat string speci es the date format mask XSQL Page Example 2 II pro lexsql lt Xml versio quot 10quot gt lt Pro le connection dbis xmlns xsq ucdavisquot gt ltStudentgt ltxsql query rmx 10 max rows max quotgt SELECT FROM Student Pro le ltlxsql querygt ltlStudentgt L Lexical substitution with default Value 10 ltMajorgt ltqul includexsql href rmjorxsqlquotgt e Nested qulpage ltIMajorgt ltIPro legt http Ilhumhusucdavisedultimlpro lexsqlmax20 XSQL Command Line Tool Provides offline XSQL page processing ability General format 39 veal anmantll 39 Example java oraclexmlxsqlXSQLCommandLine pro lexsql Optional parameters postedXml XMLDocumentURL treated the output as posted documnt a u er ag nuasn Other XSQL Utilities 1 Uses to de ne case where no row is returned from the primary XSQL II query ltxsql norowsquerygt T h a n k u SELECT Statement ltlxsql norowsquerygt II Allows user to perform DML DDL or PLSQL Operations ltxsql dmlgt DML DDL or PLISQL Operations ltlxsql dmlgt II Allows user to include XML result set win is determined by II executing a PLISQL func In ltxsql refcursorfunctiongt II Allows user to include XML content that has been generated by a II database stored procedure ltxsql includeowagt E08 150 Operating Systems Computer Security mg unt r Secw ty Goal To learn the basics of how data on computers is protected Spring Quarter 1999 1 E08 150 Operating Systems Computer Security Security and Protection Goals confidentiality integrity availability Requirements vary from site to site describe Orange book DoD Trusted Computer System Evaluation Criteria Red Book DoD Trusted Network Interpretation of the TCSEC Privacy Act all of which constrain policies at different sites Discuss policy vs mechanism Our job design mechanisms that will allow these goals to be accomplished or think about why such mechanisms are infeasible Spring Quarter 1999 2 ECS 150 Operating Systems Computer Security Saltzer39s and Schroeder39s Design Principles Following these is central to any secure architecture Economy of Mechanism the protection mechanism should have a simple and small design Failsafe Defaults the protection mechanism should deny access by default and grant access only when explicit permission exists Complete Mediation the protection mechanism should check every access to every object Open Design the protection mechanism should not depend on attackers being ignorant of its design to succeed It may however be based on the attacker39s ignorance of specific information such as passwords or cipher keys Separation of Privilege the protection mechanism should grant access based on more than one piece of information Least Privilege the protection mechanism should force every process to operate with the minimum privileges needed to perform its task Least Common Mechanism the protection mechanism should be shared as little as possible among users Psychological Acceptability the protection mechanism should be easy to use at least as easy as not using it Spring Quarter 1999 3 E08 150 Operating Systems Computer Security Issues Physical security covers access to the computer and associated equipment controlled by badges etc Operational security covers pocies and procedures used to run the system and includes access control who can do what to each object subjects actors objects either passive entities or any entity subjects too protection domain what objects a subject can access and how The basic structure is an access control matrix objects m Access control lists ACLS l 0 are the columns of the access q control matrix g Capability lists CLists Lg CList J are the rows Iof the access 3 control matrix I ACLs go down Clists across Discuss capabilities the main difference is a capability is thought of as the m means to refer to an object capabilitybased addressing although we39ve talked about C lists being for secondary storage files etc they are also used in main memory Compare capability lists to segment tables both consist of pointers and rights difference entries in a segment table point to incore structures segments but entries in a clist point to secondary storage 80 combine them use capabilities for both incore and secondary storage objects That is associate a unique capability with amLobject regardless of where it is in system the same one is used by the file manager and the memory manager Spring Quarter 1999 4 E08 150 Operating Systems Computer Security global object table enables this Each entry in the table points to exactly 1 object regardless of where it is if the object moves the table is updated A capability is an index into this table augmented with a set of rights problem must prevent users from creating capabilities This is done in one of two ways 1 store the capability in segments which the user39s can39t access 2 use a tagged architecture in which each main store location has a tag bit if the tag bit is set only system routines can minipulate that location 80 put the capability there example MULTICS implements access control using access control lists in a dynamic linking environment based upon concentric protection rings nucleus administration system I 1 a l Each segment is assigned to a ring the assignment is fixed and is part of the entry in the filedirectory for each segment in practice there is actually a bracket A process can only access going out ie if a process executing in segment 8 in ring i tries to access segment T in ring j the access is allowed if 1 j 2 i and 2 AOL for T allows the access If i gt j an interrupt occurs and control is passed to the system routine to verify the validity of the access Spring Quarter 1999 5 E08 150 Operating Systems Computer Security Note even if a process is going out it must copy arguments addresses of variables in ring i etc these copies must be put into an area accessible to T This means problem objects must be linearly ordered example with capabilities this is not true ring process p 5 P1 5 Here p can access Q 5 P1 if Q is called from segment P1 but not from segment P2 L i 2 0 P2 P2 AOL for Q r e e e e e Here p can access Q if Q is called from 7 Q Q segment P1 but not I from segment P2 Other interesting note with capabilities you do not need privileged hardware states Just take an objectoriented approach to do something you need an object thing to be manipulated and an operation The object is of a certain type example consider scheduling and dispatching should only be done by the kernel 80 scheduling and dispatching are operations defined for process objects and undefined for all other objects Just make sure that no user gets capabilities for the objects which are of the types on which privileged operations work problem Why are capabilities not used more often Too expensive and such systems execute more slowly logging actions and examining system state logging and auditing good mechanism for detecting potential problems useful with IDES and other surveillance programs requires verification of user identity user authentication passwords keys andor biometrics limits on number of attempts to log in leading to keeping data private confidentiality Spring Quarter 1999 6 process p CList for P1 E08 150 Operating Systems Computer Security keeping data unaltered integrity Spring Quarter 1999 7 ECS 150 Operating Systems Computer Security Cryptography Used as a tool to augment or replace other security mechanisms or where other security mechanisms infeasible ie packet radio networks Two goals Privacy is protection against disclosure Authentication is assurance of identity Typical uses are to provide privacy to personal or proprietary information and to provide assurance of its source Two styles Classical cryptography uses one secret key privacy is done by keeping the key and message secret whereas authentication is done by keeping the key secret but making the message public Public Key cryptography uses two keys one public one private privacy is done by encrypting using the recipient39s public key which she can decrypt using her private key and authenticity is done by encrypting using the sender39s private key which anyone can decrypt using her public key Attacks on cipher systems Ciphertext Only attack given ciphertext determine message and key if possible 1 V 2 Corresponding Plaintext and Ciphertext attack given ciphertext and corresponding plaintext determine key 3 Chosen Plaintext attack obtain ciphertext corresponding to any plaintext you choose and then find the key Classical Ciphers Review briefly the concepts of types of ciphers Caesar ciphers etc here Public Key Ciphers Requirements let D be private key E public m message c ciphertext 1 DEm m 2 Given E it is computationally infeasiblequot to get D 3 E cannot be determined by a chosen plaintext attack Best known is RSA Cryptosystem 1 Pick two large prime numbers p and q 2 Compute n pq and n p1q1 Euler39s totient function 3 choose any d such that god d 1n 1 4 find e such that ed 1 mod 1n Spring Quarter 1999 8 E08 150 Operating Systems Computer Security Here the public key is e n and the private key is d Given n it is computationally infeasible to find n because the techniques known all involve factoring n or doing the equivalent To encrypt a plaintext message m compute c me mod n and to decrypt ciphertext c compute m cd mod n This works because of Euler39s Generalization to Fermat39s Little Theorem which says that a 1 mod n when gcda n 1 so m cd mod n me mod nd mod n med mod n mk n1mod n m n mod nk mod n m mod n m mod n m This is considered a very strong cipher provided you pick n to be at least 512 bits factoring techniques will make lesser values soon factorable example We want to use the encoding a 00 z 25 ltbankgt 26 and write letters in pairs this means n must be at least 2626 so we can represent all possible pairs of letters Take p 53 q 61 then n 53 x61 3233 and n 52 x 60 3120 Pick d 71 as gcd71 3120 1 this gives e 791 Note de mod ltn 71791 mod 3120 1 So the public key corresponding to the private key 791 is 71 3120 Now to encrypt renaissance for this user we split it into pairs of letters re na is sa nc eltbankgt In the encoding this becomes 1704 1300 0818 1800 1302 0426 To encrypt for privacy we use the recipient39s public key so the ciphertext is 3106 0100 0931 2691 1984 2927 as 170471 mod 3233 3106 etc Slgnatures for authenticity Suppose our private key is 61 then our public key must be 1381 3233 So to sign the message renaissance again we get the encoding 1704 1300 0818 1800 1302 0426 and encrypt it but using our private key 2436 0629 0818 0336 1302 1890 as 170461 mod 3233 2436 etc Note that anyone can read this as the decryption key is public but without the private key noone could generate it Spring Quarter 1999 9 ECS 150 Operating Systems File Systems F i i e S ys te ms Goal To learn how files are represented both in memory and on the secondary storage devices Spring Quarter 2008 1 ECS 150 Operating Systems File Systems EileLstampms A file is a collection of data There are two aspects of it virtual this is how the user process sees the file physical this is how the file is represented to the hardware and operating system A file39s name often reflects something about the file example in TOPS20 file names are nameext where ext is a three character extension describing the file bas for BASIC for for FORTRAN bli for BLISS obj for object exe for executable txt for text and so forth On Linux FreeBSD and MlNlX the last letter may designate something for example C source files end in c and C source files in cc Spring Quarter 2008 2 ECS 150 Operating Systems File Systems E Files can be organized into directories folders to the Mac to make organizing them easier A directory contains pairs of name location The location may be a physical location disk address or an index into an array containing those locations or any other datum used to locate files There are several main types of directory organizations in historical order they are 0 a onelevel flat directory in which all files are in the same single directory 0 no two files can have the same name so to keep users having to worry about collisions the system could make the user name a component of each file name 0 to find a file one must search the whole directory 0 hierarchical directories impose a tree structure on directories typically there is a master directory and then user directories for each user 0 do absolute and relative path names current working name 0 graphstructured directory systems are basically hierarchical systems but with the ability to alias files 0 direct aliasing occurs when one file location appears twice or more in directories often with different names indirect aliasing occurs when a special type of file containing a path name is created it is said to be an indirect alias for the file it names When you refer to the indirect alias the operating system interpolates the name of the file being aliased issues 0 naming there is no such thing as a quottruequot name now 0 deletion If a file is deleted under one alias is it inaccessible using the other aliases yes must find all other aliases and delete them expensive no don39t delete file until all aliases deleted use a link count to track how many aliases a file has accounting usually the owner of a file pays for storage and other related charges but if another user aliases to the file the owner might no longer be able to delete all references to it solution have each person owning a link to the file ie owning a directory containing a link to the file pay a percentage of the cost of the file Information kept in a directory or indicated by it is the name file type etc Spring Quarter 2008 3 ECS 150 Operating Systems File Systems Aclte CQntrol Typical protection modes are read write append delete privilege allows modification of others39 rights owner indicates owner of file and search grants permission to search directory example UNIX note difference in meaning of execute for files and directories implementation describe access lists abbreviation association of rights are privileges associated with a name or a le That is if Xis an alias for y can a user have read permission on Xbut not on y Spring Quarter 2008 4 ECS 150 Operating Systems File Systems E 1 El Processes operate on files using the following commands create find space for the file allocate it and make an entry in the directory open begin operations on a file close end operations on a file read transfer information from the file write transfer information to the file rewind move to the beginning or a random point in the file delete remove the file Spring Quarter 2008 5 ECS 150 Operating Systems File Systems As e Methods How can processes access files Spring Quarter 2008 sequential one block after the other The process keeps track of a readwrite pointer part of the PCB indicating where the next action is to be done the pointer always advances direct the readwrite pointer can move freely mapped map the file into a virtual segment and return the segment number rather than the file descriptor then treat the file as part of the process39 virtual store On closing just release the storage example TOPS20 MULTICS FreeBSD structured the file consists of a sequence of records often the operating system knows about the file type example ISAM Indexed Sequential Access Method In this a small master index points to blocks in a secondary index which in turn point to real file blocks Thus it takes at most 2 reads to locate any record ECS 150 Operating Systems File Systems It H A disk directory is like a directory for a disk it describes what blocks are in use and which are free This means it must keep track of what blocks are not in use such a list is a free list Several representations 0 a bit map with 1 bit per block 0 a linked list of blocks 0 like linked list but in each block of size n on the free list store n l numbers of free blocks the n th is the address of the next block making up the list pairs of block number number of free blocks from that block on if there is more than one contiguous block free this usually saves same space The latter three are often called file maps because each free block is represented by l word pointer Spring Quarter 2008 7 ECS 150 Operating Systems File Systems I EDIBI I El This is done in one of three ways 0 contiguous allocation here blocks are allocated sequentially contiguously advantages 0 minimal head motion for sequential reading of file problems 0 need to find space for it using the usual algorithms firstfit best fit Compaction is possible but usually requires copying almost everything on the disk 0 how much space should be allocated for the file It might grow beyond its initial allocation 0 there may be room to increase the allocation 0 the program may be terminated in this case people tend to ask for as much room as possible wasting space 0 the file may be moved elsewhere very slow Note that files may grow for years so even if you know the maximum size a file will ever get you may waste lots of space for a long time linked allocation the directory contains pointers to the first and last blocks of the file and the last n bytes of each block in the file point to the next block in the file advantages 0 this scheme eliminates the need to know the size of files in advance 0 again it is great for files accessed sequentially disadvantages 0 it is poor for direct access files as the operating system must follow links to get to the desired block it wastes n bytes of disk space per block it is unreliable if i pointer is deleted or changed the file is garbled a doublylinked list which would ameliorate this uses more memory indexed allocation this scheme brings all pointers together into one block advantages 0 compact and easy to reference blocks disadvantages 0 wastes more space as an entire block is pointers rather than just l word per block so a 511 block file and a 2 block file use the same number of pointers Spring Quarter 2008 9 ECS 150 Operating Systems File Systems implementation issue If you need more than 1 index block link them together Or use indirection if you can have 256 pointersblock 2 levels of indirection allows 2562 65536 blocks example UNIX scheme the first 12 blocks of a file are data the 13th is an index block the 14th is a doublyindexed block ie it contains pointers to index blocks and the 15th is a triplyindexed block ie it contains pointers to doublyindexed blocks Spring Quarter 2008 10 ECS 152B Computer Networks Spring 2003 Demet Aksoy wwwcsucdaviseduaksoycourse152b 32703EC8152B Demet Aksoy Highlights prerequisites ECS 1 50 and ECS 1 52A courses must have been completed undergraduate students make sure to follow up the newsgroup messages ucd class ecs152b ucd class ecs152b 61 grading 0 Projects 40 Midterm 20 Homeworks 10 0 Final 30 ECS 1 52B Demet Aksoy Road Map I Introduction Computer Networks Overview Requirements of Networks OSI Layering Overview 11 Application Layer What s a protocol HTTP FTP SMTP DNS Socket API 111 Transport Layer Responsibility of the transport layer UDP TCP Connection Establishment Sliding Window Flow Control Congestion Control Connection Termination I ECS 1 52B Demet Aksoy ECSISZB Road Map IV Netw ork Layer Overview of Network Layer Routing Overview of IP Fragmentation and Reassembly ICMP IPv6 IGMP V Data Link Layer Overview of Data Link Layer Services Multiple Access Protocol Ethernet ARP RARP SLIP PPP ATM Demet Aksoy Computer Networks Interconnected collection of autonomous computers attached to a host system Host B Host A Network Adapter Network Adapter ECS 1 52B Demet Aksoy Protocols A protocol de nes the format and the order of the messages exchanged the actions on receipttransmission of a message host Network Adapter Network Adapter host ECS 1 52B Demet Aksoy Protocols 0 Why use a protocol to provide a common language 0 There are so many protocols 0 Rules must be unambiguous and followed exactly 0 eg TCPIP IP Internet Protocol ECS 1 52B Demet Aksoy Protocol Example Brunch request URL request 0 539 hello TCP iquot V connection request yes TCP connection reply gOt pan39cakeS get httpWwwumdeduindexhtml Ayming up soon ytml not necessarily typical ECS 1 52B Demet Aksoy The Protocol Stack OSI 7 layers Application Presentation Session Transport Network Link Physical Old Saying ECS152B IP Suite 4 layers Application Transport Network Link If you know what you are doing four layers is enough HTTP FTP TCP UDP IPv4 IPv6 if you don t seven won t help Demet Aksoy The Internet Protocol Stack Layers provide information hiding doesn t matter what lower level layers use as long as higher layers use the same protocol Cl A llcatlon l 1 y lcatlon V netwo k 4 pplicati o l i e ams fro one host to another quotl t V Lima Lin or e g transmits individual bits Within the frame ECS 1 52B Demet Aksoy ECSlSZB The Internet Protocol Stack Link Demet Aksoy The Internet Protocol Stack Application Transport ECS 1 52B Demet Aksoy The Internet Protocol Stack Protocol Data Units PDU Implementation message software software segment mixed a atagram network ame interface card ECS 1 52B Demet Aksoy Protocol Layers Simpli es implementation segmentationreassembly error control ow control multiplexing connection setup in different layers Application Application Transport Transport a Link HostA router router HostB There also are some potential disadvantages may duplicate functionality may need info in a nonadj acent layer e g timestamp ECS 1 52B Demet Aksoy ClientServer Model A typical network has two components client and server client server client host that initiates the session eg asks for a Web page browser server host that gives the requested service same host can be both a client and a server for one application email ECS 1 52B Demet Aksoy Application Layer Applicationlayer protocols 7 are only one piece of a network application eg email file transfer the Web 7 define messages exchanged syntax semantics and actions taken 7 user services are provided by lower layer protocols ECSISZB Demet Aksoy ECSlSZB Application Layer Protocols 0 example application layer protocols HTTP Hypertext Transfer Protocol FTP File Transfer Protocol SMTP Simple Mail Transfer Protocol DNS Domain Name System Demet Aksoy World Wide Web the HTTP protocollg http hypertext transfer protocol WWW s application layer protocol client requests receives 2322 displays WWW objects object HTML le JPEG or GIF image audio clip etc browser server in response to requests sends objects Web server client browsar39 Uses TCP reliable transport layer protocol handshaking etc on port 80 ECS 1 52B Demet Aksoy HTTP example Suppose user enters URL wwwcsucdaviseduinstructiondefaulthtm k J 4 V V host name path name 1a http client 1n1t1ates TCP connection to http server process at lb http server at host wwwcsucdavisedu Port 80 wwwcs ucdavisedu waiting is default for http server for TCP connection at port 80 accepts connection noti es 2 http client sends http request Client message containing URL into TCP connection socket http server receives request message forms response message containing requested 39I39l me object instructiondefaulthtml 5 http client receives response Sends message into SOCket quot message containing html le 439 http sewer Closes TCP displays html connecuon39 Ecs152B Demet Aksoy 20 HTTP Stack Protocol Data Units PDU Am oa om 3 Transport qr 39W39v SOYFOB ECSlSZB 21 HTTP message format request http request message method URL version r39eques r 3913 39 GET somedirpage html HTTP1 0 GET POST Connection close HEAD 3T9 header User agent Mozilla4 0 lines Accept texthtml imagegif imagejpeg Accept language fr vextra carriage return line feed Car39r39iage r39e rur39n line feed indicaTes end of message ECS 1 52B Demet Aksoy HTTP request message general format request line Ec5152B DemetAksoy 23 HTTP message format reply sTaTus Hne roTocol s rg rus code HTTP11 200 OK s ra rus phrase Connection close Date Thu 06 Apr 2000 120015 GMT header Server Apache130 Unix lines Last Modified Sat 1 Apr 2000 062319 GMT Content Length 5021 Content Type texthtml data data data data data En ri ry body requesTed th fHe ECS 1 52B Demet Aksoy HTTP response message general format request line Emmy Evme Status code examples Ec5152B 200 301 400 404 und 5 HTTP Version Not Supported DemetAksoy OK success Moved Permanently Bad Request Not 25 try it out http client side 1 Telnet to UCD WWW server Open TCP connection To port 80 default http server port at wwwcsucdavis Anything Typed in sent To port 80 at wwwcsucdavis telnet WWW cs ucdavis edu 8O 2 Type in 21 GET http request GET index html HTTP1 0 Host www cs ucdavis edu hit carriage return Twice 3 Look at response message sent by http server in response to your minimal but complete request ECS 1 52B Demet Aksoy 26 HTTP two versions HTTP 10 RFC 1945 HTTP 11 RFC 2068 default server closes defauu SGI VGI keeps the connection after each 00111160th11 Open fOI successive re uest object nonpers1stent q pers1stent ECS 1 52B Demet Aksoy 27 Authentication and Cookies HTTP is stateless ask for the same object twice server sends it twice Authentication to control access to server documents authorization typically name and password client must present authorization in each request send Authorization header line in every request if correct server accepts access else server refuses access 401 Authorization q uthenticate Autm send with each message ECS 1 52B Demet Aksoy 28 Authentication Cookies Cookies RFC 2109 Saves to a le eg netscapecookies M send with each message ECS 1 52B Demet Aksoy 29 Conditional GET 39 Goal don t send object if M Ser39Ver39 client has upto date stored cached version object not chent spe01fy date of modified cached copy 1n http request If modified since ltdategt server response contains no object if cached copy up todate HTTPl O 304 Not Modified ECS 1 52B Demet Aksoy object modified 3O Conditional Get 0 ask to receive only if current obj eot stale GET instructiondefaulthtml HTTP11 HTTP1 1 200 OK Date Thu 6 April 2000 120015 GMT Server Apache130 Unix LastModified Sat 1 Apr 2000 062319 GMT ContentLength 6821 ContentType texthtml data data data data data GET instructiondefaulthtml HTTP11 Useragent szilla40 Accept texthtml imagegif Ifmodifiedsince Sat 1 April 2000 062319 HTTP11 304 Not Modified Date Thu 8 Apr 2000 120015 GMT Server Apache130 Unix empty entity body ECS 1 52B Demet Aksoy ECSlSZB 31 Web Caches Proxy Server Goal satisfy client request without involving origin server user sets browser WWW accesses via web cache client sends all http requests to web cache o gin Server if object at web cache web cache immediately returns object in http response else requests object from origin server then returns http response to client o gin Server Demet Aksoy 32 Suggested Reading 0 KuroseRoss Chapter 2 upto section 23 Section 29 ECS 1 52B Demet Aksoy April 26 1999 Introduction ECS 150 7 Spring 1999 Page 1 Bakery Algorithm This algorithm solves the critical section problem for n processes in software The basic idea is that of a bakery cus7 tomers take numbers and whoever has the lowest number gets service next Here of course service means entry to the critical section Algorithm 1 var 16 Comments lines 172 lines 476 lines 7712 line 14 choosing shared array 0n l of boolean number shared array 0n l of integer repeat Choosingi true numberi maxnumber0numberlnumbern l l Choosingi false for j 0 to n l do begin while choosingj do nothing while numberj ltgt 0 and numberj j lt numberii do nothing end critical section numberi 0 remainder section until false Here Choosing i is true if Pi is choosing a number The number that Pi will use to enter the critical section is in numberi it is 0 if Pi is not trying to enter its critical section These three lines rst indicate that the process is choosing a number line 4 then try to assign a unique number to the process Pi line 5 however that does not always happen Afterwards Pi indicates itis done line 6 Now we select which process goes into the critical section of all the processes waiting to enter the critical section If two processes have the same number the one with the smaller name 7 the value of the subscript 7 goes in the notation ab lt cd means true if a lt c or if both a c and b lt d lines 9710 Note that if a process is not trying to enter the critical section its number is 0 Also if a process is choosing a number when P tries to look at it Pi waits until it has done so before looking line 8 Now Pi is no longer interested in entering its critical section so it sets number i to 0 Pi waits until it has the lowest number Last modified at 9 12 am on Monday February 13 2006 April 26 1999 ECS 150 7 Spring 1999 Page 2 Bogus Bakery Algorithm Introduction Why does Lamport39s Bakery algorithm used a variable called Choosing see the algorithm lines 1 4 6 and 8 It is very instructive to see what happens if you leave it out This gives an example of mutual exclusion being violated if you don39t put choosingin But rst the algorithm with the lines involving Choosing commented out so you can see what the modi cation was Algorithm 1 var choosing shared array 0n l of boolean 2 number shared array 0n l of integer 3 repeat 4 Choosingi true 5 numberi maxnumber0numberlnumbern l l 6 Choosingi false 7 for j 0 to n l do begin 8 while Choosingj do 9 while numberj ltgt 0 and 10 numberj j lt numberii do 11 nothing 12 end 13 critical section 14 numberi 0 15 remainder section 16 until false Proof of Violation of Mutual Exclusion Suppose we have two processes just beginning call them p0 and p1 Both reach line 5 at the same time Now we39ll assume both read number 0 and number 1 before either addition takes place Let p1 complete the line assigning 1 to number 1 but p0 block before the assignment Then p1 gets through the while loop at lines 9711 and enters the critical section While in the critical section it blocks p0 unblocks and assigns 1 to number 0 at line 5 It proceeds to the while loop at lines 9711 When it goes through that loop for j 1 the condition on line 9 is true Further the condition on line 10 is false so p0 enters the critical section Now p0 and p1 are both in the critical section violating mutual exclusion The reason for Choosingis to prevent the while loop in lines 9711 from being entered when process is setting its numberj Note that if the loop is entered and then processj reaches line 5 one of two situations arises Either number j has the value 0 when the rst test is executed in which case process 139 moves on to the next process or number j has a nonzero value in which case at some point number j will be greater than number 1 since process i nished executing statement 5 before process j began Either way process 139 will enter the critical section before process j and when process j reaches the while loop it will loop at least until process 139 leaves the crit ical section Last modified at 9 12 am on Monday February 13 2006
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'