Classic Problems of Synchronization

1. Bounded-Buffer Problem -> 대표적인 동기화 문제 

2. Readers and Writers Problem -> scheduling 관련 동기화 문제

3. Dining-Philospohers Problem -> deadlock 관련 동기화 문제

Bounded-Buffer : Shared-Memory Solution

Producer, Consumer 문제

-> Bounded buffer 를 사용하여 producer는 생성만하고 consumer는 소비만 한다.

이때, buffer에 대한 동기화 문제가 발생하는데 이를 semaphore P, V 로 해결가능하다.

(버퍼가 꽉 찬 경우 Producer가 생성할 수 없고 버퍼가 비어있는 경우 Consumer가 읽어 올 수 없음 -> 쓰기,읽기 전 상태 확인 필요)

하지만 본질적인 문제는 Buffer 내의 변수들에 대한 동기화 문제도 동시에 해결해야함 -> 변수 자체를 semaphore 변수로 만들자! 

[문제 해결]

변수 자체를 semaphore 변수로 만들어 사용

integer semaphore N을 사용하여 buffer의 개수를 읽어 다른 process가 접근하지 못하도록 해야한다. 

N_empty-buf : 버퍼가 비어있는지 확인

N_full-buf : 버퍼가 가득 차있는지 확인

binary semaphore S_mutex 를 사용하여 buffer 에 대한 동기화 문제를 해결

integer semaphore 를 사용하여 buffer 가 비었는지, 꽉 차있는지 확인하여 접근에 대한 동기화 문제 해결

mutex가 필요할까?

-> buffer의 개수는 복수개이다. 반쯤 채워진 경우 두개의 프로세스가 통과하여 동기화 문제를 발생시킬 수 있으므로 P,V 를 사용하여 buffer를 보호해준다.

왔다갔다 할 수 있는 이유 -> P, V 함수가 atomic 하기때문에 가능하다.

Readers-Writers Problem

위에서 다룬 Producer, Consumer 문제와 유사하다. 하지만 생산자,소비자 문제에서는 Date를 소비하였지만 Readers-Writers Problem 에서는 Data를 소비하지 않는다는 차이점이 있다. 즉 Read-Only 동작을 하는 것이다.

동시에 Read를 할 수 있도록 하여 producer, consumer problem에 비해 Throughput을 높이고자 하는 동기화 방식으로 사용된다.

Read-Only를 하는 경우 Reader들간에는 동시에 접근이 가능하여 동기화 문제가 발생하지 않는다.

하지만 Writer 가 쓰는 도중에 읽거나, Reader가 읽는 도중에 쓰기 작업은 문제를 발생시키기 때문에 Reader와 Writer 간의 동기화 문제를 해결해줘야 한다.

<2가지 방식>

1. 모든 reader가 동시에 읽기 수행이 끝난 후 writer가 쓸수 있도록 하는 방식

2. 급한 작업인 경우 writer가 쓰고 난 후에 readers 가 읽을 수 있도록 하는 방식

여기서는 첫번째 방식을 다룬다.

reader 한명이 읽기를 시작한 경우 다른 reader들도 동시에 읽기 작업을 수행하도록 한다.

마지막 reader가 읽기 작업을 끝낸 후 writer가 쓰기 작업을 수행하도록 한다.

semaphore 변수 mutex, db를 사용하여 writer와 reader 간의 상호 배제 문제를 해결한다.

int 변수 readcount를 사용하여 reader의 읽기 상태를 확인하여 동기화 문제를 해결한다.

Reader는 첫 번째 reader 인 경우 P(db)를 호출한 뒤 읽기를 시작한다. -> Writer가 작업을 수행하지 못함

이후의 reader는 따로 P(db)를 호출할 필요가 없다. -> 두번재 reader도 호출하는 경우 동시읽기 작업 자체가 불가능해진다.

마지막 reader의 경우 읽기 작업을 끝낸 후 V(db)를 호출한다. -> Writer 가 작업을 수행할 수 있는 상태

Writer의 경우 대기하다가 마지막 reader가 읽기를 끝내고 V(db)를 호출하는 순간 쓰기 작업이 가능하여 critical section으로 넘어가게 된다.

쓰기 작업에 대해서도 마찬가지로 P(db), V(db)를 사용하여 reader 와의 동기화 문제로부터 보호한다.

Reader의 경우 P,V 함수를 호출하기 위해 첫번째,마지막 reader인지 확인을 위한 변수가 필요하다. => readcount 변수

readcount 변수 자체에 접근할 때에도 동기화 문제가 발생할 수 있다.

ex) 서로다른 reader가 동시에 readcount 를 증가시키고 읽기 작업을 수행하려는 경우 P(db)가 호출되지 않을 수 있다. 

=> 즉, read count 변수 자체에 접근하는 과정도 atomic하게 만들어줘야한다.

마찬가지로 readcount 연산 과정 앞뒤로 P,V 함수를 호출하여 count 과정 자체도 atomic하게 만들어줘 동기화 문제를 해결해준다.

( readcount ++; if(readcount ==1) , readcount --; if(readcount == 0)  해당부분이 critical section이 된다.)

Dining-Philosophers Problem : Think & Eat Repeatedly

[문제상황]

철학자들이 원탁에 둘러 앉아 생각을 하며 식사를 하는 상황.

하지만 젓가락은 양 옆으로 하나씩만 세팅되어있어 양쪽 젓가락이 사용 가능할때만 식사를 할 수 있다.

=> 젓가락을 집는 행위 자체가 동기화되어 이루어져야지 문제해결이 가능하다.

젓가락 하나를 공유변수라고 생각하면 왼쪽, 오른쪽 젓가락이 모두 사용중인 상태가 아닐 때 집어들어 식사를 할 수 있다.

P 함수(atomic한 함수)를 사용하여 P(chopstic[i])는 왼쪽, P(chopstick[(i+1)%5]) 은 오른쪽 젓가락을 나타내어 동기화 문제를 해결 할 수 있다.

But, 모든 철학자가 동시에 배가 고파 젓가락을 드는 경우를 생각해보자.

동시에 모두가 왼쪽에 있는 젓가락을 드는 과정까지는 성공을 한다. 하지만 모두의 오른쪽 젓가락은 사용중이기 때문에 대기상태에 빠진다.

서로가 기다리기만 하며 무한히 대기하는 상태가 발생하는데 이러한 상태가 Deadlock 문제가 발생한 것이다.

Deadlock이란 내가 다른 프로세스가 가진 자원을 해당 프로세스가 놓을 때까지 기다리는 형태가 원형회귀적으로 발생하여 해결되지 않고 무한히 서로가 서로를 기다리는 상태에 빠지는 것이다.

Deadlock and Starvation

Deadlock - 두 개 혹은 그 이상의 프로세스가 무한대기를 하는 경우 (대기 중인 프로세스가 깰 수 있지만 무한대기중이라 해결이 불가함)

<예시>

P0는 P(S)를 잡고 P1는 P(Q)를 잡은 상태이다.

이 경우 서로 P(Q), P(S)를 잡지 못해 서로를 계속 기다리는 상태에 빠져 다음 과정 진행이 불가하다. 마찬가지로 V(Q),V(S) 함수 호출 또한 할 수 없어 문제가 해결될 수 없다.

Starvation - 무한하게 blocking 되는 현상이다. 하지만 deadlock 문제와는 다르게 다른 어떤 프로세스는 진도를 나가고 있다는 것이 차이점이다.

LIFO 큐로 구성된 경우 Linked-List의 제일 앞의 프로세스는 거의 깨어나기 힘들어 희생되어 진행되지 못하고 있는 상태이다.

Deadlock - 3가지 해결방안

1. 젓가락을 하나씩 드는 것이 아니라 둘다 확인을 하고 동시에 들어서 문제를 해결하자 (양쪽 젓가락을 하나의 자원으로 취급)

2. Asymmetric coding -> 홀수번째 철학자는 왼쪽 젓가락을, 짝수번째 철학자는 오른쪽 젓가락을 먼저 들도록 함

3. 5명이 있는 경우 4명만 앉혀서 문제를 해결하자

-> 3가지 경우에 대해 직접 알고리즘 구현해보기!

Problems of Semaphore

: Semaphore를 이용하면 동기화 문제를 해결할 수 있지만 사용해서 해결하는 과정이 어렵다

- 코드를 구현하는 것이 어려움

- 정확성을 입증하는 것이 어려움 -> 오류를 재현하는 것이 어렵다

- 협력 과정이 필요하다.

- 잘못된 사용은 전체 시스템을 마비시킬 수 있음

* 조금 더 쉽게 해결할 수 있는 방법이 없을까? ==> Monitor 방식

Monitors : Similar to Abstract data type (private data -- public methods)

Hight-level language 에서 공유 데이터 접근 동기화 문제를 해결해주는 추상적인 데이터 타입

객체지향언어에서와 유사하게 public methods만 private data에 접근 가능한 구조이다.

Schematic View of a Monitor

Monitor 는 내부에서 단 하나의 프로세스만 active 가능하도록 보장한다. (Monitor의 기본개념)

여러 public method가 접근시도하는 경우 하나가 실행중이면 entry queue에서 나머지 프로세스가 대기하도록 한다.

Monitors

코드를 수행하는 중 조건을 만족시켜야 하는 경우가 발생하는데 다른 프로세스가 해당 조건을 만족시키는 경우가 발생한다.

=> Monitor 내부에서 wait 하도록 한다. active 하지 않게 sleep 상태로 wait 하도록 만들어주어 entry queue의 다른 프로세스가 실행할 수 있도록 해준다.

이를 위해 condition variable 을 사용한다.

condition x, y;

x.wait() -> x 조건을 만족시키지 못해 sleep 상태로 기다리도록 한다.

x.signal() -> x에서 기다리는 프로세스에게 시그널을 보내 깨워주도록 한다.

Monitor : Dining-Philosophers Problem

Dining-Philosophers Problem의 Deadlock 문제를 양쪽 젓가락을 드는 방식으로 해결한 경우

*Bounded Buffer Problem을 위한 Monitor 작성해보기

<전체코드>

전체적인 동작 과정

thinking, eating, hungry 세가지 상태로만 구분한다.

Monitor Implementation

Conditional-wait construct : x.wait(c); -> c 변수를 사용하여 우선순위를 정하여 순서를 제어하도록 하자.

Monitor 에서는 다음 두 가지 조건이 만족한다면 올바른 동기화 문제 해결책이 될 수 있다.

1. 항상 올바른 순서로 호출해야한다.

2.비협조적인 프로세스가 monitor 가 제공하는 상호배제 gateway를 무시하지 않도록 하며, 접근 프로토콜을 사용하지 않고 공유 자원에 직접 접근하도록 해야한다.

*access protocol : 장치가 네트워크를 통해 서로 통신하는 방식을 제어하는 일련의 규칙

1. 프롬프트 지니 

-> 한글로 입력시 느린 실행속도를 개선시켜줌 

2. ChatGPT for Google

-> 구글 검색시 우측에 ChatGPT 결과도 함께 출력해줌

3. YouTube Summary with ChatGPT

-> 유튜브 사용시 자막을 출력해주고 요약기능까지 가능

4. VS code에서 easycode 사용

-> vs code 내부에서 리팩터링, 코드에 대한 검색 바로 가능

과제 주제 : Timetable Application 구현

과제 조건

-Course class

먼저 Course class에 필요한 변수 (이름,교수,강의실번호,가능여부)를 선언하고 생성자를 초기화해준다.

- Timetable Class

- TimeTableAPP Class

- 크게 주어진 세 개의 클래스를 기반으로 timetable application을 구현한다.

- course class 는 시간표에 포함될 내용인 수업에 대한 속성과 메서드를 제공하는 클래스이다.

- timetable class는 강의 일정을 관리하는 메서드를 포함하는 클래스이다.

- timetableapp class는 main 함수를 포함하여 수업일정을 추가,확인 및 관리할 수 있도록 작성한 application 구현 클래스이다.

Implement

<Course Class>

package assignment;

import assignment.Course;

public class Course {		//강의 속성에 사용하는 변수 선언
	public String name;
	public String professor;
	public String roomNumber;
	public boolean isValid;

	//각각의 생성자
	public Course(String name, String tutor, String room) {
		this.name = name;
		this.professor = tutor;
		this.roomNumber = room;
	}

	public Course(String name) {
		this.name = name;
	}

	public Course(Course copy) {
		this.name = copy.name;
		this.professor = copy.professor;
		this.roomNumber = copy.roomNumber;
		this.isValid = copy.isValid;
	}

	//get 함수
	public String getName() {
		return name;
	}
	
	public String getProfessor() {
		return professor;
	}
	public String getRoomNumber() {
		return roomNumber;
	}

	//set함수
	public void setName(String name) {
		this.name = name;
	}
	public void setProfessor(String professor) {
		this.professor = professor;
	}
	public void setRoomNumber(String roomNumber) {
		this.roomNumber = roomNumber;
	}

	//동일한 강의인지 확인하는 메서드
	public boolean equals(Course s) {
        if (this.name.equals(s.name) && this.professor.equals(s.professor) && this.roomNumber.equals(s.roomNumber)) {
            return true;
        }
        return false;
    }	

	// 강의명을 반환해주는 메서드
	public String toString() {
		return name;	
	}

	// 강의명, 교수명, 강의실 정보를 반환해주는 메서드
	public String getDetails() {
		return "\nName : " + name + "\n" + "Tutor : " + professor +  "\n" + "Room : " + roomNumber + "\n";
		
	}
}

<TimeTable Class>

package assignment;

import java.util.Calendar;
import java.util.Scanner;

import assignment.Course;


public class TimeTable {
	Course[][] timeTable = new Course[5][10];
	
    //열거형 type 으로 요일 상수 정의
	public enum DAYS {
		MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY
	}

	//2차원 배열로 시간표 생성
	public TimeTable() {
		timeTable = new Course[DAYS.values().length][10];
		initialize();
		
	}
	//시간표 초기화 (점심,저녁시간 고정값으로 설정)
	private void initialize() {
        for (int i = 0; i < timeTable.length; i++) {
            for (int j = 0; j < timeTable[i].length; j++) {
                if (j == 3) {
                    timeTable[i][j] = new Course("  LUNCH", "-", "-");
                } else if (j == 7) {
                    timeTable[i][j] = new Course(" DINNER", "-", "-");
                } else {
                    timeTable[i][j] = new Course("  ----", "-", "-");
                }
            }
        }
	}
	
    //요일과 period를 받아 시간표에 입력하는 메서드
	public String getSchedule(String day, int period) {

        int dayIndex = DAYS.valueOf(day).ordinal();
        Course course = timeTable[dayIndex][period-1];
        return "At that time you have: " + course.getDetails();
	}
    
	// 강의 속성 정보를 받아 가능여부 판단
	public boolean setSchedule(String day, int period, String name, String tutor, String room) {
        if (period == 3 || period == 7) {
            return false;
        }
        int dayIndex = DAYS.valueOf(day).ordinal();
        timeTable[dayIndex][period-1].setName(name);
        timeTable[dayIndex][period-1].setProfessor(tutor);
        timeTable[dayIndex][period-1].setRoomNumber(room);
        return true;
	}

	// 시간표 format 출력
	public String toString() {		//timetable 형태를 return
            StringBuilder sb = new StringBuilder();
            sb.append("\tMONDAY TUESDAY WEDNESDAY THURSDAY FRIDAY\n");
            for (int i = 0; i < timeTable[0].length; i++) {
                sb.append((i + 1) + "\t");
                for (int j = 0; j < timeTable.length; j++) {
                    sb.append(timeTable[j][i].getName() + "\t");
                }
                sb.append("\n");
            }
            return sb.toString();
        }
        
	//요일을 입력받아 해당 요일의 시간표를 반환하는 메서드
	public String oneDaySchedule(String day) {			
        int dayIndex = DAYS.valueOf(day).ordinal();
        String result = DAYS.values()[dayIndex] + "\n";
        for (int j = 0; j < timeTable[dayIndex].length; j++) {
            result += timeTable[dayIndex][j].getDetails() + "\t";
        }
        result += "\n";
        return result;
	}
	
    //강의명을 입력 받아 요일을 반환하는 메서드
	public String subjectSchedule(String sub) {		
        String result = "";
        for (int i = 0; i < timeTable.length; i++) {
            for (int j = 0; j < timeTable[i].length; j++) {
                if (timeTable[i][j].getName().equals(sub)) {
                    result += "Subject: " + timeTable[i][j].getName() + "\n" + "Day: "+ DAYS.values()[i] + "\n" + "Lecture: "+ (j+1) + "\n" + "Professor: " + timeTable[i][j].getProfessor() + "\n" + "Room No: " + timeTable[i][j].getRoomNumber();
                }
            }
        }
        return result;
	}
	
    //날짜를 입력받아 calender class 객체에 저장후 객체 반환(calender class 사용)
	public Calendar setInputDate(String date) {			
	
        int year = Integer.parseInt(date.substring(0, 4));
        int month = Integer.parseInt(date.substring(4, 6)) - 1;
        int day = Integer.parseInt(date.substring(6));
        Calendar cal = Calendar.getInstance();
        cal.set(year, month, day);
        return cal;
    
	}
}

<TimeTableApp Class>

package assignment;

import java.util.Calendar;
import java.util.Scanner;

public class TimeTableApp {
	public static void main(String[] args) {

		Scanner keyboard = new Scanner(System.in);
		String[] weeks = { "SUNDAY", "MONDAY", "TUESDAY", "WEDNESDAY", "THURSDAY", "FRIDAY", "SATURDAY" };
		Calendar cal = Calendar.getInstance();
		TimeTable timeTable = new TimeTable();
		int enter, period;
		String name, day, tutorName, roomName, sub, str,date;
		boolean check;
		boolean when = true;
		do {
			System.out.println(timeTable.toString());
			System.out.println("===============Main Menu================");
			System.out.println("(1) Add a class to my time table");
			System.out.println("(2) View the class at a specific period");
			System.out.println("(3) View schedule of a specific class");
			System.out.println("(4) TimeTable corresponding to input date");
			System.out.println("(5) Exit the program");
			System.out.println("===============Main Menu================");
			enter = keyboard.nextInt();
			switch (enter) {
			case 1: {		//강의 정보를 입력받아서 시간표에 저장
				System.out.println("Please enter the day to add the class");
				day = keyboard.next();
				day = day.toUpperCase();
				System.out.println("Please enter the period to add the class");
				period = keyboard.nextInt();
				System.out.println("Please enter the name of the class");
				name = keyboard.next();
				System.out.println("Please enter the name of the tutor");
				tutorName = keyboard.next();
				System.out.println("Please enter the name of the room ");
				roomName = keyboard.next();

				check = timeTable.setSchedule(day, period, name, tutorName, roomName);
				if (check == true)
					System.out.println("Class successfully added");
				else
					System.out.println("Class was NOT successfully added");
				break;

			}
			case 2: {		// 요일과 교시를 입력받아 해당 시간의 강의 속성을 출력
				System.out.println("Please enter the day of the class");
				day = keyboard.next();
				day = day.toUpperCase();
				System.out.println("Please enter the peroid of the class");
				period = keyboard.nextInt();
				System.out.println(timeTable.getSchedule(day.toString(), period));
				break;

			}
			case 3: {		// 강의명을 입력받아 해당 강의 정보를 출력
				System.out.println("Please enter the class name");
				sub = keyboard.next();
				str = timeTable.subjectSchedule(sub);
				
				if (str.isEmpty()) {
					System.out.println("There are no class");
					break;
				} else {
					System.out.println(str);
				}
				break;
			}
			case 4: {		//날짜를 입력받아 해당하는 요일의 시간표를 출력
				System.out.println("Enter the date:");
				date = keyboard.next();
				cal = timeTable.setInputDate(date);
				
				if (cal.get(Calendar.DAY_OF_WEEK) - 1 == 0 || cal.get(Calendar.DAY_OF_WEEK) - 1 == 6) {
					System.out.println("There are no schedule");
					break;
				} else {
					System.out.println(timeTable.oneDaySchedule(weeks[cal.get(Calendar.DAY_OF_WEEK) - 1]));
				}

				break;

			}
			case 5: {		// 프로그램 종료
				when = false;
				break;
			}
			default:
				System.out.println("Try again");
			}
		} while (when);

	}

}

Result

1. Case1 : 강의 속성을 입력받아 시간표에 저장

2. Case2 : 요일과 교시를 입력받아 해당 강의 속성 출력

3. Case3 : 강의명을 입력받아 해당 강의 정보 출력

4. Case4 : 날짜를 입력받아 해당날짜의 시간표 출력 (2023.04.07은 금요일 -> 금공강^^)

5. Case5 : 프로그램 종료

Flow of Control (제어 흐름)

branching 과 looping 두가지를 참고할 수 있다.

branching 과 looping은 boolean expressions 로 control 된다.

Branching mechanism :

-if , else if, else

-switch

Compound Statements

→ 명령어를 여러 줄 쓰는 경우 braces({ }) 기호 사용

else는 생략 가능

The Conditional Operator

if (n1 > n2) max = n1;
else         max = n2;

→

max = (n1 > n2) ? n1 : n2;   (conditional operator)

Boolean Expressions

• and - && , or - || , not - !

-&, | 로도 사용 가능

*Short-Circuit

:&&의 경우 처음이 false이면 반드시 false이므로 이후 계산 수행x, ||의 경우 처음이 true이면 반드시 true이므로 이후 계산 수행x

→ 프로그램 실행 시간을 줄여줌(효율적) , 런타임 에러를 줄여준다.

ex1)

→ if, else if, else 를 사용하여 입력받은 값에 따른 tax 값을 계산해서 출력하는 프로그램

ex2)

→ switch 문을 사용하여 각각의 경우에 따른 출력값을 출력

-case2,3 처럼 비어 있는 경우 다음으로 넘어가서 case 4의 내용을 출력

-default는 해당 값이 없는 경우에 대해 출력

Using == with Strings

equality comparison을 위해 (==) 연산자를 사용한다.

이때, primitive type에서는 두 값을 비교하게 된다.

하지만 String class의 경우(==)연산자는 값을 비교하는 것이 아니라 같은 메모리 location을 가리키는 것인지 확인하는 용도로 사용된다.

따라서, String class의 값을 비교하기 위해서는 equals, eqaulsIgnoreCase와 같은 method를 사용하여 확인해야 한다.

Loops

-while, do-while, for statements 가 있다.

-loop에서 반복되는 부분의 코드를 body라고 한다.

-body 중에서 반복하는 부분을 iteration이라고 한다.

*while과 do-while의 차이

→while은 조건을 먼저 확인 후 body를 실행한다. 하지만, do-while의 경우 body를 먼저 실행한 뒤 조건을 evaluation한다. 따라서 do-while의 경우 반드시 1번은 body문이 실행된다.

ex3)

package chapter3;

public class chapter3_3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int countDown;
		
		System.out.println("first while loop:");
		countDown = 3;
		while(countDown > 0) {
			System.out.println("hello");
			countDown = countDown -1;
			
		}
		
		System.out.println("second while loop:");
		countDown = 0;
		while(countDown > 0) {
			System.out.println("hello");
			countDown = countDown -1;
			
		}
		
		System.out.println("first do-while loop:");
		countDown = 3;
		do
		{
			System.out.println("hello");
			countDown = countDown -1;
			
		}while(countDown>0);
		
		System.out.println("second do-while loo:");
		countDown = 0;
		do
		{
			System.out.println("hello");
			countDown = countDown - 1;
			
		}while(countDown > 0);
		

	}

}

출력결과

Flow of Control (제어 흐름)

branching 과 looping 두가지를 참고할 수 있다.

branching 과 looping은 boolean expressions 로 control 된다.

Branching mechanism :

-if , else if, else

-switch

Compound Statements

→ 명령어를 여러 줄 쓰는 경우 braces({ }) 기호 사용

else는 생략 가능

The Conditional Operator

if (n1 > n2) max = n1;
else         max = n2;

→

max = (n1 > n2) ? n1 : n2;   (conditional operator)

Boolean Expressions

• and - && , or - || , not - !

-&, | 로도 사용 가능

*Short-Circuit

:&&의 경우 처음이 false이면 반드시 false이므로 이후 계산 수행x, ||의 경우 처음이 true이면 반드시 true이므로 이후 계산 수행x

→ 프로그램 실행 시간을 줄여줌(효율적) , 런타임 에러를 줄여준다.

ex1)

→ if, else if, else 를 사용하여 입력받은 값에 따른 tax 값을 계산해서 출력하는 프로그램

ex2)

→ switch 문을 사용하여 각각의 경우에 따른 출력값을 출력

-case2,3 처럼 비어 있는 경우 다음으로 넘어가서 case 4의 내용을 출력

-default는 해당 값이 없는 경우에 대해 출력

Using == with Strings

equality comparison을 위해 (==) 연산자를 사용한다.

이때, primitive type에서는 두 값을 비교하게 된다.

하지만 String class의 경우(==)연산자는 값을 비교하는 것이 아니라 같은 메모리 location을 가리키는 것인지 확인하는 용도로 사용된다.

따라서, String class의 값을 비교하기 위해서는 equals, eqaulsIgnoreCase와 같은 method를 사용하여 확인해야 한다.

Loops

-while, do-while, for statements 가 있다.

-loop에서 반복되는 부분의 코드를 body라고 한다.

-body 중에서 반복하는 부분을 iteration이라고 한다.

*while과 do-while의 차이

→while은 조건을 먼저 확인 후 body를 실행한다. 하지만, do-while의 경우 body를 먼저 실행한 뒤 조건을 evaluation한다. 따라서 do-while의 경우 반드시 1번은 body문이 실행된다.

ex3)

package chapter3;

public class chapter3_3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int countDown;
		
		System.out.println("first while loop:");
		countDown = 3;
		while(countDown > 0) {
			System.out.println("hello");
			countDown = countDown -1;
			
		}
		
		System.out.println("second while loop:");
		countDown = 0;
		while(countDown > 0) {
			System.out.println("hello");
			countDown = countDown -1;
			
		}
		
		System.out.println("first do-while loop:");
		countDown = 3;
		do
		{
			System.out.println("hello");
			countDown = countDown -1;
			
		}while(countDown>0);
		
		System.out.println("second do-while loo:");
		countDown = 0;
		do
		{
			System.out.println("hello");
			countDown = countDown - 1;
			
		}while(countDown > 0);
		

	}

}

출력결과

Flow of Control (제어 흐름)

branching 과 looping 두가지를 참고할 수 있다.

branching 과 looping은 boolean expressions 로 control 된다.

Branching mechanism :

-if , else if, else

-switch

Compound Statements

→ 명령어를 여러 줄 쓰는 경우 braces({ }) 기호 사용

else는 생략 가능

The Conditional Operator

if (n1 > n2) max = n1;
else         max = n2;

→

max = (n1 > n2) ? n1 : n2;   (conditional operator)

Boolean Expressions

• and - && , or - || , not - !

-&, | 로도 사용 가능

*Short-Circuit

:&&의 경우 처음이 false이면 반드시 false이므로 이후 계산 수행x, ||의 경우 처음이 true이면 반드시 true이므로 이후 계산 수행x

→ 프로그램 실행 시간을 줄여줌(효율적) , 런타임 에러를 줄여준다.

ex1)

→ if, else if, else 를 사용하여 입력받은 값에 따른 tax 값을 계산해서 출력하는 프로그램

ex2)

→ switch 문을 사용하여 각각의 경우에 따른 출력값을 출력

-case2,3 처럼 비어 있는 경우 다음으로 넘어가서 case 4의 내용을 출력

-default는 해당 값이 없는 경우에 대해 출력

Using == with Strings

equality comparison을 위해 (==) 연산자를 사용한다.

이때, primitive type에서는 두 값을 비교하게 된다.

하지만 String class의 경우(==)연산자는 값을 비교하는 것이 아니라 같은 메모리 location을 가리키는 것인지 확인하는 용도로 사용된다.

따라서, String class의 값을 비교하기 위해서는 equals, eqaulsIgnoreCase와 같은 method를 사용하여 확인해야 한다.

Loops

-while, do-while, for statements 가 있다.

-loop에서 반복되는 부분의 코드를 body라고 한다.

-body 중에서 반복하는 부분을 iteration이라고 한다.

*while과 do-while의 차이

→while은 조건을 먼저 확인 후 body를 실행한다. 하지만, do-while의 경우 body를 먼저 실행한 뒤 조건을 evaluation한다. 따라서 do-while의 경우 반드시 1번은 body문이 실행된다.

ex3)

package chapter3;

public class chapter3_3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int countDown;
		
		System.out.println("first while loop:");
		countDown = 3;
		while(countDown > 0) {
			System.out.println("hello");
			countDown = countDown -1;
			
		}
		
		System.out.println("second while loop:");
		countDown = 0;
		while(countDown > 0) {
			System.out.println("hello");
			countDown = countDown -1;
			
		}
		
		System.out.println("first do-while loop:");
		countDown = 3;
		do
		{
			System.out.println("hello");
			countDown = countDown -1;
			
		}while(countDown>0);
		
		System.out.println("second do-while loo:");
		countDown = 0;
		do
		{
			System.out.println("hello");
			countDown = countDown - 1;
			
		}while(countDown > 0);
		

	}

}

출력결과

Static Methods

: object 없이 호출하여 사용가능한 method

- static method는 class에 속하며 class definition 내부에서 정의된다.

- static method를 정희할 때 static 이라는 keyoword를 사용한다.

   -> pulbic static returnedType myMethod (parameters)

        {...}

- static method는 호출 객체 대신 class 이름을 사용하여 호출한다.

   ex) returnedValue = Myclass.myMethod(arguments);

Pitfall : Invoking a Nonstatic Method Withn a Static Method

: 정적 메서드 내에서 비정적 메서드 호출

- 정적 메서드는 클래스의 instance variable을 참조할 수 없으며 클래스의 정적 메서드를 호출할 수 없다.

- 정적 메서드에는 this 값이 존재하지 않기 때문에 호출 객체에 대한 암시적,명시적 instance variable 혹은 메서드 사용이 불가하다.

- 다른 정적 메서드를 호출하는 것은 가능하다.

Static Variables

- static variables는 하나의 객체만이 아니라 클래스 전체에 속하는 변수이다.

   -> 각 객체가 하나의 복사본을 갖는 instance variable과 달리 클래스당 정적 변수의 복사본은 하나이다.

- 클래스의 모든 객체가 static variables를 읽고 쓸 수 있다.

- static methods는 instance variable에는 접근 불가하지만 static variables에는 접근가능하다.

- static variables는 instance variable처럼 선언되며 static 을 사용하여 선언한다.

   ex) private static int myStaticVariable;

- 정적 변수는 선언과 초기화를 동시에 수행 가능하다. 

   ex) private static int myStaticVariable = 0;

- 명시적으로 초기화되지 않은 경우 자동으로 초기화된다. (초기화 해주는 것이 이상적)

   -> boolean type : false, primitive types : 0, class type : null

- 정적 변수는 상수가 아닌 경우 항상 private으로 정의되어야 한다.

    -> 정적으로 정의된 상수의 경우 변경불가하므로 public으로 사용 가능하다.

    -> 해당 값이 변경불가함을 표현하기 위해 final 수식어를 사용해야 한다.

          ex) public static final int BIRTH_YEAR = 1954;

- 클래스 외부에서 상수를 참조하는 경우 클래스명을 사용하여 호출한다.

    ex) int year = MyClass.BIRTH_YEAR;

The Math class

: Math 클래스는 많은 수학적 methods를 제공

- java.lang 패키지에 포함되어있어 자동으로 import 되어 사용 가능하다. 

- 모든 methods와 data는 static으로 Math 클래스명과 함께 호출된다.

- Math 클래스는 E, PI 두가지 정의된 상수를 갖는다.

Math 클래스의 Methods

1. public static double pow (double base, double exponent)

-> 제곱을 연산

ex) Math.pow (2.0, 3.0) => 8.0

2. public static double abs(double argument)

public static float abs(float argument)

public static long abs(long argument)

public static int abs(int argument)

-> 해당 type 의 값의 절댓값을 return

ex) Math.abs(-6) => 6

3. public static double min(double n1, double n2)

public static float min(float n1, double n2)

public static long min(long n1, double n2)

public static int min(int n1, double n2)

-> 인자로 받은 값 중 최소값을 return

ex) Math.min(3, 2) => 2

4.  public static double max(double n1, double n2)

public static float max(float n1, double n2)

public static long max(long n1, double n2)

public static int max(int n1, double n2)

-> 인자로 받은 값 중 최댓값을 return

ex) Math.max(3, 2) => 3

5. public static long round(double argument)

public statci int round(float argument)

-> 인자로 받은 값을 반올림 연산하여 return

ex) Math.round(3.2) => 3 , Math.round(3.6) => 4

6. public statci double ceil(double argument)

-> 인자로 받은 값을 올림 연산하여 return

ex) Math.ceil(3.2) => 4.0, Math.ceil(3.6) => 4.0

7. public static double floor(double argument)

-> 인자로 받은 값을 내림 연산하여 return

ex) Math.floor(3.2) => 3.0 , Math.floor(3.9) => 3.0

8. public static double sqrt(double argument)

-> 인자로 받은 값의 제곱근을 연산하여 return

ex) Math.sqrt(4) => 2.0

Random Numbers

: Math 클래스는 난수를 생성하는 기능을 제공한다.

  public static double random()

  *Random 클래스는 flexible 한 난수값을 생성한다.

ex) double num = Math.random();

Wrapper class

: 기본 데이터 타입을 객체로 감싸는 클래스

primitive types : byte, short, int, long, float, double, char -> Byte, Short, Integer, Long, Float, Double, Character

- Wrapper class는 정의된 상수나 static methods를 포함한다.

Wrapper class 사용 이유

1. 객체 형태로 데이터를 다룰 수 있다.
2. 객체로 감싸지 않으면 기본 데이터 타입은 null 값을 가질 수 없다. 하지만 객체로 감싸면 null 값을 가질 수 있다.
3. 객체로 감싸면 다양한 메소드를 사용할 수 있다.

Boxing

: 기본 데이터 타입을 Wrapper class의 객체로 변환하는 것

- 새로운 객체에는 원시 값의 복사본을 저장하는 instance variable을 포함

- 다른 클래스와 다르게 wrapper class는 인자 없는 생성자를 갖지 않는다.

ex) Integer integerObject = new Integer(42);

Unboxing

: Wrapper class의 객체를 기본 데이터 타입으로 변환하는 것

ex) int i = integerObject.intValue( );.  ->   인자를 갖지 않음

Automatic Boxing and Unboxing

- java 5.0 이후로는 자동으로 boxing , unboxing이 가능하다.

- 이전 설명처럼 new를 사용하여 객체를 생성하는 것이 아니라 자동으로 생성한다.

   ex) Integer integerObejct = 42;

-  wrapper 클래스 객체에서 원시 데이터 유형으로 변환하는 경우

   ex) int i  = integerObject;

Constants and Static Methods in Wrapper Classes

-Wrapper 클래스는 최댓값,최솟값을 제공하는 상수를 제공한다.

  ex) Integer.MAX_VALUE, Integer.MIN_VALUE, Double.MAX_VALUE, Double.MIN_VALUE

- Boolean 클래스는 두 상수에 대한 이름이 존재

  ex) Boolean.TRUE, Boolean.FALSE

- Wrapper 클래스는 문자열 표현의 숫자를 변환하는 정적 메서드를 포함한다.

   ex) Integer.parseInt, Long.parseLong

- Wrapper 클래스는 숫자값을 문자열 표현으로 변환하는 정적 메서드를 포함한다.

   ex) Double.toString(123.99); -> return "123.99"

- Character class에는 문자열 처리에 유용한 정적 메서드가 포함되어있다.

Character Class의 Methods

1. toUpperCase()

public static char toUpperCase(char argument)

-> 대문자로 변환, 문자가 아닌 경우 변화없음

ex) Character.toUpperCase('a') => return 'A'

2. toLowerCase()

public static char toLowerCase(char argument)

-> 소문자로 변환, 문자가 아닌 경우 변화없음

ex) Character.toLowerCase('A') => return 'a'

3. isUpperCase()

public static boolean isUpperCase(char argument)

-> 대문자인 경우 true 반환, 아닌 경우 false

ex) Character.isUpperCase('A') = > return true

4. isLowerCase()

public static boolean isLowerCase(char argument)

-> 소문자인 경우 true 반환, 아닌 경우 false

ex) Character.isLowerCase('a') => return false

5. isWhitespace()

publci static boolean isWhitespace(char argument)

-> 공백인 경우 true 반환 (빈칸, \t, \n  세 가지 경우에 해당)

ex) Character.isWhitespace(' ') => return true

6. isLetter()

public static boolean isLetter(char argument)

-> 인자가 문자인 경우 true 반환

ex) Character.isLetter('A') => return true, Character.isLetter('5') => return false

7. isDigit()

public static boolean isDigit(char argument)

-> 인자가 정수인 경우 true 반환

ex) Character.isDigit('5') => return true

8. isLetterOrDigit()

public static boolean isLetterOrDigit(char argument)

-> 인자가 문자거나 정수인 경우 true 반환

ex) Character.isLetterOrDigit('A') => true, Character.isLetterOrDigit('5') => true

Variables and memory

대부분의 데이터 유형의 값을 1byte 이상의 저장공간을 필요로한다.

- 여러개의 인접 바이트가 데이터를 유지하는데 사용됨

- 데이터를 저장하는 전체 덩어리를 memory location 이라고 한다.

- memory location의 첫번째 주소를 데이터의 주소로 사용한다.

main memory는 다양한 크기의 memory location의 list로 생각 할 수 있다.

Reference

- 모든 변수는 memory location에서 실행된다.

- 변수가 primitive type인 경우 변수의 값은 할당된 memory location에 저장된다. -> primitive type은 일정 양의 메모리를 필요로 함 

- 변수가 class type 인 경우, 객체가 위치한 메모리 주소만 할당된 memory location에 저장

   => primitive type 과 달리 클래스 변수 값은 memory address 혹은 reference 이다.

- 두 참조 변수는 같은 객체를 가리킬 수 있다.

   variable2 = variable1; => 같은 객체를 가리킨다.  

System.out.println

System.out →Console 출력 객체 (object)

println → console output 매서드(method)

print vs println

-print 매서드는 println과 다르게 줄바꿈을 포함하지 않음(개행문자 포함x)

→ println 의 다음 output은 새로운 줄에 출력, print의 경우 해당 줄에 그대로 이어서 출력

Printf

java에서의 printfsms C언어에서의 printf와 매우 유사하다.

System.out.printf는 여러 인자(argument)를 가질 수 있다.

첫번째 인수는 항상 format string이다.

첫 번째를 제외한 모든 인수는 화면에 출력되는 값

ex)

%6.2f → 6자리로 맞춤 (앞에서 부터 공백으로 채움) , 소수점 2번째자리까지 출력

%-8.2fEnd → “-”부호를 사용하여 왼쪽 정렬로 8자리수를 채우고(빈칸으로 채움) 소수점 2번째 자리까지 출력

Importing Packages and Classes

-JAVA의 라이브러리를 packages라고 한다.

-package는 class들의 모음으로 프로그램 접근이 용이하도록 한다.

-해당 package의 class를 사용하기 위해 import 문을 작성해야 한다.

ex)

import java.text.NumberFormat; → NumberFormat 클래스만 import

import java.text.*; → java.text 패키지에 있는 모든 클래스 import

*java.lang 패키지의 class는 자동적으로 모든 Java 프로그램에 import 된다.

Scanner Class

-keyboard의 입력을 받기 위해 Scanner Class를 포함한다.(Java 5.0 이상)

Scanner 클래스 사용을 위한 import → import java.util.Scanner (java.util 패키지에서 Scanner 클래스를 찾아 import)

ex)

Scanner keyboard = new Scanner(System.in);

->keyboar라는 이름의 Scanner 클래스 객체를 생성, system.in은 키보드 입력을 처리하는 객체

->Scanner 객체가 생성된 후 객체를 사용하여 키보드 입력을 수행

nextInt(), nextDouble()

-nextInt 매서드는 하나의 int값을 변수에 할당

-nextDouble 매서드는 하나의 double형 값을 변수에 할당

-다수의 입력은 whitespac(공백)으로 구분되어야 하며 적절한 매서드의 호출로 읽혀야 함

next()

-next()매서드는 공백이 아닌 하나의 string형을 읽음

ex)

String word1 = keyboard.next();

String word2 = keyboard.next();

input = jelly beans

=> word1 = jelly, word2 = beans

nextLine()

-nextLine 매서드는 keyboard 입력 전체를 읽음

nextLine이 텍스트를 읽을 때 엔터 입력시 ‘\n’를 읽으므로 다음 입력은 다음줄 부터 입력하게 된다.(‘\n’을 string 값으로 간주하지는 않음)

ex) String line = keyboard.nextLine(); → 문장 전체를 line 변수에 입력

useDelimiter(New Delimiter)

-키보드 입력의 구분 기호를 기준으로 문자열 입력

ex) String line = keyboard.useDelimiter(",") -> ,(쉼표) 를 기준으로 문자열 입력

Operating system structure

Multiprogramming

multipromgramming 은 efficiency 측면에서 필요하다. (자원 활용의 효율성을 높여준다.)

cpu가 불필요한 wait을 하지 않도록 해준다.

job scheduling을 통해 실행한다.

i/o 와 같은 wait 이 발생하면 다른 일을 수행한다. → multitasking을 위해, 모든 프로그램이 조금씩 실행하도록

Timesharing(multitasking)

-cpu의 시간을 나눠서 사용

-모든 프로그램을 메모리에 올릴 수 없으므로 swapping 방식(실행되지 않은 프로그램을 디스크로 보내는 것)을 사용 → 속도가 느려지는 문제 발생

-virtual memory를 사용하여 swapping 방식의 문제를 해결, virtual memory는 현재 필요한 부분만 메모리에 올리는 방식으로 메모리를 관리

Operating System Operation

interrupt는 hardware로 부터 발생한다.

software error , request는 exception이나 trap을 발생 시킨다. → 현재 실행중인 것을 중단하고 error 처리(error의 파급력이 전체적으로 크기 때문), i/o 때문x, interrupt방식과 유사

Dual-mode 동작이 OS를 보호한다.

-user mode 와 kernel mode 사용

-hardware 가 mode bit 제공

-system call은 직접 호출하지 않고 라이브러리 함수를 이용하여 안전하고 편리하게 호출한다. ex)printf()

-operating system code와 application code를 구분해서 전달 (권한이 달라지기 때문) > mode bit 사용

Process Management

Process : 프로그램 실행에 필요한 모든 정보를 담는 자료구조 → 메모리에 전달하는 형식

프로그램 실행 시 필요한 요소 : cpu, memory, i/o, files, initialization data

single-threaded process 는 하나의 program counter(프로그램 실행 위치 저장) 을 갖는다.

multi-threaded process의 경우 하나의 thread당 하나의 program counter를 갖는다.

program management activities

-creating and deleting user and system process

-suspending and resuming process

-providing mechanisms for process syncronization(동기화)

-providing mechanisms for process communication → 프로세스 간 통신

-providing mechanisms for deadlock handling

memory management

processing 전과 후의 모든 메모리 관리

메모리의 어떤 위치에 어떤 것이 있는지 내용들을 관리

어떤 data나 process를 memory에 넣고, 제거할 지 관리

필요할 때 memory 공간을 할당

Storage Management

Application이 Harddisk에 접근하는 방식은 어렵고 복잡 → file 공간에 쓰고 저장해라 그러면 OS가 알아서 하드디스크에 저장할게!

file을 체계적으로 저장하고 관리하기 위해 directories를 사용

Mass-Storage Management

-대량의 데이터를 저장하고 관리 →안전성,보안성,검색성,자원최적화 등을 보장

-free-space management

-storage allocation

-disk scheduling → i/o가 느리기 때문에 요청 순서를 조절하여 harddisk head의 움직임을 최소화

Migragion of integer A from Disk to Resgister

magnetic disk → main memory → cache → hardware register

multitasking 환경은 최신 data(recent value) 라는 것을 보장해줘야한다. → core가 여러개일 때 어려워짐

multiprocessor 환경에서는 cache coherency를 보장하여 모든 cpu에서 cache에 가장 최근의 데이터 값을 갖도록 해야한다.

I/O Subsystem

OS는 사용자가 수많은 종류의 I/O 장치를 구분없이 사용할 수 있도록 해주는 것이 목표이다.

block device, clock device 만 구분해서 전달해줘 > 나머지는 OS가 해줄게

-buffering(임시저장공간)

-caching(빠른 저장 공간에 두는 것)

-spooling (직접 보내지 않고 spool에 두면 os가 읽어가는 방식)

Protection and Security

프로세스는 실행한 사용자의 권한을 승계받아서 작동

Protection - 권한 없는 사용자가 접근 시 보호

모든 사용자에 ID를 부여하고 ID에 권한을 부여하여 관리 (root는 만능 , 모두 가능)

-system은 사용자들을 구분하고 권한을 구분

-user identities

-user id

-group identifier(group id)

-privilege escalation → ex)os가 만든 영역(spool)에 사용자가 접근하는 것이 불가능 하여 print의 경우처럼 권한을 잠시 부여 후 다시 회수하는 것

Operation System Services

System Calls

:os가 제공하는 service 의 programming interface

system call을 이용하여 os가 제공하는 service를 사용 가능하다.

direct system call 보다는 주로 Application Program Interface(API) 통해서 접근

-WIn32 API → 윈도우용

-POSIX API → UNIX계열

-JAVA API → JVM

→ 계열에 따라 같은 API를 사용한다. print()의 경우 C에서 제공하는 것이라 공통적으로 사용 가능

system call 보다 api를 사용하는 이유 : portability(이식성) → 소스 코드를 하나로 통일 가능 , 쉬운 사용

System Call Implementation

일반적으로 시스템 호출 인터페이스와 관련된 번호는 이러한 번호에 따라 색인된 테이블 유지→table을 찾아서 이동

시스템 호출 인터페이스는 OS 커널에서 의도된 시스템 호출을 호출하고 시스템 호출의 상태와 반환 값을 반환

호출자는 시스템 호출이 구현되는 방법에 대해 아무것도 알 필요가 없음

-API를 준수하고 결과적으로 OS가 수행할 작업을 파악해야 함

-API에 의해 프로그래머에게 숨겨져 있는 OS 인터페이스의 대부분 세부 정보

Virtual Machines

-하드웨어와 OS를 묶어서 텅 빈 하드웨어처럼 만들어줌(실제 OS는 존재)

-a는 nonvirtual machine, b는 virtual machine

virtual machine은 각각의 os를 따로 관리할 수 있음(경제성이 높음)

The Java Virtual Machine

-사용자 PC에 가서 해당 PC에 맞도록 컴파일 하자!

-JVM을 각 기기에 설치

Background

동기화 문제를 다루는 이유?

->공유 data로의 동시적 접근이 발생하는 경우 result inconsistency 문제가 발생할 수 있음

Race condition

:몇몇의 process들이 접근하여 shared data를 동식에 조작하는 상황

-> 이 경우 final value 는 마지막 실행 프로세스의 결과에 따라 달라짐

Race condition 문제를 방지하기 위해 concurrent processes는 synchronize 되어야 한다.

The Critical-Section Problem

n개의 process들이 shared data를 사용하기 위해 competing 하는 상황

각 process는 code segment를 갖는데 이를 critical section이라고 한다. (shared data가 접근되는 영역)

Race condition을 막기 위한 solution : 하나의 process가 실행중인 경우 다른 process는 critical section을 실행하지못하도록 막자!

Requirements for the Solution

3가지 요구조건

1. Mutual Exclusion

- 상호베타적으로 Critical Section을 수행할 수 있도록 해줘야 한다.

하나의 process pi 가 critical section 에서 실행중이면 다른 어떤 process도 critical section에서 수행할 수 없도록 해야한다.

2.Progress

-과도하게 막아서 어떤 process도 critical section에서 수행중이지 않은데도 못들어가게 막는 상황은 발생하면 안된다.

3. Bounded Waiting

- 다른 process가 실행중이라 기다리는 중인데 순서가 계속해서 밀려서 기다리게 되는 경우가 발생해서는 안된다.

(기다리는 시간의 bound값을 정해야 한다. -> starvation 개념과 비슷)

Progress, Bounded Waiting 은 Race condition을 방지하되 Throughput이 떨어져 전체적인 성능이 저하되지 않도록 하기 위한 조건

Initial Attemps to Solve Problem

2개의 process p1,p2가 있는 경우

entry section과 exit section을 설정

entry section : 진입 가능한 상태인지 확인 (다른 process의 상태를 확인)

exit section : 끝난 후 다른 기다리는 process에게 알림 (본인 상태를 다른 process에게 알림)

-> process 상태를 나타내는 변수가 필요

Algorithm 1

Shared variables : int turn, initially turn = 0

turn 이라는 변수를 사용하여 해당하는 값의 process만 critical section에 들어갈 수 있음

turn이 0이 아닌 경우 while loop 문을 돌면서 기다린 후 process가 끝나서 turn =1 이 되면 실행

특징 : P0이 끝나서 turn =1 이 되면 P1이 실행되어 turn =0 이 되어야지 다시 P0 실행이 가능하다.

mutual exclusion 조건을 만족하지만 progress 조건을 만족하지 못한다. -> swap-turn 문제 발생

=> solution이 될 수 없다!

Algorithm 2

들어가고자 하는 process를 들어가도록 만들어주자

Shared variables : boolean flag[2];

initially flag[i] = flag[j] = false;

flag 값이 true 이면 critical section에 들어간다. 이때 상대방의 flag를 먼저 check 하여 true 인 경우 양보하고 기다린 후 끝나면 들어감

swap turn 문제는 해결되지만 여전히 mutual exclusion 조건만 만족하고 progress 조건을 만족시키지 못한다.

->둘 다 true 인 경우 while 문에서 서로 기다리기 때문에 막혀버려서 critical section이 비었음에도 양보하며 기다리기만 하는 현상 발생

=> solution이 될 수 없다!

Algorithm3 (Peterson's Algorithm)

Algorithm1 과 Algorithm2 의 변수를 모두 사용하여 합친 개념

(1의 경우 들어갈 생각이 없는 process에게 turn을 줘서 문제 발생, 2의 경우 둘 다 들어가려고 하는 상황에서 교통정리를 못해줘서 문제 발생)

flag,turn 두 가지 변수를 모두 사용하여 문제를 해결 (상대가 들어갈 생각이 있고 순서를 갖는다면 문제 해결)

3가지 요구조건을 모두 만족 시킴 -> solution이 될 수 있음!

But 문제점

1. Busy waiting (waiting 상태에서 process가 while loop를 돌면서 CPU를 잡아먹고 있음 -> 매우 비효율적)

2.entry section 부분의 코드가 길다. -> 각 process 마다 작성하는데 너무 code가 복잡해질 수 있다. 개발자 입장에서 비효율적

Solution to Critical-section Problem using Locks

-위의 문제를 locking system을 이용하여 해결하자.

lock을 사용하여 해당 process 가 key를 확보하면 critical section에 진입하고 끝나면 key를 반납하여 다른 process가 사용가능하도록 설계

중요한 전제 조건 : key는 반드시 단 하나의 process만 갖도록 보장되어야 한다.

Synchronization Hardware

: 특별한 Hardware 회로를 제공하여 하나의 실행이 끝까지 수행되도록 보장해줌 (Atomic Hardware)

Cpu가 하나인 경우 CPU Scheduling에 의해서 process를 이동하며 문제가 발생한다. -> interleaved execution 발생

P1이 LOAD 되기 전에 CPU Scheduling이 발생하지 않도록 한다면 괜찮지 않을까?

->critical section을 빠져나오면 그때 cpu를 놓을 수 있도록 하자

How? -> interrupt가 발생하는 경우 cpu scheduling이 일어남

interrupt가 발생하는 경우는 i/o device, time out 두 가지 경우가 있음. critical section에서 I/O 발생은 일어나지 않으므로 time outㄹ을 활용하자

timer device가 time quantum이 끝나서 interrupt를 발생 시킬때 cpu scheduling이 발생한다.

critical section에 들어가면 timer interrupt를 disable 시키고 끝나고 나오면서 enable 시키자! => critical section 동안 cpu를 계속 사용 가능함

최근에는 atomic hardware instruction을 제공한다

atomic = non -interruptible

1. Test - and - Set (TAS)

2. Swap

Synchronization Hardware (1. TAS)

Test and modify (= Test and Set, TAS)

-한번 실행하면 중지 없이 끝을 보장한다. (atomically)

Mutual Exclusion with Test-and-Set

초기 lock은 false 값을 가지며 TAS에 의해 false를 return 하고 lock 은 true 값을 갖게 된다.

이 경우 lock 값이 true 이므로 새로운 process가 들어오려고 해도 while 문을 돌게 된다.

critical section이 끝나고 lock이 false 값을 가지면 새로운 프로세스가 들어올 수 있는 상태가 된다.

=>Peterson's Algorithm에 비해 매우 간단하다.

TAS 라는 atomic hardware가 존재하기 때문이다. (atomic 한 성질때문에 가능)

Synchronization Hardware (2.Swap)

shared data : boolean lock; (초기값 false 설정)

-swap(lock, key)를 사용하여 lock이 false 인 경우에만 critical section으로 들어갈 수 있다.

이미 실행중인 경우 lock 값이 true 가 되어 swap(true,true) 가 되며 key값이 그대로 true값을 가져 while문을 실행하게 된다.

=>결론 : atomic 한 hardware가 있다면 synchronization 문제를 해결할 수 있다.

Semaphores

Hardware를 사용하지 않고 Software적으로 해결할 수 있는 방법은 없을까? -> Semaphores

Semaphores : primitive한 것만 호출함으로써 동기화 문제를 해결해주는 도구

integer variable Semaphore S 사용

반드시 두 개의 atomic operation으로만 access 가능

1. P( ) : wait function

2. V( ) : signal function

S는 초기값 0을 사용하여 0보다 작은 경우 실행하지 않고 실행이 끝나 1값을 가지면 critical section 수행

Critical Section of n Processes

shared data : semaphore mutex (초기값 1)

mutex가 초기값 1을 가지고 critical section에 들어가면 0값을 가진다. 이때, 다른 프로세스가 와도 mutex값이 0이므로 while 문 실행

critical section이 끝나면 mutex는 다시 1값을 가지고 다음 프로세스가 들어가게됨

가능한 이유?

P, V 함수가 atomic 함수이기 때문이다. (atomic hardware와 동일하게 동작)

P, V 가  atomic한 함수가 아니라면 어떤 문제가 발생할까?

-> critical section에 두 process가 동시에 진입가능하게 될 것이다. atomic 하지 않다면 동시에 mutex 값을 1로 읽을 수 있음

Semaphore Implementation

Single Process인 경우 P 함수 첫부분에 interrupt disable을 설정하고 제일 마지막 부분에 interrupt able을 설정한다.

Single Process가 아닌 경우 Semaphore S를 Peterson Algorithm으로 감싸서 보호하여 S에 대한 동시 접근이 불가하도록 한다.

기존의 Peterson's Algorithm 과의 차이점?

->Semaphore를 사용하지 않는다면 critical section을 만날때마다 Peterson's Algorithm 구현이 필요하다.

하지만 Semaphore를 사용하여 P, V에 구현을 해두면 사용할 때마다 구현할 필요가 없다. (P, V 자체가 Peterson's Algorithm에 의해 Synchronization 되고 있다!)

P() 를 사용하는 경우 busy waiting 문제가 발생한다. 

critical section이 커지게 되는 경우 waiting 이 길어져 오버헤드가 커진다. 

Block / Wakeup Implementation

busy waiting 문제를 줄이기 위해 사용

while문을 돌면서 busy waiting을 하는 대신에 sleep을 시키고 조건이 충족되면 wakeup 해서 실행하도록 하자.

semaphore를 변수가 아닌 구조체로 정의

*L -> 포인터를 사용하여 sleep process들을 linked-list로 저장

block, wakeup 을 사용하여 관리

Implementation : block/wakeup version of P() & V()

초기값 1로 설정하여 S.value --를 통해 0이 되고 if문에 걸리지 않아 critical section을 수행하게 된다.

하지만 이후 들어오는 프로세스는 -값을 가져 if문에 걸려 block 된 후 linked-list에 추가된다.

critical section이 끝난 후 value값에 1을 더하고 하나를 list에서 제거 후 wakeup을 실행하여 다음 프로세스가 수행하게 된다.

이때 wakeup을 하는 경우 block 된 위치부터 실행하므로 바로 critical section으로 들어가게 된다.

integer semaphore -> value값을 사용하여 기다리는 프로세스의 개수를 파악 할 수 있음

binary semaphore -> 개수는 파악할 수 없고 유/무만 파악 가능

=>while loop 가 없어서 busy waiting 문제가 해결된다.

But! 무조건 좋은 것은 아니다. sleep, linked_list 저장, wakeup 모두 overhead를 발생시키기 때문이다

=> critical section이 짧은 경우 그냥 busy waiting을 하는 것이 더 효율적일 수 있다.

When the CS problem occurs in Operating System?

: 여러개의 Process 가 동시에 일하는 일이 OS에서도 일어날까? -> 발생한다!

3가지 경우

1.  Interrupt handler 와 kernel 사이에서 발생

2. kernel 이 system call 수행중 context switch 가 발생하는 경우

3. Multiprocessor - shared memory에서 kernel data 사용하는 경우

CS problem in OS (1) Interrupt handler v.s kernel

kernel process는 하나임에도 내부에서 동기화문제가 발생한다.

kernel code 실행중에 interrupt가 발생하여 interrupt handler code 실행 중 같은 kernel 변수를 사용하는 경우

-> disable/enable intrp 을 사용하여 해결

CS problem in OS (2) Preempt a process running in kernel?

: 프로세스간 scheduling 에 의해서 발생하는 문제

shared data가 없음에도 systemcall이 수행되는 동안 interleaved execution이 발생 할 수 있음

If you preempt CPU while in kernel mode

system call 이 발생하여 kernel code 수행 중 CPU Scheduling이 발생하여 다른 프로세스가 실행되고 이 프로세스가 kernel code 를 수행하게 되면 잘못된 결과를 도출한다.

-> System call 발생동안 CPU Scheduling이 발생하지 않도록 해서 문제를 해결하자

*UNIX의 경우 systemcall이 끝날 때까지 기다린다.

CS problem in OS (3) Multiprocessor

System 내에 CPU가 여러개인 경우 Interrupt disable,enable로 해결 할 수 없다.

1. Operating System 자체를 하나의 거대한 critical section으로 취급하는 방법 (간단한 방법)

CPU가 kernel 수행중이면 다른 CPU가 kernel 작업을 못하도록 한다.

-> 과도한 blocking으로 성능상의 문제가 발생한다. (CPU 개수를 늘려도 성능이 저하됨)

2. kernel 변수 하나하나에 대한 동기화 방법 (복잡한 방법)

-> 복잡하지만 성능면에서 문제가 발생하지 않음

=> 적절한 방법을 선택하는 것이 중요

[팔일3]

사람이면서 인하지 않으면 예를 행한들 무슨 소용이며, 사람이면서 인하지 않으면 음악을 연주한들 무슨 소용인가.

엄한 종법과 등급에 따라 예를 구분하던 시대이다.(주나라는 왕실과 얼마나 가까운지에 따라 등급이 정해짐)

인간 감정의 순화와 조화를 음악으로 이룩하고자 하였다.

하지만, 예악은 제도화 되어 사회를 유지하는 수단이 되어 형식만 남고 정신이나 가치는 잃은 사태를 비판하는 내용

[팔일5]

오랑캐에게 임금이 있는 것이 중국에 임금 없는 것과 같지 않다./ 것만 못하다.

제하 : 중국 고대 왕조를 의미

~과 같지 않다 - 오랑캐에도 임금이 있고 질서가 잡혔는데 중국은 무질서하다는 한탄

~만 못하다 - 오랑캐의 도를 따르기 보다 중국의 도를 지키는 것이 낫다는 문화적 자부심

[팔일6]

계강자가 태산에 제사 지내려 하자 공자가 염유에게 말했다. "네가 구할 수 없었느냐?" "그럴 수 없었습니다."

"아아! 결국 태산의 신이 (예의 근본을 물은) 임방보다는 못하다는 말인가."

려: 산에 지내는 제사로 천자나 제후가 주관

계강자는 대부로 염유는 당시 계강자의 가신이다. 려는 천자나 제후가 제사를 지내는 것인데 대부인 계강자가 지내는 것은 헛수고임을 비판하는 것이다. (태산의 신이 흠향하지 않을 것이라 하는 것)

[팔일8]

"어여쁜 웃음에 귀여운 보조개여, 예쁜 눈에 까만 눈동자여! 흰 바탕에 채색한 것이로다" 라는 시는 무슨 뜻인가요?"

"그림 그리는 일은 흰 바탕이 마련된 뒤에 하는 일이다." / "예가 나중이라는 말씀이시군요." "나를 일깨우는 자는 상이로구나. 비로서 너와 시를 말할 수 있겠다."

앞의 구절은 시경<석인> 의 부분이다.

내면-외적 표현으로서의 예를 의미하는 것. 제자가 참된 뜻을 알아 공자가 뿌듯해함

[팔일11]

어떤 이가 체제사에 대해 물었다. 공자께서 말씀하셨다. "모릅니다. 그걸 아는 자라면 천하 다스리는 일이 마치 이것을 보는 것과 같을 것입니다." 하고는 자기 손바닥을 가리키셨다.

체제사는 천자가 하늘에 올리는 제사이다. 본질이 변하여 귀족이 올리는  제사로 변한 현실을 공자가 한탄하는 것이다.

체제사는 천자가 올리는 것이 의미가 있는 것이지 천자가 아닌 사람에게는 알아도 쓸데 없다는 의미로 비아냥 거리는 공자의 모습을 확인할 수 있다.

[팔일13]

"안방신에게 아첨하느니 차라리 부뚜막신에게 아첨하는 것이 더 낫다는 말은 무슨 뜻입니까?" "그렇지 않다. 하늘에 죄를 지으면 빌 곳이 없다."

안방신 : 지체는 높으나 실제 일은 손대지 않는 분 -> 실권 없는 제후 군주.

부뚜막신 : 지체는 낮으나 실제 손님에게 밥상을 차려주는 사람 -> 대부급의 실권자

첫 부분에서 위령공의 대부인 왕손가가 공자의 도도함을 비판한 것이다. 공자는 이를 이해하고 명분에 맞게 예를 지키는 것이 천명이라는 인식을 드러냄. 실권 없는 제후 군주에 대한 공자의 섬김을 비판하고 공자는 입장을 고수함을 확인할 수 있음

[팔일16]

활을 쏠 때 과녁가죽 뚫기를 위주로 하지 않는 것은 (쏘는 사람마다) 힘이 같지 않기 때문이다. 이것이 옛날의 활 쏘는 도이다.

본래의 활쏘기는 읍하고,양보하는 예의를 배우는 것이 주가 되는 것이었다. 하지만 살상의 시대에 따라 맞기만 하고 과녁을 뚫지 못하는 것은 인정하지 않는 현재 시대를 표현하고 있다.

Short-term scheduler라고 생각하면 된다.

현재 cpu 자원을 수행중인 프로세스 중 누구에게 줄지 결정하는 것

-> 사용자와의 interactive를 위해 i/o bound job에 cpu를 빨리 할당해줘야 한다.

State Transition Diagram

CPU Scheduler

:어떤 process에게 cpu를 줘서 실행할 것인가를 결정 (Multiprogramming environment)

cpu scheduler는 메모리에서 프로세스를 선택한다. 

cpu scheduling이 일어나는 4가지 경우

1. running 상태에서 waiting 상태로 바뀌는 경우 (i/o request)

2. running 상태에서 ready 상태로 바뀌는 경우 (timerunout)

3. waiting 상태에서 ready 상태로 바뀌는 경우 (i/o finished interrupt)

4.terminated

3의 경우는 interrupt 가 끝난뒤 원래 실행 program으로 돌아오는것이 아니기에 다시 cpu scheduling을 시작

1,4의 경우 nonpreemptive, 2,3은 preempive 경우이다.

Dispatcher

:  결정된 process에게 cpu를 주는 과정을 수행한다.

Dispatcher module

-switching context, switching to user mode, 사용자 프로그램의 적절한 위치로 jump 하고 재시작

dispatch latency

기존 프로세서를 중단하고 새로운 프로세서를 실행하는데 걸리는 시간 -> context switch overhead

Scheduling Criteria (기준)

CPU utilization : cpu가 계속 동작하도록 하는 것이 좋음 

Throughput : 단위 시간당 처리하는 작업의 양 -> maximize

Turnaround time : process 시작부터 끝까지 걸리는 시간 -> minimize

Waiting time : ready queue 에서 프로세스가 기다리는 시간

Response time : interactivity

Scheduling Algorithms

FCFS Scheduling

: First Come First Served ->먼저 온 process에게 먼저 cpu를 할당해주겠다. (공평성이 강점)

->실행시간이 짧은 프로세스가 먼저 들어오는 경우 waiting time이 줄어듬 -> convoy effect!

Shortest-Job-First(SJF) Scheduling

: 빠른 것을 앞으로 보내서 wait 시간을 줄이자 (average waiting time 측면에서 optimal)

두 가지가 존재

1. Nonpreemptive :더 짧은 것이 들어오더라도 기존의 실행이 끝난 후 실행

2. Preemptive : SRTF(Shortest-Remaining-Time-First), 더 짧은 프로세스가 들어오면 기존의 것을 중지하고 짧은 것을 먼저 실행

Determining Length of Next CPU Burst

: 알고리즘 사용을 위해 process의cpu 사용시간을 알아야함 -> 알수없음

estimate 하는 방식!

기존의 값들을 참고하여 예측하는 방식을 사용한다.

a값이 작아질수록 과거의 데이터가 공평하게 반영되고 값이 커질수록 최근에 대한 가중치가 높아진다. 최근 데이터에 가중치를 높게 주면 정확도가 높아지는 것을 확인 할 수 있다. 증감이 일정한 경우에는 정확도가 높은 값을 가질수 있다.

증감이 일정하지 않고 증감이 수시로 반복되는 경우 완전히 잘못된 결과를 가져올 수 있음 -> why?

최근 데이터에 가중치가 높으면 증가하다가 감소로 변하는 지점에서 감소에 대한 데이터 대신에 직전에 증가하던 데이터에 가중치가 높아져 정확도가 떨어지는 결과를 낼 수 있음

Priority Scheduling

:우선순위를 고려한 Scheduling 방식

각 process 에 priority number가 부여되고 이 번호에 따라 실행 (작은수가 높은 우선순위)

문제 : Starvation, 낮은 우선순위 프로세스는 계속 뒤로 밀려남

해결 : Aging, 대기시간이 길어짐에 따라 우선순위를 높여줌

Round Robin(RR)

: time quantum(cpu사용 가능 최대시간)을 설정하여 모든 프로세스가 돌아가면서 한번식 실행될 수 있도록 함 -> multiprogramming 목적으로 나온 방식

단점 :  time quantum 이 너무 작은 경우 context switch overhead 발생

higher average turnaround 이지만 response가 뛰어나다.

Multilevel Queue

Ready queue를 나눈다.

forground(interactive) : RR -> i/o bound job

background(batch - no human interaction) : FCFS -> cpu bound job

RR자체로만 쓰기에는 부족하여 Multi level queue 사용

Scheduling 은 queue 사이에서 진행

1.Fixed priority scheduling : 모든 forground 를 수행 한 뒤에 background 수행 -> starvation 문제 발생

2.Time slice : 조금씩 나눠서 starvation 문제를 해결 eg. forground in RR 80%, background in FCFS 20%

Multilevel Feedback Queue

I/O bound job, CPU bound job을 어떻게 구분하기 위함

process들은 queue 간 이동을 함

MLFQ의 5가지 정책

1. queue의 개수

2. 각 queue에 해당하는 scheduling algorithms

3. upgrade 방식

4. demote 방식

5. 어떤 queue에 process를 넣을 것인지

Real-Time Scheduling

Hard real-time systems

: guaranteed amount of time (deadline) 내에 반드시 수행되어야 함