과제개요 Nachos Project Assignment #2 스레드와동기화 이번과제는 Nachos 운영체제의스레드와동기화부분의코드와기능을분석하고여러가지기능을구현함으로써운영체제의스레드와동기화를파악할수있는과제입니다. 운영체제의핵심적인기능인스레드와동기화를파악하면서시스템에치명

Transcription

1 운영체제 2 차 Nachos Project 팀명 구성원 garbage 2000XXXX X X X 2000XXXX X X X 2000XXXX X X X 과목명 : 운영체제 교수님 : XXX 교수님 제출일 : 0X 년 X 월 X 일 ( 火 )

2 과제개요 Nachos Project Assignment #2 스레드와동기화 이번과제는 Nachos 운영체제의스레드와동기화부분의코드와기능을분석하고여러가지기능을구현함으로써운영체제의스레드와동기화를파악할수있는과제입니다. 운영체제의핵심적인기능인스레드와동기화를파악하면서시스템에치명적인문제를일으킬수있는교착과기아상태에대한내용과예방등을학습할수있는과제인거같습니다. 팀구성원작업분담내용 저희 garbage 팀의분담내용은아래의표와같습니다. 팀명 garbage 성명학번작업내용 고 X X 김 X X 이 X X 2000XXXXX 2000XXXXX 2000XXXXX thread 코드및루틴분석 Nachos 운영체제의전체적인 System 구조분석 주석문해석 각종자료및문서검색 semaphore 코드및 condition variable 의차이점분석 동기화실험문제자료검색 Thread::Join() 구현 Nachos Java 버전에서사용된 Java 언어적특징과 C++ 버전과의차이분석 priority scheduling 구현 동기화실험식당문제구현 레포트작성 Thred 루틴분석 소스코드를분석한내용은굵은이탤릭체에그림자를넣어서 표시하였습니다. 29-1

3 KThread.java 파일소스분석 KThread.java package nachos.threads; //nachos 디렉토리안의 threads 안에포함시킴. import nachos.machine.*; //nachos 디렉토리안의 machine 디렉토리밑에있는모든함수 import 시킴. KThead * KThread 는 nachos 커널코드를실행시키기위해사용할수있는스레드로써 * 다중스레드를지원한다. * 실행하기위해새로운스레드생성할때 Runable 인터페이스로구현된클래스를 * 먼저선언해야한다. * Runable 은하나의메소드 run() 만을선언하며, 이것이바로스레드가시작되면 * 실행되는메소드이다. KThread 가생성될때 run() 메소드를통해인수를보내고 * forked 시킴. public class KThread { * Get the current thread. // current thread 얻음 the current thread. // current thread 리턴 public static KThread currentthread() { Lib.assert(currentThread!= null); return currentthread; currentthread() * currentthread 가 null 값이아니면 Lib.assert() 에 true 값전달 * true 면 assert 하고 false 면에러메시지보냄. currentthread 리턴 * * public static void assert(boolean expression) { * if (!expression) * throw new AssertionFailureError(); * public KThread() { if (currentthread!= null) { tcb = new TCB(); else { readyqueue = ThreadedKernel.scheduler.newThreadQueue(false); readyqueue.acquire(this); currentthread = this; tcb = TCB.currentTCB(); name = "main"; restorestate(); createidlethread(); 29-2

4 KThread() * 새로운 KThread 를할당한다. * 이것이첫번째 KThread 이면 idle thread 도생성한다. * currentthread 값이있으면 TCB() 생성, * currentthread 값이 null 이면 readyqueue 에 newtreadqueue 에 false 로지정. * Allocate a new KThread. 새로운 KThread 할당 * target the object whose <tt>run</tt> method is called. * run() 메소드에있는 target 호출 public KThread(Runnable target) { this(); this.target = target; KThread(Runnable target) * Runnable 의 target( 실행될스레드 ) 을인수로받아 KThread 의 target 에저장. * Set the target of this thread. 이스레드에서 target 을정함 * target the object whose <tt>run</tt> method is called. * target 은 run() 메소드에서호출된객체이다 this thread. 이스레드를리턴함 public KThread settarget(runnable target) { Lib.assert(status == statusnew); this.target = target; return this; * Set the name of this thread. This name is used for debugging purposes * only. * 이스레드의이름을정한다. 이것의이름은단지디버깅을하기위해서사용한다. * name the name to give to this thread. * 이스레드의이름을얻음 this thread. 이것의스레드리턴한다 public KThread setname(string name) { this.name = name; return this; 29-3

5 * Get the name of this thread. This name is used for debugging purposes * only. * 이것의스레드의이름을얻는다. * 이것의이름은단지디버깅을하기위해서만사용된다. * the name given to this thread. * 이것의스레드에서주어진이름을리턴함 public String getname() { return name; * Get the full name of this thread. This includes its name along with its * numerical ID. This name is used for debugging purposes only. * 이것의전체이름을얻는다. 이것은숫자로된 ID 를포함한다. * 이이름도단지디버깅을위해서만사용된다. * the full name given to this thread. * 이스레드에서얻어진전체이름을반환한다. public String tostring() { return (name + " (#" + id + ")"); * Deterministically and consistently compare this thread to another * thread. * 다른스레드에대해이스레드를비교한다. public int compareto(object o) { KThread thread = (KThread) o; if (id < thread.id) return -1; else if (id > thread.id) return 1; else return 0; 이객체 o 를인수로받아들임. 현재 id 값이더작으면 -1 을반환하고현재 id 값이더크면 1 을반환현재 id 와다른스레드의 id 가같으면 0 을반환한다. 29-4

6 * 이스레드를실행시키기위해 fork() 메소드호출. * 이결과는 2 개의스레드가병행적으로실행되도록한다. * 이 2 개의스레드는 fork() 메소드로부터호출되어반환된 current thread 와 * run() 메소드에의해 target 되어실행되는또다른스레드이다. public void fork() { Lib.assert(status == statusnew); Lib.assert(target!= null); Lib.debug(dbgThread, "Forking thread: " + tostring() + " Runnable: " + target); // 이 forking 될스레드의이름과 runnable 된 target 을저장 boolean intstatus = Machine.interrupt().disable(); // 초기상태를 false 로지정함 tcb.start(new Runnable() { public void run() { runthread(); ); // tcb 안에있는스레드를실행시키기위해 start() 를호출함 // Runnable() 의공간을할당시키고 run() 을통해서실행될수있다. ready(); // ready() 함수호출 : 스레드를실행하기위해준비시킴 Machine.interrupt().restore(intStatus); // intstatus 를복구시킴 private void runthread() { begin(); target.run(); finish(); // run//thread() 는 private 로선언 ( 현재클래스에서만사용가능 ) private void begin() { Lib.debug(dbgThread, "Beginning thread: " + tostring()); // flag 상태디버깅 Lib.assert(this == currentthread); restorestate(); Machine.interrupt().enable(); // 인터럽트가능하게함 29-5

7 * finish() 는 current thread 가끝나고 * 안전하게스레드가제거되기위해 schedule 한다. * 이메소드는스레드의 run() 값이반환될때자동으로호출된다. * 그러나또한직접호출될수있다. * * current thread 의스택과다른실행상태가여전히사용중일수있기때문에 * current thread 는즉시제거될수없다. * * 대신이스레드는다음레드가실행됨에따라자동으로제거되고 * 안전하게삭제된다. public static void finish() { Lib.debug(dbgThread, "Finishing thread: " + currentthread.tostring()); Machine.interrupt().disable(); Machine.autoGrader().finishingCurrentThread(); Lib.assert(toBeDestroyed == null); tobedestroyed = currentthread; currentthread.status = statusfinished; //currentthread 의상태를 finish 상태로바꿔줌 sleep(); // sleep() 함수호출. * 다른스레드가실행하기위해 ready 상태에있으면 * 그스레드에게 CPU 를양도한다. * 만약레디큐에현재스레드를놓으면언젠가는다시스케줄되어야한다. * * 만약다른스레드가실행할준비가되어있지않다면즉시리턴한다. * 그렇지않으면 readyqueue.nextthread() 에의해다시선택되어진 * current thread 를리턴한다. * * 인터럽트는 disable 된다. * current thread 는스스로 ready queue 에더해지고다음 thread 와교환한다. * return 될때인터럽트는그전상태로복구된다. * cyield() 는인터럽트가 disabled 된상태로호출된다. public static void yield() { Lib.debug(dbgThread, "Yielding thread: " + currentthread.tostring()); Lib.assert(currentThread.status == statusrunning); boolean intstatus = Machine.interrupt().disable(); currentthread.ready(); runnextthread(); Machine.interrupt().restore(intStatus); //currentthread 는 ready() 함수호출 // 인터럽트그전상태로복구 29-6

8 * current thread 가끝나거나 block 되었을때 CPU 를양도한다. * 이스레드는반드시 current thread 이어야만한다. * * current thread 가 ( 동기화인세마포어, 락, 컨디션에의해 ) 블록되었다면 * 언젠가는어떤스레드는이스레드를재시작시킬것이고, * 새로스케줄될수있으므로레디큐위에다시놓여진다. * 그렇지않으면 finish() 메소드는다음스레드의실행에의해 * 이스레드가제거되되도록스케줄되어야한다. public static void sleep() { Lib.debug(dbgThread, "Sleeping thread: " + currentthread.tostring()); if (currentthread.status!= statusfinished) currentthread.status = statusblocked; // currentthread 상태가 finish 가아니면 currentthread 상태를 block 으로저장한다. runnextthread(); // 다음스레드를실행한다. * 이스레드를레디상태로이동하고레디큐의스케줄러에추가한다. public void ready() { Lib.debug(dbgThread, "Ready thread: " + tostring()); Lib.assert(status!= statusready); status = statusready; // 상태를레디상태로저장 if (this!= idlethread) readyqueue.waitforaccess(this); Machine.autoGrader().readyThread(this); * 이스레드가끝나기를기다린다. * 만약이스레드가이미끝났다면즉시리턴한다. * join() 메소드는단지한번만호출되어야만한다. * 이스레드는 current thread 가되서는안된다. 29-7

9 public void join() { Lib.debug(dbgThread, "Joining to thread: " + tostring()); Lib.assert(this!= currentthread); * idle 스레드생성. * 실행하기위해준비된스레드가없을때에는 runnextthread() 를호출되고 * 그것은 idle thread 를실행시킬것이다. * idle 스레드는절대 block 되지않고 * 단지모든다른스레드들이블록되었을때만할당된다. private static void createidlethread() { Lib.assert(idleThread == null); idlethread = new KThread(new Runnable() { public void run() { while (true) yield(); ); idlethread.setname("idle"); Machine.autoGrader().setIdleThread(idleThread); idlethread.fork(); * 다음실행될스레드를결정한다. * 그다음 run() 을이용하여 CPU 을 dispatch 시킨다. private static void runnextthread() { KThread nextthread = readyqueue.nextthread(); if (nextthread == null) nextthread = idlethread; // 다음실행될스레드가없으면다음스레드를 idle 스레드로바꾼다. nextthread.run(); * 이스레드에 CPU 를 dispatch 시킨다. * current thread 의상태를저장하고 TCB.contextSwitch() 의호출에의해 * 새로운스레드로바꾼다. * 그리고새로운스레드의상태를 load 시킨다. * 새로운스레드는 current thread 가된다. * * 만약새로운스레드와그전스레드가같으면이메소드는 * savestate(), contextswitch(), restorestate() 를호출해야한다. 29-8

10 private void run() { Machine.yield(); currentthread.savestate(); Lib.debug(dbgThread, "Switching from: " + currentthread.tostring() + " to: " + tostring()); currentthread = this; tcb.contextswitch(); currentthread.restorestate(); * 만실행이되기위해이스레드를준비한다. * statusrunning 을위한 status 를정하고 tobedestroyed 를체크한다. protected void restorestate() { Lib.debug(dbgThread, "Running thread: " + currentthread.tostring()); Lib.assert(this == currentthread); Lib.assert(tcb == TCB.currentTCB()); Machine.autoGrader().runningThread(this); status = statusrunning; if (tobedestroyed!= null) { tobedestroyed.tcb.destroy(); tobedestroyed.tcb = null; tobedestroyed = null; /* * 스레드를프로세서와끊기위한준비. * 커널스레드는여기서아무것도필요하지않다. protected void savestate() { Lib.assert(this == currentthread); private static class PingTest implements Runnable { PingTest(int which) { this.which = which; 29-9

11 public void run() { for (int i=0; i<5; i++) { System.out.println("*** thread " + which + " looped " + i + " times"); currentthread.yield(); private int which; public static void selftest() { Lib.debug(dbgThread, "Enter KThread.selfTest"); new KThread(new PingTest(1)).setName("forked thread").fork(); new PingTest(0).run(); private static final char dbgthread = 't'; * Additional state used by schedulers. * 스케줄러에의해사용되는추가적인상태. * nachos.threads.priorityscheduler.threadstate public Object schedulingstate = null; private static final int statusnew = 0; private static final int statusready = 1; private static final int statusrunning = 2; private static final int statusblocked = 3; private static final int statusfinished = 4; // 스레드 5 가지상태정의 * 이스레드의상태. * 스레드는 new, ready, running, blocked 의상태로이루어질수있다. private int status = statusnew; private String name = "(unnamed thread)"; private Runnable target; private TCB tcb; * 이스레드를위한식별자는유일하다. * 이식별자는스레드를비교하고결정하는데사용한다

12 private int id = numcreated++; Number of times the KThread constructor was called. private static int numcreated = 0; private static ThreadQueue readyqueue = null; private static KThread currentthread = null; private static KThread tobedestroyed = null; private static KThread idlethread = null; Thread 생성에서소멸까지의경로 Nachos Java 버전쓰레드의생성에서소멸까지의도식 KThread.KThread (Garbage collection) New KThread.fork KThread.run (TCB.contextSwitch) Finished KThread.finish Ready Running KThread.ready KThread.yield Blocked KThread.sleep 1 먼저스레드가생성된다. KThread.KThread 에의해스레드생성 public KThread() { if (currentthread!= null) { tcb = new TCB(); else { readyqueue = ThreadedKernel.scheduler.newThreadQueue(false); readyqueue.acquire(this); currentthread = this; tcb = TCB.currentTCB(); name = "main"; restorestate(); 29-11

13 createidlethread(); public KThread(Runnable target) { this(); this.target = target; createidlethread(); 2 생성된스레드를 Ready 시킨다. public void fork() { Lib.assert(status == statusnew); Lib.assert(target!= null); KThread.fork 에의해 Ready 시킴 Lib.debug(dbgThread, "Forking thread: " + tostring() + " Runnable: " + target); boolean intstatus = Machine.interrupt().disable(); tcb.start(new Runnable() { public void run() { runthread(); ); ready(); Machine.interrupt().restore(intStatus); 3 스레드를실행시킨다. KThread.run 에의해 Thread 실행시킴 private void run() { Machine.yield(); currentthread.savestate(); Lib.debug(dbgThread, "Switching from: " + currentthread.tostring() + " to: " + tostring()); currentthread = this; tcb.contextswitch(); currentthread.restorestate(); // 문맥교환일어남 29-12

14 4 yield() 가호출되어 Running 상태에서 Ready 상태로전환된다. KThread.yield 에의해 Running 상태에서 Ready 상태로전이됨. public static void yield() { Lib.debug(dbgThread, "Yielding thread: " + currentthread.tostring()); Lib.assert(currentThread.status == statusrunning); boolean intstatus = Machine.interrupt().disable(); currentthread.ready(); runnextthread(); Machine.interrupt().restore(intStatus); 5 sleep() 메서드에의해 block 된다. KThread.sleep 에의해 block 상태로바뀜 public static void sleep() { Lib.debug(dbgThread, "Sleeping thread: " + currentthread.tostring()); if (currentthread.status!= statusfinished) currentthread.status = statusblocked; runnextthread(); 6 ready() 메서드에의해다시 Ready 상태로돌아온다. KThread.ready 에의해다시 ready 상태로변함 public void ready() { Lib.debug(dbgThread, "Ready thread: " + tostring()); Lib.assert(status!= statusready); status = statusready; if (this!= idlethread) readyqueue.waitforaccess(this); Machine.autoGrader().readyThread(this); 29-13

15 7 finish() 메서드에의해스레드가소멸된다. KThread.finish 에의해스레드소멸 public static void finish() { Lib.debug(dbgThread, "Finishing thread: " + currentthread.tostring()); Machine.interrupt().disable(); Machine.autoGrader().finishingCurrentThread(); Lib.assert(toBeDestroyed == null); tobedestroyed = currentthread; currentthread.status = statusfinished; sleep(); contextswitch() 분석 위에있는 thread 생성에서소멸까지의경로에서볼수있듯이 run() 메소드에서문맥교환이일어난다. TCB(Thread Control Block) 에순서대로저장되어있는 Thread가 Ready 상태에서 Running 상태로되면서스레드를문맥교환해준다. private void run() {... currentthread = this; tcb.contextswitch(); => 문맥교환일어남 currentthread.restorestate(); 왜 sleep() 은 interrupt disable을가정했을까? sleep() 은스레드가잠시 block 되도록만드는데 block 된상태에서 interrupt가되면 block이해재되고문제가발생하기때문에 interrupt().disabled() 로설정한다

16 Semaphore.java 파일소스분석 package nachos.threads; import nachos.machine.*; semaphore.java * A <tt>semaphore</tt> is a synchronization primitive with an unsigned value. * A semaphore has only two operations: * 세마포어는 unsigned 값을가진동기화도구이다. 세마포어는 2 개의연산만가진다. * <ul> * <li><tt>p()</tt>: waits until the semaphore's value is greater than zero, * then decrements it. * <li><tt>v()</tt>: increments the semaphore's value, and wakes up one thread * waiting in <tt>p()</tt> if possible. * </ul> * P(): 세마포어의값을하나감소시킨다음그값이 0 보다커질때까지기다린다. * V(): 세마포어의값을하나증가시키고 P() 안에기다리고있는한스레드의실행을재시작시킨다. public class Semaphore { public Semaphore(int initialvalue) { value = initialvalue; // 초기값설정 * Atomically wait for this semaphore to become non-zero and decrement it. *public Semaphore( int initialvalue); Semaphore class 의 2-parameter constructor 이다. 첫번째 parameter debugname 은 debug 용 semaphore 의 name 이고, initialvalue 는 semaphore 의초기 value 값이다. 이 value 는 P() 에서감소하고, V() 에서증가하는값이다. 이값을 1 로하면, 한 critical section 에한 thread 만들어갈수있음을의미한다. 내부에서는 queue 라는 List 변수를만들어다른 thread 가 critical section 으로들어갔을때 P() 를부르게되면기다리게되는 thread 들을저장하는 FIFO 형태의 queue list 이다. public void P() { boolean intstatus = Machine.interrupt().disable(); if (value == 0) { waitqueue.waitforaccess(kthread.currentthread()); KThread.sleep(); else { value--; 29-15

17 Machine.interrupt().restore(intStatus); void P() atomic 하게구현된세마포어함수이다. thread 가진입할때마다 value 를감소시키고, value 가 0 이라면더 thread 가진입할수없는상황이다. 이때 thread 가진입을시도하면 Sleep() 당해서 queue 에달리게된다. * Atomically increment this semaphore and wake up at most one other thread * sleeping on this semaphore. -> 세마포어를증가시키고 sleeping 되어있는다른스레드중하나을재시작시킨다. public void V() { boolean intstatus = Machine.interrupt().disable(); KThread thread = waitqueue.nextthread(); if (thread!= null) { thread.ready(); else { value++; Machine.interrupt().restore(intStatus); private static class PingTest implements Runnable { PingTest(Semaphore ping, Semaphore pong) { this.ping = ping; this.pong = pong; public void run() { for (int i=0; i<10; i++) { ping.p(); pong.v(); private Semaphore ping; private Semaphore pong; void V(): atomic 하게구현된세마포어함수이다. value 를하나더하고, queue 에서잠든상태로기다리고있는 thread 가있으면하나를깨워서대기중상태로만든다. * Test if this module is working. public static void selftest() { Semaphore ping = new Semaphore(0); Semaphore pong = new Semaphore(0); 29-16

18 new KThread(new PingTest(ping, pong)).setname("ping").fork(); for (int i=0; i<10; i++) { ping.v(); pong.p(); private int value; private ThreadQueue waitqueue = ThreadedKernel.scheduler.newThreadQueue(false); semaphore와 condition variable의차이점 semaphore에는 P() 함수와 V() 함수가있지만, condition variable에는 Wait() 함수와, Signal() 함수가있다. thread가 semaphore나 condition variable에서 Sleep() 하는경우, semaphore의경우, 그곳에서 thread가기다리려면 P() 함수를호출해서 semaphore.value가 0이라면 thread가그 semaphore안에있는 queue에매달리면서 Sleep() 을하고, 이미진입한 thread가계속나가면서자신의차례가올때까지 semaphore의 queue에서자고있다. 그러나 condition variable의경우에는조건없이 thread를 condition variable 안에있는 queue에매달고 Sleep() 을하는 Wait() 만이존재한다. semaphore나 condition variable에서 Sleep() 하고있는 thread를깨우기위해서 semaphore의경우에는 V() 함수를통해서그 semaphore의 queue에매달려있는 thread들을 ready-list 로넣고 semaphore 안에있는 value++ 를하지만, condition variable의경우에는 Signal() 함수를통해서 condition variable 안에있는 queue에서기다리고있는 thread들을하나깨워 ready-list로넣는다. ( 혹은 Broadcast() 를통해모두깨워서 ready 상태로만든다 ) semaphore를이용해서코딩을하는경우, 코딩을하는사람은반드시 P() 함수와 V() 함수를쌍으로구현해야한다. 만일, 이 rule을지키지않으면, 일부 thread들이 semaphore에서기다리기만하는경우가생길수있다 (dead lock). 하지만 condition variable의경우에는대체로이런위험이적다고한다

19 semaphore는 interrupt disable/enable으로 atomicity가보장된 P(), V() 함수를이용해 value값을조절하여 Synchronization을구현한다. 반면, condition variable은물론 semaphore를사용하지만이는 thread가 critical section으로진입하고나올때만호출되어지는단순한기능을한다고볼수있다. condition variable은 semaphore와다르게 critical section으로진입하지못한 thread들을저장하는자료구조 list waitqueue를사용한다. 또한 protection으로 Lock variable을사용한다. wait() 내부에서는 Release() 를부른후 P() 를불러기다린다. signal() 이불려지면, waitqueue에서나와서 V() 를호출하고 wait() 내에서 lock을 Acquire() 한다. Broadcast() 함수는 waitqueue에있는모든 thread들의 signal() 을불러준다. alarm, timer, interrupt의관계 Interrupt::OneTick() 은 stats->totalticks를증가시키고, pending interrupt가있는지없는지를검사한다 (Interrupt::CheckIfDue()). 이때 pending interrupt는 SortedList에 PendingInterrupt* 의형태로들어가게된다. 그리고, PendingInterrupt class에는 interrupt가언제처리될지와, 처리될때어떤함수를불러서처리할지에대한정보를담은 member들이들어간다. Interrupt::CheckIfDue(bool advanceclock) 에서는 PendingInterrupt 들을처리한다. 현재의 tick이인터럽트가발생해야할때의 tick보다작은경우, 인자로넘어온, advanceclock의값에따라결정된다. 만일이값이 TRUE이라면, 현재의 tick을인터럽트가발생할때만큼증가시켜주고, 인터럽트를처리한다. 예를들어 PendingInterrupt가 Timer 객체인경우를생각해보자. 우선 nachos에서는 Timer 객체는 Alarm class안에서정의된다. Alarm객체는 Kernel class에서정의된다. PendingInterrupt를처리하는경우, 그인터럽트의 CallBack() 함수를호출하게된다. 이때 Timer에대한 CallBack() 함수는 Alarm::CallBack() 함수를부른다. 이때, 이 Alarm::CallBack() 함수가, nachos 에서는 Timer인터럽트에대한 Interrupt Handler로취급된다. Interrupt Handler루틴이끝난후에, Timer::CallBack() 함수는, 다음 time interrupt를 PendingInterrupt에매단다 (Timer::SetInterrupt())

20 Thread::Join() 구현 Join() 을구현하기위해서는먼저 Join() 이무엇인지알아야하는데문제 에서 C 의 wait() 와유사한기능이라고제시하였기때문에먼저 C 의 wait() 함수가무엇인지분석하였습니다. wait() 함수는유닉스에서사용되는함수로서프로세스가대기하도록하는 함수이다. wait() 시스템콜을호출하면커널은프로세스들이종료되었는지검사하고 부모프로세스는자식프로세스가종료할때까지기다리며, 종료된자식의 PID(Process ID) 를돌려준다. 종료된프로세스를좀비 (zombie) 프로세스라고하는데, 종료된프로세스는 부모프로세스가자신에게 wait() 시스템콜을호출하기전까지좀비 프로세스로남아있는다. 만약에부모프로세스가 wait() 를호출하지않고종료된다면자식프로세스는 작업이종료된후에도 wait() 시스템콜을기다리면서좀비프로세스로남아 시스템자원을계속차지하게될것이다. 이에대한해결책으로시스템은초기화중에 init 이라는특별한시스템 프로세스를만든다. 한프로세스가종료되면커널은모든자식프로세스들의 디스크립터포인터를변경하여그들을 init 프로세스의자식으로만든다. 그리고 init 프로세스는모든자식들의실행상태를지켜보며정기적으로 wait() 시스템콜을호출하여모든좀비프로세스들을제거한다. 간단하게 C 언어로작성된소스를살펴보면서 wait() 의기능을확인해보자. 유닉스 C 언어로작성된 wait() 기능 main() { int pid; printf("parent pid of a.out: pid = fork(); // 자식프로세스생성 // 부모프로세스코드부분 if (pid > 0 ) wait((int *)0); // 자식프로세스가끝날때까지기다린다! printf("\nparent process id: %d, parent pid: exit(0); 29-19

21 // 자식프로세스코드부분 if (pid == 0) { printf("child process id: %d, parent pid: execl("/bin/ps","ps",(char *)0); fatal("execl failed"); // 에러발생 fatal("fork failed"); fatal(char *s) { perror(s); exit(1); 위의소스를보면 pid=fork(); 부분에서자식프로세스가생성되는데이는부모프로세스와똑같은코드가된다. 단, 차이점은 fork() 의값이 0이면자식프로세스이고아니면부모프로세스이다. 그래서 if (pid > 0 ) {... 이부분에서는부모프로세스만실행되고 if(pid == 0){... 부분에서는자식프로세스만실행된다. 저희조가프로젝트에사용한 Nachos Java버전에서는 threads 디렉토리아래에있는 KThread.java 파일안에 Join() 메서드가구현되어있습니다. 그리고 Java라는언어자체가 thread를구현하는데 join() 메서드를지원합니다. 따라서소스구현은위에제시한 C언어버전으로대신하고 Java언어상의 join() 메서드에대해서알아보겠습니다. wait() 메서드는스스로자원에대한권한을포기하고대기상태로들어가는기능을구현한다. 생산자와소비자가있을때생산자가자원이없으면소비자를깨운뒤 wait() 를이용하여스스로실행불능상태로옮겨가고, 반대로소비자가자원이없으면생산자를깨운뒤스스로대기상태로들어가서자원이생기도록유도한다. wait() 를호출하기위해서는메서드를호출하는스레드가반드시자원의락 ( 권한 ) 을가지고있어야하고, 동기화 (synchronized) 블록안에서만호출이가능하다. wait() 된스레드를 notify() 를호출하여깨울때는자신이소유하고있는자원을기다리는스레드에한해서만깨우게된다

22 wait() 메서드는 wait(long timeout, int nanos); 와같이최대대기시간을 지정할수있어서주어진시간이지나면자동으로반환되게할수있다. Preemptive priority scheduling 구현 thread 에 priority 항목을추가하여우선순위를고려하게만들라는 문제입니다. 그런데자바언어에서는 thread를생성하면반드시우선순위인 priority가설정되어야하고 setpriority() 메서드를이용하여우선순위를부여할수있으며명시하지않았을경우에는기본적으로부모스레드와같은값을할당받게된다. 저희가분석한 Nachos Java 버전에서는 threads 폴더안에있는 Scheduler.java 와 PriorityScheduler.java 파일에우선순위를부여하는 코드가작성되어있으므로따로구현하지않고그부분의코드를분석 하도록하겠습니다. package nachos.threads; import nachos.machine.*; public abstract class Scheduler { public Scheduler() { Scheduler.java public abstract ThreadQueue newthreadqueue(boolean transferpriority); // ThreadQueue 라는추상메서드를설정하여자식클래스들이구현하도록강제함. public int getpriority(kthread thread) { // interrupt 가되지않도록 disabled() 로설정 return 0; public int getpriority() { return getpriority(kthread.currentthread()); // current thread 의우선순위를얻어낸다 29-21

23 public int geteffectivepriority(kthread thread) { // interrupt 가되지않도록 disabled() 로설정 return 0; public int geteffectivepriority() { return geteffectivepriority(kthread.currentthread()); // 현재스레드의유효한우선순위를얻는다. public void setpriority(kthread thread, int priority) { // interrupt 가되지않도록 disabled() 로설정 public void setpriority(int priority) { setpriority(kthread.currentthread(), priority); // 여기에서현재스레드의우선순위를설정한다 public boolean increasepriority() { return false; // 가능한범위안에서현재스레드의우선순위를높인다. public boolean decreasepriority() { return false; // 가능한범위안에서우선순위를낮추는메서드 PriorityScheduler.java package nachos.threads; import nachos.machine.*; import java.util.treeset; import java.util.hashset; import java.util.iterator; public class PriorityScheduler extends Scheduler { // 위에서분석한 Scheduler 를상속받았다. public PriorityScheduler() { // 디폴트생성자 public ThreadQueue newthreadqueue(boolean transferpriority) { return new PriorityQueue(transferPriority); // 부모클래스에서추상메서드로구현해놓은 ThreadQueue 메서드를오버라이딩했다

24 public int getpriority(kthread thread) { return getthreadstate(thread).getpriority(); // interrupt 가되지않도록 disabled() 로설정하고스레드의우선순위를얻는다. public int geteffectivepriority(kthread thread) { return getthreadstate(thread).geteffectivepriority(); public void setpriority(kthread thread, int priority) { Lib.assert(priority >= priorityminimum && priority <= prioritymaximum); getthreadstate(thread).setpriority(priority); public boolean increasepriority() { // 상속받은클래스의메서드를오버라이딩 boolean intstatus = Machine.interrupt().disable(); KThread thread = KThread.currentThread(); // 현재스레드를설정하고, int priority = getpriority(thread); // 스레드의우순순위를받고, if (priority == prioritymaximum) return false; // 만약에현재스레드의우선순위가 Maximum 이면더이상증가시킬수없으므로 false 를돌려준다. setpriority(thread, priority+1); // 우선순위를증가시킨다. Machine.interrupt().restore(intStatus); return true; public boolean decreasepriority() { // 메서드오버라이딩 boolean intstatus = Machine.interrupt().disable(); KThread thread = KThread.currentThread(); // 현재스레드를설정하고, int priority = getpriority(thread); // 스레드의우선순위를받고, if (priority == priorityminimum) return false; // 만약에현재스레드의우선순위가최소이면더이상감소시킬수없으므로 false 를돌려준다. setpriority(thread, priority-1); // 우선순위감소 Machine.interrupt().restore(intStatus); return true; 29-23

25 * 스레드가생성되면디폴트우선순위를갖고그값은 1 이다. * public static final int prioritydefault = 1; * * 최소우선순위 (priorityminumim) 값은 0 이다. * public static final int priorityminimum = 0; * * 최대우선순위값은 7 이다. * public static final int prioritymaximum = 7; protected ThreadState getthreadstate(kthread thread) { if (thread.schedulingstate == null) thread.schedulingstate = new ThreadState(thread); return (ThreadState) thread.schedulingstate; // ThreadQueue 는스레드를우선순위별로저장한다. protected class PriorityQueue extends ThreadQueue { PriorityQueue(boolean transferpriority) { this.transferpriority = transferpriority; public void waitforaccess(kthread thread) { getthreadstate(thread).waitforaccess(this); public void acquire(kthread thread) { getthreadstate(thread).acquire(this); public KThread nextthread() { // implement me return null; // 다음스레드가선택된다. // 다음스레드가선택된다. protected ThreadState picknextthread() { // implement me return null; 29-24

26 public void print() { public boolean transferpriority; protected class ThreadState { public ThreadState(KThread thread) { this.thread = thread; setpriority(prioritydefault); // 디폴트우선순위 (1) 로설정된다. // 관련된스레드의우선순위를돌려준다. public int getpriority() { return priority; // 스레드가사용가능한유효한우선순위를돌려준다. public int geteffectivepriority() { // implement me return priority; public void setpriority(int priority) { if (this.priority == priority) return; this.priority = priority; public void waitforaccess(priorityqueue waitqueue) { public void acquire(priorityqueue waitqueue) { // 객체의스레드 protected KThread thread; // 관련된스레드의우선순위 protected int priority; 29-25

27 Synchronization 실험문제 이번에제시된문제는동기화를구현하기위한문제로서 Worker가음식을만들면 Student들이음식을먹는프로그램을스레드들이교착상태에빠지지않도록만드는것입니다. 문제의해결을위해음식을만드는 Worker 스레드와음식을먹는 Student 스레드를구현한 Java 프로그램을작성하였습니다. Worker 는하나의스레드로구현하였고, 음식 (Food) 를만들고나서 wait() 로대기상태에들어갑니다. Student 는 3 개의스레드로구현하였고, 음식을놓고서로경쟁합니다. Worker는음식을만들고나서 notifyall() 을호출해서모든 Student들을깨웁니다. 깨어난 Student들은음식에대한권한을놓고서로경쟁하여권한을얻은스레드만음식을먹고다른스레드들은모두 get() 메서드에서멈추어져있는상태가됩니다. Student 스레드의 get() 메서드에서 Worker 스레드가음식을만들기를무한정기다리지않도록 100ms의시간마다스레드의종료조건을검사해서종료조건이참이면예외를발생시키도록하였습니다. 예외를받은스레드는이를처리한후종료하게됩니다. 이렇게함으로써 Worker 가만든음식을다른 Student 가모두먹어서 종료조건이참이되어도다른 Student 가종료하지못하는상황을막을 수있습니다. ( 그렇지않으면기아상태에빠질수있습니다 ) 음식은총 10개를만든다고가정하였고, 마지막 10번째의음식을먹는스레드만이종료조건을검사할수있고, 나머지 2개의스레드들은모두 get() 메서드를호출하는곳에서대기하게됩니다. 이때 get() 메서드내부에서는종료조건을점검해서예외를발생하고처리해서다른스레드도종료하게됩니다

28 아래에작성한 Java 프로그램소스는문제에서제시한모든조건을 구현하지는못했습니다. 하지만스레드들을작성하여동기화 (Synchronized) 시켰고, 기아가발생할만한요소를제거함으로서 deadlock 이나 starvation 이발생하지않고작동하도록하였습니다. 문제에서의도한 기본에는충실하게작성하였습니다. public class OurHome{ static class Worker extends Thread{ Food xres = null; OurHome.java public Worker(String name, Food res){ super(name); xres = res; public void run() { // 1 부터 10 까지의음식을만든다. for(int i=0; i<10; i++) { xres.put(i); System.out.println("Make Food : " + i); xres.stop(); static class Student extends Thread{ Food xres = null; public Student(String name, Food res){ super(name); xres = res; public void run() { // 학생스레드가실제로작동하는부분... 음식이있는동안먹는다. while(xres.qstop == false) { try { System.out.println( getname() + ", Eat food No. " + xres.get() ); catch(exception ex){ 29-27

29 static class Food{ boolean qavailable = false; int ndata; boolean qstop = false; Worker xproducer = null; public synchronized void stop(){ qstop = true; public synchronized int get() throws Exception{ while (qavailable == false) { try { // Worker 스레드가음식을만들때까지기다린다. // 만약 100ms 이상시간이지나면예외를발생하며반환된다. wait(100); catch (InterruptedException e){ // 만약종료조건이참이면음의값을반환한다. if (qstop == true) throw new Exception(); qavailable = false; // Worker 스레드를깨워서음식을만들도록한다. if(xproducer!= null && xproducer.isalive()) xproducer.interrupt(); return ndata; public synchronized void put(int value) { while (qavailable == true) { try { // Student 스레드가음식을먹을때까지기다린다. wait(); catch (InterruptedException e) { ndata = value; qavailable = true; // 모든 Student 스레드를깨운다. notifyall(); public void setproducer(worker prd) { xproducer = prd; 29-28

30 public static void main(string args[]){ Food res = new Food(); Worker prd = new Worker("Worker", res); Student eat = new Student("Student 1", res); Student eat2 = new Student("Student 2", res); Student eat3 = new Student("Student 3", res); res.setproducer(prd); prd.start(); eat.start(); eat2.start(); eat3.start(); try{ prd.join(); eat.join(); eat2.join(); eat3.join(); catch(exception ex){ 29-29