Inplementation on Unix Operating System Kernel (core of the operating system) maintains files on mass storage devices and it allows processes to store new information or to recall previously stored information. When a process wants to access data from a file, the kernel brings the data into main memory where the process can examine it and request that the data be saved in the file system again. The kernel could read and write directly to and from the disk for all the system accesses, but the system response time and the throughput would be poor due to slow disk transfer rate. The kernel therefore attempts to minimize the frequency of disk access by keeping a pool of internal data buffers, called the buffer cache which contains the data in recently used disk blocks. ( Buffer cache is software structure that should not be confused with hardware caches that speed up memory references.) When reading data from the disk, kernel attempts to read from the buffer cache. If the data is already in cache, the kernel reads the data from the cache, it does not need to read it from the disk. If the data is not in the cache, the kernel reads it from the disk and caches it by using an algorithm that tries to save as much healthy data in the cache as possible. Buffer Header During the system initialization the kernel allocates space for a number of buffers, configurable according to memory size and system performance constrains. A buffer consists of two parts: a memory array that contains data from the disk and a buffer header that identifies the buffer. There is one to one mapping of buffer headers to data arrays, the ensuing(as a sequence) text will frequently refer to both parts as a "buffer", and the context should make clear which part is being discussed.
Kernel caches data in the buffer pool according to a least recently used algorithm: after it allocates a buffer to a disk block, it cannot use the buffer for another block until all other buffers have been used more recently. The kernel maintains a free list of buffers that preserves at least recently used order. The free list is a doubly link circular list of buffers with a buffer header that marks its beginning and end. Every buffer is put on the free list when the system is booted. The kernel takes a buffer from the head of the free list when it wants any free buffer, but it can only take a buffer from the middle of the free list if it identifies a particular block in the buffer pool. In both cases, it removes the buffer from the free list. In reverse operation, when the kernel returns a buffer to the buffer pool, it usually attaches the buffer to the tail of the free list. The kernel, in some situation (error cases), attaches the buffer in the head of the list but it never adds in the middle of the list. As the kernel removes buffers from a free list, a buffer with valid data moves closer and closer to the head of the free list, therefore the buffers that are closer to the head of the list have not been used as recently as those that further from the head of the free list. ALL THE ARTICLE IS TAKEN FROM THE BOOK: THE DESING OF THE UNIX OPERATING SYSTEM( P.39-40-41)
Add node in the end void add_end(LIST *list,int *input) { NODE *temp,*pre; if(list->head==NULL) //checks if the first node is empty if so, creates a new node. { temp=(NODE*)malloc(sizeof(NODE)); temp->data=input; temp->link=NULL; list->head=temp; list->rear=temp; (list->count)++; return; //adds node sucessfully } else { temp=list->head; while(temp->link!=NULL) //goes to the last node { temp=temp->link; } pre=(NODE*)malloc(sizeof(NODE)); pre->data=input; pre->link=NULL; temp->link=pre; (list->count)++; return; //adds node sucessfully } return; //error occurs during node insertion. } Add node in a specific location void add_after(LIST *list,int after,int *input) { NODE *temp,*pre; int cntr; temp=(NODE*)malloc(sizeof(NODE)); temp=list->head; for(cntr=0;cntr<after;cntr++) // skip since desired position run into. { temp=temp->link; if(temp==NULL) // if temp is NULL it stops, not the link of temp { printf("\n There are not %d node in the list\n",after); return; } } pre=(NODE*)malloc(sizeof(NODE)); pre->link=temp->link; pre->data=input; temp->link=pre; return; } Display first node int *displayfirst(LIST *list) { return list->head->data; } Display Last node int *displaylast(LIST *list) { return list->rear->data; } Display a specific node int displayany(LIST *list, int after) { NODE *temp; int cntr; temp=(NODE*)malloc(sizeof(NODE)); if(list->count==1) { printf(" Node is %d",list->head->data); return (0); }; for(cntr=0;cntr<after;cntr++) { temp=temp->link; if(temp==NULL) { printf(" There are less that %d node in the list\n",after); return(0); } } printf(" The node is %d",temp->data); return(0); } Display node quantity int node_count(LIST *list) { return list->count; } Switch two specific node in the list void replace(LIST *list, int first, int second) { int i; NODE *temp1,*temp2,*pre1,*pre2,*replace; if(first<0 || first>(list->count) || second<0 || second>(list->count) ) { printf(" You entered wrong number of node. List contains less number of nodes than your input\n"); return; } temp1=(NODE*)malloc(sizeof(NODE)); temp2=(NODE*)malloc(sizeof(NODE)); pre1=(NODE*)malloc(sizeof(NODE)); pre2=(NODE*)malloc(sizeof(NODE)); replace=(NODE*)malloc(sizeof(NODE)); pre1=list->head; pre2=list->head; temp1=list->head; temp2=list->head; for(i=1;i<first;i++) { pre1=pre1->link; } for(i=1;i<second;i++) { pre2=pre2->link; } replace=pre1; pre1=pre2; pre2=replace; for(i=0;i<second;i++) { temp1=temp1->link; } for(i=0;i<second;i++) { temp2=temp2->link; } replace=temp1; temp1=temp2; temp2=replace; return; } Destroy list LIST* destroy (LIST* list) { NODE* des; des=(NODE *)malloc(sizeof(NODE)); if (list) { while ( (list->count) > 0 ) { free (list->head->data); des=list->head; list->head=list->head->link; (list->count)--; free (des); } free (list); } printf(" Your list has been destroyed.\n"); return NULL; } |