Unit 2.1 Introduction to Kernel.ppt (Kernel Services and Architecture)

This is for learning purpose. This will help engineering students to learn Operating System in details.

1. Operating System and Administration
UNIT-II
Introduction To The Kernel
Reference:
“TheDesignoftheUNIXOperating
System”,byMauriceJ.Bach.
17/05/2024 1

2. Objectives
•Tounderstandsystemkernelarchitecture.
•Tounderstandfilessubsystemandprocesscontrol
subsystemofkernel.
•TolearnandunderstandProcessstatesand
contexts.
17/05/2024 2

3. Contents
•ArchitectureofUnixOperatingSystem
•IntroductiontotheSystemConcepts
–Anoverviewofthefilesubsystem
–Processes
•Contextofaprocess
•Processstates
•Statetransitions
•Sleepandwakeup
•KernelDataStructure
•SystemAdministration
17/05/2024 3

4. What is Kernel
•Itactsasaninterfacebetweentheuser
applicationsandthehardware.
•Themaintasksofthekernel
are:
–Processmanagement
–Devicemanagement
–Memorymanagement
–Interrupthandling
–I/Ocommunication
–Filesystem...etc..
17/05/2024 4

5. Contents
•ArchitectureofUnixOperatingSystem
17/05/2024 5
•Introduction to the System Concepts
–An overview of the file subsystem
–Processes
•Context of a process
•Process states
•State transitions
•Sleep and wakeup
•Kernel Data Structure
•System Administration

6. Architecture of the UNIX
•Unixsystemsupportstwocentralconcepts
–Filesystem:has“Places”
(basicunitofinformationstorage)
– -Processes:have“life”
– (basicunitofcomputation)
17/05/2024 6

7. 7
Block Diagram of System Kernel
Libraries
System Call Interface
File Subsystem
Process
Control
Subsystem
Inter-process
Communication
Scheduler
Memory
Management
Hardware Control
Hardware
Buffer Cache
Device Drivers
Character Block
User Level
Kernel
Level
Kernel Level
Hardware Level
Trap
User Programs
17/05/2024

8. 8
System calls & Libraries
Libraries
System Call Interface
File Subsystem
Process
Control
Subsystem
Inter-process
Communication
Scheduler
Memory
Management
Hardware Control
Hardware
Buffer Cache
Device Drivers
Character Block
User Level
Kernel
Level
Kernel Level
Hardware Level
Trap
User Programs
17/05/2024

9. System calls & Libraries
•Systemcalllibrary
–SystemcallsinuserprogramslookslikenormalCfunction.
–ThenlibrariesmapsthemtoprimitivesrequirestoenterinOS.
•Standardlibrary
–UserprogramuseslibrariessuchasstandardI/O.
–Linkedwiththeprogramsatcompiletimeandarepartofthe
userprogram
17/05/2024 9

10. System calls & Libraries
•Systemcallsinteractswithfilesubsystem
–Managingfilesandstructuresoffilesystem
–Allocatingfilespace
–Administeringfreespace
–Controllingaccesstofiles
–Retrievingdataforusers
•Systemcallsforprocesstointeractwithfilesubsystem
–open(toopenfileforreading/writing)&close
–read&write
–stat(toquerytheattributesoffile)
–chown(tochangetherecordofwhoownsthefile)
–chmod(tochangeaccesspermissionsofafile)
17/05/2024 10

11. 11
File Subsystem
Libraries
System Call Interface
File Subsystem
Process
Control
Subsystem
Inter-process
Communication
Scheduler
Memory
Management
Hardware Control
Hardware
Buffer Cache
Device Drivers
Character Block
User Level
Kernel
Level
Kernel Level
Hardware Level
Trap
User Programs
17/05/2024

12. 12
Buffering Mechanism
Libraries
System Call Interface
File Subsystem
Process
Control
Subsystem
Inter-process
Communication
Scheduler
Memory
Management
Hardware Control
Hardware
Buffer Cache
Device Drivers
Character Block
User Level
Kernel
Level
Kernel Level
Hardware Level
Trap
User Programs
17/05/2024

13. 13
Buffering Mechanism (Cont..)
•InteractwithblockI/Odevicedriverstoinitiate
datatransfertoandfromkernel.
•Devicedriversarethekernelmodulesthatcontrols
operationsofperipheraldevices.
•BlockI/Odevicesarerandomaccessstorage
devices.
–SuchasTapeunit,
–harddisk,
–USBcamerasetc.
17/05/2024

14. •Filesubsystemalsointeractswith“raw”I/O
devicedriverswithoutbufferingmechanism.
•Rawdevicesalsocalledascharacterdevices.
–Suchasserialport,
–parallelport,
–soundcards,etc.
17/05/2024 14
File Subsystem

15. 15
Process Control Subsystem
Libraries
System Call Interface
File Subsystem
Process
Control
Subsystem
Inter-process
Communication
Scheduler
Memory
Management
Hardware Control
Hardware
Buffer Cache
Device Drivers
Character Block
User Level
Kernel
Level
Kernel Level
Hardware Level
Trap
User Programs
17/05/2024

16. 16
Process Control Subsystem (Cont..)
•Responsibleforprocesssynchronization
•Inter-processcommunication(IPC)
•Memorymanagement
•Processscheduling
•Communicatewithfilesubsystem
–Loadingafileintomemoryforexecution
•Interactwithsetofsystemcalls
–fork(tocreatenewprocess)
–exec(tooverlayimageofprogramontorunningprocess)
–exit(tofinishexecutingprocess)
–wait(synchronizeprocessexecutionwithexitofpreviouslyforkedprocess)
–brk(tocontrolsizeofmemoryallocatedtoaprocess)
–signal(tocontrolprocessresponsetoextraordinaryevents)
17/05/2024

17. 17
Process Control Subsystem (Cont..)
•Memorymanagementmodule
–Controltheallocationofmemorytoaprocess
–Inabsenceofenoughmemorykernelmovesprocessesbetweenmainmem.&
sec.mem.
–Memorymanagementisdonewithswapping&demandpaging
•Schedulermodule
–AllocatetheCPUtoprocesses
•Interprocesscommunication
–Thereareseveralforms.
•Asynchronoussignalingofevents
•Synchronoustransmissionofmessagesbetweenprocesses.
17/05/2024

18. 18
Hardware Control
Libraries
System Call Interface
File Subsystem
Process
Control
Subsystem
Inter-process
Communication
Scheduler
Memory
Management
Hardware Control
Hardware
Buffer Cache
Device Drivers
Character Block
User Level
Kernel
Level
Kernel Level
Hardware Level
Trap
User Programs
17/05/2024

19. 19
Hardware Control (Cont..)
•Responsibleforhandlinginterruptsandfor
communicatingwiththemachine.
•Devicessuchasdisksorterminalsmayinterrupt
theCPUwhileaprocessisexecuting.
•Ifso,kernelmayresumeexecutionofinterrupted
processafterservicingtheinterrupt.
17/05/2024

20. Contents
•ArchitectureofUnixOperatingSystem
•IntroductiontotheSystemConcepts
–Anoverviewofthefilesubsystem
–Processes
•Contextofaprocess
•Processstates
•Statetransitions
•Sleepandwakeup
•KernelDataStructure
•SystemAdministration
17/05/2024 20

21. 17/05/2024
Files
•Whatisfile?
–Acontainerfordatawithname
•contiguous/non-contiguousstorage
•Typesoffiles
21

22. Overview of File Subsystem
•Eachfileondiskhasanassociateddatastructure
intheoperatingsystem,calledan"inode"
17/05/2024 22

23. Inode Structure
17/05/2024 23

24. •Severalfilenamesmaybeassociatedwitha
singleinode,buteachfileiscontrolledby
exactlyONEinode.
•ls–i(togetinodenumber)
•$ls-li/tmp/a/home/bob/xfile/var/tmp/file
114693-rw-r-r-3hjchjc5Sep613:55/tmp/a
114693-rw-r-r-3hjchjc5Sep613:55/home/bob/xfile
114693-rw-r-r-3hjchjc5Sep613:55/var/tmp/file
17/05/2024 24
Overview of File Subsystem (cont..)
Inode
no.
Permissions Link countOwner/group size Time Stamp

25. Finding a file’s Inode on Disk
17/05/2024 25

26. Example
•whenauserissuesopen(``/etc/passwd'',...)the
kernelperformsthefollowingoperations:
–kernelfindstheinodeoftherootdirectoryandsearchthe
correspondingfilefortheentry``etc''
•whentheentry``etc''isfound,fetchitscorrespondinginodeandcheck
thatitisoftypedirectory
–scanthefileassociatedwith``/etc''lookingfor``passwd'‘
–finally,fetchtheinodeassociatedwithpasswd'sdirectoryentry,
verifythatitisaregularfile,andstartaccessingthefile.
17/05/2024 26

27. •InodeTable
–ListofallI-nodes
•GlobalFiletable
–Itisglobaltothekernel
–Itkeepstrackofthebyteoffsetinthefilewheretheuser'snextread/write
willstart.
–Italsokeepstrackoftheaccessrightsallowedtotheopeningprocess.
•User/ProcessFileDescriptortable
–localtoeveryprocess
–containsinformationliketheidentifiersofthefilesopenedbytheprocess.
–Whenever,aprocesscreates/openafile,itgetsanindexfromthistable
calledas”FileDescriptor”.
Data Structure for File Access
17/05/2024 27
User File
Descriptor Table
File
Table
Inode
Table

28. Interaction between tables with an Example
•Example:
•Process A:
fd1 = open("/var/file1", O_RDONLY);
fd2 = open("/var/file2", O_RDWR);
fd3 = open("/var/file1", O_WRONLY);
•Process B:
fd1 = open("/var/file1", O_RDONLY);
fd2 = open("/var/file3", O_RDONLY);
17/05/2024 28

29. File Descriptors, File Table and Inode
table
17/05/2024 29

30. Explanation of figure
•Eachopen()returnsafiledescriptortotheprocess,andthe
correspondingentryintheuserfiledescriptortablepointstoa
uniqueentryintheglobalfiletableeventhoughafile(/var/file1)is
openedmorethenonce.
•Theseglobalfiletableentriesmaptothein-coreinodetableentry.
Everyopenedfilehasauniqueentryintheglobalfiletableand
theuserfiledescriptortablebutkernelkeepsonlysingleentryper
fileinthein-coreinodetable.
•Separateentriesarecreatedinuserfiledescriptorandglobalfile
table,butonlythereferencecountisincreasedintheinodetable.
Allthesystemcallsrelatedtofilehandlingusethesetablesfor
datamanipulation.
17/05/2024 30

31. File System
17/05/2024 31
Physical Drive
Files and Directories Partitions

32. File System
•A file system is consists of a sequence of logical blocks
(512/1024 byte etc.)
17/05/2024 32
partition partition partition
disk drive
file system
super
block
boot
block
I-list
Data blocks for files, dirs, etc.
. . . . . . . .
.
i-nodei-nodei-node i-node

33. File System: Boot Block
•Typicallyoccupiesthefirstsectorofthe
disk
•Holdsbootprogram,ashortprogramfor
loadingthekernelofOSandlaunchingit
17/05/2024 33

34. File System: Super Block
•Containsinformationaboutthegeometryofthe
physicaldisk
•Describesthestateofafilesystem
•Describesthesizeofthefilesystem
•achainoffreedatablocknumbers
•achainoffreei-nodenumbers
17/05/2024 34

35. File System: Inode List
•Inodesareusedtoaccessdiskfiles.
•Inodesmapsthediskfiles
•Foreachfilethereisaninodeentryintheinode
listblock
•Inodelistalsokeepstrackofdirectorystructure
17/05/2024 35

36. File System: Data Block
•Startsattheendoftheinodelist
•Containsdiskfiles(Data)
•Anallocateddatablockcanbelongtooneand
onlyonefileinthefilesystem
17/05/2024 36

37. Contents
•ArchitectureofUnixOperatingSystem
•IntroductiontotheSystemConcepts
–Anoverviewofthefilesubsystem
–Processes
•Contextofaprocess
•Processstates
•Statetransitions
•Sleepandwakeup
•KernelDataStructure
•SystemAdministration
17/05/2024 37

38. Processes
•Aprocessistheexecutionofaprogram
•Aprocessisconsists
–objectcode(program)tobeexecuted
–datawhichtheprocessworkson
–Stack
–Requiredresources
17/05/2024 38
Code Data
Status
Resource R
0
Resource R
1
Resource R
N
Abstract Machine Environment (OS)
Process P
k

39. •Manyprocesscanrunsimultaneouslyaskernelschedules
themforexecution
•Severalprocessesmaybeinstancesofoneprogram
•Aprocessreadsandwritesitsdataandstacksections,but
itcannotreadorwritethedataandstackofother
processes
•AprocesscommunicateswithallprocessesinUNIX
systemarecreatedbytheforksystemcall,exceptthevery
firstprocess(process0)whichiscreatedbythesystem
bootcode
17/05/2024 39
Processes (Cont..)

40. Process (Cont..)
17/05/2024 40
•Kernelloadsanexecutablefileintomemory
during‘exec’systemcall’
•Loadedprocessconsistoftext,data,&stack.
•Stackconsistoflogicalstackframes
•StackFramehas
–Localvariables,addressofpreviousframe,returnaddress,parametersto
function

41. #include<fcntl.h>
charbuffer[2048];
intversion™1;
main(argc,argv)
intargc;
char*argv[];
{
intfdold,fdnew;
if(argc!=-3)
{printfC'need2argumentsforcopyprogram\n");
exit(l);
}
fdold=-open(argv[l],O_RDONLY);
/*opensourcefilereadonly*/
if(fdold1)
{printf("cannotopenfile%s\n",argv[l]);
exit(l);
}
fdnew-creat(argv[2],0666);/*createtargetfilerwforall*/
if(fdnew---1){printf("cannotcreatefile%s\n",argv[2]);exit(1);}
copy(fdold,fdnew);
exit(l);
}
41
Processes (Cont..)
copy(old,new)
intold,new;
{
intcount;
while((count-readfold,buffer,sizeof(buffer)))>
0)
write(new,buffer,count);
}
17/05/2024

42. 17/05/2024 42
Processes (Cont..)
Addr of Frame 2
Ret addr after write call
Local
Vars
not
shown
params to
write
new buffer
count
Addr of Frame 1
Ret addr after copy call
Local
Vars
count
params to
copy
old
new
Addr of Frame 0
Ret addr after main call
Local
Vars
fdold
fdnew
params to
main
argc
argv
user stack
Addr of Frame 1
Ret addr after func2 call
Local
Vars
parms to kernel func2
Addr of Frame 0
Ret addr after func1 call
Local
Vars
params to kernel
func1
kernel stack
frame 3
call write()
frame 2
call copy()
frame 1
call main()
frame 3
frame 2
call func2()
frame 1
call func1()
frame 0 start frame 0 system call
interface
Direction of
stack growth

43. Processes (Cont..)
•Kernelhasaprocesstablethatkeepstrackof
allactiveprocesses
•Processtablecontainsaperprocessregion
tablewhoseentrypointstoentriesinregion
table.
17/05/2024 43

44. Data Structures for Process
17/05/2024 44
uarea
main memory
region table
per process
region table
process table

45. •Fieldsofprocesstableentry:
–Statefield
–UserID(UID)-ownerofprocess
–Aneventdescriptorsetwhenaprocessissuspended
•upointer(address)
17/05/2024 45
Process: Process Table
User

46. Process: Region Table
•Aregionisacontiguousareaofaprocess’s
addressspacesuchas
–text,dataandstack.
•Regiontableentriesdescribestheattributesof
theregion,suchas
–whetheritcontainstextordata,
–whetheritissharedorprivateand
–Wherethe“data”ofregionislocatedinmemory
17/05/2024 46

47. Process: U Area
•UAreaistheextensionofprocesstableentry
•FieldsofUArea
–Pointertoprocesstableentryofcurrentlyexecutingprocess
–Parametersofthecurrentsystemcall,returnvaluesanderror
codes.
–Filedescriptorsofallopenfiles
–Currentdirectoryandcurrentroot
–I/Oparameters
–Processandfilesizelimit
•KernelcandirectlyaccessfieldsoftheUAreaofthe
executingprocessbutnotoftheUAreaofotherprocesses
17/05/2024 47

48. Contents
•ArchitectureofUnixOperatingSystem
•IntroductiontotheSystemConcepts
–Anoverviewofthefilesubsystem
–Processes
•Contextofaprocess
•Processstates
•Statetransitions
•Sleepandwakeup
•KernelDataStructure
•SystemAdministration
17/05/2024 48

49. Process Context
•Thecontextofaprocessisitsstate,whichis
definedby
–Itstext,
–Valuesofglobaluservariables,datastructures,and
machineregisters
–ValuesstoredinProcesstableandUArea
–Contentsofuserandkernelstack
•Whenexecutingaprocess,thesystemissaidto
beexecutinginthecontextoftheprocess.
17/05/2024 49

50. Context Switch
•Whenthekerneldecidesthatitshouldexecute
anotherprocess,itdoesacontextswitch,sothat
thesystemexecutesinthecontextoftheother
process
•Whendoingacontextswitch,thekernelsaves
enoughinformationsothatitcanlaterswitch
backtothefirstprocessandresumeits
execution.
17/05/2024 50

51. Mode of Process Execution
•TheUNIXprocessrunsintwomodes:
–Usermode
•Canaccessitsowninstructionsanddata,butnotkernel
instructionanddata
–Kernelmode
•Canaccesskernelanduserinstructionsanddata
•requiresspecialinstructionsequencetochangefromuser
tokernelmode
•Whenaprocessexecutesasystemcall,the
executionmodeoftheprocesschangesfrom
usermodetokernelmode
17/05/2024 51

52. Mode of Process Execution (cont..)
•Whenmovingfromusertokernelmode,the
kernelsavesenoughinformationsothatitcan
laterreturntousermodeandcontinueexecution
fromwhereitleftoff.
•Modechangeisnotacontextswitch,just
changeinmode.
17/05/2024 52

53. Contents
•ArchitectureofUnixOperatingSystem
•IntroductiontotheSystemConcepts
–Anoverviewofthefilesubsystem
–Processes
•Contextofaprocess
•ProcessstatesandStatetransitions
•Sleepandwakeup
•KernelDataStructure
•SystemAdministration
17/05/2024 53

54. Process States
•Lifetimeofprocesscanbedividedintoaset
ofstates.
•Processstatesare:
–Usermode:currentlyexecuting
–Kernelmode:currentlyexecuting
–Readytorun:soonastheschedulerchoosesit
–Sleeping:waitingforI/Otocomplete.
17/05/2024 54

55. Process State Transition
17/05/2024 55
1
2
4 3
kernel
running
user
running
context switch
permissible
ready to run
returnsys call
or interrupt
interrupt,
interrupt return
schedule
processsleep
wakeup

56. Process State Transition(cont..)
•Thekernelallowsacontextswitchonlywhena
processmovesfromthestatekernelrunningto
thestateasleep
•Processrunninginkernelmodecannotbe
preemptedbyotherprocesses.
•Kernelmaintainsconsistencyofitsdata
structuresbecauseitisnon-preemptive,uses
mutualexclusiontorestrictcriticalsection.
17/05/2024 56

57. Example
structqueue{
}*bp,*bpl;
bpl—>forp—bp—>forp;
bpl—>backp—bp;
bp—>forp—bpl;
/*considerpossiblecontextswitchhere*/
bp1—>forp—>backp~bpl;
•Unixpreventssuchsituationbydisallowing
contextswitchingwhenprocessisinkernelmode.
17/05/2024 57

58. Contents
•ArchitectureofUnixOperatingSystem
•IntroductiontotheSystemConcepts
–Anoverviewofthefilesubsystem
–Processes
•Contextofaprocess
•ProcessstatesandStatetransitions
•Sleepandwakeup
•KernelDataStructure
•SystemAdministration
17/05/2024 58

59. Sleep and wakeup
•Processgotosleepwhenawaitingtohappensome
eventsuchas
–WaitingforI/Ocompletion
–Waitingforprocesstoexit
–Waitingforsystemresourcestobecomeavailable
–Andsoon
•Wheneventoccursallsleepingprocessonthat
eventgetwakeupandenterin“readytorun”state
•SleepingprocessesdonotconsumeCPUresources
17/05/2024 59

60. Sleep and wakeup (cont..)
•Locks
–usedtolocksomeshareddatastructuresandotherresources.
•Implementationoflock
while(conditionistrue)
sleep(event:conditionbecomesfalse);
setconditiontrue;
•Wheneventoccurunlockthelockandawakensall
processesasleeponlock.
setconditionfalse;
wakeup(event:conditionisfalse);
•ConsiderprocessesA,BandCcontendedforalocked
buffer.
17/05/2024 60

61. 17/05/2024 61

62. Kernel Data Structures
•Fixedsizetables
–Advantage:Kernelcodeissimple
–Disadvantage:Limitsno.ofentriesintable
–Iftablesizeexceedskernelshouldreporterrorto
user.
•Dynamicallocation
–Excesstablespaceiswasted
•ForsimplicityofkernelalgorithmsFixedsize
tablesareused.
17/05/2024 62

63. System Administration
•AdministrativeProcessesareusedtoperformvariousfunctionsfor
generalwelfareofusercommunity.
–Diskformatting
–Creationofnewfilesystems
–Repairofdamagedfilesystems
–Kerneldebugging,etc…
•Administrativeprocessesaredistinguishedintermsofrightsand
privilegesprovidedtothem.
–Eg.Fileaccesspermissionsallowsmanipulationtoadministrativeprocessnot
touserprocess.
•Superuser
–hasspecialprivileges.
–Usermaybecomesuperuserbyusinglogin-password.
17/05/2024 63

64. Exercise
•Assignment1:
Whatshouldhappenifthekernelattemptstoawakenallprocesses
sleepingonanevent,butnoprocessareasleepontheeventatthe
timeofthewakeup?
•Noprocessiswakenup.
–Ifschedulerfindsatleastoneprocessinthequeue,everythinggoeson.
–Ifnot,noprocesswillbescheduled,andkernelwillnothaveanythingtodosoit
willnotdoanything.Itwillbeidle.
–Thenhowwouldthekernelknow,ifitisidle,thatsomeprocesswantsittodo
something?
–Well,theansweris,schedulercomesachecksthereadytorunqueueon
every/someclockinterrupts.
17/05/2024 64

65. Exercise
•Assignment2:
Considerthefollowingsequenceofcommands:
Case1:grepmaina.cb.cc.c>grepout&
wc—1<grepout&
rmgrepout&
Theampersand("&")attheendofeachcommandlineinformsthe
shelltorunthecommandinthebackground,anditcanexecute
eachcommandlineinparallel.Whyisthisnotequivalenttothe
followingcommandline?
Case2:grepmaina.cb.cc.c|wc—1
17/05/2024 65

66. Excercise
•Assignment3:
structqueue{ }*bp,*bpl;
bp1—>forp=bp—>forp;
bp1—>backp=bp;
bp—>forp=bp1;
/*considerpossiblecontextswitchhere,andscheduled
processexecutesremove()function*/
voidremove(structqueue*qp)
{
qp—>forp—>backp=qp—>backp;
qp—>backp—>forp=qp—>forp;
qp—>forp=qp—>backp=NULL;
}
/*Returnfromcontextswitchtoexecuteremaining
code*/
bp1—>forp—>backp=bp1;
17/05/2024 66
So what is the status of the
link list if
case 1: qp = bp;
case 2: qp = bp1;
case 3: qp = Node that follows
bp in original Link List i.e.
before adding bp1.

67. 6717/05/2024