現(xiàn)代操作系統(tǒng)作業(yè)答案課件

1Modern

OperatingSystemsSolutionsZhang

YangSpring

20152Chapter

2

1.

The

transition

from

blocked

to

running

iconceivable.

Suppose

that

a

process

isblocked

on

I/O

and

the

I/O

finishes.

If

theCPU

is

otherwise

idle,

the

process

could

godirectly

from

blocked

to

running.

The

other

missing

transition,

from

readyblocked,

is

impossible.

A

ready

processcannot

do

I/O

or

anything

else

that

mightblock

it.

Only

a

running

process

can

block.?3

8.

A

worker

thread

will

block

when

it

has

toread

a

Web

page

from

the

disk.

If

user-level

threads

are

being

used,

this

actionwill

block

the

entire

process,

destroyingthe

value

of

multithreading.

Thus

it

isessential

that

kernel

threads

are

used

topermit

some

threads

to

block

withoutaffecting

the

others.

11.

Threads

in

a

process

cooperate.

Theyare

not

hostile

to

one

another.

If

yieldingneeded

for

the

good

of

the

application,then

a

thread

will

yield.

After

all,

it

isusually

the

same

programmer

who

writesFigure

2-8

A

multithreadedWeb

server5

14.

The

biggest

advantage

is

efficiency.

Ntraps

to

the

kernel

are

needed

to

switchthreads.

The

biggest

disadvantage

is

that

if

onethread

blocks,

the

entire

process

blocks.

28.

With

kernel

threads,

a

thread

can

blocon

a

semaphore

and

the

kernel

can

runsome

other

thread

in

the

same

process.Consequently,

there

is

no

problem

usingsemaphores.

With

user-level

threads,

when

one

threadblocks

on

a

semaphore,

the

kernel

thinks37.

(a)

For

round

robin,

during

the

first

10minutes

each

job

gets

1/5

of

the

CPU.

At

theend

of

10

minutes,

C

finishes.

During

thenext

8

minutes,

each

job

gets

?

of

the

CPU,after

which

time

D

finishes.

Then

each

of

ththree

remaining

jobs

gets

1/3

of

the

CPU

for6

minutes,

until

B

finishes,

and

so

on.

Thefinishing

times

for

the

five

jobs

are

10,

1824,

28,

and

30,

for

an

average

of

22minutes.Average

=

(10

+

18

+

24

+

28

+

30)

/

5

=

22minutes37.Turn

around

time

of

B

=

6

minutesTurn

around

time

of

E

=

14

minutesTurn

around

time

of

A

=

24

minutesTurn

around

time

of

C

=

26

minutesTurn

around

time

of

D

=

30

minutesAverage

=

(6

+

14

+

24

+

26

+

30)

/

5

=

20minutes(b)

priorityB

E0

6ACD1424

263037.Turn

around

time

of

A

=

10

minutesTurn

around

time

of

E

=

16

minutesTurn

around

time

of

A

=

18

minutesTurn

around

time

of

C

=

22

minutesTurn

around

time

of

D

=

30

minutesAverage

=

(10

+

16

+

18

+

22

+

30)

/

5

=

19.2minutesB(c)

FCFSA0

10ECD16

18

22

3037.Turn

around

time

of

C

=

2

minutesTurn

around

time

of

D

=

6

minutesTurn

around

time

of

B

=

12

minutesTurn

around

time

of

E

=

20

minutesTurn

around

time

of

A

=

30

minutesAverage

=

(2

+

6

+

12

+

20

+

30)

/

5

=

14minutesB(d)

SJFC

D0

2

6EA12

20

30?用信號量解題的關(guān)鍵步驟：(1)分析題目中存在的同步和互斥關(guān)系(2)信號量的設(shè)置

(3)給信號量賦初值（常用的互斥和同步信號量值的大?。?/p>

(4)P、V操作安排的位置（其中，P的順序不能顛倒，V的順序任意）1151.

int

w_count

=

0,

m_count

=0

;semaphore

w_mutex

=1,

m_mutex

=1;semaphore

bathroom

=1;woman_wants_to_enter:down(&w_mutex

)

;w_count

=

w_count

+1;if

(w_count

==1)

down

(&bathroom);up(&w_mutex)

;woman_leaves:down(&w_mutex

)

;w_count

=

w_count

-1;1251.

(ctd.)man_wants_to_enter:down(&m_mutex

)

;m_count

=

m_count

+1;if

(m_count

==1)

down

(&bathroom);up(&m_mutex)

;man_leaves:down(&m_mutex

)

;m_count

=

m_count

-1;if

(m_count

==0)

up

(&bathroom);up(&m_mutex)

;13補(bǔ)充題1：

有一個閱覽室，共有100個座位，讀者進(jìn)入時必須先在一張登記表上登記，該表為每一座位列一表目，包括座號和讀者姓名等，讀者離開時要消掉登記的信息，試用PV操作描述讀者

進(jìn)程之間的同步關(guān)系。答：讀者的動作有兩個，一是填表進(jìn)入閱覽室，這時要考慮閱覽室里是否有座位；一是讀者閱讀完畢，離開閱覽室，這時的操作要考慮閱覽室里是否有讀者。讀者在閱覽室讀書時，由于沒有引起資源的變動，不算動作變化。

算法的信號量有三個：seats——表示閱覽室是否有座位（初值為100，代表閱覽室的空座位數(shù)）；readers——表示閱覽室里的讀者數(shù)，初值為0；用于互斥的mutex，初值為1。?讀者進(jìn)入閱覽室的動作描述getin：while(TRUE){

P(seats);離開*/

P（mutex）區(qū)*/填寫登記表;進(jìn)入閱覽室讀書;

V（mutex）區(qū)*//*沒有座位/*進(jìn)入臨界/*離開臨界?讀者離開閱覽室的動作描述getout：while(TRUE){P（readers）是否有人讀書*//*閱覽室

P（mutex）區(qū)*//*進(jìn)入臨界消掉登記；離開閱覽室；

V（mutex）區(qū)*//*離開臨界V（seats）/*釋放一個17

練習(xí)題：桌上有一只盤子，每次只能放一個水果，爸爸專向盤中放蘋果，媽媽專向盤中放桔子，兒子專等吃盤里的桔子，女兒專等吃盤里的蘋果。只要盤子空，則爸爸或媽媽可向盤中放水果，僅當(dāng)盤中有自己需要的水果時，兒子或女兒可從中取出，請給出四人之間的同步關(guān)系，并用P、V操作實現(xiàn)四人正確活動的程序。問題分析四人之間的關(guān)系

爸爸，媽媽要互斥使用盤子，所以兩者之間是互斥關(guān)系；

爸爸放的蘋果，女兒吃，所以兩者是同步關(guān)系；

媽媽放的桔子，兒子吃，所以兩者也是同步關(guān)系。信號量設(shè)置一個信號量表示是否可向盤中放水果一個信號量表示可否取桔子解 設(shè)置三個信號量s，so，sa，初值分別為1，0，0，表示是否可向盤中放水果，表示可否取桔子，表示可否取蘋果semaphore

s=1,so=0,sa=0

main()daughter()

{while(true)

father();p(sa);father(){

while(true){{

p(s);補(bǔ)充題2

Consider

the

following

set

of

processes,

withe

length

of

CPU

burst

time

given

inmillisecondsProcessDurationPriorityArrival

TimeP11030P2110P3250P4140P5520補(bǔ)充題2（續(xù)）

The

processes

are

assumed

to

have

arrivedin

the

order

of

P1,P2,P3,P4,P5

all

at

time

0

a.

Draw

four

Gantt

chart

illustrating

theexecution

of

these

processes

using

FCFS,SJF,

a

non-preemptive

priority

(a

smallerpriority

number

implies

a

higher

priority)RR

scheduling

(time

quantum=1).

b.

What

is

the

turn

around

time

of

eachprocess

for

each

scheduling

algorithm

inpart

a?c.

What

is

the

waiting

time

of

each

process

Turnaround

Time

(also

called

elapsetime)

Amount

of

time

to

execute

a

particularprocess

from

creation

to

exitWaiting

Time

Amount

of

time

process

has

been

waitingin

ready

queue補(bǔ)充題2SolutionFCFSSJFa

non-preemptive

priorityRR補(bǔ)充題2

Solutionb.

Turn

around

timeFCFS:

P1=10,

P2=11,P3=13,P4=14,P5=19SJF:

P1=19,P2=1,

P4=2,

P3=4,

P5=9Priority:

P1=16,

P2=1,

P3=19,

P4=17,P5=6RR:

P1=19,

P2=2,

P3=7,

P4=4,

P5=14c.

Waiting

timeFCFS:

P1=0,

P2=10,P3=11,P4=13,P5=14SJF:

P1=9,P2=0,

P3=2,

P4=1,

P5=4Priority:

P1=6,

P2=0,

P3=17,

P4=16,P5=1RR:

P1=9,

P2=1,

P3=5,

P4=3,

P5=9fork（）創(chuàng)建一個新進(jìn)程。系統(tǒng)調(diào)用格式：pid=fork(

)參數(shù)定義：int

fork(

)fork()返回值意義如下：

0：在子進(jìn)程中，pid變量保存的fork()返回值為0，表示當(dāng)前進(jìn)程是子進(jìn)程。

>0：在父進(jìn)程中，pid變量保存的fork()返回值為子進(jìn)程的id值（進(jìn)程唯一標(biāo)識符）。fork（）核心為fork()完成以下操作：（1）為新進(jìn)程分配一進(jìn)程表項和進(jìn)程標(biāo)識符

進(jìn)入fork()后，核心檢查系統(tǒng)是否有足夠的資源來建立一個新進(jìn)程。若資源不足，則fork()系統(tǒng)調(diào)用失??；否則，核心為新進(jìn)程分配一進(jìn)程表項和唯一的進(jìn)程標(biāo)識符。（2）檢查同時運行的進(jìn)程數(shù)目

超過預(yù)先規(guī)定的最大數(shù)目時，fork()系統(tǒng)調(diào)用失敗。（3）拷貝進(jìn)程表項中的數(shù)據(jù)將父進(jìn)程的當(dāng)前目錄和所有已打開的數(shù)據(jù)拷貝fork（）#include

<stdio.h>main(

){int

p1,p2;

while((p1=fork(

))=

=

-1);p1*/if

(p1=

=0)

putchar("b");else{while((p2=fork(

))=

=

-1);/*創(chuàng)建子進(jìn)程/*創(chuàng)建子進(jìn)程p2練習(xí)題：練習(xí)題：練習(xí)題：32Chapter

3

3.

The

bitmap

needs

1

bit

per

allocationunit.

With /n

allocation

units,

this

isbytes.

The

linked

list

has

/

ornodes,

each

of

8

bytes

for

a

total

ofbytes.

For

small

n,

the

linked

list

is

better.

Folarge

n,

the

bitmap

is

better.

The

crossover

point

can

be

calculated

byequating

these

two

formulas

and

solvingfor

n.

The

result

is

1

KB.

For

n

smallerthan

1

KB,

a

linked

list

is

better.

For

n334.Request:

12KB,

10KB,

9KBFirst

fit:

20KB,

10KB,18KBBest

fit:

12KB,

10KB,

9KBWorst

fit:

20KB,

18KB,

15KBNext

fit:

20KB,

18KB,

9KB5.4KB

page

8KB

page?20000(4,3616)(2,3616)?32768(8,0)(4,0)?60000(14,2656)(7,2656)10KB

4KB

20KB

18KB

7KB9KB12KB15KB34

11.

(a)

A

multilevel

page

table

reduces

thenumber

of

actual

pages

of

the

page

tablethat

need

to

be

in

memory

because

of

itshierarchic

structure.

In

fact,

in

a

programwith

lots

of

instruction

and

data

locality,only

need

the

top-level

page

table

(onepage),

one

instruction

page

and

one

datapage.

(b)

Allocate

12

bits

for

each

of

the

twopage

fields.

The

offset

field

requires

14bits

to

address

16

KB.

That

leaves

24

bitsfor

the

page

fields.

Since

each

entry

is

435

12.

Twenty

bits

are

used

for

the

virtualpage

numbers,

leaving

12

over

for

theoffset.

This

yields

a

4-KB

page.

Twentybits

for

the

virtual

page

implies

2

20pages.14.

One-level

page

table,

1M

pages,

1M

pagetable

entries.

Two-level

page

table,

the

main

page

tablehas

1K

entries,

each

of

which

points

to

asecond

page

table.

Only

two

of

these

areused.

Thus

in

total

only

three

page

table3624.

The

counters

arePage

0:

0110110Page

1:

01001001Page

2:

00110111Page

3:

1000101128.NRU

removes

page

2FIFO

removes

page

3LRU

removes

page

1Second

chance

removes

page

2

29.

Fragment

B

since

the

code

has

morespatial

locality

than

Fragment

A.

The

inneloop

causes

only

one

page

fault

for

everyother

iteration

of

the

outer

loop.

(There

wonly

be

32

page

faults.)

Aside

(Fragment

A)Since

a

frame

is

128

words,

one

row

of

theX

array

occupies

half

of

a

page

(i.e.,

64words).

The

entire

array

fits

into

64

×32/128

=

16

frames.

The

inner

loop

of

thecode

steps

through

consecutive

rows

of

Xfor

a

given

column.

Thus

every

otherreference

to

X

[i][j]

will

cause

a

page

fauThe

total

number

of

page

faults

will

be

64

31.

The

text

is

eight

pages,

the

data

are

fpages,

and

the

stack

is

four

pages.

Theprogram

does

not

fit

because

it

needs

174096-byte

pages.

With

a

512-byte

page,

thesituation

is

different.

Here

the

text

is

64pages,

the

data

are

33

pages,

and

the

stackis

31

pages,

for

a

total

of

128

512-bytepages,

which

fits.

With

the

small

page

sizeis

OK,

but

not

with

the

large

one.37.Chapter

6

2.

Deadlock

Situation:

If

the

printer

starprint

a

file

before

the

entire

file

has

beereceived

(this

is

often

allowed

to

speedresponse),

the

disk

may

fill

with

otherrequests

that

can’t

be

printed

until

the

ffile

is

done,

but

which

use

up

disk

spaceneeded

to

receive

the

file

currently

beingprinted.

Deadlock

Avoidance:

If

the

spooler

doesnot

start

to

print

a

file

until

the

entire

fbeen

spooled

it

can

reject

a

request

that

itoo

big.

Starting

to

print

a

file

is

equiva

5.

Yes,

illegal

graphs

exist.

We

stated

tharesource

may

only

be

held

by

a

singleprocess.

An

arc

from

a

resource

square

to

aprocess

circle

indicates

that

the

processowns

the

resource.

Thus

a

square

with

arcsgoing

from

it

to

two

or

more

processes

means

that

all

those

processes

hold

theresource,

which

violates

the

rules.Consequently,

any

graph

in

which

multiplearcs

leave

a

square

and

end

in

differentcircles

violates

the

rules.

Arcs

from

squarto

squares

or

from

circles

to

circles

alsoviolate

the

rules.

13.

There

are

states

that

are

neither

safenor

deadlocked,

but

which

lead

todeadlocked

states.

As

an

example,

supposewe

have

four

resources:

tapes,

plotters,scanners,

and

CD-ROMs,

as

in

the

text,

andthree

processes

competing

for

them.

Wecould

have

the

following

situation:HasNeedsAvailableA:

2

0

0

01

0

2

00

1

2

1B:

1

0

0

00

1

3

1C:

0

1

2

11

0

1

0This

state

is

not

deadlocked

because

17.

The

system

is

deadlock

free.

Supposethat

each

process

has

one

resource.

There

is

one

resource

free.

Either

process

can

askfor

it

and

get

it,

in

which

case

it

can

finisand

release

both

resources.

Consequentlydeadlock

is

impossible.

18.

If

a

process

has

m

resources

it

canfinish

and

cannot

be

involved

in

a

deadlock.Therefore,

the

worst

case

is

where

everyprocess

has

m

-1

resources

and

needs

another

one.

If

there

is

one

resource

leftover,

one

process

can

finish

and

release

all

22.把題目中processB的Allocated改為

20111，Maximum改為22211The

needs

matrix

is

as

follows:0

1

0

0

10

2

1

0

01

0

3

0

00

0

1

1

1If

x

=

0,

we

have

a

deadlock

immediately.

If

x

=

1,

process

D

can

run

to

completion.When

it

is

finished,

the

available

vector

i1

2

2

1.

Unfortunately

we

are

nowdeadlocked.

28.

I’d

give

it

an

F

(failing)

grade.

Whatdoes

the

process

do?

Since

it

clearly

needsthe

resource,

it

just

asks

again

and

blocksagain.

This

is

no

better

than

stayingblocked.

In

fact,

it

may

be

worse

since

thesystem

may

keep

track

of

how

long

competing

processes

have

been

waitingand

assign

a

newly

freed

resource

to

theprocess

that

has

been

waiting

longest.

Byperiodically

timing

out

and

trying

again,

aprocess

loses

its

seniority.

29.

A

deadlock

occurs

when

a

set

ofprocesses

are

blocked

waiting

for

an

eventthat

only

some

other

process

in

the

set

cancause.?

On

the

other

hand,

processes

in

alivelock

are

not

blocked.

Instead,

theycontinue

to

execute

checking

for

a

conditioto

become

true

that

will

never

become

true.Thus,

in

addition

to

the

resources

they

areholding,

processes

in

livelock

continue

toconsume

precious

CPU

time.Finally,

starvation

of

a

process

occurs補(bǔ)充題

A

system

has

five

processes

and

four

allocatableresources.

The

current

allocation

and

additionalneeds

are

as

follows:Please

answer

the

following

questions:（1）Is

this

state

safe?

Why?（2）The

request

(1,2,2,2)

of

P3

can

be

grantedProcessAllocationNeedAvailableABCDABCDABCDP

100305312042401200012P

210750P

3133561622P

403652P

500656補(bǔ)充題答案(1)

P1’s

request

(0,0,1,2)<(1,6,2,2),

so

P1

canacquire

max

resources

and

release.

The

availablebecomes

(1,6,5,4).

P4’s

request

(0,6,5,2)<(1,6,5,4),

so

P4

canacquire

max

resources

and

release.

The

availablebecomes

(1,9,8,6).

P2’s

request

(1,7,5,0)<(1,9,8,6),

so

P2

canacquire

max

resources

and

release.

The

availablebecomes

(2,9,8,6).

P3’s

request

(2,3,5,6)<(2,9,8,6),

so

P3

canacquire

max

resources

and

release.

The

availablebecomes

(3,12,13,10)P5’s

request

(0,6,5,6)<(3,12,13,10),

so

P5

can補(bǔ)充題答案(2)

P3’s

request

(1,2,2,2)<(1,6,2,2),

so

first

alloc(1,2,2,2)

to

P3.

The

available

becomes

(0,4,0,0).

None

of

the

processes

can

complete.

So

therequest

(1,2,2,2)

of

P3

can

not

be

granted.52Chapter

411.

Data

transfer

rate

=

8MB/s

Transfer

time

of

8KB

=

8KB

/

8MB

=

2

–

10sec

=

0.977

msec

Time

of

read

and

write

a

file

=

2×

(5

+

4

+0.977

)

=

19.954

msec

Compaction

time

of

half

of

a

8GB

disk

=(8GB

/

8KB)

×

19.954

=

20923

sec

≈

5.8hours53

17.

Elinor

is

right.

Having

two

copies

of

thnode

in

the

table

at

the

same

time

is

adisaster,

unless

both

are

read

only.

Theworst

case

is

when

both

are

being

updatedsimultaneously.

When

the

i-nodes

are

writteback

to

the

disk,

whichever

one

gets

writtenlast

will

erase

the

changes

made

by

the

otheone,

and

disk

blocks

will

be

lost.

18.

(1)Hard

links

do

not

require

any

extradisk

space,

just

a

counter

in

the

i-node

tokeep

track

of

how

many

there

are.

Symboliclinks

need

space

to

store

the

name

of

the

filpointed

to.5420.

The

beginning

of

the

bitmap

looks

like:(a)

After

writing

file

B:

1111

1111

1111

000(b)

After

deleting

file

A:

1000

0001

11110000(c)

After

writing

file

C:

1111

1111

1111

110(d)

After

deleting

file

B:

1111

1110

00001100

32.

maximum

size

of

file

blocks

=

10

+256+256*256

+

256*256*256

=

266

+

65536+

16777216

=16843018

Maximum

file

size

=

16843018

*

1KB

=16.06GB55

34.

Some

pros

are

as

follows.

First,

no

diskspace

is

wasted

on

unused

i-nodes.

Second,it

is

not

possible

to

run

out

of

i-nodes.

Thiless

disk

movement

is

needed

since

the

i-node

and

the

initial

data

can

be

read

in

oneoperation.

Some

cons

are

as

follows.

First,

directorentries

will

now

need

a

32-bit

disk

addressinstead

of

a

16-bit

i-node

number.

Second,an

entire

disk

will

be

used

even

for

fileswhich

contain

no

data

(empty

files,

devicefiles).56

34.

Third,

file

system

integrity

checks

wilslower

because

of

the

need

to

read

an

entireblock

for

each

i-node

and

because

i-nodeswill

be

scattered

all

over

the

disk.

Fourth,files

whose

size

has

been

carefully

designeto

fit

the

block

size

will

no

longer

fit

thesize

due

to

the

i-node,

messing

upperformance.57Chapter

5

3.

It

is

not

a

good

idea.

The

memory

bus

issurely

faster

than

the

I/O