Queueing & File I/OCS 241: Systems ProgrammingDiscussion, Week 7slides prepared by Sameer SundreshLMP1QueueingFiles OverviewFile I/OLMP1LMP1 is the first part of a three-MP set aimed at implementing a functional network file system.LMP1 deals with file I/O, while subsequent MPs add memory management and networking.In LMP1, you implement a basic file system, and test its performance using the Bonnie filesystem benchmark.LMP1: four parts1. Use Bonnie with the provided stub code to understand its functionality2. Implement basic FS operations for our file system (file_read, file_write, file_info).1 & 2 will be due Wednesday after Spring Break3. Implement additional FS operations (file creation/deletion, directory ops, checksums)4. Modify Bonnie to use our custom FS implementation and test performanceLMP1QueueingFiles OverviewFile I/OQueuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPUSteady statePoisson arrival with λ constant arrival rate (customers per unit time) each arrival is independent. P( τ≤t ) = 1- e–λt Queueing Theory01tAv λ0.5Analysis of Queueing BehaviorProbability n customers arrive in time interval t is: e–λt (λt) n/ n!Assume random service times (also Poisson): μ constant service rate (customers per unit time)Queuing Diagram for Processes StartStartEvent QueueEvent QueueExitExitTime SliceTime SliceARRIVAL RATE ARRIVAL RATE λλSERVICE RATE SERVICE RATE μμSERVICE RATE SERVICE RATE μμ11ARRIVAL RATE ARRIVAL RATE λλ11Useful Facts From Queuing TheoryWq= mean time a customer spends in the queue λ = arrival rateLq = λ Wq number of customers in queueW = mean time a customer spends in the systemL = λ W ( Little's theorem) number of customers in the systemIn words – average length of queue is arrival rate times average waiting timeServer Utilization: ρ = λ/μTime in System: W = 1/(μ-λ)Time in Queue: Wq = ρ/(μ-λ)Number in Queue (Little): Lq = ρ2/(1-ρ)Analysis of Single Server QueuePoisson Arrival & ServiceRates Sum ARRIVAL RATE ARRIVAL RATE λλ11SERVICE RATE SERVICE RATE μμInput QueueInput QueueServerServerARRIVAL RATE ARRIVAL RATE λλ22λ λ == λλ1+1+ λλ22LMP1QueueingFiles OverviewFile I/OOverviewHow do you get data in/out of a program?Unix solution:Files.Many different kinds of I/O are viewed, to some degree, as accessing a file stream:stdin, stdout, stderr, /dev/audio,pipes (cat file | grep text), network socket, ...Unix file system tree/ /bin/ /home/ /home/someuser/ /home/someuser/somefile.txt /usr/ /usr/bin/ /usr/lib/FilesA file is structured as a sequence of bytes, modeled after the notion of a tape:“Text contents of some file go here.”Te x t c o n t e n t s o f...start of file file offset(similar to tape head)I/O librariesKernelUser processopen, read, write, close, select, poll, ...(direct to kernel I/O)stdio: fopen, fread, fwrite, fclose, ...(buffered I/O)kernel system call handlerfileI/OterminalI/OpipeI/OnetworkI/OaudioI/OLMP1QueueingFiles OverviewFile I/OBuffered I/O: stdio.hWe've previously used stdio.h lightly:printf(3)fprintf(3)etc.The stdio functions performing buffering:Read a large chunk from a fileWhen the user requests a few bytes, just read them out of the buffer ⇒ lower overheadUnbuffered kernel I/OInternally, stdio calls kernel I/O functions:read(2)write(2)open(2)close(2)These directly call into the kernel, and only read/write as much as caller requested.File descriptorsstdio uses a FILE * to denote an open file:FILE *stdin, *stdout, *stderr;The kernel uses int's as file descriptors:0 mean standard input1 means standard output2 means standard error...File descriptorsA file actslike a tape....Array in kernel:fd = 1fileoffsetText contents of somefile go here...read(2)#include <unistd.h>ssize_t read(int fd, void *buf, size_t count);Blocks until data is available.write(2)#include <unistd.h>ssize_t write(int fd, void *buf, size_t count);Blocks until data can be written(e.g., pipes block: cat file | grep text).open(2)#include <sys/types.h>#include <sys/stat.h>#include <fcntl.h>int open(const char *pathname, int flags, mode_t mode);Flags set access: read, write, append, etc.close(2)#include <unistd.h>int close(int fd);Any file can be closed—even standard input!Example: show file contentsWe'll write a program to print the contents of a file to the terminal (similar to cat, but for one file).$ ./show-file somefile.txtText contents of somefile go here.$Uses open(2), read(2), write(2), close(2).lseek(2)#include <sys/types.h>#include <unistd.h>off_t lseek(int fd, off_t offset, int whence);Moves the file offset. whence is one of SEEK_SET, SEEK_CUR, or SEEK_END.Returns the new offset.FilesA file is structured as a sequence of bytes, modeled after the notion of a tape:“Text contents of some file go here.”Te x t c o n t e n t s o f...start of file file offset(use lseek() to move or read position)Example: get byte at offsetNow we'll write a program to print the byte at a given offset in a file, or by default, the file length.$ ./get-byte somefile.txt35$ ./get-byte somefile.txt 3t$Uses lseek(2) plus functions from before.LMP1QueueingFiles OverviewFile I/OENDPolling multiple filesWhat if you have two file descriptors open, and want to wait for input on either one?Example:A web server connected to multiple clientsUnix solutions:select(2) or poll(2)select(2)#include <sys/select.h>int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *errorfds, struct timeval *timeout);Waits until read or write will not block, or an error, or timeout expires.select(2) related macrosClear out (empty) a set of file descriptors:void FD_ZERO(fd_set *fdset);Add a file descriptor to a set:void FD_SET(int fd, fd_set *fdset);Remove a file descriptor from a set:void FD_CLR(int fd, fd_set *fdset);Check if a file descriptor is in a set:int FD_ISSET(int fd, fd_set *fdset);poll(2)#include <poll.h>int poll(struct pollfd *fds, nfds_t nfds, int timeout);struct pollfd { int fd; short events; short revents;};Some poll(2) eventsPOLLINData is available to readPOLLOUTWriting now will not blockPOLLERRError conditionPOLLHUPHang up (output
View Full Document