1. 상속

- 부모 클래스에 정의된 멤버 변수, 메소드를 자식 클래스가 물려 받음

- class 자식 extends 부모 { }

class Car {
    int speed;
    public void setSpeed(int Speed) {
        this.speed = speed;
    }
}

public class EletricCar extends Car {
    int battery;
    public void charge(int amount) {
        battery += amount;
    }
}

public class ElectricCarTest {
    public static void main(String[] args) {
        ElectricCar obj = new ElectricCar();
        
        obj.speed = 10;
        obj.setSpeed(60);
        obj.charge(10);
    }
}

 

- 상속 -> 이미 존재하는 클래스의 필드와 메소드 재사용 -> 중복되는 코드 줄일 수 있음

 

2. 자바 상속의 특징

- 다중 상속 지원하지 않음 (여러 개의 클래스로부터 상속 X)

- 다단계 상속은 가능 (A / B extends A / C extends B)

- 상속의 횟수에는 제한 없음 (자식 클래스의 개수 상관 X)

- 상속 계층 구조의 최상위에는 java.lang.Object 클래스가 있음

    - 모든 클래스의 부모 클래스

    - toString( ) 메소드

- 다른 패키지의 클래스도 상속 가능 (패키지.클래스 import 필요)

 

class Animal {
    int age;
    void eat() {
        System.out.println("먹고 있음 ... ");
    }
}

class Dog extends Animal {
    void bark() {
        System.out.println("짖고 있음 ...");
    }
}

public class DogTest {
     public static void main(String[] args) {
         Dog d = new Dog();
         d.bark();
         d.eat();
     }
 }
 
 // 짖고 있음 ...
 // 먹고 있음 ...

 

class Shape {
    int x, y;
}

class Circle extends Shape {
    int radius;
    public Circle(int radius) {
        this.radius = radius;
        x = 0;
        y = 0;
    }
    
    double getArea() {
        return 3.18 * radius * radius;
}

public class CircleTest {
    public static void main(String[] args) {
        Circle obj = new Circle(10);
        System.out.println("원의 중심: (" + obj.x + "," + obj.y + ")");
        System.out.println("원의 면적: " + obj.getArea());
    }
}

// 원의 중심: (0,0)
// 원의 면적: 314.0

 

3. 상속과 접근 지정자

- 자식 클래스는 부모 클래스의 public 멤버, protected 멤버, 디폴트 멤버(같은 패키지에 있는 경우) 상속 받음

- private 멤버는 상속되지 않음!

 

4. 상속과 생성자 

- 자식 클래스의 객체가 생성될 때 부모 클래스의 생성자도 호출됨!

class Base {
    public Base() {
        System.out.println("Base() 생성자");
    }
}

class Derived extends Base {
     public Derived() {
         System.out.println("Derived() 생성자");
     }
 }
 
 public class Test {
     public static void main(String[] args) {
         Derived r = new Derived();
     }
 }
 
 
// Base() 생성자
// Derived() 생성자

 

- 자식 클래스 객체 안에는 부모 클래스에서 상속된 부분이 들어있음

-> 부모 클래스 부분을 초기화하기 위해 부모 클래스의 생성자도 호출됨

 

- 순서) (부모 클래스 생성자) -> (자식 클래스 생성자)

 

5. 명시적인 생성자 호출

- super();  : 부모 클래스의 생성자 호출

class Base {
    public Base() {
        System.out.println("Base() 생성자");
    }
}

class Derived extends Base {
     public Derived() {
         super();
         System.out.println("Derived() 생성자");
     }
 }
class TwoDimPoint {
    int x, y;
    
    public TwoDimPoint() {
        x = y = 0;
    }
    
    public TwoDimPoint(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class TreeDimPoint extends TwoDimPoint {
    int z;
    public ThreeDimPoint(int x, int y, int z) {
        super(x, y);
        this.z = z;
    }
}

- 이 경우 부모 클래스의 두 생성자 중 TwoDimPoint(int x, int y)가 호출됨

- 인수의 형태에 따라 적절한 생성자 선택

 

6. 묵시적인 생성자 호출

class Base {
    public Base() {
        System.out.println("Base() 생성자");
    }
}

class Derived extends Base {
     public Derived() {
         System.out.println("Derived() 생성자");
     }
 }

- 컴파일러는 부모 클래스의 기본 생성자가 자동으로 호출되도록 함

- 묵시적인 생성자 호출을 하려면 부모 클래스에 기본 생성자(매개 변수가 없는 생성자)가 반드시 정의되어 있어야 함!

 

7. 메소드 오버라이딩

- 자식 클래스가 부모 클래스의 메소드를 자신의 필요에 맞춰 재정의하는 것

- 메소드 이름이나 매개 변수, 반환형은 같아야 함!

 

class Shape {
    public void draw() { System.out.println("Shape"); }
}

class Circle extends Shape {
    @override
    public void draw() { System.out.println("Circle을 그립니다."); }
}

class Rectangle extends Shape {
    @override
    public void draw() { System.out.println("Rectangle을 그립니다."); }
}

class Triangle extends Shape {
    @override
    public void draw() { System.out.println("Triangle을 그립니다."); }
}

public class ShapeTest {
    public static void main(String[] args) {
        Rectangle s = new Rectangle();
        s.draw();
    }
}

// Rectangle을 그립니다.

- Rectangle 클래스의 객체에 대해 메소드가 호출되면 Rectangle 클래스 안에서 오버라이딩된 draw()가 호출됨

- 철자를 잘못 쓰는 경우 컴파일러는 새로운 메소드로 인식하기 때문에 오버라이드가 일어나지 않음

-> @Override 어노테이션을 앞에 붙이면 이러한 경우 오류 발생시키므로 붙이는 것이 좋음!

 

8. 오버라이딩 & 오버로딩

- 오버로딩 (overloading) : 같은 이름을 가진 여러 개의 메소드 작성

- 오버라이딩 (overriding) : 부모 클래스의 메소드를 자식 클래스가 다시 정의하는 것

 

9. 정적 메소드 오버라이드

- 어떤 참조 변수를 통해 호출되는지에 따라 달라짐

class Animal {
    public static void A() {
        System.out.println("static method in Animal");
    }
}

public class Dog extends Animal {
    public static void A() {
        System.out.println("static method in Dog");
    }
    
    public static void main(String[] args) {
        Dog dog = new Dog();
        Animal a = dog;
        a.A();
        dog.A();
    }
}

// static method in Animal
// static method in Dog

 

10. 키워드 super 

- super는 상속 관계에서 부모 클래스의 메소드나 필드를 명시적으로 참조하기 위해 사용됨

- 부모 클래스의 메소드를 오버라이딩한 경우에 super를 사용하면 부모 클래스의 메소드 호출 가능

class Shape {
    public void draw() {
        System.out.println("Shape 중에 하나를 그릴 예정입니다.");
    }
}

class Circle extends Shape {
    @Override
    public void draw() {
        super.draw();              // 부모 클래스의 draw 호출 
        system.out.println("Circle을 그립니다.");
    }
}

public class ShapeTest {
    public static void main(String[] args) {
        Circle s = new Circle();
        s.draw;
    }
}

// Shape 중에 하나를 그릴 예정입니다.
// Circle을 그립니다.

 

11. 다형성

- 오버로딩은 컴파일 시간에서의 다형성 지원

- 메소드 오버라이딩은 실행 시간에서의 다형성 지원

 

- 다형성: 객체들의 타입이 다르면 똑같은 메시지가 전달되더라도 서로 다른 동작을 하는 것

- 동일한 코드로 다양한 타입의 객체를 처리할 수 있는 기법

 

12. 업캐스팅

- 부모 클래스 변수로 자식 클래스 객체 참조 가능! 

- 자식 클래스의 필드와 메소드에는 접근할 수 없음

- 자식 클래스의 부모 클래스 부분만 접근 가능!

- ex) Rectangle 클래스의 x, y (O) // width, height (X)

 

- 부모 클래스로 캐스팅 된다는 것은 멤버의 갯수 감소 의미! (부모 클래스의 멤버만 접근 가능)

- 업캐스팅을 하고 메소드를 실행할때 자식 클래스에서 오버라이딩한 메소드가 있을 경우, 오버라이딩 된 메소드가 실행됨!

 

// ex) Rectangle, Triangle, Circle 등의 도형 클래스가 부모 클래스인 Shape 클래스로부터 상속된 경우

class Shape {
    protected int x, y;      // 모든 도형의 공통 속성인 위치 기준점 (x, y)
    public void draw() { System.out.println("Shape draw"); }
}

class Rectangle extends Shape {
    private int width, height;
    public void draw() { System.out.println("Rectangle draw"); }
}

class Triangle extends Shape {
    private int base, height;
    public void draw() { System.out.println("Triangle draw"); }
}

class Circle extends Shape {
    private int radius;
    public void draw() { System.out.println("Circle draw"); }
}

public class ShapeTest {
    public static void main(String[] args) {
        Shape s1, s2;
        
        s1 = new Shape();
        s2 = new Rectangle();
    }
}
publc class ShapeTest {
    public static void main(String[] args) {
        Shape s = new Rectangle();
        // 업캐스팅
        // s는 Shape 타입, Rectangle 객체 가리킴
        
        Rectangle r = new Rectangle();
        
        s.x = 0;
        x.y = 0;
        //s.width = 100;    -> 오류!
        //s.height = 100;   -> s로 Rectangle의 필드와 메소드에 접근할 수 없음
    }
}

 

- 다운캐스팅: 부모 객체를 자식 참조 변수로 참조하는 것, 명시적으로 해야 함

class Parent {
    void print() { System.out.println("Parent 메소드 호출"); }
}

class Chile extends Parent {
    @Override void print() { System.out.println("Child 메소드 호출"); }
}

public class Casting {
    public static void main(String[] args) {
        Parent p = new Child();   // 업캐스팅: 자식 객체를 부모 객체로 형변환
        p.print();                // 동적 메소드 호출, 자식의 print() 호출
        
        // Child c = new Parent();  -> 컴파일 오류!
        
        Child c = (Child)p;       // 다운캐스팅: 부모 객체를 자식 객체로 형변환
        c.print();                // 메소드 오버라이딩, 자식의 print() 호출
    }
}

// Child 메소드 호출
// Child 메소드 호출

 

13. 업캐스팅 하는 이유

- 공통적으로 할 수 있는 부분을 만들어 간단하게 다루기 위해

- 상속 관계에서 상속 받은 자식 클래스가 몇 개이든 하나의 인스턴스로 묶어서 관리할 수 있기 때문

// 기존
Rectangle[] r = new Rectangle[];
r[0] = new Rectangle();
r[1] = new Rectangle();
 
Triangle[] t = new Triangle[];
t[0] = new Triangle();
t[1] = new Triangle();
 
Circle[] c = new Circle[];
c[0] = new Circle();
c[1] = new Circle();
// 업캐스팅
Shape[] s = new Shape[];
s[0] = new Rectangle();
s[1] = new Rectangle();
s[2] = new Triangle();
s[3] = new Triangle();
s[4] = new Circle();
s[5] = new Circle();

- 하나의 타입으로 묶어 배열을 구성

- 코드량도 훨씬 줄어들고 가독성도 좋아지며 유지보수성도 좋아짐

- 자식 고유의 메소드 실행하려면 다운캐스팅

 

14. 동적 바인딩

- 업캐스팅: 여러 가지 타입의 객체를 하나의 자료구조 안에 모아서 처리하려는 경우에 필요

 

- 도형 클래스 예제) 각 도형을 그리는 방법은 모두 다르기 때문에 종류에 따라 다른 draw() 호출해야 함

- Shape 클래스가 draw() 갖고 있고, 자식 클래스들이 이 draw() 오버라이딩 한 경우

public class ShapeTest {
    public static void main(String[] args) {
        Shape[] arrayOfShapes;         // Shape의 배열 arrayOfShapes[] 선언
        arrayOfShapes = new Shape[3];
        
        // 배열 arrayOfShapes의 각 원소에 객체를 만들어 대입
        // 다형성에 의해 Shape 객체 배열에 모든 타입의 객체 저장 가능
        arrayOfShapes[0] = new Rectangle();
        arrayOfShapes[1] = new Triangle();
        arrayOfShapes[2] = new Circle();
        
        for (int i = 0; i < arrayOfShapes.length; i++) {
            arrayOfShapes[i].draw();
        }
    }
}

// Rectangle draw
// Triangle draw
// Circle draw

 

15. 업캐스팅의 활용

- 메소드의 매개 변수를 부모 타입으로 선언하면 훨씬 넓은 범위의 객체 받을 수 있음

- 부모 클래스에서 파생된 모든 클래스의 객체를 다 받을 수 있음

public class ShapeTest {
    public static void print(Shape s) {
        System.out.println("x= " + s.x + " y= " + s.y);
    }
    
    public static void main(String[] args) {
        Rectangle s1 = new Rectangle();
        Triangle s2 = new Triangle();
        Circle s3 = new Circle();
        
        print(s1);
        print(s2);
        print(s3);
    }
}

 

16. instanceof 연산자

- 변수가 가리키는 객체의 실제 타입 반환

 

17. 종단 클래스와 종단 메소드

- 종단 클래스(final class) : 상속시킬 수 없는 클래스

- 보안상의 이유로 주로 사용

- 서브 클래스에서 재정의 불가

final class String {
    ...
}

class Baduk {
    enum Player { WHITE, BLACK }
    ...
    final Player getFirstPlayer() {
        return Player.BLACK;
    }
}

1. 객체지향 프로그래밍

- 데이터와 함수를 하나의 덩어리로 묶어서 생각하는 방법: 캡슐화

public class Circle {
	double radius;           // data
	String color;            // data
	double getArea() {return 3.14*radius*radius; }   // func
}

 

2. 정보 은닉

- 객체의 외부에서는 내부 데이터와 알고리즘을 볼 수 없게 함

- 공개된 인터페이스를 통해서만 객체에 접근하도록

 

3. 상속

- 이미 작성된 클래스(부모 클래스)를 이어받아서 새로운 클래스(자식 클래스) 생성 가능

- 자식 클래스는 부모의 속성과 동작 물려받음

 

4. 클래스

- 객체에 대한 설계도 (틀)

- 클래스로부터 만들어지는 각각의 객체 -> '인스턴스'

- 하나의 클래스로 여러 인스턴스를 만들어내지만, 인스턴스마다 속성의 값은 다름

public class Circle {
    // 필드
    public int radius;
    public String color;
    
    // 메소드
    public double getArea() {
        return 3.14*radius*radius;
    }
}

 

5. 객체 생성

- 참조 변수 선언

//Type   변수명  
 Circle   obj;

- 객체 생성

//변수       객체의 참조값
  obj = new Circle();

 

public class CircleTest {
    public static void main(String[] args) {
        // 참조 변수 선언
        Circle obj;
        
        // 객체 생성 & 객체의 참조값 -> 참조 변수에 저장
        obj = new Circle();
        
        // 객체의 필드 사용
        obj.radius = 100;
        obj.color = "blue";
        
        // 객체의 메소드 사용
        double area = obj.getArea();
        System.out.println("원의 면적= " + area);
    }
}

 

6. 참조 변수

- 객체 를 참조할 때 사용되는 변수 - 객체의 참조값이 저장되어 있음

- 참조값은 일반적으로 객체의 주소

- 자바에서 모든 객체는 new 연산자를 이용해야 생성됨

public class DeskLamp {
    // 인스턴스 변수 정의
    private boolean isOn;
    
    // 메소드 정의
    public void turnOn()  { isOn = true; }
    public void turnOff() { isOn = false; }
    public String toString() {
        return "현재 상태는" + (isOn == true ? "켜짐" : "꺼짐");
    }
}

public class DeskLampTest {
    public static void main(String[] args) {
        // 객체 생성
        DeskLamp myLamp = new DeskLamp();
        
        // 객체의 메소드 호출
        myLamp.turnOn();
        System.out.println(myLamp);
        myLamp.turnOff();
        System.out.println(myLamp);
    }
}

 

7. 메소드 오버로딩

- 이름이 동일한 여러 개의 메소드 작성 가능

- 매개변수의 수, 타입, 순서 등이 달라야 함

public class MyMath {
    int add(int x, int y)          { return x+y; }
    int add(int x, int y, int z)   { return x+y+z; }
    int add(int x, int y, int z, int w)   { return x+y+z+w; }
    
    public static void main(String[] args) {
        MyMath obj;
        obj = new MyMath();
        System.out.println(obj.add(10, 20));
        System.out.println(obj.add(10, 20, 30));
        System.out.println(obj.add(10, 20, 30, 40));
    }
}

 

8. 생성자

- 객체가 생성될 때 객체를 초기화하는 특수한 메소드

- 중복 정의 가능

class Pizza {
    int size;
    String type;
    public Pizza 90 {
        size = 12;
        type = "슈퍼슈프림";
    }
    
    public Pizza(int s, String t) {
        size = s;
        type = t;
    }
}

public class PizzaTest {
    public static void main(String[] args) {
        Pizza obj1 = new Pizza();
        System.out.println("(" + obj1.type + ", " + obj1.size + ",)");
        
        Pizza obj2 = new Pizza(24, "포테이토");
        System.out.println("(" + obj2.type + ", " + obj2.size + ",)");

 

9. 기본 생성자

- 매개변수 없는 생성자

- 생성자 하나도 정의하지 않으면 컴파일러가 자동으로 기본 생성자 만듦

 

10. this 참조 변수

- 현재 객체 자신을 가리키는 참조 변수

- 컴파일러에서 자동으로 생성

- 생성자에서 매개 변수 이름과 필드 이름이 동일한 경우에 사용

public Circle (int radius) {
    this.radius = radius;
}

 

11. this()

- 다른 생성자 의미

 

12. 접근 제어

- private: 클래스 안에서만 접근 가능

- public: 누구나 접근 가능

- protected: 자식 클래스만 접근 가능

- 접근지정자 x (default) : 동일 패키지 안에서만 접근 가능

 

13. 접근자와 설정자

- 접근자 (getters) 메소드: 필드값 반환

- 설정자 (setters) 메소드: 필드값 설정

 

- 접근자와 설정자 메소드만을 통해 필드에 접근해야 함!

- 설정자에서 매개변수를 통해 잘못된 값이 넘어오는 경우, 이를 사전에 차단할 수 있음

- 필요할 때마다 필드값을 동적으로 계산하여 반환할 수 있음

- 접근자만 제공 -> 읽기만 가능한 필드 만들 수 있음

- Source 메뉴에서 자동 입력 가능

 

class Account {
    private int regNumber;
    private String name;
    private int balance;
    
    // 접근자
    public String getName() {
    	return name;
    }
    
    // 설정자
    public String setName(String name) {
    	this.name = name;
    }
    
    public int getBalance() {
    	return balance;
    }
    
    public int setBalance(int balance) {
    	this.balance = balance;
    }
}

 

14. 객체의 소멸과 가비지 컬렉션

- 객체 삭제 연산자 없음

- 자동 메모리 시스템 사용: 가비지 컬렉션

 

- 가비지 컬렉터: 힙 메모리에서 더이상 필요없는 객체를 찾아 지움

- 가비지 컬렉션 요청 -> 모든 다른 애플리케이션 멈춤 -> JVM이 실행 여부 판단

System.gc;

 

15. 인수전달 방법

- 기본적으로 Call by value

- 객체를 메소드로 전달 -> 객체의 참조값만 복사되어 전달됨

- 참조 변수는 참조값(주소) 갖고 있음

- 배열도 객체 -> 배열 전달은 배열 참조 변수를 복사하는 것

 

public class ArrayArgumentTest {
	public static double minArray(double[] list) {
    	double min = list[0];
        for (int i = 1; i < list.length; i++) {
        	if(list[i] < min) 
            	min = list[i];
        }
        return (min);
    }
    
    public static void main(String[] args) {
    	double[] a = { 1.1, 2.2, 3.3, 4.4, 0.1, 0.2 };
        double[] b = { -2.0, 3.0, -9.0, 2.9, 1.5 };
        double min;
        
        min = minArray(a);
        System.out.println("첫번째 배열의 최솟값= " + min);
        min = minArray(b);
        System.out.println("두번째 배열의 최솟값= " + min);
    }
}

// 0.1
// -9.0

 

16. 정적 멤버

- 여러 개의 객체가 하나의 변수를 공유해야 하는 경우 

-> 이러한 멤버를 정적 멤버 (static member) / 클래스 멤버 (class member) 라고 함 

- 정적 변수: 클래스 당 하나만 생성되는 변수

- 여러 개가 존재할 수 있음, 한개의 static 변수는 한 번 선언됨

 

- 클래스를 통한 접근

Television.count = 100;

 

- 객체를 통한 접근

Television obj = new Televison();
obj.count = 100;

 

- 정적 메소드: 객체를 생성하지 않고 클래스 이름으로 접근해서 사용 가능

public class Math {
	public static double sqrt(double a) {
    	...
    }
}
...
double value = Math.sqrt(9.0);  // 클래스.함수명 으로 사용

 

17. 정적 변수의 활용

- 정적 메소드는 정적 멤버만 사용할 수 있음

class Test {
    int a;              // 인스턴스 변수
    static int b;       // 정적 변수
    
    void sub1() { a = 0; }         // OK
    static void sub2() { a = 0; }  // 오류! 정적 메소드에서는 인스턴스 멤버 사용할 수 없음

- 정적 메소드에서 정적 메소드를 호출하거나 정적 멤버를 사용하는건 가능

- 정적 메소드는 this를 사용할 수 없음

class Test {
    static int a;
    static void sub(int x) { this.a = x; }    // 오류!

 

- main()도 정적 메소드이기 때문에 인스턴스 메소드를 호출할 수 없음

- 정적 메소드는 main()에서 호출 가능!

public class Test {
    public static int cube(int x) {
        int result = x*x*x;
        return result;
    }
    
    public static void main(String args[]) {
        System.out.println("10*10*10은 " + cube(10));   // 정적 메소드 호출
    }
}

 

18. final 키워드

- 필드에 final을 붙이면 상수가 됨

- static과 동시에 사용하는 경우 많음

public class Car {
    static final int MAX_SPEED = 100;
}

- 상수는 클래스 변수로 만들어서 공유하는 것이 메모리 공간 절약

 

19. 싱글톤 패턴

- 객체 중 전체 시스템을 통틀어서 딱 하나만 존재해야 하는 것들이 있음

- ex) 환경설정 클래스, 네트워크 연결 풀 / 스레드 풀을 관리하는 클래스들

- 싱글톤 패턴은 하나의 프로그램 내에서 하나의 인스턴스만을 생성해야 하는 경우에 사용

 

class Single {
    private static Single instance = new Single();   
    private Single() { }      // 전용 생성자
    
    public static Single getInstance() {
        return instance;
    }
}

public class SingleTest {
    public static void main(String[] args) {
        Single obj1 = Single.getInstance();
        Single obj2 = Single.getInstance();
        System.out.println(obj1);
        System.out.println(obj2);
    }
}

 

20. 객체배열

- 객체를 저장하는 배열

- 객체에 대한 참조값 저장

 

class Rect {
    int width, height;
    
    public Rect(int w, int h) {
        this.width = w;
        this.height = h;
    }
    
    double getArea() {
        return (double) width * height;
    }
}

public class RectArrayTest {
    public static void main(String[] args) {
        Rect[] list = new Rect[5];             // 객체 배열 생성
        
        for (int i = 0; i < list.length; i++)
            list[i] = new Rect(i,i);           // 배열에 객체 값 저장 
            
        for (int i = 0; i < list.length; i++)
            System.out.println(i + "번째 사각형의 면적= " + list[i].getArea());
    }
}

/** 
0번째 사각형의 면적= 0.0
1번째 사각형의 면적= 1.0
2번째 사각형의 면적= 4.0
3번째 사각형의 면적= 9.0
4번째 사각형의 면적= 16.0
**/

 

for(int i = 0; i < list.length; i++)
     list[i] = new Rect(i, i);

 

21. 동적 객체 배열

- ArrayList<>

import java.util.ArrayList;

public class ArrayListTest {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<String>();
        list.add("홍콩");
        list.add("싱가포르");
        list.add("괌");
        list.add("사이판");
        list.add("하와이");
        
        System.out.println("여행지 추천 시스템");
        int index = (int)(Math.random()*list.size());
        System.out.println("추천 여행지는 " + list.get(index));
    }
}

- list.add(); 로 추가

 

import java.util.ArrayList;

class Person {
    String name;
    String tel;
    
    public Person(String name, String tel) {
        this.name = name;
        this.tel = tel;
    }
}

public class ArrayListTest2 {
    public static void main(String[] args) {
        ArrayList<Person> list = new ArrayList<Person>();
        list.add(new Person("Anna", "01023459293"));
        list.add(new Person("Jane", "01082983491"));
        list.add(new Person("Jim", "01012349722"));
        list.add(new Person("Emily", "01092938475"));
        for (Person obj : list)
            System.out.println("(" + obj.name + "," + obj.tel + ")");
    }
}

'Software > JAVA' 카테고리의 다른 글

[JAVA] Day6. 추상클래스, 인터페이스, 중첩클래스  (0) 2022.12.29
[JAVA] Day5. 상속  (0) 2022.12.29
[JAVA] Day2. 조건문, 반복문, 배열  (0) 2022.12.27
[JAVA] Day1. 자바 기초  (0) 2022.12.27
[JAVA] 예외처리  (0) 2021.07.22

C언어와 비슷한 문법!

 

1. if-else문

public class Nested {
	public static void main(String[] args) {
    
    	Scanner sc = new Scanner(System.in);
        System.out.print("정수 입력: ");
        int num = sc.nextInt();
        
        if (num > 0)
        	System.out.println("양수");
        else if (num == 0) 
        	System.out.println("0");
        else
        	System.out.println("음수");
            
    }
}

 

2. switch문

- 제어식에 숫자, 문자, 문자열 가능

 

import java.util.*;

public class Score2Grade {
	public static void main(String[] args) {
    	int score, num;
        char grade;
        
        Scanner sc = new Scanner(System.in);
        System.out.print("성적 입력: ");
        score = sc.nextInt();
        num = score / 10;
        
        switch(num) {
        case 10:
        case 9:		grade = 'A';    break;
        case 8:		grade = 'B';	break;
        case 7:		grade = 'C';	break;
        case 6:		grade = 'D';	break;
        default:	grade = 'F';	break;
        }
        System.out.println("학점: " + grade);
    }
}
switch(num) {
	case 10:
	case 9:    return 'a';
    
	case 10, 9 ->    return 'a';
}

// 둘 다 가능

 

3. for문

- for (초기식; 조건식; 증감식) {

   }

public class Sum {
	public static void main(String[] args) {
    	int sum = 0;
        
        for (int i = 1; i <= 10; i++) {
        	sum += i;
        }
        
        System.out.println("1부터 10까지의 정수의 합 = %d" + sum)l     
    } 
}

 

4. while문

- while (조건식) {

  }

import java.util.Scanner;

public class GetSum {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        
        int sum = 0, value = 0;
        
        while (value != -1) {
            sum += value;
            System.out.print("정수 입력: ");
            value = sc.nextInt();
        }
        System.out.println("정수의 합은 " + sum + "입니다.");
    }
}

 

5. do-while문

- 조건이 참인 동안 do 안의 문장 반복

- 우선 do 문장 한 번 실행하고 조건 확인

import java.util.Scanner;

public class CheckInput {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int month;
        do {
            System.out.print("올바른 월을 입력하세요 [1-12]: ");
            month = sc.nextInt();
        } while (month < 1 || month > 12);
        System.out.println("사용자가 입력한 월은 " + month);
    }
}

 

6. break, continue

- break: 반복문을 벗어남

- continue: 해당 반복을 멈추고 다음 반복으로 넘어감

 

7. 무한루프

- while문에서 종료 조건을 만들기 까다로운 경우 while(true)를 이용한 후 그 안에서 break문으로 반복을 빠져나가는 것이 좋음


8. 배열 선언과 사용

- 자바에서 배열은 객체

// 배열 생성
int[] s = new int[10];

// 배열 채우기
for (int i = 0; i < s.length; i++) {
	s[i] = i;
}

// 배열 출력
for (int i = 0; i < s.length; i++) {
	System.out.print(s[i] + " ");
} 
// 0 1 2 3 4 5 6 7 8 9

- 배열의 크기: s.length

// 배열 초기화
int [] scores = {10, 20, 30, 40, 50};

 

9. for-each 루프

int[] list = {1, 2, 3, 4, 5};

for (int e : list) {
	System.out.println(e);
}
// 배열 전부 출력

 

10. 2차원 배열

// 2차원 배열 생성
int[][] s = new int[3][5];

// 2차원 배열 초기화
int[][] testArray = {
	{10, 20, 30, 1, 2},
	{40, 50, 60, 3, 4},
	{70, 80, 90, 5, 6}
};

// 2차원 배열 출력
for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 5; j++) {
    	System.out.println(s[i][j]);
    }
}

 

11. 래그드 배열

int[][] ragged = new int[MAX_ROWS + 1][];

for (int r = 0; r <= MAX_ROWS; r++)
	ragged[r] = new int[r+1];

 

public class RaggedArray {
	public static void main(String[] args) {
    	int[][] ragged = new int[3][];
        ragged[0] = new int[1];
        ragged[1] = new int[2];
        ragged[2] = new int[3];
        
        for (int r = 0; r < ragged.length; r++) {
            for (int c = 0; c < ragged[r].length; c++)
            	ragged[r][c] = c;
        }
    }
}

 

12. ArrayList

- 배열의 크기 동적 변경하면서 사용 가능

ArrayList<String> list;    // list: 문자열을 저장하는 ArrayList 참조 변수 선언
list = new ArrayList<>();  // ArrayList 생성

list.add("Apple");
list.add("Grape");
import java.util.*;

public class ArrayListTest {
	public static void main(String[] args) {
    	ArrayList<String> list = new Arraylist<>();
        list.add("Anna");
        list.add("Mike");
        list.add("Joy");
        list.add("Lina");
        for (String obj : list)
        	System.out.print(obj + " ");
    }
}
// Anna Mike Joy Lina

'Software > JAVA' 카테고리의 다른 글

[JAVA] Day5. 상속  (0) 2022.12.29
[JAVA] Day 3-4. 클래스와 객체  (2) 2022.12.29
[JAVA] Day1. 자바 기초  (0) 2022.12.27
[JAVA] 예외처리  (0) 2021.07.22
[JAVA] 객체지향  (0) 2021.07.22

1. 클래스

- 객체 지향 언어의 기본적인 빌딩 블록

public class Name {

}

- 자바 소스파일 (.java) 는 항상 public이 붙은 클래스의 이름과 동일해야 함

- 하나의 소스파일 안에 public 클래스가 2개 이상 있으면 오류 발생

 

2. 메소드

- 특정한 작업을 수행하는 코드의 묶음

public static void main (String[] args) {
	System.out.println("Hello World!");
}

 

3. 자료형

- 기초형

    - 정수형: byte(1), short(2), int(4), long(8)

    - 실수형: float(4), double(8)

    - 논리형: boolean

    - 문자형: char (2, 유니코드)

 

- 참조형: 클래스, 인터페이스, 배열

 

- 리터럴:

    - 소스코드에 직접 쓰여있는 값 (ex, x = 100;)

    - 정수형, 부동소수점형, 문자형 등의 여러 타입 있음

 

- 상수: 프로그램이 실행되는 동안 값이 변하지 않는 수

 

4. 형변환

- 산술 연산 전에 피연산자의 타입 통일해야 함

- 강제 형변환

int x = 3;
double y = (double) x;

 

5. 콘솔에서 입력받기 (Scanner)

- System.in 사용

import java.util.Scanner;
Scanner sc = new Scanner(System.in);

 

- 키보드로부터 바이트 값 받아서 분리자를 이용하여 토큰으로 분리

- default 분리자는 공백문자 (' ', '\n', '\t')

String name = sc.next();           // 한 단어 입력
int age = sc.nextInt();            // 문자열(토큰)을 정수로 변환하여 반환
double weight = sc.nextDouble();   // 문자열을 실수로 변환하여 반환
String line = sc.nextLine();       // 한 줄 입력

 

6. 조건 연산자

'Software > JAVA' 카테고리의 다른 글

[JAVA] Day 3-4. 클래스와 객체  (2) 2022.12.29
[JAVA] Day2. 조건문, 반복문, 배열  (0) 2022.12.27
[JAVA] 예외처리  (0) 2021.07.22
[JAVA] 객체지향  (0) 2021.07.22
[JAVA] 배열  (0) 2021.07.20

[수업출처] 숙명여자대학교 소프트웨어학부 김주균 교수님 운영체제 수업 & [OS? Oh Yes!] 

 

1. (CPU) 스케줄링

- 시분할 시스템에서 현제 프로세스로부터 다른 프로세스로 CPU를 넘겨주어야 할 때, 기다리는 프로세스들 중에 어떤 프로세스를 선택해야할 지에 대한 방식이나 기준

 

- 수행 단계에 따라 장기, 중기, 단기 스케줄링

- 장기

    - 어느 작업을 커널에 등록시켜 프로세스로 만들어 줄 것인가 결정

    - 작업 스케줄링

    - 일괄처리) 작업: 디스크 → 일괄처리 큐 대기 → 장기 스케줄러 → 프로세스

    - 시분할) 사용자의 접속 시도를 허용할지 말지 결정하는 단계

    - 요청된 일을 프로세스로 만들어 시스템에 알려진 일거리로 추가하느냐 결정 → 다중 프로그래밍 정도 조절

    - 수행 횟수 적음, 대부분 FIFO 방식

 

- 중기

    - 보류 상태의 프로세스 중에서 어느 프로세스에 메모리를 할당할 것인지 결정

    - Swap In (or Resume)

 

- 단기

    - 준비 상태의 프로세스 중에서 어느 프로세스에 CPU를 할당할 것인지 결정

    - 프로세스 스케줄러 (디스패처)라 불리는 것에 의해 수행

    - 입출력, 시간 종료 인터럽트, 시스템 콜 등과 같은 다양한 이유에 의해 가동

    - 자주 수행됨 → 실행 시간 줄여야 함

 

2. 스케줄링의 목적과 기준

1) 목적

- 사용자 관점

    - 응답시간: 프로세스 요청에 의해 시스템이 최초로 출력을 내주기 시작할 때까지 걸린 시간 → 대화형 시스템

    - 반환시간: 요청으로부터 결과를 돌려받는 데까지 걸린 시간 (일괄처리)

    - 예측가능성: 요청한 일이 얼마 후쯤에는 완료될 수 있을 것이라는 예측

 

- 시스템 관점

    - 처리량: 단위 시간에 완료된 프로세스의 개수 → 일괄처리 시스템

    - 활용도: 주어진 시간동안 특정 자원이 실제로 가동된 시간의 비율

 

- 가능한 한 CPU 시간을 공평하게 나누어 주어야 함 (공평성)

- 특정 프로세스가 장기간 CPU를 받지 못하게 되는 경우 최대한 피해야 함

- 시스템에 있는 여러 자원들은 가급적 균형있게 사용되어야 함

 

- 빠른 응답시간을 주기 위해 스케줄링을 자주 한다면 문맥교환이 자주 일어나게 되고, 이것은 CPU 시간의 상당 부분이 문맥교환에 사용된다는 것을 의미 → 사용자 프로세스를 실행할 시간이 줄어 전체적으로는 처리량 감소

- 주어진 기간 동안에 많은 프로세스 처리하여 처리량을 높이려고 수행 시간이 짧은 프로세스들 주로 처리 → 수행시간이 긴 프로세스는 처리가 늦어져 응답시간이 길어짐

 

2) 고려해야 할 기준들

- 프로세스의 성격

    - CPU를 사용하는 연산이 입출력에 비해 상대적으로 많은 것: 연산 위주 프로세스 (CPU-bound)

    - 입출력이 상대적으로 많은 것: 입출력 위주 프로세스 (I/O-bound)

    - 목적에 따라 어떤 종류의 프로세스 우대할지 생각

 

- 시스템이 사용될 환경

    - 응답시간을 우선으로 할지, 처리량을 우선으로 할지

    - 특정 프로세스에게 우선적으로 빠른 응답시간을 보장해야 하는 경우 → 가능케 하는 기능 필요

    - 프로세스 크고 작음에 따라 어떤 것을 우선적으로 처리할 지 기준 필요 (CPU 요구량 & 메모리 요구량)

 

3. 스케줄링 기법들

[스케줄링이 가동되어야 할 때]

- 실행 상태에서 대기 상태로 전환될 때 (ex 입출력)

- 실행 상태에서 준비 상태로 전환될 때 (ex 시간 종료 인터럽트)

- 대기 상태에서 준비 상태로 전환될 때 (ex 입출력 종료)

- 프로세스 수행 종료

 

- 비선점 스케줄링: 프로세스가 CPU를 스스로 반납할 때까지 계속 사용

- 선점 스케줄링: 실행 중인 프로세스로부터 CPU를 빼앗아 다른 프로세스에 할당 가능

 

- 위의 4가지 경우 중 1번과 4번의 경우에만 스케줄링을 하게 되면 비선점 방식이 되고, 

- 2번과 3번에도 적용되는 스케줄링을 선점 방식이라 함

 

- Average Waiting Time 평균 대기 시간: 준비 큐에 도착한 후 실행될 때까지 걸린 시간, 사용자 만족도의 기준

 

1) FCFS (First Come First Service = FIFO) 스케줄링 

- 준비 큐에 먼저 도착한 프로세스에게 먼저 CPU 할당

- 비선점 방식

- 프로세스가 CPU를 독점하여 사용하기 때문에 아주 긴 프로세스가 실행될 경우 평균 응답시간이 길어짐

- 대화형 시스템에 적합하지 않음

- 프로세스들의 개수와 크기를 짐작할 수 있다면 각각의 프로세스들이 언제쯤 실행될 지 예측 가능, 공평함

- 실제 시스템에서 바로 사용되기는 어렵지만, 다른 스케줄링 기법의 보조 장치로서 활용 가능

 

- ex

프로세스 도착 시간 CPU 요구량 (초)
P1 0 100
P2 0 10
P3 0 10
P4 0 10

- P1, P2, P3, P4의 순서로 거의 동시에 도착했을 때

- 평균 응답시간 = (100 + 110 + 120 + 130) / 4 = 115

- 평균 대기시간 = (0 + 100 + 110 + 120) / 4 = 82.5

 

- P2, P3, P4, P1의 순서로 거의 동시에 도착했을 때

- 평균 응답시간 = (10 + 20 + 30 + 130) / 4 = 47.5

- 평균 대기시간 = (0 + 10 + 20 + 30) / 4 = 15

 

2) SPN (Shortest Process Next) 스케줄링

- 준비 큐에 있는 프로세스들 중 가장 짧은 프로세스 (CPU 요구량이 가장 적은)를 먼저 실행

- 비선점 방식

- 평균 응답시간을 최소화할 수 있지만, 실행시간이 긴 프로세스가 CPU를 할당받지 못하고 계속 대기하는 무한 대기 현상 발생

    - 긴 프로세스일수록 그 편차가 커져 예측가능성은 감소할 것

    - 무한 대기 가능성을 낮추는 방법으로는 기다린 시간만큼 우선순위를 높여 실행가능성을 높여주는 것이 있음 (Aging)

- 각 프로세스들의 크기를 실행 전에는 정확히 알 수 없음에도 그 크기를 가지고 스케줄을 해야한다는 단점

    - 해결책: 프로세스의 크기를 실행 전에 추정해보는 지수 평균 방법 (Exponential Averaging)

    - 이전에 실행되었을 때의 크기와 그때의 추정 크기로 지금 실행되어질 크기 짐작

    - 이전 단계의 실제 크기 → 다음 추정 크기

    - 추정 크기와 실제 크기의 가중치를 각각 0.5로 설정하고, 추정크기를 a, 실제크기를 b라 했을 때

    - 실제1 = 추정2 = 0.5a + 0.5b

    - 실제2 = 추정3 = 0.5(0.5a + 0.5b) + 0.5b ...

 

- ex)

프로세스 도착 시간 CPU 요구량 (초)
P1 0 10
P2 0.5 5
P3 1 2

- 평균 응답시간 = (10 + 16.5 + 11) / 3 = 12.5

- 평균 대기시간 = (0 + 11.5 + 9) / 3 = 6.84

 

3) SRT(Shortest Remaining Time) 스케줄링

- SPN을 선점 방식으로 운영하는 것

- 새로 도착하는 프로세스의 실행시간 크기는 완료까지 남은 시간과 같으며, CPU를 할당받아 실행된 양만큼 남은 시간은 줄어들 것

- 준비 큐에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행시켜 주는 방식

- 실행 도중 남은 실행 시간이 더 적은 프로세스가 준비 큐에 들어올 경우 현재 실행 중인 것을 중단하고 새 프로세스에 CPU 할당

- 완료까지 남은 실행시간의 계산, 잦은 문맥교환의 부담 존재

- 반환시간을 기준으로 했을 때 SPN보다 우수

 

- 위의 예제에 대입해보면

- P1 (0.5s) → P2 (0.5) → P3 (2) → P2 (4.5) → P1 (9.5) 의 순서로 CPU가 할당됨

- 평균 응답시간 = (17 + 7 + 2) / 3 = 8.67

- 평균 대기시간 = (7 + 2 + 0) / 3 = 3

 

- 이때 실제로는 SPN보다 더 많은 문맥교환이 요구되어 평균 응답시간이 조금 더 길어질 것임을 예상할 수 있음

- 만약 가까운 미래에 도착하게 될 프로세스의 정보를 알 수 있다면, 위의 예제에서 1초 뒤에 P3가 들어올 것을 알 수 있다면 P1을 할당하는 대신 1초를 기다렸다가 SPN을 적용하여 평균 응답시간을 줄일 수 있음 

→ 반복적인 시스템에서는 사용할 수 있겠지만 사실 어려움. idea 차원의 개념. Future-knowledge 스케줄링

 

- 잦은 문맥교환을 줄이는 방법

- SRT 스케줄링을 위한 임계값을 정해두고 두 프로세스의 남은 시간 차이가 임계값을 넘지 않을 경우에는 다음 프로세스의 실행시간이 더 짧더라도 선점되지 않도록 함

 

4) HRRN (Highest Response Ratio Next) 스케줄링

- 수행시간이 긴 프로세스의 무한 대기 현상을 방지하기 위한 기법

- 준비 큐에 있는 프로세스들 중에서 응답률이 가장 높은 우선순위를 줌

- 비선점 방식

- 응답률 = (대기시간 + CPU 요구량) / CPU 요구량

- 프로세스가 기다리는 시간이 길어질수록 우선순위가 높아지므로 곧 CPU 할당받을 수 있음

 

5) 라운드 로빈 (Round-Robin) 스케줄링

- FCFS 스케줄링을 기반으로 하여 CPU를 할당히되, 각 프로세스는 시간 할당량이 지나면 시간 종료 인터럽트에 의해 CPU 뺏기는 방식

- 선점 방식

- CPU를 반환한 프로세스는 다시 준비 큐의 끝에 들어가게 되고, 준비 큐의 맨 앞에 있는 프로세스가 CPU 선점

 

- ex)

프로세스 CPU 요구량 (ms)
P1 30
P2 8
P3 15
P4 10

- 위 프로세스들이 거의 동시에 도착했고, 시간 할당량이 10ms 일 때

- P1 (10) → P2 (8) → P3 (10) → P4 (10) → P1 (10) → P3 (5) → P1 (10) 순서로 CPU 할당 받음

- 평균 응답시간 = (63 + 18 + 53 + 38) / 4 = 43

- 평균 대기시간 = (33 + 10 + 38 + 28) / 4 = 27.25

 

- 한 프로세스가 CPU를 독점하는 단점을 방지할 수 있지만, CPU 선점에 따른 문맥교환의 오버헤드 감수해야 함

- 오버헤드: 문맥교환에 필요한 시간, 메모리 등

- 오버헤드에도 불구하고 이 기법은 대화식 시스템이나 시분할 시스템에 적합한 방식으로 알려져 있음

- 시간 할당량의 크기에 따라 시스템의 성능이 크게 달라질 수 있음

- 시간 할당량이 매우 크면 FCFS 방식과 같아지게 되며, 작을수록 문맥교환이 자주 발생하므로 문맥교환의 오버헤드가 커짐

- 일반적으로 시간 할당량은 10~100ms가 적당

 

- 연산 위주의 프로세스가 입출력 위주의 프로세스보다 우대받고 있음

- 입출력 위주 프로세스는 대부분 시간 할당량을 남긴 채 입출력을 발생시킨 다음 입출력이 완료되면 당시 남겨진 시간 할당량을 보상받지 못한 채 큐의 맨 뒤로 들어감 

→ 입출력을 마친 프로세스가 들어가는 준비 큐를 따로 하나 두고 우선순위는 더 높게 하되, 이 큐에서 CPU를 받을 때에는 이전 입출력을 발생시켰을 때 남긴 시간 할당량만큼만 주도록 하는 방식이 있음 : 가상 라운드 로빈 방식

 

- 프로세스가 생성될 때 부여된 우선순위가 완료 때까지 변하지 않는 값 → 정적 우선순위

- 시스템에 있는 동안 조정되도록 → 동적 우선순위

 

6) 다단계 큐 (Multi-level Queue) 스케줄링

- 정적 우선순위를 사용하는 선점 방식

- 우선순위의 개수만큼 큐 필요 → 같은 우선순위를 가지는 프로세스끼리 큐에 들어감

- 큐들 간에 프로세스 이동 불가능

- 우선순위가 낮은 하위 단계 큐의 작업은 실행 중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU 뺏김

 

7) 다단계 피드백 큐 (MFQ, Multi-level, Feedback Queue)

- 프로세스들의 CPU 요구량을 몰라도 짧은 프로세스들에게 유리하면서 입출력 프로세스를 우대할 수 있는 기법

- 입출력 프로세스 우대 → 짧은 연산 후 입출력 발생하면 CPU는 다른 프로세스에게 주어지고 입출력 작업과 병행되어 시스템 성능 향상

- 동적 우선순위를 기반으로 하는 선점 방식

 

- 우선순위 개수만큼 큐가 있으며 각 단계마다 서로 다른 CPU 시간 할당량을 가지도록 함

- 우선순위가 높은 단계의 큐일수록 시간 할당량 작도록 함

- 새로운 프로세스는 최상위 단계의 준비 큐에 들어간 후 FCFS의 순서로 CPU를 할당받아 실행되다가 그 큐의 시간 할당량이 끝나면 한 단계 아래의 준비 큐에 들어감으로써 우선순위가 한 단계 낮아짐

- 각 단계에서도 그 단계 큐의 시간 할당량을 다 사용할 때까지 계속 실행된다면 다음 단계의 큐로 들어감

- 마지막 단계에서는 라운드 로빈 방식으로 실행 (시간 할당량이 지나면 다음 프로세스에게 CPU 할당, 준비 큐 맨 뒤로 들어감)

 

- 어떤 단계에서든 시간 할당량이 끝나기 전에 입출력 등으로 CPU를 내놓게 되면 다시 준비 상태가 되었을 때 한 단계 위의 큐에 들어가도록 함으로써 우선순위를 높여줌

 

- 중간 단계의 맨 앞에 있는 프로세스는 상위 단계의 큐들이 비어있는 경우에만 CPU를 받을 수 있고, 시간 종료 인터럽트에 의해 선점되거나 입출력이 발생하지 않는 한 그 큐의 시간 할당량까지 쓸 수 있음

- 일단 CPU를 받은 프로세스는 실행 중 상위 단계의 프로세스에 의해 선점되지 않고 부여받은 시간 할당량까지는 보장됨

 

- 상대적으로 짧은 프로세스들이 하위 큐까지 내려가지 않도록함으로써 비교적 높은 우선순위를 유지할 수 있도록 함

- 입출력은 우선순위의 상향조정으로 이어져 우대받음을 알 수 있음

- Behavior Adaptive 스케줄링

 

- 변형)

- 각 단계에서 시간 할당량을 다 쓸 경우 그 단계의 큐에서 몇 번의 순환 후 다음 단계로 떨어뜨림

- 입출력의 완료 시 단계의 상승 폭을 더 크게 줌 

- 현재 큐에서 대기한 시간이 일정 시간을 넘기면 상위 큐로 이동시켜 줌

 

8) Fair-share 스케줄링

- 프로세스들의 특성이나 중요도에 따라 몇 개의 그룹으로 나누고, 각 그룹에 할애된 일정량의 CPU 시간은 그 그룹에만 영향을 미치도록 함

- ex)

- 1(A B) 2(C D) 3(E F)

- 1그룹에는 CPU 시간의 50%, 2그룹과 3그룹에는 각 25% 할당

- ACBEADBF의 순서대로 스케줄을 하거나, A에게 많은 시간을 주어야 할 경우 B를 줄이고 A를 늘리는 등 타 그룹에는 영향이 가지 않도록

 

4. 실시간 Realtime 스케줄링

- 실시간 시스템: 실행될 모든 프로세스들이 정해진 시간 내에 완료되어야 하는 시스템

- 경성 실시간 시스템

    - 작업이 마감시한 내에 완료되지 않으면 치명적인 결과를 초래하는 시스템 (시스템이 중지되는 등) 

    - 마감시한을 넘긴 후 완료되는 일은 아무 가치가 없음

    - 일반적으로 실시간 시스템은 경성 실시간 시스템을 말함

- 연성 실시간 시스템

    - 작업이 마감시한 내에 종료되지 않으면 데이터의 손실 등 피해가 발생하지만 시스템은 계속 운영 가능한 시스템

    - 마감시한을 넘긴 후부터는 완료의 가치가 점점 떨어짐

 

- 정적인 방법:  프로세스들의 특징과 개수를 알 수 있는 경우에 유용

- 동적인 방법: 프로세스의 생성 시간이나 특성을 알 수 없는 경우에 사용

- 실시간으로 운영되는 환경은 대부분 특수한 상황으로, 실행되어야 할 일들의 성격이나 개수를 사전에 알 수 있는 경우가 많음

 

1) RM (Rate Monotonic) 알고리즘

- 대표적인 정적 스케줄링 방식

- 크기와 개수가 알려진 프로세스들이 각자 주기적으로 발생되는 환경에서 사용

- 프로세스는 서로 독립적이고 주기적으로 수행되는 환경에서 각 프로세스의 마감시한은 각자의 주기와 같다고 가정

- 주기가 짧을수록 높은 우선순위 받음

- 낮은 우선순위의 프로세스가 더 높은 우선순위의 프로세스가 도착할 경우 CPU를 뺏기는 선점 방식

- 정적 환경에서 최적의 기법으로 알려져 있음

 

- n개로 구성된 프로세스 집합이 있을 때, 이 프로세스들에 의한 CPU 사용률 U는 아래와 같음

- U = U1 + U2 + ... Un = C1/P1 + C2/P2 + ... + Cn/Pn ≤ n(2^(1/n) - 1)

- 이 식이 만족되면 RM 기법으로 모든 프로세스의 마감시한을 맞출 수 있는 스케줄링이 가능하다는 것이 알려져 있음

- 1보다 작거나 같을 경우 될 수도 있고 안될 수도 있으며, 1보다 큰 경우엔 불가능함

- P는 주기, D는 마감시한, C는 크기(수행시간)

 

- 스케줄링 비용이 적게 드는 대신, 새로운 프로세스가 추가되는 환경에 바로 적응하지 못하고 전체 스케줄링을 다시 해야하는 단점

 

- ex) 

  주기 크기
T1 3 2
T2 6 2

- T1의 주기가 짧으므로 먼저 시작

- T1 (2) → T2 (1) // 3 → T1 (2) → T2 (1) // 6

- T1과 T2 모두 주기 내에서 일이 완료되었기 때문에 성공

- U = 2/3 + 2/6 = 1

 

2) EDF (Earliest Deadline First) 알고리즘

- 프로세스 마감시한이 가까울수록 우선순위 높게 부여하는 선점 방식의 동적 스케줄링

- 동적: 새로운 프로세스가 도착할 때 바로 대응할 수 있음

- 우선순위에 의해 실행 중 CPU 뺏길 수 있음

- 한 프로세스의 실행이 완료될 경우 마감시한이 가장 가까운 것을 찾아 스케줄

- 모든 프로세스가 주기적일 필요는 없으며, 주기가 있을 경우에는 마감시한을 주기로, 그렇지 않을 경우는 마감시한이 알려져야 함

 

- n개의 프로세스가 있을 때 아래와 같은 조건이 성립한다면 EDF 기법으로 가능한 스케줄이 존재

- C1/P1 + C2/P2 + ... + Cn/Pn ≤ 1

 

- 새로운 프로세스의 동적인 수용이 허용되나, 그럴 때마다 가능한 스케줄을 찾기 위한 계산을 해야하는 부담 존재

 

- ex)

프로세스 도착시간 CPU 요구량 (크기) 마감 시간
P1 0 8 25
P2 4 3 10
P3 5 10 20

- P1 (4) → P2 (3) → P3 (10) → P1 (4) //21

- P1이 수행되다가 4초 후에 마감 시간이 더 짧은 P2가 들어오면 P2가 CPU를 선점

- 1초 후에 P3가 들어오지만 여전히 P2의 마감 시간이 더 짧기 때문에 P2 수행 완료

- 그 다음 P3가 20초 내에 종료되어야 하기 때문에 P3 실행

- P3 종료 후 P1 마무리 → 성공

'Software > OS' 카테고리의 다른 글

[OS] 3장. 프로세스와 스레드  (0) 2022.04.11
[OS] 2장. OS 상식과 인터럽트  (0) 2022.04.10
[OS] 1장. OS의 정의와 역사, 기능  (0) 2022.03.05

[수업출처] 숙명여자대학교 소프트웨어학부 유석종교수님 자료구조 수업 & [파이썬으로 배우는 자료구조 프로그래밍]

* 수강생이 혼자 푼 답을 기록한 것으로 정답이 아닐 수 있습니다 😁

 

1. 

l = [21, 7, 40, 29, 11, 5, 90, 78, 64, 15, 88]
max = 0
min = 1000

for i in range(len(l)):
    if l[i] > max:
        max = l[i]
    if l[i] < min:
        min = l[i]
    
print((min, max))
(5, 90)

 

2.

def mul(n, m):
    l = []
    for i in range(1, n):
        if i % m == 0:
            l.append(i)
    return l

print(mul(10, 3))
[3, 6, 9]

 

3.

def gcd(a, b):
    while a % b != 0:
        a, b = b, a % b
    return b

def fraction(num):
    down = 10**len(str(num))
    up = num * down
    common = gcd(up, down)
    new_up = int(up // common)
    new_down = int(down // common)
    print(new_up, '/', new_down)
fraction(3.14)
# 157/50

 

4. 

def palindrome(string):
    while len(string) > 1:
        if string[0] != string[-1]:
            return False
        else:
            string = string[1:-1]
    return True
palindrome('abnnba')
# True

palindrome('sdfg')
# False

 

5.

l = [1]
num = 1
for i in range(14):
    num += 3
    l.append(num)
[1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 35, 37, 40, 43]

 

6.

l = []
num = 1
for i in range(15):
    num += i
    l.append(num)
[1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106]

 

7.

scores = [[75, 90, 85], [60, 100, 75], [90, 70, 80]]

for score in scores:
    for i in score:
        print(i, end = ',')
    print()
75,90,85,
60,100,75,
90,70,80,

 

8.

p = [(9, 4), (5, 3), (4, 2)]
q = [(7, 3), (2, 2)]
add_list = []
mul_list = []

def add(p, q):
    while p and q:
        coef1, exp1 = p[0]
        coef2, exp2 = q[0]
        if exp1 > exp2:
            add_list.append(p.pop(0))
        elif exp1 < exp2:
            add_list.append(q.pop(0))
        else:
            add_list.append((coef1 + coef2, exp1))
            p.pop(0)
            q.pop(0)
    for coef, exp in p:
        add_list.append((coef, exp))
    for coef, exp in q:
        add_list.append((coef, exp))
    return add_list
        
def mul(p, q):
    while p and q:
        coef1, exp1 = p[0]
        for coef, exp in q:
            mul_list.append((coef1*coef, exp1+exp))
        p.pop(0)
    return mul_list
add(p, q)        
print('P + Q = ', add_list)
# P + Q =  [(9, 4), (12, 3), (6, 2)]

mul(p, q)
print('P * Q = ', mul_list)
# P * Q =  [(63, 7), (18, 6), (35, 6), (10, 5), (28, 5), (8, 4)]

- 곱셈 후 지수가 같은 항 합치는 방법 생각해야함!

'Software > Data Structures' 카테고리의 다른 글

[Python] 2. Python Data Type  (0) 2022.04.16
[Python] 1. Introduction  (0) 2022.03.08
[자료구조] 탐색  (0) 2021.04.20
[자료구조] 연결 리스트  (0) 2021.04.20
[자료구조] 선형 자료구조  (0) 2021.04.18

[수업출처] 숙명여자대학교 소프트웨어학부 유석종 교수님 자료구조 수업

 

1. Python

- Interpreter

- 객체 지향 Object-oriented

- 자료형 미리 선언하지 않음 Dynamic typing

- Sequence, collection data type

- 값 저장X, 참조 방식 Literal reference

- 동적 할당 Dynamic allocation

 

- 파이썬의 모든 변수 → 포인터

- 값에 대한 참조 변수 (값이 저장되어 있는 곳의 주소 참조)

- a, b = b, a : swap

 

2. Data type

1) Immutable data type 불변자료형

- int, float, string

- 값 변경 불가능 → 값 변경이 아니고 새로운 literal 참조하는 것

- 매개변수 전달시 값 변경 불가능

 

2) Mutable data type 가변자료형

- list, dictionary

- 원소 값 변경, 추가 가능

- 리스트는 각 원소 값에 대한 참조들의 모음

- 매개변수 전달시 인수 값 변경될 수 있음

- 가변자료형: '참조변수'를 바꿀 수 있다는 것

 

3. Parameter Passing

- call by value

- call by reference

- python → call by object reference 객체 참조 전달

 

def f(a):
    a = 3
    print(a)
    return(a)
   
b = 2
f(b)         # 3
print(b)     # 2
b = f(b)     # 3
print(b)     # 3

return을 받으려면 변수에 입력해야함

 

4. Alias 별명

- 두 변수가 하나의 객체를 동시에 참조하여 공유하는 것

A = [[2, 3, 4], 5]
B = A
B[0][1] = 'f'
print(A, id(A))   # [[2, 'f', 4], 5] 1860139826944
print(B, id(B))   # [[2, 'f', 4], 5] 1860139826944

 

5. Shallow copy 얕은 복사

- 변수는 복사하여 새로 생성하지만 참조하는 리터럴은 공유하는 복사 방법

- copy 모듈의 copy() 함수로 실행

- 첫번째 level 객체만 복사

 

import copy

A = [[2, 3, 4], 5]
B = copy.copy(A)    # B = list(A)
B[0][1] = 'f'
B[1] = 7
print(A, id(A), id(A[0]), id(A[0][1]))  # [[2, 'f', 4], 5] 1860140611008 1860140611584 1860137884464
print(B, id(B), id(B[0]), id(B[0][1]))  # [[2, 'f', 4], 7] 1860140611904 1860140611584 1860137884464

- list A를 변수 B에 얕은 복사

- list B의 원소들은 새롭게 생성되지만, 원소들이 참조하는 객체는 원본과 동일하며 새로 생성되지 않음

- list A 와 B의 주소는 다르지만 리스트 원소가 참조하는 객체는 동일

 

6. Deep copy 깊은 복사

- 변수와 대상 객체(리터럴)를 모두 복제하여 생성

- 완전히 독립됨

 

import copy
A = [[2, 3, 4], 5]
B = copy.deepcopy(A)
B[0][1] = 'f'
B[1] = 7
print(A, id(A), id(A[0]), id(A[0][1]), id(A[1])
# [[2, 3, 4], 5] 1482518103488 1482518184832 1482509412720 1482509412784

print(B, id(B), id(B[0]), id(B[0][1]), id(B[1])
# [[2, 3, 4], 5] 14825181072000 1482518204544 1482509753136 1482509412848

- 변수 A와 B, 리스트 원소, 원소가 참조하는 객체의 주소가 모두 다름

- 리스트 원소가 참조하는 객체도 복제되기 때문에 B의 원소 값을 수정해도 리스트 A가 참조하는 객체에는 변화가 없음

 

7. List

- 원소의 자료형 같을 필요 없음

- 파이썬은 정적 배열 지원하지 않음

- 사이즈는 고정되어 있지 않음 dynamic

- referential array 리스트 원소는 값에 대한 참조 변수

A = [2, 3, 4]
A.append(7)
A[1] = 9

 

 

1) 리스트 생성

    - 리스트 복합 표현

    - range(), list() 함수 사용

    - 빈 리스트 선언 후 원소 추가

# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

num1 = [i for i in range(10)]
num2 = list(range(10))
num3 = []
for i in range(10):
    num3 = num3 + [i]  # num3.append(i)

 

2) 주사위 던지기 예제

import random

def throw_dice(count, n):
    for i in range(n):
        eye = random.randint(1, 6)
        count[eye-1] += 1
    
def calc_ratio(count):
    ratio = []
    total = sum(count)
    for i in range(6):
        ratio.append(count[i]/total)
    return ratio

def print_percent(num):
    print('[', end = '')
    for i in num:
        print('%4.2f %i, end = ' ')
    print(']')
dice = [0]*6
for n in [10, 100, 1000]:
    print('Times = ', n)
    throw_dice(dice, n)
    print(dice)
    ratio = calc_ratio(dice)
    print_percent(ratio)
    print()
Times = 10
[2, 1, 2, 1, 2, 2]
[0.20, 0.10, 0.20, 0.10, 0.20, 0.20]

Times = 100
[17, 14, 24, 28, 16, 21]
[0.15, 0.13, 0.22, 0.16, 0.15, 0.19]

Times = 1000
[197, 185, 176, 162, 188, 202]
[0.18, 0.17, 0.16, 0.15, 0.17, 0.18]

 

3) 2차원 배열 생성

scores = [[75, 90, 85], [60, 100, 75], [90, 70, 80]]
print('scores', scores)
for score in scores:
    for num in score:
        print(num, end = ' ')
    print()
print()

print('scores[0][1]', scores[0][1])
print('scores[2]', scores[2])
print('scores[2][2]', scores[2][2])
scores [[75, 90, 85], [60, 100, 75], [90, 70, 80]]
75 80 85
60 100 75
90 70 80

scores[0][1] 90
scores[2] [90, 70, 80]
scores[2][2] 80

 

4) 볼링 점수 계산 예제

score1 = [(8,0), ((4,3), (8,2), (4,6), (2,6), \
         (10,0), (9,0), (10,0), (8,2), (10,0), (10,10)]
score2 = [(10,0), (10,0), (10,0), (10,0), (10,0), \
          (10,0), (10,0), (10,0), (10,0), (10,0), (10, 10)]

score_list = [score1, score2]      # 첫번째, 두번째 게임
for score in score_list:
    i = total = 0
    frame = []                     # (프레임 점수, 결과)
    for first, second in score:    # 1회, 2회 쓰러뜨린 핀의 수
        f_total = first + second
        next_first, next_second = score[i+1]
        if first == 10:
            result = 'STRIKE'
            f_total += next_first + next_second
            # 1~9 프레임에서 더블을 친 경우
            if i != 9 and next_first == 10:
                next_next_first, next_next_second = score[i+2]
                f_total += next_next_first
        elif (first + second) == 10:
            result == 'SPARE'
            f_total += next_first
        else: result = 'NONE'
            
        total += f_total
        frame.append((f_total, result))
        i += 1
        if i == 10: break
    print(frame)
    print('Total = ', total)
    print()
[(8, 'NONE'), (7, 'NONE), (14, 'SPARE'), (12, 'SPARE'), (8, 'NONE'), (19, 'SPARE'), (9, 'NONE'), (20, 'STRIKE'), (20, 'SPARE'), (30, 'STRIKE')]
Total = 147

[(30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE')]
Total = 300

 

8. Set and Dictionary

1) Set

- 수학의 집합과 유사한 자료구조로 집합 연산자 지원

- 원소의 나열 순서가 없으며 중복 허용하지 않음

- s1 = set([1, 2, 3])

- s2 = {2, 3, 4}

- 연산자

    - membership( in ), 합집합 union( | ), 차집합 difference( - )

    - add()

    - update( {  } )

    - remove()

 

2) Dictionary

- key & value의 쌍으로 구성된 자료형

- 키를 통해 원소에 접근

- items() : 각 항목 튜플로 반환

- keys() : 키만을 추출하여 리스트로 반환

- values() : 값만을 추출하여 리스트로 반환

 

- 단어 출현 빈도 예제

sentence = sentence.lower()    # 소문자로 변환
words = sentence.split()       # 단어 단위로 분리
dic = {}
for word in words:
    if word not in dic:
        dic[word] = 0
    dic [word] += 1
print('# of different words =', len(dic))
n = 0
for word, count in dic.items():
    print(word, '(%d)' %count, end = ' ')
    n += 1
    if n % 3 == 0: print()
# sentence = 'Van Rossum was born and raised in the Netherlands, where he received a master's degree in mathematics and computer science from the University of Amsterdam in 1982. In December 1989, Van Rossum had been looking for a hobby programming project that would keep him occupied during the week around Christmas as his office was closed when he decided to write an interpreter for a new scripting language he had been thinking about lately, a descendant of ABC that would appeal to Unix / C hackers. '

# of different words = 66
van (2) rossum (2) was (2) born (1) and (2) raised (1) ...

 

9. Polynomial ADT 다항식 객체 (추상자료형)

- polynomial A(x) = 3x^20 + 2x^5 + 4

- x: variable, a: 계수 coefficient, e: 지수 exponent

- 튜플로 저장해야할 것: coefficient, exponent

 

# 다항식 덧셈

def padd(a, b, d):
    while a and b:
        coef1, exp1 = a[0]
        coef2, exp2 = b[0]
        if exp1 > exp2:
            d.append(a.pop(0))
        elif exp1 < exp2:
            d.append(b.pop(0))
        else:
            if coef1 + coef2 == 0:
                a.pop(0)
                b.pop(0)
            else:
                d.append((coef1 + coef2, exp1))
                a.pop(0)
                b.pop(0)
    for coef, exp in a:
        d.append((coef, exp))
    for coef, exp in b:
        d.append((coef, exp))
a = [(5, 12), (-6, 8), (13, 3)]
b = [(10, 15), (4, 8), (9, 0)]
d = []

padd(a, b, d)
print(d)

# [(10, 15), (5, 12), (-2, 8), (13, 3), (9, 0)]

 

10. Sparse Matrix 희소 행렬

- 2D array: matrix[m][n] → 공간복잡도 S(m, n) = m*n

- Sparse matrix A[m, n] : 유효한 값은 거의 없고 나머지는 0인 행렬

- 2D array에 저장하기에 메모리 공간이 아까운 경우 → 0이 아닌 값 저장 (행, 열, 값)

 

- a[0].row: 행렬의 행 수

- a[0].col: 행렬의 열 수

- a[0].value: 0이 아닌 값의 개수

- a[1]부터 0이 아닌 값의 행, 열, 값 저장 (left-right, top-bottom)

 

class SparseMatrix:
    def __init__(self):
        self.matrix = [[15, 0, 0, 22, 0, 15], \
                       [0, 11, 3, 0, 0, 0], \
                       [0, 0, 0, -6, 0, 0], \
                       [0, 0, 0, 0, 0, 0], \
                       [91, 0, 0, 0, 0, 0], \
                       [0, 0, 28, 0, 0, 0]]
        self.sparse_list = []

def toTuple(self):
    row = count = 0
    for rows in self.matrix:
        col = 0
        for value in rows:
            if value != 0:
                count += 1
                self.sparse_list.append((row, col, value))
            count += 1
        row += 1
    height = len(self.matrix)
    width = len(self.matrix[0])
    self.sparse_list.insert(0, (height, width, count))
s = SparseMatrix()
s.toTuple()
print(s.sparse_list)

# [(6, 6, 8), (0, 0, 15), (0, 3, 22), (0, 5, 15), 
# (1, 1, 11), (1, 2, 3), (2, 3, -6), (4, 0, 91), (5, 2, 28)]

 

'Software > Data Structures' 카테고리의 다른 글

[Python] 2장 연습문제  (0) 2022.04.16
[Python] 1. Introduction  (0) 2022.03.08
[자료구조] 탐색  (0) 2021.04.20
[자료구조] 연결 리스트  (0) 2021.04.20
[자료구조] 선형 자료구조  (0) 2021.04.18

[수업출처] 숙명여자대학교 소프트웨어학부 김주균 교수님 '운영체제' 수업 & [OS? Oh Yes!]

 

1. 프로세스

- 시분할 시스템에서 메모리의 한 부분을 차지하는 작업, 동시에 CPU라는 자원을 분배해 주어야 하는 대상이 되는 작업들

- CPU를 할당받는 단위이자 주어진 자원들의 소유자로서의 역할

- 수행 중인 프로그램 = 프로그램데이터를 기본으로 정상적인 실행을 위해 필요한 환경을 시스템으로부터 부여받은 능동적인 존재

 

2. 프로세스 제어 플록(PCB)

- 프로세스에 대한 모든 것을 표현하는 테이블 형태의 자료구조

- 프로세스 하나가 만들어진다는 것은 PCB 하나가 만들어진다는 말과 같음

- 운영체제가 프로세스를 관리한다는 것은 해당 PCB에 대한 행동(생성, 수정, 관련 리스트 연결, 삭제 등)

- 기본적으로 메모리에 저장

 

- 프로세스 번호, 프로세스 상태(준비, 실행, 대기, 보류 등), 프로세스 우선순위, 프로그램 카운터 값(PC), 메모리 포인터, 문맥 데이터, 할당받은 자원들에 대한 목록, 계정 정보, 입출력 정보 등

 

3. 프로세스 상태 변화

점선 부분의 구현을 빼는 시스템도 있음

 

 

1) 생성

- 사용자가 요청한 작업이 커널에 등록되고 PCB가 만들어져 프로세스가 만들어진 다음, 준비나 보류 준비 상태로 되기 위해 잠시 거치는 상태

- 메모리 공간을 검사하여 충분한 공간이 있으면 메모리를 할당하며 준비 상태로 바꿔주고, 그렇지 못할 경우 보류 준비 상태로

 

2) 준비

- CPU를 할당받기 위해 기다리고 있는 상태

- CPU만 주어지면 바로 실행할 준비가 되어있는 상태

- 큐 또는 리스트가 사용됨

 

3) 실행

- CPU를 할당(Dispatch)받아 실행 중인 상태

- 단일 CPU 시스템에서는 한 개의 프로세스만 실행 상태에 있음

- CPU 스케줄링 정책에 의해 CPU를 뺏길 수 있으며 이 경우 준비 상태로 바뀜

- 시간 할당량이 소진되어 CPU를 뺏기는 경우를 시간 종료라고 함 → 인터럽트가 동원되어 처리

- 입출력이 필요하여 시스템 호출을 하면 대기 상태로 바뀌게 되고, 준비 상태의 프로세스 중 하나가 다음으로 실행됨

 

4) 대기

- 프로세스가 실행되다가 입출력 처리를 요청하거나, 바로 확보될 수 없는 자원을 요청할 때

- CPU를 양도하고 요청한 일이 완료되기를 기다리며 대기하는 상태

- 큐 또는 리스트가 사용됨

- 요청한 일이 완료되면 준비 상태로 바뀌면서 CPU를 기다림

 

5) 종료

- 프로세스가 종료될 때 아주 잠시 거치는 상태

- 할당되었던 모든 자원들이 회수되고 PCB만 커널에 남아있는 상태

- 운영체제가 시스템에 남아있는 프로세스의 흔적들을 최종 정리 후 PCB를 삭제하면 프로세스가 완전히 사라짐

 

- 준비, 실행, 대기 상태 → 활성 상태: 메모리 공간의 일정량 부여받음

- 활성 상태에 있는 프로세스 개수: Multi-programming degree

- 메모리가 부족하거나 다른 이유에 의해 메모리를 회수당한 경우 → 보류 상태

- 보류 상태) PCB는 메인 메모리에 저장, Multi-programming degree - 1

 

6) 보류

- 프로세스가 메모리 공간을 뺏기고 디스크로 나가는 경우

- 이 경우 스왑되어 나간다고 하고(Swapped Out), 다시 메모리로 들어오면 스왑되어 들어온다 함(Swapped In) → Swapping

- 보류 준비 상태

    - 생성된 프로세스가 바로 메모리를 받지 못할 때나,

    - 준비 또는 실행 상태에서 메모리를 잃게 될 때를 위해 필요

    - 실행 상태의 프로세스가 CPU를 반납하면서 준비 상태로 바뀔 때 메모리까지 잃어야 하는 경우(Suspended)

    → 충분한 메모리 공간의 확보를 위해 준비 상태의 프로세스를 보류시킬 수밖에 없는 경우   

    → 높은 우선순위의 보류 대기 상태 프로세스가 준비 상태가 되면서 실행 상태의 프로세스로부터 CPU를 뺏는 경우

 

    - 메모리의 여유가 생기거나 준비 상태의 프로세스가 전혀 없을 때 대기 상태의 프로세스를 보류 대기로 만들고, 메모리 공간이 확보되면 준비상태로 바뀌게 됨(Resume) → Swapping

 

- 보류 대기 상태

    - 대기 상태일 때 메모리 공간을 잃은 상태

    - 준비 상태의 프로세스가 아예 없어 대기를 보류 대기로 만드는 경우

    - 준비 상태의 프로세스가 있었다고 해도 메모리의 여유 공간을 더 확보하기 위해 

    - 특별한 경우가 아니면 입출력이나 기다리던 사건의 종료 시 보류 준비 상태가 됨

    - 메모리의 여유가 생겼을 때 대기시켰던 원인이 곧 해소될 것으로 판단되는 프로세스가 보류 대기 상태에 있는데, 보류 상태 중인 어떤 프로세스보다 우선순위가 높은 경우에는 그 프로세스에게 메모리를 주고 대기 상태로 만드는 것이 더 효과적일 것

 

- 보류 상태의 필요 이유

    - 일차적으로 메모리 공간의 확보를 위해

    - 실행되는 프로세스의 현재 결과가 바라던 것이 아닌 오류가 보일 때

    - 시스템에 위해를 가할 수 있는 수상한 행동을 보일 때

    - 주기적인 일이어서 다음 주기의 실행 때까지 메모리를 회수해도 문제되지 않을 때 등

 

4. 문맥교환

- 프로세스의 상태 변화는 인터럽트에 의해 처리됨

- 인터럽트 이전에 실행되던 프로세스가 인터럽트 처리 후에 계속 실행될 때도 있고, 다른 프로세스로 CPU가 할당될 때도 있음

- 인터럽트 처리 전후의 프로세스가 같은 경우 문맥교환을 위해 필요한 양이 적음 (PCB의 일부분만 보관)

- 다른 경우 문맥의 저장, PCB에서 관련 데이터들의 변경과 함께 PCB를 적절한 상태의 큐로 옮기기, 스케줄링, 그 프로세스의 PCB 변경과  문맥의 복원 등이 필요함

 

- 모드 스위칭: 인터럽트 처리 전후의 프로세스가 같은 경우 (사용자 모드 - 커널 모드의 변경만 생김)

- 프로세스 스위칭(문맥교환): 인터럽트 처리 전후 프로세스가 다른 경우

 

5. 스레드 Thread

- 하는 일은 서로 다르지만 관련 있는 작은 일들이 모여 프로세스를 구성한 경우, 세분된 작은 일들을 스레드라 함

- 프로세스는 부여된 자원의 소유자로서, 스레드는 스케줄링의 단위(CPU를 할당받는 단위)로서 존재

- 프로세스가 가지는 자원을 공유하면서, 각자는 자신의 실행환경(프로그램 카운터로 표현되는 현재 실행 위치, 스택, 레지스터 값)을 따로 가짐

- 다중 스레딩: 하나의 프로세스를 다수의 스레드로 만들어 실행하는 것

- 다수의 실행 단위들이 존재하여 작업의 수행에 필요한 자원들을 공유하기 때문에 자원의 생성과 관리가 중복되는 것을 줄일 수 있음

 

- 다중 스레딩에서 프로세스란 보호와 자원의 할당 단위

- 프로세스의 코드와 데이터를 수용하기 위한 가상주소 공간과 CPU, 다른 프로세스의 파일들, 입출력에 사용되는 자원에 대한 보호된 액세스를 보장하기 위한 단위

 

- 스레드 각각은 스레드의 수행 상태, 예를 들어 실행, 준비 등과 실행 상태가 아닐 경우를 위한 스레드 문맥, 각자의 실행 스택, 자신이 속한 프로세스가 가지는 메모리와 자원에 대한 접근 권한을 가짐

- 한 스레드에 의해 메모리의 데이터가 변경될 경우 다른 스레드들은 변경된 데이터를 사용하게 됨

- 열린 파일은 다른 스레드들에게도 열린 상태로 사용됨

 

- 단일 스레드 프로세스: PCB, 사용자 주소 공간, 사용자 스택과 커널 스택

- 다중 스레드 프로세스

    - 프로세스) PCB, 사용자 주소 공간 : 스레드들과 공유

    - 스레드) 스레드 제어 블록, 사용자 스택과 커널 스택

 

- 스레드의 생성, 삭제, 스위칭에 소요되는 시간과 비용이 프로세스 단위로 이루어질 때보다 빠르고 저렴

- 프로세스 간의 통신은 커널의 개입을 필요로 하지만, 한 프로세스 내 스레드 간 통신은 커널의 개입이 필요없음

- CPU 스위칭을 위한 스레드 단위의 자료는 유지되어야 하며, 프로세스 단위로 행해지는 보류, 종료 등은 전체 스레드에 동일한 영향 미침

 

6. 스레드 상태와 동기화 Synchronization

- 스레드 역시 실행, 준비, 대기의 상태를 가짐 (메모리 자원은 프로세스 단위로 할당되기 때문에 보류 상태는 없음)

- 대기는 레지스터 값, 프로그램 카운터(PC), 스택 포인터 등의 보관이 요구되며, 스레드의 종료는 해당 스레드의 레지스터 값들과 스택을 없앰

- 주소 공간과 자원 공유 → 특정 스레드가 변경시킨 내용이 다른 스레드에 바로 영향 미침

- 상호 간의 간섭이나 데이터 파괴 등을 방지하기 위한 스레드 실행의 동기화가 요구됨

→ 프로세스 간의 동기화에서 발생하는 문제와 해결책과 동일

 

7. 스레드의 종류

1) 사용자 레벨 스레드 

- 스레드 라이브러리에 의해 관리됨

- 스레드 라이브러리의 메모리에서의 위치는 사용자 공간

- 스레드와 관련된 모든 행위는 사용자 공간에서 이루어지므로 커널은 스레드의 존재를 알지 못함

- 커널은 스레드들의 행위를 프로세스의 행위로 인식함

- 스레드 라이브러리는 스레드의 생성, 소멸을 위한 코드와, 스레드 간의 메시지나 데이터의 전달, 스레드의 스케줄링, 스레드 문맥의 보관, 재 저장 등을 담당

- 스레드를 지원하지 않는 운영체제에서도 사용 가능

 

- 특정 스레드의 실행에서 대기는 소속된 프로세스의 대기 초래

- 당시 실행중이던 스레드는 지금 실제로 실행 중이 아니지만 스레드 라이브러리에 의해 실행으로 계속 간주되고 있다가 나중에 CPU가 다시 이 프로세스에 할당되었을 때 계속 실행해 나갈 수 있도록 해줌

 

- 스레드의 실행 중 프로세스의 시간 초과가 될 경우 커널은 프로세스의 스위칭 수행

- 당시 실행중이던 스레드 역시 실행 상태로 유지되다가 프로세스가 CPU 받으면 다시 실행됨

- 스레드의 스위칭 도중 프로세스 스위칭이 일어나도 CPU를 다시 받았을 때 스레드의 스위칭이 계속 진행되도록 함

 

- 스레드 스위칭에 커널의 개입 필요 없음 (모드 스위칭 필요 없음)

- 스레드 간의 스위칭 시 운영체제가 정한 스케줄링(프로세스 스케줄링)에 따를 필요 없고, 응용 별로 독자적인 스케줄링 사용할 수 있음

- 스위칭은 스레드 라이브러리에 있는 스위칭 프로그램에 의해 결정됨

 

- 특정 스레드의 대기가 프로세스 내의 모든 스레드들의 대기를 초래하며, 다중처리 환경이 주어진다해도 스레드 단위의 다중처리가 되지 못한다는 단점 (CPU는 프로세스 단위로 할당되기 때문)

 

2) 커널 레벨 스레드

- 모든 스레드의 관리를 커널이 하는 경우

- 스케줄링은 커널에 의해 스레드 단위로 이루어지므로 사용자 레벨 스레드의 단점을 극복할 수 있음

- 다중처리의 환경일 경우 한 프로세스 내의 다수 스레드는 각각 CPU를 할당받아 병렬 실행 가능

- 한 스레드의 대기 시 같은 프로세스에 속한 다른 스레드로 스위칭 가능

- 같은 프로세스에 속한 스레드 간의 스위칭에도 커널의 개입 필요 → 모드 스위칭 요구됨

 

- 커널 레벨 스레드라 해도 다중처리가 아닌 환경이라면 어차피 하나밖에 없는 CPU를 가동하기 때문에 시간적인 차이가 없을 것이라고 생각할 수 있음

- 단일 처리기 환경에서 다른 서버에 있는 프로시저 호출하고 그 다음 또 다른 서버에 있는 프로시저 호출하는, 즉 두 번의 순차적인 원격 프로시저 호출(RPC)을 수행하는 일을 할 때

- 스레드 없이 프로세스로 한 경우는 RPC 이후 서버로부터 결과를 받을 때까지 기다린 후 다음 RPC 호출을 실행함

- 스레드가 있는 경우 첫번째 호출을 한 스레드에게 맡기고 대기가 될 때 바로 다른 스레드를 실행시켜 두번째 호출을 실행함

- 두 개의 스레드가 대기 중인 시간대가 중복된 만큼 전체 일의 종료 시간이 앞당겨짐

 

 

 

 

'Software > OS' 카테고리의 다른 글

[OS] 4장. CPU 스케줄링  (0) 2022.04.18
[OS] 2장. OS 상식과 인터럽트  (0) 2022.04.10
[OS] 1장. OS의 정의와 역사, 기능  (0) 2022.03.05

[수업출처] 숙명여자대학교 소프트웨어학부 김주균 교수님 '운영체제' 수업 & [OS? Oh Yes!]

 

1. OS의 목적

- 사용자와 컴퓨터 사이의 가교 역할 → 사용자가 컴퓨터를 보다 편리하게 사용할 수 있도록 함

- 컴퓨터 시스템의 자원들을 효율적으로 사용될 수 있게 해야 함

 

- 사용자의 입장에서는 사용하기 쉽고 편리하며, 배우기 쉽고 신뢰할 수 있으며 빨라야 함

- 만드는 사람의 입장에서는 설계, 유지, 보수가 쉽고 적응성이 좋으며 오류없이 효율적이어야 함

- 경우에 따라 모두 가질 수 없는 경우가 많기 때문에 사용되는 환경에 맞춰 순위에 따라 합의해야 함

 

2. 부팅

- 전원이 꺼져있는 시스템에서 운영체제 전부는 디스크에 저장되어 있음

- 전원이 켜지면 운영체제의 일부인 '커널'이 메모리에 올라와 실행됨

→ 장치 준비, 각종 레지스터 값 초기화, 사용자의 입력 받을 준비 완료 → '부팅되었다'

- 이때 동원되는 것이 부트 프로그램(부츠트랩 로더), 대개 ROM에 저장되어 있음 → 전원이 켜지면 무조건 제일 먼저 실행됨

→ 커널을 찾아 메모리에 올린 후 실행시키는 역할

 

3. 레지스터

- CPU에 내장되어 있는 메모리보다 빠른 기억장치

- 시스템과 사용 목적에 따라 8비트, 16비트, 32비트 등의 크기 가짐

- 일반적으로 데이터, 주소, 조건 코드 레지스터 등이 있음

    - 데이터 레지스터: 연산 (메모리보다 빠름)

    - 주소 레지스터: 데이터나 명령어의 메모리 주소 저장하거나 계산

        - 인덱스 레지스터: 주소 지정

        - 세그먼트 포인터, 스택 포인터: 해당 포인터 값 저장

- CPU 연산 제어하기 위한 레지스터

    - MBR, MAR, IR, PC 등

- 모든 CPU는 현재 상태 정보를 저장하기 위해 프로그램 상태 워드(PSW)라는 레지스터 가짐

    - 여러가지 조건(condition)코드와 함께 인터럽트 가능, 불가능을 표시하는 비트, 현재 실행 모드를 나타내는 비트 등 포함

 

4. 명령어 처리

- 명령어 반입: 레지스터를 이용하여 메모리에 있는 명령어를 읽어 처리기에 있는 레지스터로 갖고 옴

- 연산 종류 파악, 실행 → 하나의 명령어 처리

- 반입에서 다음에 실행해야 할 메모리에 있는 명령어의 주소는 PC 레지스터가 갖고 있음

 

5. 인터럽트

1) 폴링(Polling)

- 컴퓨터 시스템의 각 자원들의 현 상황을 파악할 수 있는 방법 중 하나

- CPU가 일정한 시간 간격을 두고 각 자원들의 상태를 주기적으로 확인하는 방식

- 자원들은 폴링 신호를 받은 후 자신의 상태나 원하는 바를 CPU에게 알려줌

- 폴링의 간격을 정해야 하며, 각 자원들은 직전 폴링 이후 변화된 상태를 다음번 폴링 때까지는 알릴 수 없다는 단점

- 아무 일이 없을 때에도 CPU는 폴링에 일정량의 시간을 들여야 한다는 부담

 

2) 인터럽트

- 각 자원들이 능동적으로 자신의 상태변화를 CPU에게 알리는 방식

- CPU는 따로 시간을 들이지 않아도 되고, 자원들은 상황을 즉시 알려 처리받을 수 있음

- 오늘날 거의 대부분의 시스템에서 채택하고 있음

- 하드웨어 인터럽트: 장치 또는 주변장치들로부터의 인터럽트

- 소프트웨어 인터럽트: CPU 스스로 자신에게 인터럽트(=trap) (명령어 때문), 입출력할 때 시스템 콜

 

3) 인터럽트 처리 과정

- 장치가 CPU에 인터럽트 신호 전송 → 명령어 실행중이라면 명령어 실행을 우선 완료시키고 인터럽트 신호 확인 → 인터럽트 처리 루틴 실행 전, 실행중이던 프로그램의 현 상태 정보(PSW, PC 레지스터 값 등)를 시스템 스택에 저장 → 인터럽트 처리 루틴의 시작 주소를 PC에 넣어 실행 → 인터럽트 처리 루틴 실행

 

- 인터럽트 처리 루틴: CPU에 있는 레지스터들의 값 저장 → 필요한 인터럽트 처리

 

- 인터럽트 처리가 끝나면 이전에 저장했던 레지스터 값들 다시 재저장, PSW와 PC 값 원래 자리에 넣어주고 실행 → PC에 들어가있는 값이 인터럽트 이전에 실행 중이던 프로그램에서 다음에 실행할 명령어 위치 → 프로그램 실행 이어나감

 

4) 중첩된 인터럽트의 처리

- 순차적 처리: 인터럽트를 처리하는 동안 발생하는 인터럽트는 현재 처리가 끝난 뒤 차례대로 하나씩 처리해줌

- 중첩 처리: 현재 처리 중인 인터럽트를 잠시 접어두고 또 다른 인터럽트로 실행을 옮길 수 있음

- 인터럽트의 중요도에 따라 우선순위가 더 높은 경우에는 중첩을, 그렇지 않은 경우는 순차적으로 구현하는 방법

 

6. 기억 장치의 계층적 구조

[자기테이프 - 광디스크 - 자기디스크 - 전자디스크 - 주기억장치 - 캐시 - 레지스터]

 

- 보통 속도와 가격은 비례하기 때문에 용도에 맞게 적절히 저장장치를 계층적으로 구성하는 타협 필요

- 상위계층에 있을수록 속도와 가격이 올라감

- CPU에 의해 처리되어질 명령어나 데이터가 상위에 있을수록 시스템의 성능은 좋아짐

- 프로그램 또는 데이터는 평소에는 하위계층에 저장되다가 실행시에 적당량이 상위계층과 하위계층으로 번갈아 교체되어지면서, CPU는 최대한 상위계층으로 접근하도록 만들어 처리 속도를 높임

 

- 프로그램이 실행되기 위해서는 반드시 주기억장치(메모리)에 있어야 함

- 메모리에 있는 프로그램의 일부분이 다시 캐시로, 그 중 실행되어질 명령어는 처리기 레지스터에 적재되어 실행됨

- 메모리 관리를 어떻게 하느냐에 따라 시스템의 성능 좌우 → 운영체제의 역할 중요

 

7. I/O 방식 (입출력 방식)

- 하나의 입출력 장치에는 컨트롤러가 있고, 여기에는 CPU와 입출력 데이터를 저장하는 버퍼 존재

 

[CPU의 개입 정도에 따라]

1) 프로그램에 의한 입출력

- CPU는 입력을 지시한 후 워드가 컨트롤러의 버퍼에 입력되었는지 계속 확인

- 인터럽트가 필요없는 대신 CPU가 지속적으로 완료 여부 확인해야 함 

→ 전체 입출력 완료될 때까지 CPU 낭비됨

 

2) 인터럽트에 의한 입출력 

- 입력을 지시한 후 입력이 이루어지는 사이에 CPU는 다른 작업에 활용됨

- 입력 완료 시 인터럽트를 통해 CPU에 알림

- 프로그램에 의한 입출력 때의 CPU 낭비 없앨 수 있음

- 버퍼의 크기에 비해 입출력할 데이터가 클수록 잦은 인터럽트 처리가 요구됨

 

3) 메모리에 직접 접근하는 입출력(DMA)

- 인터럽트에 의한 입출력에서 인터럽트가 호출되는 횟수를 줄이고자 한 방식

- 입출력 작업을 CPU 대신 해줄 수 있는 '채널'이라는 위성 프로세서 필요

- CPU는 입출력할 데이터의 시작주소와 크기 등을 채널에게 알려주고 다른 작업에 동원됨

- 이때부터 입출력은 채널의 주도하에 이루어짐

- 일반적으로 한 번의 입출력 단위를 블록이라고 부르며, 채널은 블록 단위로 CPU에게 인터럽트를 보내 알림

 

- CPU와 채널이 동시에 메모리에 접근할 때, 메모리는 한 번에 하나의 접근만 허용하기 때문에 둘 중 하나를 결정해야 함

- Cycle Stealing: 일반적으로 속도가 빠른 CPU가 평소 메모리 접근 기회를 더 많이 가지기 때문에, 이때는 채널에게 기회를 주는 것이 공평하다고 보고 설계함

 

[하드웨어의 구성에 따라]

1) 독립적인 입출력

- 입출력 장치들이 입출력 버스(I/O Bus)를 통해 CPU와 연결되어 있는 경우

- 메모리는 따로 메모리 버스를 통해 연결되어 있음

- 입출력은 입출력을 담당하는 명령어를 통해 실행되는데, 입출력 버스를 통해 해당 장치의 지정, 데이터, 입출력을 구분해주는 제어값이 전달됨

- 입출력 명령어가 명령어 집합에 추가되므로 제어 로직이 복잡해지고, 입출력 버스를 장착하는데 추가 비용이 드는 단점

 

2) 메모리 주소지정 입출력

- 입출력 장치들이 메모리와 함께 메모리 버스에 연결되어 있음

- 입출력을 위한 명령어를 따로 두지 않고, 메모리에 대한 명령어(MOVE, LOAD 등)를 사용하여 실제 입출력 실행

- 입출력 장치들은 각각 메모리의 한 번지를 할당받아, 메모리에 대한 명령어로 그 번지에 해당하는 장치로의 입출력이 되도록 하는 것

- ex) 입출력 장치 2개, 주소의 크기가 3비트(0~7번지)라면 메모리는 0번지부터 5번지를 가는 크기이고, 6, 7번지는 입출력 장치를 나타내도록 하는 것인데 주소 공간만큼의 메모리를 활용할 수 없다는 단점이 있음

'Software > OS' 카테고리의 다른 글

[OS] 4장. CPU 스케줄링  (0) 2022.04.18
[OS] 3장. 프로세스와 스레드  (0) 2022.04.11
[OS] 1장. OS의 정의와 역사, 기능  (0) 2022.03.05

[수업출처] 숙명여자대학교 소프트웨어학부 유석종 교수님 수업 '자료구조'

 

1. Data Structures

- 문제 해결을 위한 대량의 데이터를 효율적으로 처리하고 조직하는 방법 또는 구조

 

- Linear DS: list, stack, queue, deque

- Non-Linear DS: tree, graph

- Advanced DS: BST, Weight networks

- Searching and Sorting algorithms

 

2. Algorithm

- 특정 작업을 수행하기 위한 명령어들의 유한한 집합

- 조건

    - Input: 명시적 입력이 필요하지 않다.

    - Output: 적어도 하나의 출력값이 있어야 한다.

    - Definiteness: 구체적이고 모호하지 않은 명령어들의 집합이어야 한다.

    - Finiteness: 유한한 단계를 거친 후 끝나야 한다.

    - Effectiveness: 쓸모 있어야하고, 효율적이어야 한다.

- 표현 방법

    - Pseudo code, Flow chart

    - 자연어, 프로그래밍 언어

 

3. System Life Cycle

- Requirement 요구사항 명세

    - 프로젝트의 목적을 정의하는 일련의 설계 명세서

    - 사용자, 플랫폼, 함수, 인터페이스 등

- Analysis 분석

    - 큰 프로젝트를 작은 모듈들로 나누는 과정

    - Divide and conquer 전략

    - Top-down approach

        - 주 목적에서 구성요소로 가는 계층적 접근

        - program -> subroutines -> instructions

    - Bottom-up approach

        - 구성요소가 모여 전체 시스템이 되는 방법

- Design 설계

    - 각 모듈에 대한 객체와 함수 정의

- Implementation 구현

    - 객체 및 알고리즘 코드 구현

- Verification 검증

    - 알고리즘의 정확성 증명

    - program test: black-box test, white-box test

 

4. Fibonacci Numbers

# fb는 리스트

def fibo(fb):
    a = 0
    b = 1
    fb.append(a)
    fb.append(b)
    while True:
    	a, b = b, a+b
        if b < n: break
        fb.append(b)

피보나치 수열을 구하는 함수이다.

리스트에 우선 0과 1을 넣고, b가 n이 되기 전까지 a = b, b = a+b로 대입하여 b, 즉 a+b를 리스트에 추가한다.

 

n = 100000
fb = []
fibo(fb)
print(fb)
print("# of fibos", len(fb))

 

5. Prime Numbers

- 소수: 1보다 큰 자연수 중 1과 자기자신 이외의 수로 나누어 떨어지지 않는 수

 

def find_prime(num):
    for i in range(2, num+1):
        prime = 1
        for j in range(2, i):
            if i % j == 0:
                prime = 0
                break
        if prime: prime_list.append(i)

2부터 num까지의 수를 각각 i로 둘 때, i를 2부터 i까지의 수로 나누어 본다. 

이 때, 나누어 떨어지면 소수가 아니기 때문에 prime = 0으로 둔다. 

i까지 전부 나눈 후  prime이 여전히 1이면 소수이기 때문에 prime_list에 추가한다. 

이 과정을 num까지 반복한다.

 

prime_list = []
max_num = 1000
find_prime(max_num)


for i in range(2, max_num):
    if i in prime_list: print('%3d' %i, end = '')
    else: print('_', end = '')
    if i % 50 == 0: print()
print()
print('# of prime numbers = ', len(prime_list))

 

6. Data Types

- 객체와 해당 객체에 작용하는 명령어들의 집합

 

- 내장 자료형

    - Basic type: char, int, float

    - Collection type: string, list, tuple, set, dictionary

 

- 추상 자료형

    - 객체의 자료형

 

7. Abstract Data Type (ADT) 추상 자료형

- 객체의 속성(attributes, properties, member variables)과 행동(methods, operations, member funtions)을 추상화하는 자료형

- 사용자가 필요에 의해 자료형을 직접 정의하는 것

- 객체지향 프로그래밍에서는 공통적인 행위를 하는 Class를 정의한다.

- ex) bank account, student, fraction

 

8. Fraction 분수

- 분자와 분모로 이루어져 있다.

- 기본적으로 분수는 내장되어있지 않기 때문에 객체로 정의해주어야 한다.

- 약분까지 해야 함 -> gcd(x, y)

 

class Fraction:
    def __init__(self, up, down):
        self.num = up
        self.den = down
    
    def __str__(self):
        return str(self.num) + '/' + str(self.den)
    
    def __add__(self, other):
        new num = self.num * other.den + self.den * other.num
        new_den = self.den * other.den
        common = self.gcd(new_num, new_den)
        return Fraction(new_num//common, new_den//common
        
    def multiply(self, other):
        new num = self.num * other.num
        new_den = self.den * other.den
        common = self.gcd(new_num, new_den)
        return Fraction(new_num//common, new_den//common)
        
    def gcd(self, a, b):
        while a % b != 0:
            a, b = b, a % b
        return b

def __init__(self, up, down)은 Fraction 클래스를 호출했을 때 두번째 매개변수 up을 self.num에, 세번째 매개변수 down을 self.den에 대입하는 메서드이다. 이때 self.num은 분자, self.den은 분모이다.

 

def __str__(self)는 print(Fraction(up, down)을 실행했을 때 호출되는 메서드이다. 분수형태로 출력해준다.

 

def __add__(self, other)는 덧셈 메서드이다. + 로 두 변수를 연결했을 때 자동으로 호출된다.

분자는 self의 분자 x other의 분모 + self의 분모 x other의 분자이고,

분모는 self의 분모 x other의 분모이다.

common은 덧셈 결과의 분자와 분모의 최대공약수로, 이후에 나올 gcd 메서드를 통해 구할 수 있다.

최종적으로 덧셈 결과의 분자와 분모를 최대공약수로 약분해서 결과를 도출한다.

 

def multiply(self, other)는 곱셈 메서드이다.

분자는 self의 분자와 other의 분자를 곱한 값이고,

분모는 self의 분모와 other의 분모를 곱한 값이다.

마찬가지로 gcd 메서드로 최대공약수를 구한 후 곱셈 결과를 약분해서 도출한다.

 

def gcd(self, a, b)는 분자와 분모의 최대공약수를 구하는 메서드이다.

gcd(a, b) = gcd(b, a%b) 공식을 이용하였다.

 

num1 = Fraction(1, 4)
num2 = Fraction(1, 2)
num3 = num1 + num2
print(num1, '+', num2, '=', num3)

num1 = Fraction(3, 4)
num2 = Fraction(2, 9)
num3 = num1.multiply(num2)
print(num1, '*' num2, '=', num3

 

9. Performance Analysis

- 이상적 기준 → 추상적

    - 고객의 요구사항을 만족하는지?

    - 잘 작동하는지?

    - 효율적으로 구현했는지?

- 현실적 기준 → 객관적 수치 도출

    - 공간복잡도: 실행할 때 메모리 공간을 얼마나 사용하는지

    - 시간복잡도: 연산 시간이 얼마나 소요되는지

 

10. 공간복잡도 Space Complexity

- Fixed space requirements(Sc) : 명령어, 단순 변수, 고정크기의 구조체 변수, 상수 등으로 컴파일 전에 알 수 있음

- Variable space requirements(Sv): 배열 함수 전달, 재귀호출 등으로 실행 중에 결정됨. Sv를 구해야 함

- S = Sc + Sv

 

def abc(a, b, c):
    return a + b * c  + (a + b - c) / (a + b) + 4.00

- input: 3개의 단순 변수

- output: 1개의 단순 변수

- 배열 전달, 재귀 X → 가변 요구공간 = 0

- 고정 요구공간은 있지만 관심있는 부분이 아님

 

def iSum(num):
    total = 0
    for item in num:
        total = total + num
    return total

- input: 배열(num)

- output: 단순 변수

- 공간복잡도는 배열 함수 전달 방법에 달려있음 (copy or 주소 전달)

 

- call by value 

    - 배열 요소들은 함수로 '복사'되어짐

    - 배열 크기에 비례하여 추가적인 메모리 공간이 요구됨

    - Sv = n

    - ex) Pascal

 

- call by reference 

    - 배열의 시작 주소만 함수로 전달됨

    - 추가적인 메모리 공간 요구되지 않음 

    - Sv = 0

    - ex) C, Python

 

- 재귀호출

def rsum(sum):
    if len(num):
        return rsum(num[:-1]) + num[-1]
    else:
        return 0
print(rsum([1, 2, 3, 4, 5])

- 함수가 호출될 때마다 현재 실행중인 문맥 모두 저장되어야 함

    - variables, return address, n times funcion calls (rsum(n-1), ..., rsum(0))

    - space complexity = n * (size(num) + return address)

 

11. 시간복잡도 Time complexity

- 알고리즘이 수행되는데 걸리는 시간

- T = compile time(Tc) + excution time(Te)

- 실행시간(Te)가 시간복잡도를 구할 때 사용되며, 실행 환경에 영향을 받음

→ 명령어 개수로 시간 측정, 명령어 별로 실행 시간 다른 것은 무시함

 

- Step count table

    - steps: 한 라인에 명령어가 몇 개인지 (함수 헤더, 변수 선언은 무시함)

    - frequency: 명령어가 몇 번 실행되는지 (for, while loops)

    - total steps = steps * frequency per line

 

12. Big-O Notation

- n이 매우 큰 경우 시간복잡도 함수를 점근적으로 근사한 것

- n이 증가할 경우 알고리즘을 실행하는데 소요되는 시간

- 알고리즘 성능 평가를 위한 표준

 

- T(n) = n² + 2n → O(n²)

 

- f(n) ≤ c * g(n) for all n ≥ n0 를 만족하는 정수 n0와 c가 존재하면 Big-O notation 사용 가능

- c * g(n)은 f(n)의 상한선 → c * g(n)보다는 시간이 적게 걸림

 

- ex) f(n) = 10n + 10,000 ∈ O(n)

    - f(n) ≤ 20n (=c) for all n ≥ 1000 (=n0)

 

13. Big-Omega Notation

- f(n) ≥ c * g(n) for all n ≥ n0 를 만족하는 정수 n0와 c가 존재하면 Big-Omega notation 사용 가능

- c * g(n)은 f(n)의 하한선

 

- ex) f(n) = 3n + 2 ∈ Ω(n)

    - f(n) ≥ 3n for n ≥ 1

 

14. Big-Theta Notation

- f(n) ∈ Ω(n) 이고 f(n) ∈ O(n)을 만족하는 c1, c2, n0가 존재하면 f(n) ∈ θ(g(n()) 존재

- c1 * g(n)  f(n)  c2 * g(n) for all n ≥ n0

 

- ex) f(n) = 3n + 2 ∈ θ(n)

    - 3n ≤ f(n) ≤ 4n for all n ≥ 2

 

15. Time complexity class

'Software > Data Structures' 카테고리의 다른 글

[Python] 2장 연습문제  (0) 2022.04.16
[Python] 2. Python Data Type  (0) 2022.04.16
[자료구조] 탐색  (0) 2021.04.20
[자료구조] 연결 리스트  (0) 2021.04.20
[자료구조] 선형 자료구조  (0) 2021.04.18

+ Recent posts