Implementing a Buffer Cache | Assignment 2 | Operating System

Brief Information

Title: Implementing a Buffer Cache
Hand-in date: 2016-04-14 Mon.
Due date: 2016-05-13 Wed.
How to do the assignment: (pdf files)
- Operating System) Assignment 2) Homework2-1(partially edited by SJ).pdf
- Operating System) Assignment 2) Homework2-2(partially edited by SJ).pdf

Trace

2016-04-12 Tue.: Homework 2-1.pptx handed in. The file was explained on this day.
2016-04-14 Thu.: Homework 2-2.pptx handed in.?The file was explained on this day.
2016-04-30 Sat.: Read Homework 2-1.pptx.
2016-04-30 Sat. 4:53PM: Step 1 has been done.
2016-04-30 Sat. 10:37PM: Step 2 has been done.
2016-05-01 Sun. 12:09AM: Read Homework 2-1.pptx.?BufInit() has been implemented. Step 3?has been done.
2016-05-01 Sun. 11:41AM: void AddNewBufIntoLruList(Buf* pBuf)?has been implemented.?Step 4-1 has been done.
2016-05-01 Sun. 12:11PM: Buf* GetBufFromLruList(Buf* pBuf)?has been implemented.?Step 4-2 has been done.
2016-05-01 Sun. 1:39PM: void UpdateBufAsMru(Buf* pBuf)?has been implemented.?Step 4-3 has been done.
2016-05-01 Sun. 3:49PM: void BufRead(int blkno, void* pData) has been implemented. Two suspicious design: [1] if a buffer is got from the free list, is the buffer inserted into the head or tail of a hash? [2] “Copy data in the buffer to pData”, does it mean pData = pBuf->pMem??Step 5 has been done.
2016-05-01 Sun. 9:54PM: void BufWrite(int blkno, void* pData) has been implemented.?Step 6 has been done.
2016-05-01 Sun. 10:23PM: void BufSync(void) has been implemented.?Step 7 has been done.?BufInit() has been updated.
2016-05-02 Mon. 4:06PM: Step 8 has been done.
2016-05-02 Mon. 4:06PM: Step 9, 10 and 11 have been done.?BufWrite and BufRead have been edited.
2016-05-03 Tue. 1:20AM: Step 12?has been done.
2016-05-03 Tue. 5:45PM: Step 14 has been done. But I did not test those functions.
2016-05-03 Tue. 6:21PM: Step 13 has been done.
2016-05-04?Wed.: Debug bugs aroused by testcase.c
2016-05-04 Wed.: Step 16 has been done. I implemented the daemon system using process signals.
2016-05-04 Wed.: Create makefile and organize files to submit.
2016-05-04?Wed. 10:22PM: The assignment has been submitted.
Total time = 8(Sat.) + 7(Sun.) + 7.25(Mon.)?+ 5(Tue.) + 7.25(Wed.) =approx. 34.5 hrs

Steps to Conquer the Assignment

Modify the header hw2.h used in Assignment 1 following the instruction. Then, check the whole program works correctly using the test code.
Modify the name of functions and their arguments in the source file hw2.c. Then, Then, check the whole program works correctly using the test code.
Implement void BufInit().
Make a function that renew the LRU list when a new buffer is added or a buffer in the list is used again. (Subtask:
- [1] Make a function that adds a new buffer in the list.
- [2] Make a function that return a result whether a buffer exists in the LRU list.
- [3] Make a function that renew an existing buffer as the MRU.)
Implement?void BufRead(int blkno, void* pData).
Implement?void BufWrite(int blkno, void* pData).
Implement?void BufSync(void).
Make a function that returns the number of buffers in the free list. The function is going to be used with buffer replacement.
Learn how to use clone().
Make a daemon thread just for testing the thread behavior.
Make the real daemon thread.
Implement?void GetBufInfoInLruList(Buf** ppBufInfo, int* pNumBuf).
Implement void GetBufInfoByListNum(BufList listnum, Buf** ppBufInfo, int* pNumBuf).
Use Dev functions.
- DevCreateDisk, DevOpenDisk?in BufInit.
- DevWriteBlock in BufSync, BufDaemon.
- DevReadBlock in BufRead.
Execute testcase.c and solve bugs in my source codes. It requires to edit overall source code I have made.
Implement daemon system.

Given Template C Source Codes

hw2.h

#ifndef __HW2_H__

#define __HW2_H__


#define HASH_TBL_SIZE    (8)
#define MAX_BUFLIST_NUM  (3)
#define BLKNO_INVALID  (-1)


/* 추가됨: 전체 버퍼의 개수, 즉, 초기에 free list에서 생성될 버퍼의 개수 */
#define MAX_BUF_NUM      (10)


typedef struct Buf Buf;

typedef enum {   
	FALSE = 0,
	TRUE = 1
} BOOL;

typedef enum __BufState 
{
	BUF_STATE_CLEAN = 0,
	BUF_STATE_DIRTY = 1
} BufState;

typedef enum __BufList
{
    BUF_LIST_DIRTY = 0,
    BUF_LIST_CLEAN = 1,
    BUF_LIST_FREE = 2
} BufList;

struct Buf
{
    int			blkno;
    BufState		state;
    void*		pMem;
    int			atime;
    Buf*		phPrev;	/* the previous pointer in hash linked list */
    Buf*		phNext; /* the next pointer in hash linked list */
    Buf*		poPrev; /* the previous pointer in object linked list */
    Buf*		poNext; /* the next pointer in object linked list */
    Buf*		plPrev;
    Buf*		plNext;
};

Buf*  ppHashHead[HASH_TBL_SIZE];
Buf*  ppHashTail[HASH_TBL_SIZE];

Buf*  ppObjListHead[MAX_BUFLIST_NUM];
Buf*  ppObjListTail[MAX_BUFLIST_NUM];


Buf*  pLruListHead;
Buf*  pLruListTail;



extern void		BufInit(void);
extern void		BufRead(int blkno, void* pData);
extern void		BufWrite(int blkno, void* pData);
extern void		BufSync(void);
extern void		BufFinish(void);	// modified....


/*
 * GetBufInfoByListNum: Get all buffers in a list specified by listnum.
 *                      This function receives a memory pointer to "ppBufInfo" that can contain the buffers.
 */
extern void           GetBufInfoByListNum(BufList listnum, Buf** ppBufInfo, int* pNumBuf);



/*
 * GetBufInfoInLruList: Get all buffers in a list specified at the LRU list.
 *                         This function receives a memory pointer to "ppBufInfo" that can contain the buffers.
 */
extern void           GetBufInfoInLruList(Buf** ppBufInfo, int* pNumBuf);



#endif /* __HW2_H__ */

#ifndef __HW2_H__

#define __HW2_H__

#define HASH_TBL_SIZE (8)

#define MAX_BUFLIST_NUM (3)

#define BLKNO_INVALID (-1)

/* 추가됨: 전체 버퍼의 개수, 즉, 초기에 free list에서 생성될 버퍼의 개수 */

#define MAX_BUF_NUM (10)

typedef struct Buf Buf;

typedef enum {

FALSE = 0,

TRUE = 1

} BOOL;

typedef enum __BufState

{

BUF_STATE_CLEAN = 0,

BUF_STATE_DIRTY = 1

} BufState;

typedef enum __BufList

{

BUF_LIST_DIRTY = 0,

BUF_LIST_CLEAN = 1,

BUF_LIST_FREE = 2

} BufList;

struct Buf

{

int blkno;

BufState state;

void* pMem;

int atime;

Buf* phPrev; /* the previous pointer in hash linked list */

Buf* phNext; /* the next pointer in hash linked list */

Buf* poPrev; /* the previous pointer in object linked list */

Buf* poNext; /* the next pointer in object linked list */

Buf* plPrev;

Buf* plNext;

};

Buf* ppHashHead[HASH_TBL_SIZE];

Buf* ppHashTail[HASH_TBL_SIZE];

Buf* ppObjListHead[MAX_BUFLIST_NUM];

Buf* ppObjListTail[MAX_BUFLIST_NUM];

Buf* pLruListHead;

Buf* pLruListTail;

extern void BufInit(void);

extern void BufRead(int blkno, void* pData);

extern void BufWrite(int blkno, void* pData);

extern void BufSync(void);

extern void BufFinish(void); // modified....

* GetBufInfoByListNum: Get all buffers in a list specified by listnum.

* This function receives a memory pointer to "ppBufInfo" that can contain the buffers.

extern void GetBufInfoByListNum(BufList listnum, Buf** ppBufInfo, int* pNumBuf);

* GetBufInfoInLruList: Get all buffers in a list specified at the LRU list.

* This function receives a memory pointer to "ppBufInfo" that can contain the buffers.

extern void GetBufInfoInLruList(Buf** ppBufInfo, int* pNumBuf);

#endif /* __HW2_H__ */

hw2.c

#include <stdio.h>
#include "hw2.h"

void BufInit(void)
{

}

void BufRead(int blkno, void* pData)
{

}

void BufWrite(int blkno, void* pData)
{

}

void BufSync(void)
{

}

void BufFinish(void)
{

}

#include <stdio.h>

#include "hw2.h"

void BufInit(void)

{

}

void BufRead(int blkno, void* pData)

{

}

void BufWrite(int blkno, void* pData)

{

}

void BufSync(void)

{

}

void BufFinish(void)

{

}

Disk.h

#ifndef __DISK_H__
#define __DISK_H__


#define BLOCK_SIZE (512*2)

extern void DevCreateDisk(void);

extern void DevOpenDisk(void);
    
extern void DevReadBlock(int blkno, char* pBuf);

extern void DevWriteBlock(int blkno, char* pBuf);

extern int DevGetDiskReadCount(void);

extern int DevGetDiskWriteCount(void);

extern void DevResetDiskAccessCount(void);

#endif /* __DISK_H__ */

#ifndef __DISK_H__

#define __DISK_H__

#define BLOCK_SIZE (512*2)

extern void DevCreateDisk(void);

extern void DevOpenDisk(void);

extern void DevReadBlock(int blkno, char* pBuf);

extern void DevWriteBlock(int blkno, char* pBuf);

extern int DevGetDiskReadCount(void);

extern int DevGetDiskWriteCount(void);

extern void DevResetDiskAccessCount(void);

#endif /* __DISK_H__ */

Disk.c

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <string.h>
#include <assert.h>
#include "Disk.h"

int fd; 
int diskReadCount = 0;
int diskWriteCount = 0;

void DevResetDiskAccessCount(void)
{
	diskReadCount = diskWriteCount = 0;
}

int DevGetDiskReadCount(void)
{
	return diskReadCount;
}

int DevGetDiskWriteCount(void)
{
	return diskWriteCount;
}

void DevCreateDisk(void)
{
    fd = open("MY_DISK", O_RDWR | O_CREAT | O_TRUNC, 0644);
}

void DevOpenDisk(void)
{
	fd = open("MY_DISK", O_RDWR);
}

void __DevMoveBlock(int blkno){
    lseek(fd, (off_t)+(BLOCK_SIZE*blkno),SEEK_SET);
}

void DevReadBlock(int blkno, char* pBuf)
{
   __DevMoveBlock(blkno);
   read(fd, pBuf, BLOCK_SIZE);
   diskReadCount++;
}

void DevWriteBlock(int blkno, char* pBuf)
{
   __DevMoveBlock(blkno);
   write(fd, pBuf, BLOCK_SIZE);
   diskWriteCount++;
}

#include <stdio.h>

#include <stdlib.h>

#include <fcntl.h>

#include <sys/types.h>

#include <sys/stat.h>

#include <string.h>

#include <assert.h>

#include "Disk.h"

int fd;

int diskReadCount = 0;

int diskWriteCount = 0;

void DevResetDiskAccessCount(void)

{

diskReadCount = diskWriteCount = 0;

}

int DevGetDiskReadCount(void)

{

return diskReadCount;

}

int DevGetDiskWriteCount(void)

{

return diskWriteCount;

}

void DevCreateDisk(void)

{

fd = open("MY_DISK", O_RDWR | O_CREAT | O_TRUNC, 0644);

}

void DevOpenDisk(void)

{

fd = open("MY_DISK", O_RDWR);

}

void __DevMoveBlock(int blkno){

lseek(fd, (off_t)+(BLOCK_SIZE*blkno),SEEK_SET);

}

void DevReadBlock(int blkno, char* pBuf)

{

__DevMoveBlock(blkno);

read(fd, pBuf, BLOCK_SIZE);

diskReadCount++;

}

void DevWriteBlock(int blkno, char* pBuf)

{

__DevMoveBlock(blkno);

write(fd, pBuf, BLOCK_SIZE);

diskWriteCount++;

}

Study of Everything

Learning Based Life

Implementing a Buffer Cache | Assignment 2 | Operating System

Brief Information

Trace

Steps to Conquer the Assignment

Given Template C Source Codes

A Source Code to Test

References

Leave a Reply Cancel reply

Brief Information

Trace

Steps to Conquer the Assignment

Given Template C Source Codes

A Source Code to Test

References

Related Posts

Leave a Reply Cancel reply