IT25a - Operating System Project
A extensive research work on the following:
1. One Non-Windows Operating System
2. One CPU Scheduling Algorithm
CPU Scheduling
Algorithm
First Come
First Serve (FCFS)
In the
"First come first serve" scheduling algorithm, as the name suggests,
the process which arrives first, gets executed first, or we can say that the
process which requests the CPU first, gets the CPU allocated first.
- First Come First Serve, is just like FIFO(First in First out) Queue data structure, where the data element which is added to the queue first, is the one who leaves the queue first.
- This is used in Batch Systems.
- It's easy to understand and implement programmatically, using a Queue data structure, where a new process enters through the tail of the queue, and the scheduler selects process from the head of the queue.
- A perfect real life example of FCFS scheduling is buying tickets at ticket counter.
- Process that requests the CPU FIRST is allocated the CPU FIRST.
- Also called FIFO
- Used in Batch Systems
- Real life analogy?
§ Buying tickets?
- Implementation
§ FIFO
queues
§ A
new process enters the tail of the queue
§ The
schedule selects from the head of the queue
- Performance Metric: Average Waiting Time.
- Given Parameters:
§ Burst
Time (in ms), Arrival Time and Order
First come,
first served (FCFS) is an operating system process scheduling algorithm and a
network routing management mechanism that automatically executes queued requests
and processes by the order of their arrival. With first come, first served,
what comes first is handled first; the next request in line will be executed
once the one before it is complete.
FCFS
is also known as first-in, first-out (FIFO) and first come, first choice (FCFC).
Other names of this algorithm
are:
- First-In-First-Out
(FIFO)
- Run-to-Completion
- Run-Until-Done
Perhaps,
First-Come-First-Served algorithm is the simplest scheduling algorithm is the
simplest scheduling algorithm. Processes are dispatched according to their
arrival time on the ready queue. Being a nonpreemptive discipline, once a
process has a CPU, it runs to completion.
The FCFS
scheduling is fair in the formal sense or human sense of fairness but it is
unfair in the sense that long jobs make short jobs wait and unimportant jobs
make important jobs wait.
FCFS is more predictable than
most of other schemes since it offers time. FCFS scheme is not useful in
scheduling interactive users because it cannot guarantee good response time.
The code for FCFS scheduling is simple to write and understand. One of
the major drawback of this scheme is that the average time is often quite long.
The
First-Come-First-Served algorithm is rarely used as a master scheme in modern
operating systems but it is often embedded within other schemes.
FCFS provides
an efficient, simple and error-free process scheduling algorithm that saves
valuable CPU resources. It uses nonpreemptive scheduling in which a process is
automatically queued and processing occurs according to an incoming request or
process order. FCFS derives its concept from real-life customer service.
Given n
processes with their burst times, the task is to find average waiting time and
average turnaround time using FCFS scheduling algorithm.
First in,
first out (FIFO), also known as first come, first served (FCFS), is the
simplest scheduling algorithm. FIFO simply queues processes in the order that
they arrive in the ready queue.
In this, the
process that comes first will be executed first and next process starts only
after the previous gets fully executed.
Here we are
considering that arrival time for all processes is 0.
FCFS also
termed as First-In-First-Out i.e. allocate the CPU in order in which the
process arrive. When the CPU is free, it is allowed to process, which is
occupying the front of the queue. Once this process goes into running state,
its PCB is removed from the queue. This algorithm is non-preemptive.
Let's take a
look at how FCFS process scheduling works. Suppose there are three processes in
a queue: P1, P2 and P3. P1 is placed in the processing register with a waiting
time of zero seconds and 10 seconds for complete processing. The next process,
P2, must wait 10 seconds and is placed in the processing cycle until P1 is
processed. Assuming that P2 will take 15 seconds to complete, the final process,
P3, must wait 25 seconds to be processed. FCFS may not be the fastest process
scheduling algorithm, as it does not check for priorities associated with
processes. These priorities may depend on the processes' individual execution
times.
Advantage
- Suitable
for batch system.
- It
is simple to understand and code.
Disadvantage
- Waiting
time can be large if short request wait behind the long process.
- It
is not suitable for time sharing system where it is important that each
user should get the CPU for equal amount of time interval.
Problems with FCFS Scheduling
Below we have a few shortcomings
or problems with the FCFS scheduling algorithm:
- It
is Non Pre-emptive algorithm, which means the process
priority doesn't matter.
If
a process with very least priority is being executed, more like daily
routine backup process, which takes more time, and all of a sudden
some other high priority process arrives, like interrupt to avoid
system crash, the high priority process will have to wait, and hence in
this case, the system will crash, just because of improper process scheduling.
- Not
optimal Average Waiting Time.
- Resources
utilization in parallel is not possible, which leads to Convoy
Effect, and hence poor resource(CPU, I/O etc) utilization.
What is Convoy Effect?
Convoy Effect
is a situation where many processes, who need to use a resource for short time
are blocked by one process holding that resource for a long time.
This
essentially leads to poor utilization of resources and hence poor performance.
Why
Convoy Effects?
·
Consider 100 I/O-bound processes
and 1 CPU-bound job in the system.
·
I/O-bound processes pass quickly
through the ready queue and suspend themselves waiting for I/O.
·
The CPU-bound process arrives at
head of queue and executes the program until completion.
·
I/O bound processes rejoin the
ready queue and wait for the CPU-bound processes releasing the CPU.
·
I/O devices idle until the
CPU-bound process completes.
·
In general, a convoy effect
happens when a set of processes need to use a resource for a short time, and
one process holds the resource for a long time, blocking all of the other
processes. Essentially, it causes poor utilization of the other resources in
the system.
Calculating
Average Waiting Time
For every scheduling algorithm, Average
waiting time is a crucial parameter to judge it's performance.
AWT or Average
waiting time is the average of the waiting times of the processes in the queue,
waiting for the scheduler to pick them for execution.
Lower
the Average Waiting Time, better the scheduling algorithm.
Consider the processes P1, P2,
P3, P4 given in the below table, arrives for execution in the same order, with
Arrival Time 0, and given Burst Time, let's find the average waiting time using
the FCFS scheduling algorithm.
The average waiting time will be 18.75 ms
For the above given proccesses,
first P1 will be provided with the CPU resources,
- Hence,
waiting time for P1 will be 0
- P1 requires 21
ms for completion, hence waiting time for P2 will
be 21 ms
- Similarly,
waiting time for process P3 will be execution time
of P1 + execution time for P2, which will
be (21 + 3) ms = 24 ms.
- For
process P4 it will be the sum of execution times of P1, P2 and P3.
The GANTT chart above
perfectly represents the waiting time for each process.
Implementation:
1.
Input the processes along with
their burst time (bt).
2. Find
waiting time (wt) for all processes.
3. As
first process that comes need not to wait so waiting time for process 1 will be
0 i.e. wt[0] = 0.
4. Find
waiting time for all other processes i.e. for process i -> wt[i] =
bt[i-1] + wt[i-1] .
5. Find
turnaround time = waiting_time + burst_time for all processes.
6. Find
average waiting time = total_waiting_time / no_of_processes.
7.
Similarly, find average
turnaround time = total_turn_around_time / no_of_processes.
References:
Non-Windows
Operating System (FreeBSD)
An operating
system (OS), in its most general sense, is software that allows a user to run
other applications on a computing device. While it is possible for a software
application to interface directly with hardware, the vast majority of
applications are written for an OS, which allows them to take advantage of
common libraries and not worry about specific hardware details.
The
operating system manages a computer's hardware resources, including:
- Input
devices such as a keyboard and mouse
- Output
devices such as display monitors, printers and scanners
- Network
devices such as modems, routers and network connections
- Storage
devices such as internal and external drives
The OS also
provides services to facilitate the efficient execution and management of, and
memory allocations for, any additional installed software application programs.
Some operating
systems were developed in the 1950s, when computers could only execute one
program at a time. Later in the decade, computers included many software
programs, sometimes called libraries, which were linked together to create the
beginning of today's operating systems.
The OS
consists of many components and features. Which features are defined as part of
the OS vary with each OS. However, the three most easily defined components
are:
- Kernel:
This provides basic-level control over all of the computer hardware
devices. Main roles include reading data from memory and writing data to
memory, processing execution orders, determining how data is received and
sent by devices such as the monitor, keyboard and mouse, and determining
how to interpret data received from networks.
- User
Interface: This component allows interaction with the user, which may
occur through graphical icons and a desktop or through a command line.
- Application
Programming Interfaces: This component allows application developers to
write modular code.
What is FreeBSD?
FreeBSD is an
advanced computer operating system used to power modern servers, desktops, and
embedded platforms. A
large community has
continually developed it for more than thirty years. Its advanced networking,
security, and storage features have made FreeBSD the platform of choice for
many of the busiest web
sites and most pervasive embedded networking and storage
devices.
FreeBSD is a
free, open-source, Unix-like operating system based on Berkeley Software
Distribution (BSD) Unix. It is the most popular among the BSD-based operating
systems, with an installed base of more than 75%. Due to legal constraints,
FreeBSD cannot be labeled as a Unix system, although it is compliant with Unix
internals and application programming interfaces (APIs). FreeBSD’s licensing
terms give developers a high degree of freedom to reuse it, so other operating
systems (such as MAC OSX) have reused many FreeBSD codes. Although FreeBSD is
not categorized as Unix, MAC OSX does have a formal Unix branding.
FreeBSD is
used by millions of users all over the world, as well as some of the busiest
sites on the Internet such as Yahoo, Sony Japan, etc.
Users attest
to the reliability of FreeBSD, its amazing stability, and high performance are
due to the following:
- FreeBSD
is a complete operating system environment with a kernel, device drivers
and a shell tool. In contrast, most Linux-based operating systems have a
separately-developed kernel, application, and userland utilities.
- Several
emulation tools are built into FreeBSD, allowing third-party software
package installation, most of which employ the FreeBSD ports system.
- FreeBSD
supports a wide variety of networking protocols, including TCP/IP, IPv6,
Stream Control Transmission Protocol (SCTP), IPSec, Internetwork Packet
Exchange (IPX), and AppleTalk, allowing users to integrate FreeBSD-based
computers with other operating systems running within the same network.
It runs on
processors such as the Pentium that are compatible with Intel's x86
architecture and also on amd64, Alpha/AXP, IA-64, PC-98 and UltraSPARC
processors. FreeBSD is an alternative to Linux that will run Linux
applications.
FreeBSD is said to be fast, stable, and
especially appropriate for use as an Internet server or as a file server.
FreeBSD supports all major X Window desktops, such as KDE and GNOME.
FreeBSD is a UNIX-like operating system
for the i386, amd64, IA-64, arm, MIPS, powerpc, ppc64, PC-98 and UltraSPARC
platforms based on U.C. Berkeley's "4.4BSD-Lite" release, with some
"4.4BSD-Lite2" enhancements. It is also based indirectly on William
Jolitz's port of U.C. Berkeley's "Net/2" to the i386, known as
"386BSD", though very little of the 386BSD code remains. FreeBSD is
used by companies, Internet Service Providers, researchers, computer
professionals, students and home users all over the world in their work,
education and recreation. FreeBSD comes with over 20,000 packages (pre-compiled
software that is bundled for easy installation), covering a wide range of
areas: from server software, databases and web servers, to desktop software,
games, web browsers and business software - all free and easy to install.
Although for legal reasons FreeBSD cannot
use the Unix trademark, it is a direct descendant of BSD, which was
historically also called "BSD Unix" or "Berkeley Unix". The
first version of FreeBSD was released in 1993, and as of 2005 FreeBSD was the
most widely used open-source BSD distribution, accounting for more than
three-quarters of all installed systems running open-source BSD derivatives.
FreeBSD has
similarities with Linux, with two major differences in scope and licensing:
FreeBSD maintains a complete operating system, i.e. the project delivers
kernel, device drivers, userland utilities, and documentation, as opposed to
Linux only delivering a kernel and drivers, and relying on third-parties for
system software; and FreeBSD source code is generally released under a
permissive BSD license, as opposed to the copyleft GPL used by Linux.
The FreeBSD
project includes a security team overseeing all software shipped in the base
distribution. A wide range of additional third-party applications may be
installed using the pkgng package management system or the FreeBSD Ports, or by
directly compiling source code. Due to its permissive licensing terms, much of
FreeBSD's code base has become an integral part of other operating systems,
such as Juniper JUNOS, Apple's Darwin (which is the base for macOS, iOS,
watchOS, and tvOS operating systems by Apple), pfSense, the Nintendo Switch
system software, and the operating systems running on Sony's PlayStation 3 and
PlayStation 4.
History
Background
FreeBSD's roots go back to the
University of California, Berkeley. The university acquired a UNIX source
license from AT&T. Students of the university started to modify and improve
the AT&T Unix and called this modified version "Berkeley Unix" or
"BSD", implementing features such as TCP/IP, virtual memory and the
Unix File System. The BSD project was founded in 1976 by Bill Joy. But since
BSD contained code from AT&T Unix, all recipients had to get a license from
AT&T first in order to use BSD.
In June 1989, "Networking Release
1" or simply Net-1 – the first public version of BSD – was released. After
releasing Net-1, Keith Bostic, a developer of BSD, suggested replacing all
AT&T code with freely-redistributable code under the original BSD license.
Work on replacing AT&T code began and, after 18 months, much of the
AT&T code was replaced. However, six files containing AT&T code
remained in the kernel. The BSD developers decided to release the "Networking
Release 2" (Net-2) without those six files. Net-2 was released in 1991.
Birth of FreeBSD
In 1992, several months after the
release of Net-2, William Jolitz and Lynne Jolitz wrote replacements for those
six missing files, ported BSD to the Intel 80386-based microprocessors, and
called their new operating system 386BSD. They released 386BSD via an anonymous
FTP server. The development flow of 386BSD was slow and after a period of
neglect, a group of 386BSD users decided to branch out on their own and create
FreeBSD so that they could keep the operating system up to date. On 19 June
1993, the name FreeBSD was chosen for the project. The first version of FreeBSD
was released on November 1993.
In the early days of the project's
inception, a company named Walnut Creek CDROM, upon the suggestion of the two FreeBSD
developers, agreed to release the operating system on CD-ROM. In addition to
that, the company employed Jordan Hubbard and David Greenman, ran FreeBSD on
its servers, sponsored FreeBSD conferences and published FreeBSD-related books,
including The Complete FreeBSD by Greg Lehey. By 1997, FreeBSD was Walnut
Creek's "most successful product". The company itself later renamed
to The FreeBSD Mall and later iXsystems.
Today, FreeBSD is used by many IT
companies such as IBM, Nokia, Juniper Networks, and NetApp to build their product.
Certain parts of Apple's Mac OS X operating system are based on FreeBSD. The
PlayStation 3 operating system also borrows certain components from FreeBSD,
while the PlayStation 4 operating system is derived from FreeBSD 9. Netflix,
WhatsApp, and FlightAware are also examples of big, successful and heavily
network-oriented companies which are running FreeBSD.
Lawsuit
386BSD and FreeBSD were both derived
from 1992's BSD release.[17] In January 1992, BSDi started to release BSD/386,
later called BSD/OS, an operating system similar to FreeBSD and based on 1992's
BSD release. AT&T filed a lawsuit against BSDi and alleged distribution of
AT&T source code in violation of license agreements. The lawsuit was
settled out of court and the exact terms were not all disclosed. The only one
that became public was that BSDi would migrate their source base to the newer
4.4BSD-Lite sources. Although not involved in the litigation, it was suggested
to FreeBSD that they should also move to 4.4BSD-Lite.[24] FreeBSD 2.0, which
was released on November 1994, was the first version of FreeBSD without any
code from AT&T.
Features
Ø Uses
-
As a general purpose operating
system, FreeBSD is used in various scenarios:
Ø Servers
-
FreeBSD contains a significant
collection of server-related software in the base system and the ports
collection, it is possible to configure and use FreeBSD as a mail server, web
server, Firewall, FTP server, DNS server and a router, among other applications.
Ø Desktop
-
The X Window System is not
installed by default, but is available in the FreeBSD ports collection. A
number of Desktop environments such as GNOME, KDE and Xfce, and lightweight
window managers such as Openbox, Fluxbox and dwm are also available to FreeBSD.
Ø Embedded
systems
-
Although it explicitly focuses on
the IA-32 and x86-64 platforms, FreeBSD also supports others such as ARM, PowerPC
and MIPS to a lesser degree.
Ø Networking
-
FreeBSD's TCP/IP stack is based
on the 4.2BSD implementation of TCP/IP which greatly contributed to the
widespread adoption of these protocols.
Ø Storage
-
FreeBSD has several unique features
related to storage.
Ø Security
-
FreeBSD provides several
security-related features including access control lists (ACLs), security event
auditing, extended file system attributes, mandatory access controls (MAC) and
fine-grained capabilities.
Ø Portability
-
FreeBSD has been ported to a
variety of instruction set architectures.
Ø Third-party
software
-
FreeBSD has a software repository
of over 26,000 applications that are developed by third parties.
Ø Jails
-
First introduced in FreeBSD version
4, jails is a security mechanism and an implementation of
operating-system-level virtualization that enables the user to run multiple
instances of a guest operating system on top of a FreeBSD host.
Ø Virtualization
-
bhyve, a new virtualization
solution was introduced in FreeBSD 10.0. bhyve allows a user to run a number of
guest operating systems (FreeBSD, OpenBSD, Linux, and Microsoft Windows)
simultaneously.
Ø OS
compatibility layers
-
Most software that runs on Linux
can run on FreeBSD using an optional built-in compatibility layer.
Ø Kernel
-
FreeBSD's kernel provides support
for some essential tasks such as managing processes, communication, booting and
filesystems.
Ø Documentation
and support
-
FreeBSD's documentation consists
of its handbooks, manual pages, mailing list archives, FAQs and a variety of
articles, mainly maintained by The FreeBSD Documentation Project.
Ø Installers
-
From version 2.0 to 9.0, FreeBSD
used the sysinstall program as its main installer.
Development
FreeBSD is
developed by a volunteer team located around the world. The developers use the
Internet for all communication and many have not met each other in person. In
addition to local user groups sponsored and attended by users, an annual
conference, called BSDcon, is held by USENIX. BSDcon is not FreeBSD-specific so
it deals with the technical aspects of all BSD operating systems, including
OpenBSD and NetBSD. In addition to BSDcon, three other annual conferences,
EuroBSDCon, AsiaBSDCon and BSDCan take place in Europe, Japan and Canada
respectively.
Logo
FreeBSD's
mascot is the generic BSD Daemon, also known as Beastie. For many years
FreeBSD's logo was the generic BSD daemon, also called Beastie, a distorted
pronunciation of BSD. However, Beastie was not unique to FreeBSD. First
appearing in 1976 on Unix T-shirts purchased by Bell Labs, the more popular
versions of the BSD daemon were drawn by animation director John Lasseter
beginning in 1984. Several FreeBSD-specific versions were later drawn by
Tatsumi Hosokawa.
The name
"FreeBSD" was coined by David Greenman on 19 June 1993, other
suggested names were "BSDFree86" and "Free86BSD". FreeBSD's
slogan, "The Power to Serve", is a trademark of The FreeBSD
Foundation.
References:
Mark Jason T. Raboy
BS Info. Tech 3B
Mr. Peter Rabanal (Instructor)
Comments
Post a Comment