CS作业代写 Design philosophy of operating systems (IV)

Design philosophy of operating systems (IV)

Recap: Each process has a separate virtual memory space
static data

heap Virtual memory
static data
heap Virtual memory
static data
heap Virtual memory
static data
heap Virtual memory
They are isolated from one another. Each of them is not supposed to know what happens to another one
Virtually, every process seems to have a processor, but only a few of them are physically executing.

Recap: The basic process API of UNIX

Recap: How to implement redirection in shell
Say, we want to do ./a > b.txt
• The forked code opens b.txt
Homework for you:
Think about the case when
your fork is equivalent to fork+exec()
The forked code dup the file descriptor to stdin/stdout The forked code closes b.txt
exec(“./a”, NULL)
int pid, fd;
char cmd[2048], prompt = “myshell$” while(gets(cmd) != NULL) {
if ((pid = fork()) == 0) {
fd = open(“b.txt”, O_RDWR | O_CREAT, S_IRUSR |
S_IWUSR); dup2(fd, stdout); close(fd);
}execv(“./a”,NULL);
} printf(“%s ”,pro
static data
The shell can respond to next in
heap stack
int pid, fd;
char cmd[2048], prompt = “myshell$” while(gets(cmd) != NULL) {
if ((pid = fork()) == 0) {
fd = open(“b.txt”, O_RDWR | O_CREAT, S_IRUSR |
S_IWUSR); dup2(fd, stdout); close(fd);
}execv(“./a”,NULL);
} printf(“%s ”,pro
static data
heap stack

The hardware is changing
• Multiprocessors
Why “Mach”?
• Networkedcomputing
The software
• ThedemandofextendinganOSeasily
• Repetitivebutconfusingmechanismsforsimilarstuffs
Make UNIX great again!

Mach: A New Kernel Foundation For UNIX Development (cont.) Taxonomy of Kernels
Synchronization

Mach: A New Kernel Foundation For UNIX
Development
, , , , , ,
Computer Science Department, University

Tasks/processes
PC CPU Memory
Each process has its own unique virtual memory address ace, it of execu set of I/O
s own states
tion, its own
static data
static data
heap Virtual memory
a = 0x01234567
heap Virtual memory
a = 0xDEADBEEF
static data
static data
heap Virtual memory
a = 0x87654321
heap Virtual memory
a = 0x95273310

Intel Sandy Bridge
Share L3 $

Concept of chip multiprocessors
Core Core Registers Registers
L1-$ L1-$ L2-$ L2-$
Registers L2-$ L2-$
Last-level $ (LLC)
Main memory is eventually shared among processor
Main memory

Task#1 Thread #1 Thread #2
CPU PC CPU
Thread #3 Thread #1 Thread #2
CPU PC PC CPU PC CPU
Each process has its own unique virtual memory address
space, its own states of execution, its own set of I/Os
Each thread has its own PC, states of execution, but shares
memory address spaces, I/Os without threads within the
same process
static data
static data
heap Virtual memory
a = 0x01234567
heap Virtual memory
a = 0x01234567

Tasks/Processes and threads
How many of the following regarding the comparison of parallelizing
computation tasks using processes and threads is/are correct?
! Thecontextswitchandcreationoverheadofprocessesishigher
— you have to change page tables, warm up TLBs, warm up caches, create a new memory space …
” Theoverheadofexchangingdataamongdifferentcomputingtasksforthe same applications is higher in process model
# Thedemandofmemoryusageishigherwhenusingprocesses
— separate address, it’s not easy to access data from another process
— you cannot directly share data without leveraging other mechanisms
— each process needs its own address space even if most data are potentially identical
$ Thesecurityandisolationguaranteesarebetterachievedusingprocesses

Case study: Chrome v.s. Firefox each of these is a process
Memory usage? Stability? Security? Latency?
each of these is a thread

Poll close in
What’s in the kernel?
How many of the following Mach features/functions are
implemented in the kernel?
! I/Odevicedrivers
” Filesystem
$ Virtualmemorymanagement A. 0
B. 1 C. 2 D. 3 E. 4

! I/Odevicedrivers
” Filesystem
$ Virtualmemorymanagement A. 0
Mechanisms
What’s in the kernel?
How many of the following Mach features/functions are
implemented in the kernel?

Poll close in
How many of the following terms belongs to “policies”? ! Least-recentlyused(LRU)
” First-in,first-out
$ Preemptivescheduling % Capability
C. 2 D. 3 E. 4
Policy? Mechanisms?

How many of the following terms belongs to “policies”?
! Least-recentlyused(LRU) ” First-in,first-out
$ Preemptivescheduling
% Capability A. 0
—Mechanism —Mechanism —Mechanism
Policy? Mechanisms?

How many pairs of the “why” and the “what” in Mach are correct?
Whys v.s. whats
(1) (2) (3) (4)
Support for multiprocessors
Networked computing
OS Extensibility
Messages/Ports
MKeircnreolkderbnueglg/Oerbject-oriented design
Repetitive but confusing mechanisms Messages/Ports
A. 0 B. 1 C. 2

Poll close in
Types of kernels
What type of kernels does the UNIX described in . Ritchie’s
paper belong to?
A. Microkernel—thekernelonlyprovidesaminimalsetofservices/ mechanisms including memory management, multitasking and inter- process communication
B. Monolithic—thekernelimplementseveryfunctionthatcannotbeina user-space library: device drivers, scheduler, memory handling, file systems, network stacks
C. Modular — the kernel provides a basic set of functions like microkernels, but allows load/unload kernel modules if necessary
D. Layeredkernel—thekernelfollowsstrictlayereddesignthatlower- order module cannot interact with higher-order modules

Types of kernels
What type of kernels does the UNIX described in . Ritchie’s
paper belong to?
A. Microkernel—thekernelonlyprovidesaminimalsetofservices/ mechanisms including memory management, multitasking and inter- process communication Mach, Nucleus
B. Monolithic—thekernelimplementseveryfunctionthatcannotbeina
user-space library: device drivers, scheduler, memory handling, file
systems, network stacks
C. Modular — the kernel provides a basic set of functions like
microkernels, but allows load/unload kernel modules if necessary
D. Layeredkernel—thekernelfollowsstrictlayereddesignthatlower- order module cannot interact with higher-order modules THE
Linux, Windows, MacOS, FreeBSD

Monolithic
dynamically loadable kernel modules
Types of Kernels
Applications
Applications
Applications
Virtual File Systems, System calls, IPC, File systems, scheduler, virtual memory, device drivers, dispatcher.
Application IPC
Server programs
Device Drivers
File Server
File Server
kernel mode
kernel mode
Basic IPC, Virtual Memory, Scheduling
Server programs
Device Drivers
Application IPC
Basic IPC, Virtual Memory, Scheduling
operating system
Original UNIX
Only mechanisms are in the kernel
Nucleus, , Windows, MacOS

Poll close in
Although Mach’s design strongly influenced modern operating systems, why most modern operating systems do not adopt the design of microkernels?
A. Microkernelsaremoredifficulttoextendthanmonolithickernels
B. Microkernelsaremoredifficulttomaintainthanmonolithic kernels
C. Microkernels are less stable than monolithic kernels
D. Microkernelsarenotascompetitiveasmonolithickernelsin terms of application performance
E. Microkernelsarelessflexiblethanmonolithickernels 26
Why not microkernels?

Although Mach’s design strongly influenced modern operating systems, why most modern operating systems do not adopt the design of microkernels?
A. Microkernelsaremoredifficulttoextendthanmonolithickernels
B. Microkernelsaremoredifficulttomaintainthanmonolithic kernels
C. Microkernels are less stable than monolithic kernels
E. Microkernelsarelessflexiblethanmonolithickernels 28
Why not microkernels?
D. Microkernelsarenotascompetitiveasmonolithickernelsin
terms of application performance
Context switches!

Threads The impact of Mach
Extensible operating system kernel design
Strongly influenced modern operating systems • WindowsNT/2000/XP/7/8/10

Thread programming & synchronization

The virtual memory of multithreaded applications
static data
Everything here is shared/
visible among all threads
within the same process!
Virtual memory

Also referred to as “producer-consumer” problem Producer places items in shared buffer
Consumer removes items from shared buffer
Bounded-Buffer Problem

We need to control accesses to the buffer!
int buffer[BUFF_SIZE]; // shared global
int main(int argc, char *argv[]) {
pthread_t p;
printf(“parent: begin\n”);
// init here
Pthread_create(&p, NULL, child, NULL);
int in = 0;
while(TRUE) {
void *child(void *arg) {
int out = 0;
printf(“child\n”);
while(TRUE) {
} // do something w/ item
return NULL;
int item = …;
}printf(“parent: end\n”);
return 0; }
int item = buffer[out];
out = (out + 1) % BUFF_SIZE;
buffer[in] = item;
in = (in + 1) % BUFF_SIZE;

Solving the “Critical Section Problem”
1. Mutual exclusion — at most one process/thread in its critical section
2. Progress—athreadoutsideofitscriticalsectioncannot block another thread from entering its critical section
3. Fairness—athreadcannotbepostponedindefinitelyfrom entering its critical section
4. Accommodatenondeterminism—thesolutionshouldwork regardless the speed of executing threads and the number of processors

int main(int argc, char *argv[]) {
int buffer[BUFF_SIZE]; // shared global volatile unsigned int lock = 0;
pthread_t p;
printf(“parent: begin\n”);
// init here
Pthread_create(&p, NULL, child, NULL);
int in = 0;
while(TRUE) {
int item = …;
Pthread_mutex_lock(&lock);
buffer[in] = item;
in = (in + 1) % BUFF_SIZE;
} Pthread_mutex_unlock(&lock);
printf(“parent: end\n”);
return 0; }
void *child(void *arg) {
int out = 0;
printf(“child\n”);
while(TRUE) {
Pthread_mutex_lock(&lock);
int item = buffer[out];
out = (out + 1) % BUFF_SIZE; Pthread_mutex_unlock(&lock);
} // do something w/ item
} return NULL;

How to implement lock/unlock

int buffer[BUFF_SIZE]; // shared global volatile unsigned int lock = 0;
int main(int argc, char *argv[]) {
pthread_t p;
printf(“parent: begin\n”);
// init here
Pthread_create(&p, NULL, child, NULL);
int in = 0;
while(TRUE) {
Naive implementation
void *child(void *arg) {
int out = 0;
printf(“child\n”);
while(TRUE) {
Pthread_mutex_lock(&lock);
int item = buffer[out];
out = (out + 1) % BUFF_SIZE; Pthread_mutex_unlock(&lock);
} // do something w/ item
return NULL;
void Pthread_mutex_lock(volatile unsigned int *lock) { while (*lock == 1) // TEST (lock)
int item = …;
Pthread_mutex_lock(&lock);
buffer[in] = item;
in = (in + 1) % BUFF_SIZE;
} Pthread_mutex_unlock(&lock);
*lock = 1;
// SET (lock)
printf(“parent: end\n”);
return 0; }
void Pthread_mutex_unlock(volatile unsigned int *lock)
{ *lock = 0; } 38

Poll close in
Naive implementation
How many of the following can the naive implementation guarantee for the
producer-consumer problem?
! Atmostoneprocess/threadinitscriticalsection
” Athreadoutsideofitscriticalsectioncannotblockanotherthreadfromentering its critical section
# Athreadcannotbepostponedindefinitelyfromenteringitscriticalsection
$ Thesolutionshouldworkregardlessthespeedofexecutingthreadsandthe number of processors
void Pthread_mutex_lock(volatile unsigned int *lock) { while (*lock == 1) // TEST (lock)
*lock = 1; // SET (lock)
void Pthread_mutex_unlock(volatile unsigned int *lock) {
*lock = 0;

Poll close in
producer-consumer problem?
Naive implementation
How many of the following can the naive implementation guarantee for the
! Atmostoneprocess/threadinitscriticalsection
” Athreadoutsideofitscriticalsectioncannotblockanotherthreadfromentering its critical section
# Athreadcannotbepostponedindefinitelyfromenteringitscriticalsection
$ Thesolutionshouldworkregardlessthespeedofexecutingthreadsandthe number of processors
void Pthread_mutex_lock(volatile unsigned int *lock) { while (*lock == 1) // TEST (lock)
*lock = 1; // SET (lock)
void Pthread_mutex_unlock(volatile unsigned int *lock) {
*lock = 0;

int buffer[BUFF_SIZE]; // shared global volatile unsigned int lock = 0;
int main(int argc, char *argv[]) {
pthread_t p;
printf(“parent: begin\n”);
// init here
Pthread_create(&p, NULL, child, NULL);
int in = 0;
while(TRUE) {
int item = …;
Pthread_mutex_lock(&lock);
buffer[in] = item;
in = (in + 1) % BUFF_SIZE;
Naive implementation
void *child(void *arg) {
int out = 0;
printf(“child\n”);
while(TRUE) {
Pthread_mutex_lock(&lock);
int item = buffer[out];
out = (out + 1) % BUFF_SIZE; Pthread_mutex_unlock(&lock);
} // do something w/ item
return NULL;
void Pthread_mutex_lock(volatile unsigned int *lock) { while (*lock == 1) // TEST (lock)
what if context switch
*lock = 1;
printf(“parent: end\n”);
void Pthread_mutex_unlock(volatile unsigned int *lock)
{ *lock = 0; } 41
Pthread_mutex_unlock(&lock);
happens here?
// SET (lock)

Naive implementation
How many of the following can the naive implementation guarantee for the
producer-consumer problem?
! Atmostoneprocess/threadinitscriticalsection
” Athreadoutsideofitscriticalsectioncannotblockanotherthreadfromentering its critical section
# Athreadcannotbepostponedindefinitelyfromenteringitscriticalsection
$ Thesolutionshouldworkregardlessthespeedofexecutingthreadsandthe number of processors
void Pthread_mutex_lock(volatile unsigned int *lock) { while (*lock == 1) // TEST (lock)
*lock = 1; // SET (lock)
void Pthread_mutex_unlock(volatile unsigned int *lock) {
*lock = 0;

Naive implementation
int buffer[BUFF_SIZE]; // shared global volatile unsigned int lock = 0;
void *child(void *arg) {
int out = 0;
printf(“child\n”);
while(TRUE) {
Pthread_mutex_lock(&lock);
int item = buffer[out];
out = (out + 1) % BUFF_SIZE; Pthread_mutex_unlock(&lock); // do something w/ item
int main(int argc, char *argv[]) {
pthread_t p;
printf(“parent: begin\n”)c;rashes/halts here? // init here
Pthread_create(&p, NULL, child, NULL);
int in = 0;
while(TRUE) {
what if the thread
int item = …;
Pthread_mutex_lock(&lock);
buffer[in] = item;
in = (in + 1) % BUFF_SIZE;
return NULL;
what if context switch
void Pthread_mutex_lock(volatile unsigned int *lock) { while (*lock == 1) // TEST (lock)
printf(“parent: end\n”);
void Pthread_mutex_unlock(volatile unsigned int *lock)
{ *lock = 0; } 43
Pthread_mutex_unlock(&lock);
*lock = 1;
happens here?
// SET (lock)

int item = …;
Pthread_mutex_lock(&lock);
return NULL;
Naive implementation
int buffer[BUFF_SIZE]; // shared global volatile unsigned int lock = 0;
void *child(void *arg) {
int out = 0;
printf(“child\n”);
while(TRUE) {
Pthread_mutex_lock(&lock);
int item = buffer[out];
out = (out + 1) % BUFF_SIZE; Pthread_mutex_unlock(&lock); // do something w/ item
int main(int argc, char *argv[]) {
pthread_t p;
printf(“parent: begin\n”)c;rashes/halts here? // init here
Pthread_create(&p, NULL, child, NULL);
int in = 0;
while(TRUE) {
what if the thread
buffer[in] = item;
in = (in + 1) % BUFF_SIZE;
void Pthread_mutex_lock(volatile unsigned int *lock) { while (*lock == 1) // TEST (lock)
what if context switch
all threads can see
void Pthread_mutex_unlock(volatile unsigned int *lock)
{ *lock = 0; } 45
Pthread_mutex_unlock(&lock);
*lock = 1;
happens here?
lock as 0 at this point
}printf(“parent: end\n”);
// SET (lock)
return 0; }

producer-consumer problem?
Naive implementation
How many of the following can the naive implementation guarantee for the
! Atmostoneprocess/threadinitscriticalsection
” Athreadoutsideofitscriticalsectioncannotblockanotherthreadfromentering its critical se

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts